Comprehensive spectral approach for community structure analysis on complex networks

A simple but efficient spectral approach for analyzing the community structure of complex networks is introduced. It works the same way for all types of networks, by spectrally splitting the adjacency matrix into a “unipartite” and a “multipartite” component. These two matrices reveal the structure of the network from different perspectives and can be analyzed at different levels of detail. Their entries, or the entries of their lower-rank approximations, provide measures of the affinity or antagonism between the nodes that highlight the communities and the “gateway” links that connect them together. An algorithm is then proposed to achieve the automatic assignment of the nodes to communities based on the information provided by either matrix. This algorithm naturally generates overlapping communities but can also be tuned to eliminate the overlaps.

Figure 1

A simple nearly bipartite network.

Figure 2

Split eigenvalue expansions of the adjacency matrix for the network in Fig. 1. Red (solid) and blue (hollow) dots represent positive and negative matrix entries, respectively. The dot in the legend box has unity diameter.

Figure 3

The eigenvalues for Zachary's karate network. Prominent positive eigenvalues 1 through 4 define the unipartite community structure. Prominent negative eigenvalue 34 defines a bipartite approximation of the network.

Figure 4

A modular unipartite network with 21 nodes.

Figure 5

Unipartite eigenvalue expansions of the adjacency matrix for the network in Fig. 4. Red (solid) and blue (hollow) dots represent positive and negative matrix entries, respectively.

Figure 6

The adjacency matrix and three low-rank unipartite and bipartite components for Zachary's karate network. Red (solid) and blue (hollow) dots represent positive and negative matrix entries, respectively. The dot in the legend box has unity diameter.

Figure 7

The adjacency matrix and three low-rank unipartite and bipartite components for the Southern women network. Red (solid) and blue (hollow) dots represent positive and negative matrix entries, respectively. The dot in the legend box has unity diameter.

Figure 8

Ensemble averages of the mutual information versus the average modularity of the built-in partition for $N=300,\langle k\rangle =8,k_{max}=16$. Results are presented for the leading eigenvector algorithm (unrefined: continuous black line, with refining: dotted red line), extremal optimization with refining (dashed green line), spectral split of $M$ (dash-dotted blue line), and spectral split of $A$ (dash-dot-dotted brown line).

Figure 9

Ensemble averages of the mutual information versus the average modularity of the built-in partition for $N=300,\langle k\rangle =20,k_{max}=40$. Results are presented for the leading eigenvector algorithm (unrefined: continuous black line, with refining: dotted red line), extremal optimization with refining (dashed green line), spectral split of $M$ (dash-dotted blue line), and spectral split of $A$ (dash-dot-dotted brown line).

Figure 10

Ensemble averages of the mutual information versus the average modularity of the built-in partition for $N=1000,\langle k\rangle =20,k_{max}=40$. Results are presented for the leading eigenvector algorithm (unrefined: continuous black line, with refining: dotted red line), extremal optimization with refining (dashed green line), spectral split of $M$ (dash-dotted blue line), and spectral split of $A$ (dash-dot-dotted brown line).