An algebraic analysis of the graph modularity

DOI10.1137/130943455MaRDI QIDQ2936583zbMATH OpenOpenAlexFDO

Authors Francesco Tudisco, Dario Fasino

Publication date 17 December 2014

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.3031

zbMATH Keywords

community detectiongraph modularitygraph partitioningnodal domainsspectral partitioning

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Eigenvalues, singular values, and eigenvectors (15A18)

Abstract: 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, incidence and Laplacian matrices. This is the reason we propose a graph analysis based on the algebraic and spectral properties of such matrix. In particular, we propose a nodal domain theorem for the eigenvectors of $M$; we point out several relations occurring between graph's communities and nonnegative eigenvalues of $M$; and we derive a Cheeger-type inequality for the graph optimal modularity.

Recommendations

• Generalized modularity matrices
• Modularity bounds for clusters located by leading eigenvectors of the normalized modularity matrix
• Spectral properties of modularity matrices
• Modularity spectra, eigen-subspaces, and structure of weighted graphs
• Community detection in networks via nonlinear modularity eigenvectors

Cited in

(25)

• The expected adjacency and modularity matrices in the degree corrected stochastic block model
• A modularity based spectral method for simultaneous community and anti-community detection
• Spectral properties of modularity matrices
• Modularity spectra, eigen-subspaces, and structure of weighted graphs
• Nodal domain count for the generalized graph \(p\)-Laplacian
• The complexity of modular graph automorphism
• Generalized modularity matrices
• Localization of dominant eigenpairs and planted communities by means of Frobenius inner products.
• A characterization of modularity in graphs
• Modularity of regular and treelike graphs
• Some properties of E-quality function for network clustering
• An Algorithm for the Modular Decomposition of Hypergraphs
• scientific article; zbMATH DE number 1136076 (Why is no real title available?)
• Node and Layer Eigenvector Centralities for Multiplex Networks
• Community detection in networks via nonlinear modularity eigenvectors
• On the stability of network indices defined by means of matrix functions
• scientific article; zbMATH DE number 7378595 (Why is no real title available?)
• Total variation based community detection using a nonlinear optimization approach
• Modularity of Erdős-Rényi random graphs
• Modularity bounds for clusters located by leading eigenvectors of the normalized modularity matrix
• A note on graphs whose largest eigenvalues of the modularity matrix equals zero
• Modularity Maximization for Graphons
• Generating large scale‐free networks with the Chung–Lu random graph model
• Characterization of expansion-related properties of modular graphs
• Modularity and graph expansion

This page was built for publication: An algebraic analysis of the graph modularity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2936583)