Modularity

Graph theoretic measure quantifying the relative decomposability of a network Girn2023.

[@Newman2004] popularized graph-partitioning problems by introducing modularity. An unweighted, undirected network has some modularity:

$$Q=\frac{1}{2m}\sum _{C\in P}\sum _{i,j\in C}\left[A_{ij}-\frac{k_i{k}_j}{2m}\right]$$

where A$$ is the adjacency matrix, m$isthetotalnumberofedges,and$k_i = \sum_j A_{ij}$isthedegreeofnode$i$.

Modularity counts the number of edges between all pairs of nodes belonging to the same community or module and compares it to the expected number for an equivalent random graph.

Discovering the modules of a network can be done by optimizing modularity (finding the partition with the highest modularity)

• Computationally intractable to exhaust all possible partitions
• Heuristic algorithms such as greedy optimization can be used.

Hierarchical modularity

Each module obtained at the highest-level partition can be decomposed into sub-modules, and so on and so forth.

The Louvain method accomplishes this.

---

---

Appendix

References

Q&A

---

References