Abstract
| Language | English |
|---|---|
| Pages | 997-1018 |
| Number of pages | 12 |
| Journal | SIAM Journal on Matrix Analysis and Applications |
| Volume | 35 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - 17 Jul 2014 |
Fingerprint
Keywords
- graph partitioning
- spectral partitioning
- graph modularity
- nodal domains
- community detection
Cite this
}
An algebraic analysis of the graph modularity. / Fasino, Dario; Tudisco, Francesco.
In: SIAM Journal on Matrix Analysis and Applications, Vol. 35, No. 3, 17.07.2014, p. 997-1018.Research output: Contribution to journal › Article
TY - JOUR
T1 - An algebraic analysis of the graph modularity
AU - Fasino, Dario
AU - Tudisco, Francesco
PY - 2014/7/17
Y1 - 2014/7/17
N2 - 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.
AB - 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.
KW - graph partitioning
KW - spectral partitioning
KW - graph modularity
KW - nodal domains
KW - community detection
U2 - 10.1137/130943455
DO - 10.1137/130943455
M3 - Article
VL - 35
SP - 997
EP - 1018
JO - SIAM Journal on Matrix Analysis and Applications
T2 - SIAM Journal on Matrix Analysis and Applications
JF - SIAM Journal on Matrix Analysis and Applications
SN - 0895-4798
IS - 3
ER -