Modularity-based graph partitioning using conditional expected models

Modularity-based partitioning methods divide networks into modules by comparing their structure against random networks conditioned to have the same number of nodes, edges, and degree distribution. We propose a novel way to measure modularity and divide graphs, based on conditional probabilities of the edge strength of random networks. We provide closed-form solutions for the expected strength of an edge when it is conditioned on the degrees of the two neighboring nodes, or alternatively on the degrees of all nodes comprising the network. We analytically compute the expected network under the assumptions of Gaussian and Bernoulli distributions. When the Gaussian distribution assumption is violated, we prove that our expression is the best linear unbiased estimator. Finally, we investigate the performance of our conditional expected model in partitioning simulated and real-world networks.

Figure 1

Random graph models and modularity. First column: Nodes $i$ and $j$ of the original graph are connected with an edge $A_{ij}$. Second column: Random graph A has the same node degrees $k_i$ and $k_j$ as the original graph, but the edge strength is replaced by its conditional expected value $E\left(A_{ij}\right|\mathbf{k})$, with analytic expressions given in Table . The contribution of this edge to modularity is $A_{ij}-E\left(A_{ij}\right|\mathbf{k})$ when the two nodes are assigned to the same group, and the total modularity involves a sum over all edges of the graph. Third column: Similarly for random graph B, with the exception that $R_{ij}$ in Eq. (1) is used instead of the conditional expected edge strength.

Figure 2

Two simple four-node complete networks with different topological configurations.

Figure 3

Partition results for Gaussian graphs. (a) Performance against different values of variance (${\sigma }^2$) of the Gaussian distribution and zero additive noise (${\sigma }_N^2=0$); (b) adjacency matrix; (c) difference between adjacency matrix of original graph versus null model ${\mathbf{A}}_{|\mathbf{k}}^{\mathrm{NULL}}$; (d) same for $\mathbf{R}$ null model. Top row: 12 vs 8 cluster size; bottom row: 10 vs 10 cluster size. Method $Q_A$ accurately partitions the graph for all values of ${\sigma }^2$, whereas method $Q_B$ fails for low values of ${\sigma }^2$.

Figure 4

Partition results of Gaussian graphs for several levels of edge variance ${\sigma }^2$, noise variance ${\sigma }_N^2$, and cluster size ratio $N_1/N$. Method $Q_A$ is more robust to noise, and method $Q_B$ fails for small values of ${\sigma }^2$ but performs better for large values of ${\sigma }^2$.

Figure 5

Partitioning graphs with both positive and negative connections. (a) Adjacency matrix; (b) difference between adjacency matrix of original graph versus null model ${\mathbf{A}}_{|\mathbf{k}}^{\mathrm{NULL}}$; (c) same for $\mathbf{R}$ null model. In the presence of negative connections, null model $\mathbf{R}$ fails to partition the graph, as indicated by the lack of structure of matrix $\mathbf{A}-\mathbf{R}$.

Figure 6

Comparison of null graph models against a random rewiring scheme. Distance is expressed as root-mean-square difference between the elements of the adjacency matrices of the graphs [Eq. (25)]. For each box plot, the central mark is the median, the edges of the box are the 25th and 75th percentiles, and the whiskers extend to the most extreme data points not considered outliers. Left: Distance does not depend on the number of rewiring steps $N_r$. Right: As the size of graph $N$ increases, distance becomes smaller. Overall, $Q_A$ null models are closer to an actual rewiring scheme than $Q_B$ models.

Figure 7

Partition results for the binary network described in Ref. [4]. Top row: Higher values of $k_o$ lead to less community structure of the network. Bottom row: Partition results for different values of $k_o$. Performance of all methods is practically equal.

Figure 8

Results of benchmark in Ref. [70] for $Q_A$ and $Q_B$ methods. The performance of all methods is almost identical for all values of mixing parameter $\mu$ and average degree $\langle k\rangle$.

Figure 9

Partition results for a binary network for different values of cluster size ratio. (a) Adjacency matrix for 10 vs 10 cluster size; (b) adjacency matrix for 17 vs 3 cluster size. (c) Performance is very similar for all methods, across all cluster size ratio values.

Figure 10

Karate club network. Nodes indicate 34 club members, and color indicates the actual split of the group after a conflict between its members.

Figure 11

Graph analysis of a structural network based on diffusion brain imaging. (a) Adjacency matrix with the upper-left and lower-right quadrants corresponding to regions of interest on the right and left hemispheres, respectively; (b) structural brain network with edges greater than 0.1; (c) partition results for method $Q_A$. Color indicates cluster membership; (d) same as before for method $Q_B$; (e) partition results for method $Q_A$, but now spheres indicate ROIs and larger spheres indicate network hubs; (f) same as before for method $Q_B$.

Figure 12

Partitioning results with $Q_A$, $Q_B$, and $Q_B^{\pm }$ [73] methods of a real functional brain network. Different modules detected by the algorithm are labeled by color. First row indicates the symmetric across-hemisphere results while the second row highlights the asymmetric ROIs.