> By Thomas Aynaud and Jean-Loup Guillaume

When you try to detect communities in a complex network, you often build a hierarchical decomposition of the nodes. This decomposition is a tree (called a dendrogram). The leaves of the tree are the nodes, and each of its levels defines a partition: two nodes of the graph are in the same part if they have the same ancestor at the considered level. For each level, the partition is a decomposition in communities, and each part is a community. The first level of the tree gives the main communities, the second level gives the sub-communities (inside the main communities), the third level gives the sub-sub-communities (inside the sub-communities), etc.

Here, we apply an algorithm to detect communities on a social network, which produces a tree. We plot the distributions of the sizes of the parts for each level (thus the size of main communities, sub-communities, sub-sub-communities, etc.) with a different color. In other words, the x-axis gives the sizes of communities, and the y-axis gives the fraction of communities of a given size (for the considered level).

It appears that the sizes of communities are very heterogeneous: there are huge communities and really small ones. What is more surprising is that, for large and small communities, the different plots are really close: the largest communities remain at almost all levels; the changes are mostly related to intermediate sizes.