An Algebraic Analysis of the Graph Modularity

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.

• Publication year

  2013

• Venue

  SIAM Journal on Matrix Analysis and Applications

• Publication date

  2013-10-10

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/130943455arXiv 1310.3031
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Moments of parameter estimates for Chung-Lu random graph models

  2012influential reference
• On the Perron–Frobenius theory for complex matrices

  2012cited by this paper
• Network analysis

  2011influential reference
• Limits of modularity maximization in community detection

  2011cited by this paper
• Narrow scope for resolution-limit-free community detection.

  2011influential reference
• Networks: An Introduction

  2010cited by this paper
• Community detection in graphs

  2009influential reference
• Fast unfolding of communities in large networks

  2008cited by this paper
• Analysis of the structure of complex networks at different resolution levels

  2007cited by this paper
• Statistical mechanics of community detection.

  2006influential reference
• Finding community structure in networks using the eigenvectors of matrices.

  2006influential reference
• Complex Graphs and Networks

  2006cited by this paper
• Modelling protein–protein interaction networks via a stickiness index

  2006cited by this paper
• Resolution limit in community detection

  2006influential reference
• Limited resolution in complex network community detection with Potts model approach

  2006influential reference
• Modularity and community structure in networks.

  2006influential reference
• Expander Graphs and their Applications

  2006influential reference
• Network Analysis: Methodological Foundations (Lecture Notes in Computer Science)

  2005cited by this paper
• The Structure and Function of Complex Networks

  2003influential reference
• Finding and evaluating community structure in networks.

  2003influential reference
• Economic inequality and burden-sharing in the provision of local environmental quality

  2002influential reference
• Discrete Nodal Domain Theorems

  2000influential reference
• Perron–Frobenius type results and discrete versions of nodal domain theorems

  1999influential reference
• Spectral Graph Theory

  1996cited by this paper
• Graph Partitioning by Eigenvectors

  1988influential reference
• Graduate Texts in Mathematics

  1982cited by this paper
• Nonnegative Matrices in the Mathematical Sciences

  1979cited by this paper
• A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory

  1975influential reference
• Algebraic connectivity of graphs

  1973influential reference

• Mathematical modeling of biological interactions: formalisms and contemporary applications

  2024cites this paper
• A Spectral Framework for Tracking Communities in Evolving Networks

  2024cites this paper
• Modularity and Graph Expansion

  2023cites this paper
• Evaluating brain modularity benefits of an acting intervention: a discriminant-analysis framework

  2023cites this paper
• Nodal domain count for the generalized graph p-Laplacian

  2022cites this paper
• The self-consistent field iteration for p-spectral clustering

  2021cites this paper
• Generating large scale‐free networks with the Chung–Lu random graph model

  2019cites this paper
• Total variation based community detection using a nonlinear optimization approach

  2019cites this paper
• Cipolla, Stefano and Di Fiore, Carmine and Tudisco, Francesco (2017) Euler-Richardson method preconditioned by weakly stochastic matrix

  2018cites this paper
• Modularity of Erdős‐Rényi random graphs

  2018cites this paper
• Impact of Document Representation on Neural Ad hoc Retrieval

  2018cites this paper
• The expected adjacency and modularity matrices in the degree corrected stochastic block model

  2018cites this paper
• Fasino, Dario and Tudisco, Francesco (2017) Modularity bounds for clusters located by leading eigenvectors of the normalized modularity

  2018influential citation
• COMMUNITY DETECTION IN NETWORKS VIA NONLINEAR

  2018cites this paper
• Node and layer eigenvector centralities for multiplex networks

  2017cites this paper
• Community detection in networks via nonlinear modularity eigenvectors

  2017cites this paper
• A modularity based spectral method for simultaneous community and anti-community detection

  2017cites this paper
• On the stability of network indices defined by means of matrix functions

  2017cites this paper
• Euler-Richardson method preconditioned by weakly stochastic matrix algebras: a potential contribution to Pagerank computation

  2017cites this paper
• A nodal domain theorem and a higher-order Cheeger inequality for the graph $p$-Laplacian

  2016cites this paper
• Modularity bounds for clusters located by leading eigenvectors of the normalized modularity matrix

  2016cites this paper
• Nodal domain theorem for the graph p-Laplacian

  2016cites this paper
• Statistical Signal Processing for Graphs

  2015cites this paper
• Generalized modularity matrices

  2015influential citation
• A Spectral Framework for Anomalous Subgraph Detection

  2014cites this paper
• Applications to network analysis : Graph partitioning and community detection Lecture notes

  2014cites this paper
• ournal of M athematical I nequalities

  year unknowninfluential citation