Modularity bounds for clusters located by leading eigenvectors of the normalized modularity matrix

Dario Fasino, Francesco Tudisco

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

Nodal theorems for generalized modularity ma trices ensure that the cluster located by the positive entries of the leading eigenvector of various modularity matrices induces a connected subgraph. In this paper we obtain lower bounds for the modularity of that subgraph showing that, under certain conditions, the nodal domains induced by eigenvectors corresponding to highly positive eigenvalues of the normalized modularity matrix have indeed positive modularity, that is, they can be recognized as modules inside the network. Moreover we establish Cheeger-type inequalities for the cut-modularity of the graph, providing a theoretical support to the common understanding that highly positive eigenvalues of modularity matrices are related with the possibility of subdividing a network into communities.
LanguageEnglish
Pages701-714
Number of pages14
JournalJournal of Mathematical Inequalities
Volume11
Issue number3
DOIs
Publication statusPublished - 30 Sep 2017

Fingerprint

Modularity
Eigenvector
Subgraph
Nodal Domain
Eigenvalue
Lower bound
Module
Graph in graph theory
Theorem

Keywords

  • nodal theory
  • modular matrices
  • complex networks

Cite this

@article{f5bf6ad9e3e5419eb6b3a017523cde1f,
title = "Modularity bounds for clusters located by leading eigenvectors of the normalized modularity matrix",
abstract = "Nodal theorems for generalized modularity ma trices ensure that the cluster located by the positive entries of the leading eigenvector of various modularity matrices induces a connected subgraph. In this paper we obtain lower bounds for the modularity of that subgraph showing that, under certain conditions, the nodal domains induced by eigenvectors corresponding to highly positive eigenvalues of the normalized modularity matrix have indeed positive modularity, that is, they can be recognized as modules inside the network. Moreover we establish Cheeger-type inequalities for the cut-modularity of the graph, providing a theoretical support to the common understanding that highly positive eigenvalues of modularity matrices are related with the possibility of subdividing a network into communities.",
keywords = "nodal theory, modular matrices, complex networks",
author = "Dario Fasino and Francesco Tudisco",
year = "2017",
month = "9",
day = "30",
doi = "10.7153/jmi-2017-11-56",
language = "English",
volume = "11",
pages = "701--714",
journal = "Journal of Mathematical Inequalities",
issn = "1846-579X",
publisher = "Element d.o.o.",
number = "3",

}

Modularity bounds for clusters located by leading eigenvectors of the normalized modularity matrix. / Fasino, Dario; Tudisco, Francesco.

In: Journal of Mathematical Inequalities, Vol. 11, No. 3, 30.09.2017, p. 701-714.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Modularity bounds for clusters located by leading eigenvectors of the normalized modularity matrix

AU - Fasino, Dario

AU - Tudisco, Francesco

PY - 2017/9/30

Y1 - 2017/9/30

N2 - Nodal theorems for generalized modularity ma trices ensure that the cluster located by the positive entries of the leading eigenvector of various modularity matrices induces a connected subgraph. In this paper we obtain lower bounds for the modularity of that subgraph showing that, under certain conditions, the nodal domains induced by eigenvectors corresponding to highly positive eigenvalues of the normalized modularity matrix have indeed positive modularity, that is, they can be recognized as modules inside the network. Moreover we establish Cheeger-type inequalities for the cut-modularity of the graph, providing a theoretical support to the common understanding that highly positive eigenvalues of modularity matrices are related with the possibility of subdividing a network into communities.

AB - Nodal theorems for generalized modularity ma trices ensure that the cluster located by the positive entries of the leading eigenvector of various modularity matrices induces a connected subgraph. In this paper we obtain lower bounds for the modularity of that subgraph showing that, under certain conditions, the nodal domains induced by eigenvectors corresponding to highly positive eigenvalues of the normalized modularity matrix have indeed positive modularity, that is, they can be recognized as modules inside the network. Moreover we establish Cheeger-type inequalities for the cut-modularity of the graph, providing a theoretical support to the common understanding that highly positive eigenvalues of modularity matrices are related with the possibility of subdividing a network into communities.

KW - nodal theory

KW - modular matrices

KW - complex networks

UR - http://arxiv.org/abs/1602.05457

U2 - 10.7153/jmi-2017-11-56

DO - 10.7153/jmi-2017-11-56

M3 - Article

VL - 11

SP - 701

EP - 714

JO - Journal of Mathematical Inequalities

T2 - Journal of Mathematical Inequalities

JF - Journal of Mathematical Inequalities

SN - 1846-579X

IS - 3

ER -