Clustering algorithm for determining community structure in large networks

We propose an algorithm to find the community structure in complex networks based on the combination of spectral analysis and modularity optimization. The clustering produced by our algorithm is as accurate as the best algorithms on the literature of modularity optimization; however, the main asset of the algorithm is its efficiency. The best match for our algorithm is Newman’s fast algorithm, which is the reference algorithm for clustering in large networks due to its efficiency. When both algorithms are compared, our algorithm outperforms the fast algorithm both in efficiency and accuracy of the clustering, in terms of modularity. Thus, the results suggest that the proposed algorithm is a good choice to analyze the community structure of medium and large networks in the range of tens and hundreds of thousand vertices.

Figure 1

(Color online) Working of the PDB algorithm in the Zachary network. (a) shows the initial vertices (labeled with 2), which are seeds for the random walkers vertices labeled. (b) shows the initial partition of the network into communities produced by the random walker stage. (c) and (d) show different partitions created by the modularity optimization process. The optimal partition, whose modularity is maximal, is shown in (c).

Figure 2

(Color online) Community structure of the Zachary network produced by the PDB algorithm. Circles and squares over the individuals denote to whom they align to after the karate club broke up. Those who aligned with the instructor are represented by circles, and those who aligned with the administrator are represented by squares.

Figure 3

(Color online) Modularity $Q$ over the execution of the algorithms for the cond-mat network. The PBD algorithm is shown as the solid line and the Newman’s fast algorithm (N) as the dashed line. Note that the number of merge operations required for both algorithms is different (PBD optimization stage starts with the partition given by the spectral analysis stage). PBD algorithm requires approximately the 22% of the merge operations performed by the N algorithm. Both the figure and the inset contain the very same information, but it is depicted in a different fashion to better illustrate the evolution of modularity. Note that the main figure is plotted in a log scale, and the time goes from right to left. This is done in order to magnify the last steps of the algorithms, which is when maximum modularity is found. We would like to remark that the number of remaining groups decreases over time, while the number of merge operations increases over time.

Figure 4

Behavior of the merge operation of the PBD (above) and the N (below) algorithms. For each merge operation the normalized ratio of the size of groups to be merged is calculated as $r_{\mathit{mo}}=\frac{\min (s_i,s_j)}{s_i+s_j}$, where $s_i$ and $s_j$ are the size of group $i$ and $j$, respectively. The merge operation creates a new group $z=i\cup j$ of size $s_z=s_i+s_j$. The line corresponds to the evolution of modularity $Q$.

Figure 5

(Color online) Comparison between the efficiency in CPU time (in seconds) for ten networks of different sizes. The solid circles show the results for the Newman’s fast algorithm. The results of the PBD algorithm are represented by solid squares.

Figure 6

(Color online) Fraction of vertices correctly classified using computer-generated networks. The circles show the result of the Girvan-Newman algorithm (GN). The squares show the results of the PBD algorithm. Each point is an average over 50 networks.