Localization of dominant eigenpairs and planted communities by means of Frobenius inner products

Dario Fasino, Francesco Tudisco

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

We propose a new localization result for the leading eigenvalue and eigenvector of a symmetric matrix A. The result exploits the Frobenius inner product between A and a given rank-one landmark matrix X. Different choices for X may be used, depending on the problem under investigation. In particular, we show that the choice where X is the all-ones matrix allows to estimate the signature of the leading eigenvector of A, generalizing previous results on Perron-Frobenius properties of matrices with some negative entries. As another application we consider the problem of community detection in graphs and networks. The problem is solved by means of modularity-based spectral techniques, following the ideas pioneered by Miroslav Fiedler in mid-’70s.

We show that a suitable choice of X can be used to provide new quality guarantees of those techniques, when the network follows a stochastic block model.
LanguageEnglish
Pages881–893
Number of pages13
JournalCzechoslovak Mathematical Journal
Volume66
Issue number3
DOIs
Publication statusPublished - 30 Sep 2016

Fingerprint

Frobenius
Scalar, inner or dot product
Perron-Frobenius
Community Detection
Eigenvalues and Eigenvectors
Landmarks
Modularity
Symmetric matrix
Eigenvector
Signature
Graph in graph theory
Estimate
Community
Model

Keywords

  • dominant eigenpair
  • cone of matrices
  • spectral method
  • community detection

Cite this

@article{e8a3e2aac29b41de88070f06dc298201,
title = "Localization of dominant eigenpairs and planted communities by means of Frobenius inner products",
abstract = "We propose a new localization result for the leading eigenvalue and eigenvector of a symmetric matrix A. The result exploits the Frobenius inner product between A and a given rank-one landmark matrix X. Different choices for X may be used, depending on the problem under investigation. In particular, we show that the choice where X is the all-ones matrix allows to estimate the signature of the leading eigenvector of A, generalizing previous results on Perron-Frobenius properties of matrices with some negative entries. As another application we consider the problem of community detection in graphs and networks. The problem is solved by means of modularity-based spectral techniques, following the ideas pioneered by Miroslav Fiedler in mid-’70s.We show that a suitable choice of X can be used to provide new quality guarantees of those techniques, when the network follows a stochastic block model.",
keywords = "dominant eigenpair, cone of matrices, spectral method, community detection",
author = "Dario Fasino and Francesco Tudisco",
year = "2016",
month = "9",
day = "30",
doi = "10.1007/s10587-016-0298-2",
language = "English",
volume = "66",
pages = "881–893",
journal = "Czechoslovak Mathematical Journal",
issn = "0011-4642",
publisher = "Springer",
number = "3",

}

Localization of dominant eigenpairs and planted communities by means of Frobenius inner products. / Fasino, Dario; Tudisco, Francesco.

In: Czechoslovak Mathematical Journal, Vol. 66, No. 3, 30.09.2016, p. 881–893.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Localization of dominant eigenpairs and planted communities by means of Frobenius inner products

AU - Fasino, Dario

AU - Tudisco, Francesco

PY - 2016/9/30

Y1 - 2016/9/30

N2 - We propose a new localization result for the leading eigenvalue and eigenvector of a symmetric matrix A. The result exploits the Frobenius inner product between A and a given rank-one landmark matrix X. Different choices for X may be used, depending on the problem under investigation. In particular, we show that the choice where X is the all-ones matrix allows to estimate the signature of the leading eigenvector of A, generalizing previous results on Perron-Frobenius properties of matrices with some negative entries. As another application we consider the problem of community detection in graphs and networks. The problem is solved by means of modularity-based spectral techniques, following the ideas pioneered by Miroslav Fiedler in mid-’70s.We show that a suitable choice of X can be used to provide new quality guarantees of those techniques, when the network follows a stochastic block model.

AB - We propose a new localization result for the leading eigenvalue and eigenvector of a symmetric matrix A. The result exploits the Frobenius inner product between A and a given rank-one landmark matrix X. Different choices for X may be used, depending on the problem under investigation. In particular, we show that the choice where X is the all-ones matrix allows to estimate the signature of the leading eigenvector of A, generalizing previous results on Perron-Frobenius properties of matrices with some negative entries. As another application we consider the problem of community detection in graphs and networks. The problem is solved by means of modularity-based spectral techniques, following the ideas pioneered by Miroslav Fiedler in mid-’70s.We show that a suitable choice of X can be used to provide new quality guarantees of those techniques, when the network follows a stochastic block model.

KW - dominant eigenpair

KW - cone of matrices

KW - spectral method

KW - community detection

U2 - 10.1007/s10587-016-0298-2

DO - 10.1007/s10587-016-0298-2

M3 - Article

VL - 66

SP - 881

EP - 893

JO - Czechoslovak Mathematical Journal

T2 - Czechoslovak Mathematical Journal

JF - Czechoslovak Mathematical Journal

SN - 0011-4642

IS - 3

ER -