Communities and beyond: Mesoscopic analysis of a large social network with complementary methods

Community detection methods have so far been tested mostly on small empirical networks and on synthetic benchmarks. Much less is known about their performance on large real-world networks, which nonetheless are a significant target for application. We analyze the performance of three state-of-the-art community detection methods by using them to identify communities in a large social network constructed from mobile phone call records. We find that all methods detect communities that are meaningful in some respects but fall short in others, and that there often is a hierarchical relationship between communities detected by different methods. Our results suggest that community detection methods could be useful in studying the general mesoscale structure of networks, as opposed to only trying to identify dense structures.

Figure 1

Community size distributions for IM, LV, and CP and their weighted versions. The parameter $\alpha$ denotes the exponent when the tails are fitted a power-law distribution $P(S)\propto S^{\alpha }$; solid lines correspond to the unweighted $\alpha$ and dashed lines to the weighted ${\alpha }_w$.

Figure 2

Typical (left) unweighted and (right) weighted communities of different size. These communities have been manually selected from a large random sample of communities with the intention of portraying archetypal examples. Colored (dark gray) nodes and edges denote nodes inside a single community, and the light gray nodes are the first neighbors of the nodes in the community. In weighted communities the edge width is proportional to the logarithm of edge weight, with the restriction that edges with $w_{\mathit{ij}}⩽300$ (5 min) have the minimum width and those with $w_{\mathit{ij}}⩾14\hspace{0.5em}400$ (4 h) the maximum width.

Figure 3

The distribution of relative density $D_c=L_c/(S-1)$ for communities from each method. In all plots each column represents a distribution and is normalized to one, the colors indicating probability density so that the darker the color, the higher the density (see color bar). The thick solid line denotes the average value. The dashed straight line corresponds to cliques, for which $D_c=S/2$. For IM and LV the smallest density is 1, which corresponds to trees. For CP, the smallest possible density is indicated by the curved dashed line (see text).

Figure 4

The distribution of $\rho (c)$ [Eq. (2)] as function of community size for each method. The distributions are presented as in Fig. 3, with a similar shading scheme. The black line denotes average value.

Figure 5

Average edge weights $w_{\mathit{ij}}/\langle w\rangle$ inside communities as a function of community size $S$, normalized by the network average.

Figure 6

Average neighborhood community overlap $O$ as a function of node degree $k$, between different methods (top) and unweighted and weighted versions of the same method (bottom).

Figure 7

Illustration of tiling imperfection. The eight nodes in $c^{\text{'}}$ are spread over three different communities in another partition. Using $T=\{c_1,c_2\}$ gives the best tiling; including $c_3$ would reduce $F_{\text{int}}$ to 0 but increase $F_{\text{ext}}$ by 2. The value of tiling imperfection is $\mathcal{I}=3/8$.

Figure 8

(Top) Tiling imperfection $\mathcal{I}$ and inclusion imperfection ${\mathcal{I}}^{*}$ between IM and CP. (Bottom) Tiling imperfection $\mathcal{I}$ between IM and LV.

Figure 9

Typical cases of tiling with IM (red or dark gray) and LV (black) communities of size $S=10$. Light gray nodes are the first neighbors of the community to be tiled. (a) Example of perfect tiling $\mathcal{I}=0$ when IM community (red nodes) is tiled with LV communities (black edges). A typical IM community with $S=10$ is located in a treelike region of the network, and LV covers such regions with very small communities. (b) Example of tiling imperfection $\mathcal{I}=1$ when LV community (black edges) is tiled with IM communities (in red). A typical LV community with $S=10$ is in a somewhat denser part of the network, where the IM communities are much larger.

Figure 10

To find the critical threshold $I_c$ for wCP we build up communities by adding cliques in descending order of intensity $I$, and monitor the largest component size $m(I_{>})$ ($\square$) and susceptibility $\chi (I_{>})$ ($ˆ$). The transition occurs when about 24% of cliques have been added ($I_{>}\approx 3093$).