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

Fasino, Dario and Tudisco, Francesco (2017) Modularity bounds for clusters located by leading eigenvectors of the normalized modularity matrix. Journal of Mathematical Inequalities, 11 (3). pp. 701-714. ISSN 1848-9575 (https://doi.org/10.7153/jmi-2017-11-56)

[thumbnail of Fasino-Tudisco-JMI-2017-Modularity-bounds-for-clusters-located-by leading-eigenvectors]
Preview
 Text. Filename: Fasino_Tudisco_JMI_2017_Modularity_bounds_for_clusters_located_by_leading_eigenvectors.pdf
Final Published Version
License: Creative Commons Attribution-NonCommercial 3.0 logo
Download (223kB)| Preview

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.

CORE (COnnecting REpositories)