Spectral properties of modularity matrices

DOI10.1016/J.LAA.2014.10.039MaRDI QIDQ2341898zbMATH OpenOpenAlexFDO

Authors Marianna Bolla, Brian Bullins, Sorathan Chaturapruek, Shiwen Chen, Katalin Friedl

Publication date 6 May 2015

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

spectral clusteringmodularity matrixmultipartite graphsmaximal correlationisoperimetric number\(\chi^2\) test for independence

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Contingency tables (62H17) Social networks; opinion dynamics (91D30) Signed and weighted graphs (05C22)

Abstract: In July 2012, at the Conference on Applications of Graph Spectra in Computer Science, Barcelona, D. Stevanovic posed the following open problem: which graphs have the zero as the largest eigenvalue of their modularity matrix? The conjecture was that only the complete and complete multipartite graphs. They indeed have this property, but are they the only ones? In this paper, we will give an affirmative answer to this question and prove a bit more: both the modularity and the normalized modularity matrix of a graph is negative semidefinite if and only if the graph is complete or complete multipartite.

Recommendations

• An algebraic analysis of the graph modularity
• Generalized modularity matrices
• Modularity spectra, eigen-subspaces, and structure of weighted graphs
• Modularity bounds for clusters located by leading eigenvectors of the normalized modularity matrix
• A nonparametric view of network models and Newman–Girvan and other modularities

Cites work

• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Eigenvalues and expanders
• Expander graphs and their applications
• Modularity spectra, eigen-subspaces, and structure of weighted graphs
• Optimization problems for weighted graphs and related correlation estimates
• Spectral clustering and biclustering. Learning large graphs and contingency tables

Cited in

(13)

• Eigenspectral Analysis of Hermitian Adjacency Matrices for the Analysis of Group Substructures
• Spectra of modular random graphs
• Generalized modularity matrices
• Positivity-preserving and entropy-bounded discontinuous Galerkin method for the chemically reacting, compressible Euler equations. I: The one-dimensional case
• Matrix and discrepancy view of generalized random and quasirandom graphs
• Spectral triadic decompositions of real-world networks
• A note on graphs whose largest eigenvalues of the modularity matrix equals zero
• The asymptotic distribution of modularity in weighted signed networks
• An algebraic analysis of the graph modularity
• Modularity bounds for clusters located by leading eigenvectors of the normalized modularity matrix
• Modularity of Erdős-Rényi random graphs
• The expected adjacency and modularity matrices in the degree corrected stochastic block model
• Modularity spectra, eigen-subspaces, and structure of weighted graphs

This page was built for publication: Spectral properties of modularity matrices

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