| Title:
|
Localization of dominant eigenpairs and planted communities by means of Frobenius inner products (English) |
| Author:
|
Fasino, Dario |
| Author:
|
Tudisco, Francesco |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
66 |
| Issue:
|
3 |
| Year:
|
2016 |
| Pages:
|
881-893 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
dominant eigenpair |
| Keyword:
|
cone of matrices |
| Keyword:
|
spectral method |
| Keyword:
|
community detection |
| MSC:
|
15A18 |
| MSC:
|
15B48 |
| idZBL:
|
Zbl 06644039 |
| idMR:
|
MR3556873 |
| DOI:
|
10.1007/s10587-016-0298-2 |
| . |
| Date available:
|
2016-10-01T15:31:56Z |
| Last updated:
|
2023-10-28 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/145877 |
| . |
| Reference:
|
[1] Fasino, D., Tudisco, F.: Generalized modularity matrices.Linear Algebra Appl. 502 (2016), 327-345. Zbl 1335.05108, MR 3490796, 10.1016/j.laa.2015.06.013 |
| Reference:
|
[2] Fiedler, M.: Special Matrices and Their Applications in Numerical Mathematics.Martinus Nijhoff Publishers, Dordrecht, 1986, SNTL, Praha (1986). Zbl 0677.65019, MR 1105955 |
| Reference:
|
[3] Fiedler, M.: A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory.Czech. Math. J. 25 (1975), 619-633. Zbl 0437.15004, MR 0387321, 10.21136/CMJ.1975.101357 |
| Reference:
|
[4] Fiedler, M.: Algebraic connectivity of graphs.Czech. Math. J. 23 (1973), 298-305. Zbl 0265.05119, MR 0318007, 10.21136/CMJ.1973.101168 |
| Reference:
|
[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). 10.1103/PhysRevLett.108.188701 |
| Reference:
|
[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 |
| Reference:
|
[7] Newman, M. E. J., Girvan, M.: Finding and evaluating community structure in networks.Phys. Rev. E 69 026113, 15 pages (2004). MR 2282139, 10.1103/PhysRevE.69.026113 |
| Reference:
|
[8] Nikiforov, V.: The influence of Miroslav Fiedler on spectral graph theory.Linear Algebra Appl. 439 (2013), 818-821. Zbl 1282.05145, MR 3061737 |
| Reference:
|
[9] Rohe, K., Chatterjee, S., Yu, B.: Spectral clustering and the high-dimensional stochastic blockmodel.Ann. Stat. 39 (2011), 1878-1915. Zbl 1227.62042, MR 2893856, 10.1214/11-AOS887 |
| Reference:
|
[10] Tarazaga, P., Raydan, M., Hurman, A.: Perron-Frobenius theorem for matrices with some negative entries.Linear Algebra Appl. 328 (2001),57-68. Zbl 0989.15008, MR 1823511 |
| Reference:
|
[11] Tarazaga, P.: Eigenvalue estimates for symmetric matrices.Linear Algebra Appl. 135 (1990), 171-179. Zbl 0701.15012, MR 1061534, 10.1016/0024-3795(90)90120-2 |
| . |
