An algebraic analysis of the graph modularity

Dario Fasino, Francesco Tudisco

Research output: Contribution to journalArticle

11 Citations (Scopus)

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 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.
LanguageEnglish
Pages997-1018
Number of pages12
JournalSIAM Journal on Matrix Analysis and Applications
Volume35
Issue number3
DOIs
Publication statusPublished - 17 Jul 2014

Fingerprint

Modularity
Community Detection
Adjacency Matrix
Graph in graph theory
Nodal Domain
Laplacian Matrix
Community Structure
Matrix Models
Network Analysis
M-matrix
Spectral Properties
Graph theory
Quadratic form
Eigenvector
Null
Non-negative
Clustering
Eigenvalue
Theorem

Keywords

  • graph partitioning
  • spectral partitioning
  • graph modularity
  • nodal domains
  • community detection

Cite this

Fasino, Dario ; Tudisco, Francesco. / An algebraic analysis of the graph modularity. In: SIAM Journal on Matrix Analysis and Applications. 2014 ; Vol. 35, No. 3. pp. 997-1018.
@article{8b62c35effe4461cb2331ab4b320db68,
title = "An algebraic analysis of the graph modularity",
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 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.",
keywords = "graph partitioning, spectral partitioning, graph modularity, nodal domains, community detection",
author = "Dario Fasino and Francesco Tudisco",
year = "2014",
month = "7",
day = "17",
doi = "10.1137/130943455",
language = "English",
volume = "35",
pages = "997--1018",
journal = "SIAM Journal on Matrix Analysis and Applications",
issn = "0895-4798",
number = "3",

}

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 journalArticle

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 -