Benchmark model to assess community structure in evolving networks

Detecting the time evolution of the community structure of networks is crucial to identify major changes in the internal organization of many complex systems, which may undergo important endogenous or exogenous events. This analysis can be done in two ways: considering each snapshot as an independent community detection problem or taking into account the whole evolution of the network. In the first case, one can apply static methods on the temporal snapshots, which correspond to configurations of the system in short time windows, and match afterward the communities across layers. Alternatively, one can develop dedicated dynamic procedures so that multiple snapshots are simultaneously taken into account while detecting communities, which allows us to keep memory of the flow. To check how well a method of any kind could capture the evolution of communities, suitable benchmarks are needed. Here we propose a model for generating simple dynamic benchmark graphs, based on stochastic block models. In them, the time evolution consists of a periodic oscillation of the system's structure between configurations with built-in community structure. We also propose the extension of quality comparison indices to the dynamic scenario.

Figure 1

Schematic representation of the benchmarks. (a) Grow-shrink benchmark with $q=2$. We begin with two equal-sized communities and over a period of $\tau$ nodes move from the bottom community to the top, then from the top to bottom, and then back to the symmetric state. (b) Merge-split benchmark with $q=2$. We begin with two communities and over a period of $\tau$ we linearly add edges until there is one community with uniform link density and then reverse the process. (c) Mixed benchmark with $q=4$, combining the merging and growing processes.

Figure 2

Construction of the contingency tables $m_{\alpha {\alpha }^{\prime }}$. On top we represent three steps (columns) of the time evolution of a network of four nodes (rows) and the partitions in communities we want to compare, e.g., the planted partitions from the benchmark and those obtained by a certain algorithm. To compare these two partitionings, we can do it as it is depicted in (a), which takes only one snapshot at a time $\left(\sigma =0\right)$, or as in (b), building a contingency table where the entries consider two snapshots at the same time $\left(\sigma =1\right)$. Afterward, the measures (NVI, NMI, or Jaccard index) are calculated from these tables.

Figure 3

Results of the application of the multislice community detection method to the three benchmarks proposed (in columns). The first row corresponds to the planted partition of each benchmark, while the three remaining rows are the partitions obtained by the multislice algorithm for different values of the interslice parameter $\omega$, which is the weight of the coupling between different instances of the same nodes across layers. When $\omega =0$ the slices are disconnected and then the community detection analysis is done for each slice separately. As this value increases, more importance is given to the evolving nature of the problem and communities across slices are found. In each plot, the vertical axis corresponds to the index of nodes in the network, while the horizontal axis represents the time. The color of each pair {node, time} is the label of the community at which the node is assigned at that specific time.

Figure 4

Plots of the normalized variation of information (NVI) between the planted partition and the results of the multislice algorithm in Fig. 3, for three different interslice couplings and for the three benchmarks proposed. The NVI is computed using the proposed evolving formulation and for three different window sizes: 1, 2, and 5. There is a column for each benchmark and a row for each time window size.

Figure 5

Example of the comparison of a planted evolving community structure with the results from two different algorithms. The NVI values are shown below the corresponding contingency tables for time windows of sizes 1 and 3.