Modularity clustering is force-directed layout

Two natural and widely used representations for the community structure of networks are clusterings, which partition the vertex set into disjoint subsets, and layouts, which assign the vertices to positions in a metric space. This paper unifies prominent characterizations of layout quality and clustering quality, by showing that energy models of pairwise attraction and repulsion subsume Newman and Girvan’s modularity measure. Layouts with optimal energy are relaxations of, and are thus consistent with, clusterings with optimal modularity, which is of practical relevance because the two representations are complementary and often used together.

Figure 1

Layouts with small LinLog energy $(a-r=1)$ and with small Fruchterman-Reingold energy $(a-r=3)$ of a pseudorandom network with eight clusters (intracluster density 1.0, expected intercluster density 0.2).

Figure 2

Layouts with optimal $(a,r)$ energy for different values of $a$ and $r$. All vertices and edges have weight 1, except for the small vertex between the triangles which has weight 0.

Figure 3

Impact of the parameters $a$ and $r$ on the optimal layouts of the $(a,r)$-energy model.

Figure 4

$(0,-1.5)$-energy layout and modularity clustering (represented by shapes) of the karate club network. The modularity of the clustering is 0.445. Gray boxes represent members who left the club after the instructor was fired.

Figure 5

$(0,-2)$-energy layout and modularity clustering of the book copurchase network. The modularity is 0.527. Shades represent the classification as liberal (light gray), neutral (dark gray), or conservative (black).

Figure 6

$(0,-1.5)$-energy layout and modularity clustering of the food classification network. The modularity of the clustering is 0.402. (The edges are elided to avoid clutter.)

Figure 7

$(0,-1)$-energy layout and modularity clustering of the world trade network. The modularity of the clustering is 0.275. (The edges are elided to avoid clutter.)