A modularity based spectral method for simultaneous community and anti-community detection

Dario Fasino, Francesco Tudisco

Research output: Contribution to journalArticle

Abstract

In a graph or complex network, communities and anti-communities are node sets whose modularity attains extremely large values, positive and negative, respectively. We consider the simultaneous detection of communities and anti-communities, by looking at spectral methods based on various matrix-based definitions of the modularity of a vertex set. Invariant subspaces associated to extreme eigenvalues of these matrices provide indications on the presence of both kinds of modular structure in the network. The localization of the relevant invariant subspaces can be estimated by looking at particular matrix angles based on Frobenius inner products.
LanguageEnglish
JournalLinear Algebra and its Applications
Publication statusSubmitted - 20 Sep 2017

Fingerprint

Community Detection
Complex networks
Spectral Methods
Modularity
Invariant Subspace
Vertex of a graph
Frobenius
Scalar, inner or dot product
Complex Networks
Extremes
Eigenvalue
Angle
Community
Graph in graph theory

Keywords

  • spectral methods
  • modularity matrix
  • stochastic block model
  • inflation product

Cite this

Fasino, D., & Tudisco, F. (2017). A modularity based spectral method for simultaneous community and anti-community detection. Manuscript submitted for publication.
@article{7f7b000d433840a3a293554224783e20,
title = "A modularity based spectral method for simultaneous community and anti-community detection",
abstract = "In a graph or complex network, communities and anti-communities are node sets whose modularity attains extremely large values, positive and negative, respectively. We consider the simultaneous detection of communities and anti-communities, by looking at spectral methods based on various matrix-based definitions of the modularity of a vertex set. Invariant subspaces associated to extreme eigenvalues of these matrices provide indications on the presence of both kinds of modular structure in the network. The localization of the relevant invariant subspaces can be estimated by looking at particular matrix angles based on Frobenius inner products.",
keywords = "spectral methods, modularity matrix, stochastic block model, inflation product",
author = "Dario Fasino and Francesco Tudisco",
year = "2017",
month = "9",
day = "20",
language = "English",
journal = "Linear Algebra and its Applications",
issn = "0024-3795",

}

A modularity based spectral method for simultaneous community and anti-community detection. / Fasino, Dario; Tudisco, Francesco.

In: Linear Algebra and its Applications, 20.09.2017.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A modularity based spectral method for simultaneous community and anti-community detection

AU - Fasino, Dario

AU - Tudisco, Francesco

PY - 2017/9/20

Y1 - 2017/9/20

N2 - In a graph or complex network, communities and anti-communities are node sets whose modularity attains extremely large values, positive and negative, respectively. We consider the simultaneous detection of communities and anti-communities, by looking at spectral methods based on various matrix-based definitions of the modularity of a vertex set. Invariant subspaces associated to extreme eigenvalues of these matrices provide indications on the presence of both kinds of modular structure in the network. The localization of the relevant invariant subspaces can be estimated by looking at particular matrix angles based on Frobenius inner products.

AB - In a graph or complex network, communities and anti-communities are node sets whose modularity attains extremely large values, positive and negative, respectively. We consider the simultaneous detection of communities and anti-communities, by looking at spectral methods based on various matrix-based definitions of the modularity of a vertex set. Invariant subspaces associated to extreme eigenvalues of these matrices provide indications on the presence of both kinds of modular structure in the network. The localization of the relevant invariant subspaces can be estimated by looking at particular matrix angles based on Frobenius inner products.

KW - spectral methods

KW - modularity matrix

KW - stochastic block model

KW - inflation product

M3 - Article

JO - Linear Algebra and its Applications

T2 - Linear Algebra and its Applications

JF - Linear Algebra and its Applications

SN - 0024-3795

ER -