Geodesic
Localization of dominant eigenpairs and planted communities by means of Frobenius inner products
Czechoslovak Mathematical Journal, Tome 66 (2016) no. 3, pp. 881-893
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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. \endgraf 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.
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. \endgraf 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.
DOI : 10.1007/s10587-016-0298-2
Classification : 15A18, 15B48
Keywords: dominant eigenpair; cone of matrices; spectral method; community detection 
@article{10_1007_s10587_016_0298_2,
     author = {Fasino, Dario and Tudisco, Francesco},
     title = {Localization of dominant eigenpairs and planted communities by means of {Frobenius} inner products},
     journal = {Czechoslovak Mathematical Journal},
     pages = {881--893},
     year = {2016},
     volume = {66},
     number = {3},
     doi = {10.1007/s10587-016-0298-2},
     mrnumber = {3556873},
     zbl = {06644039},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0298-2/}
}
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
SP  - 881
EP  - 893
VL  - 66
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0298-2/
DO  - 10.1007/s10587-016-0298-2
LA  - en
ID  - 10_1007_s10587_016_0298_2
ER  - 
%0 Journal Article
%A Fasino, Dario
%A Tudisco, Francesco
%T Localization of dominant eigenpairs and planted communities by means of Frobenius inner products
%J Czechoslovak Mathematical Journal
%D 2016
%P 881-893
%V 66
%N 3
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0298-2/
%R 10.1007/s10587-016-0298-2
%G en
%F 10_1007_s10587_016_0298_2
Fasino, Dario; Tudisco, Francesco. Localization of dominant eigenpairs and planted communities by means of Frobenius inner products. Czechoslovak Mathematical Journal, Tome 66 (2016) no. 3, pp. 881-893. doi: 10.1007/s10587-016-0298-2

[1] Fasino, D., Tudisco, F.: Generalized modularity matrices. Linear Algebra Appl. 502 (2016), 327-345. | DOI | MR | Zbl

[2] Fiedler, M.: Special Matrices and Their Applications in Numerical Mathematics. Martinus Nijhoff Publishers, Dordrecht, 1986, SNTL, Praha (1986). | MR | Zbl

[3] Fiedler, M.: A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czech. Math. J. 25 (1975), 619-633. | DOI | MR | Zbl

[4] Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23 (1973), 298-305. | DOI | MR | Zbl

[5] Nadakuditi, R. R., Newman, M. E. J.: Graph spectra and the detectability of community structure in networks. Phys. Rev. Lett. 108 188701, 5 pages (2012). | DOI

[6] Newman, M. E. J.: Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E 74 (2006), 036104, 19 pages. | MR

[7] Newman, M. E. J., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69 026113, 15 pages (2004). | DOI | MR

[8] Nikiforov, V.: The influence of Miroslav Fiedler on spectral graph theory. Linear Algebra Appl. 439 (2013), 818-821. | MR | Zbl

[9] Rohe, K., Chatterjee, S., Yu, B.: Spectral clustering and the high-dimensional stochastic blockmodel. Ann. Stat. 39 (2011), 1878-1915. | DOI | MR | Zbl

[10] Tarazaga, P., Raydan, M., Hurman, A.: Perron-Frobenius theorem for matrices with some negative entries. Linear Algebra Appl. 328 (2001),57-68. | MR | Zbl

[11] Tarazaga, P.: Eigenvalue estimates for symmetric matrices. Linear Algebra Appl. 135 (1990), 171-179. | DOI | MR | Zbl

Cité par Sources :