A modularity based spectral method for simultaneous community and anti-community detection. (English) Zbl 1418.05086
Summary: In a graph or complex network, communities and anti-communities are node sets whose modularity attains extremely large values, positive and negative, respectively. We consider the simultaneous detection of communities and anti-communities, by looking at spectral methods based on various matrix-based definitions of the modularity of a vertex set. Invariant subspaces associated to extreme eigenvalues of these matrices provide indications on the presence of both kinds of modular structure in the network. The localization of the relevant invariant subspaces can be estimated by looking at particular matrix angles based on Frobenius inner products.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 15A42 | Inequalities involving eigenvalues and eigenvectors |
| 15B99 | Special matrices |
Software:
SparseMatrixReferences:
| [1] | Bolla, M., Penalized versions of the Newman-Girvan modularity and their relation to normalized cuts and K-means clustering, Phys. Rev. E, 84, Article 016108 pp. (2011) |
| [2] | Chaudhuri, K.; Chung, F.; Tsiatas, A., Spectral clustering of graphs with general degrees in the extended planted partition model, (Conference on Learning Theory. Conference on Learning Theory, COLT. Conference on Learning Theory. Conference on Learning Theory, COLT, JMLR: Workshop and Conference Proceedings, vol. 23 (2012)), 35:1-35:23 |
| [3] | Chen, L.; Yu, Q.; Chen, B., Anti-modularity and anti-community detecting in complex networks, Inform. Sci., 275, 293-313 (2014) · Zbl 1341.05234 |
| [4] | Chung, F.; Lu, L., Complex Graphs and Networks, CBMS Reg. Conf. Ser. Math., vol. 107 (2006), AMS · Zbl 1114.90071 |
| [5] | Davis, T. A.; Hu, Y., The University of Florida sparse matrix collection, ACM Trans. Math. Software, 38, 1 (2011) · Zbl 1365.65123 |
| [6] | Estrada, D. J.; Higham, E.; Hatano, N., Communicability and multipartite structures in complex networks at negative absolute temperatures, Phys. Rev. E, 78, Article 026102 pp. (2008) |
| [7] | Fasino, D.; Tudisco, F., An algebraic analysis of the graph modularity, SIAM J. Matrix Anal. Appl., 35, 997-1018 (2014) · Zbl 1304.05110 |
| [8] | Fasino, D.; Tudisco, F., Generalized modularity matrices, Linear Algebra Appl., 502, 327-345 (2016) · Zbl 1335.05108 |
| [9] | Fasino, D.; Tudisco, F., Localization of dominant eigenpairs and planted communities by means of Frobenius inner products, Czechoslovak Math. J., 66, 881-893 (2016) · Zbl 1413.15016 |
| [10] | Fortunato, S.; Barthelemy, M., Resolution limit in community detection, Proc. Nat. Acad. Sci., 104, 36-41 (2007) |
| [11] | Friedland, S.; Hershkowitz, D.; Schneider, H., Matrices whose powers are M-matrices or Z-matrices, Trans. Amer. Math. Soc., 300, 343-366 (1987) · Zbl 0619.15018 |
| [12] | Garfield, E.; Pudovkin, A. I., The HistCite system for mapping and bibliometric analysis of the output of searches using the ISI Web of Knowledge, (Proceedings of the 67th Annual Meeting of the American Society for Information Science and Technology (2004)), 12-17 |
| [13] | Golub, G. H.; Van Loan, C. F., Matrix Computations, Johns Hopkins Studies in the Mathematical Sciences (2013), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD · Zbl 1268.65037 |
| [14] | Holme, P.; Liljeros, F.; Edling, C. R.; Kim, B. J., Network bipartivity, Phys. Rev. E, 68, Article 056107 pp. (2003) |
| [15] | Karrer, B.; Newman, M. E.J., Stochastic blockmodels and community structure in networks, Phys. Rev. E, 83, 1, Article 016107 pp. (2011) |
| [16] | Mercado, P.; Tudisco, F.; Hein, M., Clustering signed networks with the geometric mean of Laplacians, (Advances in Neural Information Processing Systems. Advances in Neural Information Processing Systems, NIPS (2016)), 4421-4429 |
| [17] | Morrison, J. L.; Breitling, R.; Higham, D. J.; Gilbert, D. R., A lock-and-key model for protein – protein interactions, Bioinformatics, 2, 2012-2019 (2006) |
| [18] | Newman, M. E.J., Finding community structure in networks using the eigenvectors of matrices, Phys. Rev. E, 74, Article 036104 pp. (2006) |
| [19] | Newman, M. E.J.; Girvan, M., Finding and evaluating community structure in networks, Phys. Rev. E, 69, Article 026113 pp. (2004) |
| [20] | Qin, T.; Rohe, K., Regularized spectral clustering under the degree-corrected stochastic blockmodel, (Advances in Neural Information Processing Systems. Advances in Neural Information Processing Systems, NIPS, vol. 26 (2013)), 3120-3128 |
| [21] | Stewart, G. W.; Sun, J. G., Matrix Perturbation Theory, Computer Science and Scientific Computing (1990), Academic Press, Inc.: Academic Press, Inc. Boston, MA · Zbl 0706.65013 |
| [22] | Taylor, A.; Vass, J. K.; Higham, D. J., Discovering bipartite substructure in directed networks, LMS J. Comput. Math., 14, 72-86 (2011) · Zbl 1223.68087 |
| [23] | Traag, V. A.; Van Dooren, P.; Nesterov, Y., Narrow scope for resolution-limit-free community detection, Phys. Rev. E, 84, Article 016114 pp. (2011) |
| [24] | Travers, J.; Milgram, S., The small world problem, Psychol. Today, 1, 61-67 (1967) |
| [25] | Tudisco, F.; Mercado, P.; Hein, M., Community detection via nonlinear modularity eigenvectors (2017) |
| [26] | White, S.; Smyth, P., A spectral clustering approach to finding communities in graphs, (Proceedings of the 2005 SIAM International Conference on Data Mining (2005)), 76-84 |
| [27] | Wuchty, S.; Uetz, P., Protein – protein interaction networks of E. Coli and S. Cerevisiae are similar, Sci. Rep., 4, 7187 (2014) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
