Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
dominant eigenpair; cone of matrices; spectral method; community detection
dominant eigenpair; cone of matrices; spectral method; community detection
Summary:
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.
References:
[1] Fasino, D., Tudisco, F.: Generalized modularity matrices. Linear Algebra Appl. 502 (2016), 327-345. DOI 10.1016/j.laa.2015.06.013 | MR 3490796 | Zbl 1335.05108
[2] Fiedler, M.: Special Matrices and Their Applications in Numerical Mathematics. Martinus Nijhoff Publishers, Dordrecht, 1986, SNTL, Praha (1986). MR 1105955 | Zbl 0677.65019
[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 10.21136/CMJ.1975.101357 | MR 0387321 | Zbl 0437.15004
[4] Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23 (1973), 298-305. DOI 10.21136/CMJ.1973.101168 | MR 0318007 | Zbl 0265.05119
[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 10.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. MR 2282139
[7] Newman, M. E. J., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69 026113, 15 pages (2004). DOI 10.1103/PhysRevE.69.026113 | MR 2282139
[8] Nikiforov, V.: The influence of Miroslav Fiedler on spectral graph theory. Linear Algebra Appl. 439 (2013), 818-821. MR 3061737 | Zbl 1282.05145
[9] Rohe, K., Chatterjee, S., Yu, B.: Spectral clustering and the high-dimensional stochastic blockmodel. Ann. Stat. 39 (2011), 1878-1915. DOI 10.1214/11-AOS887 | MR 2893856 | Zbl 1227.62042
[10] Tarazaga, P., Raydan, M., Hurman, A.: Perron-Frobenius theorem for matrices with some negative entries. Linear Algebra Appl. 328 (2001),57-68. MR 1823511 | Zbl 0989.15008
[11] Tarazaga, P.: Eigenvalue estimates for symmetric matrices. Linear Algebra Appl. 135 (1990), 171-179. DOI 10.1016/0024-3795(90)90120-2 | MR 1061534 | Zbl 0701.15012
Search
Partner of
