Community detection at various resolutions

Showcase and Applications
1

Introduction

A common approach to community detection in networks is to find a partitioning of a network’s vertices that maximizes a quantity called modularity. Intuitively, modularity characterizes the degree to which connections stay within individual partitions rather connecting different partitions together, relative to what would be expected in a random graph having the same degrees. It is computed relative to a given partitioning of the graph’s vertices.

Mathematically, modularity is defined as

Q = \frac{1}{2m} \sum_{i,j} \left(A_{ij} - \frac{k_i k_j}{2m} \right) \delta_{c_i,c_j},

where A is the adjacency matrix of the graph, m is its number of edges, k_i denotes the degree of vertex i, \delta_{ij} = 1 if i=j and 0 otherwise is the Kronecker symbol, and c_i is the partition to which vertex i belongs.

Here, the term k_i k_j / (2m) is the probability that vertices i and j are connected in a random graph with prescribed degrees. Q will be large if there are more connections within partitions than expected in such a random graph, our null model. However, in a large graph that has some local structure, this may not be the most reasonable null model, as vertices that are “far” would not naturally connect to each other.

Modularity can be generalized to include a “resolution parameter” \gamma that controls the weighting of the null model:

Q(\gamma) = \frac{1}{2m} \sum_{i,j} \left(A_{ij} - \gamma \frac{k_i k_j}{2m} \right) \delta_{c_i,c_j}.

Maximizing modularity with various resolution parameters allows for finding communities at different scales. A large \gamma corresponds to assuming a stronger local structure, and results in a larger number of small (more local) partitions, while a small \gamma results in few, large partitions.

Community detection methods that support resolutions in igraph

igraph 0.8 introduced igraph_community_leiden which supports specifying the resolution parameter. It is already available as IGCommunitiesLeiden in the Mathematica interface (IGraph/M 0.4) and community_leiden in the Python interface (python-igraph 0.8). It is coming soon to the R interface.

The next version of igraph will also include support for the resolution parameter for igraph_community_multilevel, thanks to the contribution of Jean Monlong.

Let us try it out on a fractal-like graph which has the connectivity of a Sierpinski triangle. In Mathematica, this can be constructed as

Needs["IGraphM`"];
g = IGMeshGraph[SierpinskiMesh[3], GraphStyle -> "BasicBlack", VertexSize -> 0.5]

image
image720×632 23 KB

For those who wish to experiment with other interfaces, I attached a 6-level Sierpinski graph to this post.

sierp6.graphml (241.5 KB)

It was exported like this:

g = IGMeshGraph[SierpinskiMesh[6], GraphStyle -> "BasicBlack", VertexSize -> 0.9];
IGExport["sierp6.graphml", g]

Let us run community detection on this graph at various resolutions using the Leiden method:

Table[
 HighlightGraph[
  g,
  IGCommunitiesLeiden[g, "Resolution" -> γ]["Communities"]
 ],
 {γ, {1/30, 1/10, 1, 5}}
]

image
image780×698 197 KB

Once the resolution parameter becomes available in the multilevel method (expected in IGraph/M 0.4.1, to be released too), we will be able to use IGCommunitiesMultlevel with the same syntax.

Table[
 HighlightGraph[
  g,
  IGCommunitiesMultilevel[g, "Resolution" -> γ]["Communities"]
 ],
 {γ, {1/30, 1/10, 1, 5}}
]

image
image780×698 218 KB

We can also make an animation that shows how the detected community structure changes as the resolution parameter is adjusted.

g = IGMeshGraph[SierpinskiMesh[7], GraphStyle -> "BasicBlack", 
   VertexSize -> 1, EdgeShapeFunction -> None];
frames = Table[
   HighlightGraph[
    g,
    IGCommunitiesMultilevel[g, "Resolution" -> 2^α]["Communities"],
    PlotLabel -> 
     With[{α = α}, 
      HoldForm[γ == 2^NumberForm[α, {2, 1}]]]
    ],
   {α, -8.0, 5.0, 0.5}
   ];

Export["animation.gif", frames, "DisplayDurations" -> 1/2, 
 AnimationRepetitions -> Infinity]

Sierpinksi clustering
Sierpinksi clustering720×664 760 KB

The code for this demonstration can be downloaded as a Mathematica notebook: Community detection and various resolutions.nb.zip (322.9 KB)

2 Likes