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.
Original languageEnglish
Pages (from-to)881–893
Number of pages13
JournalCzechoslovak Mathematical Journal
Volume66
Issue number3
DOIs
Publication statusPublished - 30 Sep 2016

Keywords

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

Cite this