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.

Please cite this work as:

@article{fasino2016localization,
  title={Localization of dominant eigenpairs and planted communities by means of Frobenius inner products},
  author={Fasino, Dario and Tudisco, Francesco},
  journal={Czechoslovak Mathematical Journal},
  volume={66},
  number={3},
  pages={881--893},
  year={2016},
  publisher={Springer}
}

Keywords: dominant eigenpair cone of matrices spectral clustering community detection modularity matrix graph modularity