Modularity spectra, eigen-subspaces, and structure of weighted graphs

DOI10.1016/J.EJC.2013.06.019MaRDI QIDQ2509741zbMATH OpenOpenAlexFDO

Authors Marianna Bolla

Publication date 29 July 2014

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Limit theorems in probability theory (60F99) Estimation in multivariate analysis (62H12)

Abstract: The role of the normalized modularity matrix in finding homogeneous cuts will be presented. We also discuss the testability of the structural eigenvalues and that of the subspace spanned by the corresponding eigenvectors of this matrix. In the presence of a spectral gap between the k-1 largest absolute value eigenvalues and the remainder of the spectrum, this in turn implies the testability of the sum of the inner variances of the k clusters that are obtained by applying the k-means algorithm for the appropriately chosen vertex representatives.

Recommendations

• Spectral properties of modularity matrices
• Modularity bounds for clusters located by leading eigenvectors of the normalized modularity matrix
• Spectral concentration and greedy k-clustering
• Spectra and structure of weighted graphs
• An algebraic analysis of the graph modularity

Cites work

• Beyond the expanders
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Eigenvalues and expanders
• Expander graphs and their applications
• Finitely forcible graphons
• Generalized quasirandom graphs
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Isoperimetric properties of weighted graphs related to the Laplacian spectrum and canonical correlations
• On measures of dependence
• Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions
• Quasi‐random graphs with given degree sequences
• Quick approximation to matrices and applications
• Recognizing linear structure in noisy matrices
• Spectra and optimal partitions of weighted graphs
• Spectra and structure of weighted graphs
• Testability of minimum balanced multiway cut densities

Cited in

(8)

• Spectral properties of modularity matrices
• Relating multiway discrepancy and singular values of nonnegative rectangular matrices
• An algebraic analysis of the graph modularity
• SVD, discrepancy, and regular structure of contingency tables
• Testability of minimum balanced multiway cut densities
• Generalized quasirandom properties of expanding graph sequences
• Modularity bounds for clusters located by leading eigenvectors of the normalized modularity matrix
• Matrix and discrepancy view of generalized random and quasirandom graphs

This page was built for publication: Modularity spectra, eigen-subspaces, and structure of weighted graphs

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