Assessing the consistency of community structure in complex networks

In recent years, community structure has emerged as a key component of complex network analysis. As more data have been collected, researchers have begun investigating changing community structure across multiple networks. Several methods exist to analyze changing communities, but most of these are limited to evolution of a single network over time. In addition, most of the existing methods are more concerned with change at the community level than at the level of the individual node. In this paper, we introduce scaled inclusivity, which is a method to quantify the change in community structure across networks. Scaled inclusivity evaluates the consistency of the classification of every node in a network independently. In addition, the method can be applied cross sectionally as well as longitudinally. In this paper, we calculate the scaled inclusivity for a set of simulated networks of United States cities and a set of real networks consisting of teams that play in the top division of American college football. We found that scaled inclusivity yields reasonable results for the consistency of individual nodes in both sets of networks. We propose that scaled inclusivity may provide a useful way to quantify the change in a network’s community structure.

Figure 1

Consider the two networks in (a) and (b). Both are realizations of a network with the same underlying nodes. Several edges change between the two, and two nodes switch communities (identified by node color). In a large network and across many realizations, it is easy to imagine such minor shifts occurring many times. The problem at hand is how to quantify the consistency of the communities identified across several such realizations.

Figure 2

Depicted are two communities in (a) merging into one community in (b) due to increased intercommunity edges. In binary exclusivity, the blue (dark gray) community would be counted as the better match since the number of nodes is greater. These nodes would be given a value of 1 in the consistency map, and the orange (light gray) nodes would be given a value of 0. In binary inclusivity, both sets of nodes would be given a value of 1. In scaled inclusivity, assuming the second network is the reference, the blue (dark gray) nodes would all receive a value of $\frac{5}{5}·\frac{5}{9}=0.\overline{5}$, and the orange (light gray) nodes would receive a value of $\frac{4}{4}·\frac{4}{9}=0.\overline{4}$, thereby fairly scaling the scores of all nodes. This metric also allows for differentiation between merging communities as shown here and one community that does not change between two networks, which would have a value of 1 for all nodes.

Figure 3

Network 30, with all nodes and edges.

Figure 4

(a) Simulated communities for network 30 and (b) simulated communities from network 3 for comparison. Here, the colors indicate membership in a community.

Figure 5

Maps showing (a) the true conference alignment for FBS in 2009 and (b) the true conference alignment for FBS in 2003. The conferences are similar in these two years, but several teams move between conferences, and several more join the FBS.

Figure 6

Network 30, with the nodes color coded by community according to the best run of QCut. Note the misclassified nodes in Texas and Louisiana.

Figure 7

Scaled inclusivity maps generated using (a) simulated communities and (b) the QCut results. For both maps, network 30 was used as the referent partition (maps in Fig. 4). Note the effects of the misclassifications visible in Fig. 6 on (b) here.

Figure 8

Scaled inclusivity for the simulated community including Texas for simulated communities and the results of QCut. As before, both maps were generated with network 30 as the referent partition. Note the similarity of results in some regions and the vast differences for the two misclassified nodes from Fig. 6.

Figure 9

Scaled inclusivity including negative values for the simulated community including Texas using results from QCut, generated using network 30 as the referent partition. Note that the central node that was misclassified is highly negative, indicating the likelihood that it is consistently in the same module as the nodes surrounding it for most other realizations in the group. The node in Louisiana that also has negative values has a much smaller absolute value, suggesting that it was not consistent in its classification across the other realizations.

Figure 10

Weighted average of scaled inclusivity maps across all communities using QCut results. Note that the misclassified nodes do not significantly contribute to the final values for those nodes from any network when all possible community structures are considered. This indicates that the nodes are in consistent neighborhoods in all networks except the referent network (network 30) used in the analysis.

Figure 11

Map showing, for each node, the index of the realization that, when used as the reference partition, yielded the highest scaled inclusivity value. In other words, this indicates the subject’s scaled inclusivity map that is most representative for each node across the entire group.

Figure 12

Scaled inclusivity including negative values for the simulated community including the northeastern United States, using partition 1 as the referent partition $Q_R$. Most of the green (light gray) values in this image are very close to 0; some nodes farther west had very small values, but they were not pictured for space reasons.

Figure 13

The best partition from the QCut runs for 2009.

Figure 14

Scaled inclusivity map for FBS conferences, with 2009 as the referent network for comparison. Shown for (a) true conference alignment and (b) the QCut approximations.

Figure 15

Weighted average map for the scaled inclusivity of the FBS conferences, shown for the results of QCut.

Figure 16

Year with maximum scaled inclusivity for each node. Network 1 here represents 1995, and network 15 represents 2009.

Figure 17

This figure shows the simulated communities for each network that overlap with the community containing Texas in the reference community (network 26). That community is outlined in each image. The colors of the other communities in each image are arbitrarily assigned.