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

preprint2016arXivOpen access

Abstract

We propose a new localization result for the leading eigenvalue and eigenvector of a symmetric matrix AA. The result exploits the Frobenius inner product between AA and a given rank-one landmark matrix XX. Different choices for XX may be used, depending upon the problem under investigation. In particular, we show that the choice where XX is the all-ones matrix allows to estimate the signature of the leading eigenvector of AA, 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 XX can be used to provide new quality guarantees of those techniques, when the network follows a stochastic block model.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.