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

Dario Fasino; Francesco Tudisco

Czechoslovak Mathematical Journal (2016)

  • Volume: 66, Issue: 3, page 881-893
  • ISSN: 0011-4642

Abstract

top
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.

How to cite

top

Fasino, Dario, and Tudisco, Francesco. "Localization of dominant eigenpairs and planted communities by means of Frobenius inner products." Czechoslovak Mathematical Journal 66.3 (2016): 881-893. <http://eudml.org/doc/286829>.

@article{Fasino2016,
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.},
author = {Fasino, Dario, Tudisco, Francesco},
journal = {Czechoslovak Mathematical Journal},
keywords = {dominant eigenpair; cone of matrices; spectral method; community detection},
language = {eng},
number = {3},
pages = {881-893},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Localization of dominant eigenpairs and planted communities by means of Frobenius inner products},
url = {http://eudml.org/doc/286829},
volume = {66},
year = {2016},
}

TY - JOUR
AU - Fasino, Dario
AU - Tudisco, Francesco
TI - Localization of dominant eigenpairs and planted communities by means of Frobenius inner products
JO - Czechoslovak Mathematical Journal
PY - 2016
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 66
IS - 3
SP - 881
EP - 893
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.
LA - eng
KW - dominant eigenpair; cone of matrices; spectral method; community detection
UR - http://eudml.org/doc/286829
ER -

References

top
  1. Fasino, D., Tudisco, F., 10.1016/j.laa.2015.06.013, Linear Algebra Appl. 502 (2016), 327-345. (2016) Zbl1335.05108MR3490796DOI10.1016/j.laa.2015.06.013
  2. Fiedler, M., Special Matrices and Their Applications in Numerical Mathematics, Martinus Nijhoff Publishers, Dordrecht, 1986, SNTL, Praha (1986). (1986) Zbl0677.65019MR1105955
  3. Fiedler, M., A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czech. Math. J. 25 (1975), 619-633. (1975) Zbl0437.15004MR0387321
  4. Fiedler, M., Algebraic connectivity of graphs, Czech. Math. J. 23 (1973), 298-305. (1973) Zbl0265.05119MR0318007
  5. Nadakuditi, R. R., Newman, M. E. J., 10.1103/PhysRevLett.108.188701, Phys. Rev. Lett. 108 188701, 5 pages (2012). (2012) DOI10.1103/PhysRevLett.108.188701
  6. Newman, M. E. J., Finding community structure in networks using the eigenvectors of matrices, Phys. Rev. E 74 (2006), 036104, 19 pages. (2006) MR2282139
  7. Newman, M. E. J., Girvan, M., 10.1103/PhysRevE.69.026113, Phys. Rev. E 69 026113, 15 pages (2004). (2004) MR2282139DOI10.1103/PhysRevE.69.026113
  8. Nikiforov, V., The influence of Miroslav Fiedler on spectral graph theory, Linear Algebra Appl. 439 (2013), 818-821. (2013) Zbl1282.05145MR3061737
  9. Rohe, K., Chatterjee, S., Yu, B., 10.1214/11-AOS887, Ann. Stat. 39 (2011), 1878-1915. (2011) Zbl1227.62042MR2893856DOI10.1214/11-AOS887
  10. Tarazaga, P., Raydan, M., Hurman, A., Perron-Frobenius theorem for matrices with some negative entries, Linear Algebra Appl. 328 (2001),57-68. (2001) Zbl0989.15008MR1823511
  11. Tarazaga, P., 10.1016/0024-3795(90)90120-2, Linear Algebra Appl. 135 (1990), 171-179. (1990) Zbl0701.15012MR1061534DOI10.1016/0024-3795(90)90120-2

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.