An algebraic analysis of the graph modularity

Dario Fasino, Francesco Tudisco

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)


One of the most relevant tasks in network analysis is the detection of community structures, or clustering. Most popular techniques for community detection are based on the maximization of a quality function called modularity, which in turn is based upon particular quadratic forms associated to a real symmetric modularity matrix $M$, defined in terms of the adjacency matrix and a rank-one null model matrix. That matrix could be posed inside the set of relevant matrices involved in graph theory, alongside adjacency and Laplacian matrices. In this paper we analyze certain spectral properties of modularity matrices, which are related to the community detection problem. In particular, we propose a nodal domain theorem for the eigenvectors of $M$; we point out several relations occurring between the graph's communities and nonnegative eigenvalues of $M$; and we derive a Cheeger-type inequality for the graph modularity.
Original languageEnglish
Pages (from-to)997-1018
Number of pages12
JournalSIAM Journal on Matrix Analysis and Applications
Issue number3
Publication statusPublished - 17 Jul 2014


  • graph partitioning
  • spectral partitioning
  • graph modularity
  • nodal domains
  • community detection


Dive into the research topics of 'An algebraic analysis of the graph modularity'. Together they form a unique fingerprint.

Cite this