A spectral method for bipartizing a network and detecting a large anti-community. (English) Zbl 1434.90037
Summary: Relations between discrete quantities such as people, genes, or streets can be described by networks, which consist of nodes that are connected by edges. Network analysis aims to identify important nodes in a network and to uncover structural properties of a network. A network is said to be bipartite if its nodes can be subdivided into two nonempty sets such that there are no edges between nodes in the same set. It is a difficult task to determine the closest bipartite network to a given network. This paper describes how a given network can be approximated by a bipartite one by solving a sequence of fairly simple optimization problems. The algorithm also produces a node permutation which makes the possible bipartite nature of the initial adjacency matrix evident, and identifies the two sets of nodes. We finally show how the same procedure can be used to detect the presence of a large anti-community in a network and to identify it.
MSC:
| 90B10 | Deterministic network models in operations research |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
References:
| [1] | Estrada, E., The Structure of Complex Networks: Theory and Applications (2011), Oxford University Press: Oxford University Press Oxford |
| [2] | Newman, M. E.J., Networks: An Introduction (2010), Oxford University Press: Oxford University Press Oxford · Zbl 1195.94003 |
| [3] | Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), Macmillan: Macmillan London · Zbl 1226.05083 |
| [4] | Yannakakis, M., Edge-deletion problems, SIAM J. Comput., 10, 297-309 (1981) · Zbl 0468.05043 |
| [5] | Estrada, E.; Gómez-Gardeñes, J., Network bipartivity and the transportation efficiency of European passenger airlines, Physica D, 323-324, 57-63 (2016) · Zbl 1364.90041 |
| [6] | Roth, R., On the eigenvectors belonging to the minimum eigenvalue of an essentially nonnegative symmetric matrix with bipartite graph, Linear Algebra Appl., 118, 1-10 (1989) · Zbl 0668.15005 |
| [7] | 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) |
| [8] | 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 |
| [9] | Estrada, E.; Knight, P. A., A First Course in Network Theory (2015), Oxford University Press: Oxford University Press Oxford · Zbl 1360.90046 |
| [10] | Fasino, D.; Tudisco, F., A modularity based spectral method for simultaneous community and anti-community detection, Linear Algebra Appl., 542, 605-623 (2017) · Zbl 1418.05086 |
| [11] | Chen, L.; Yu, Q.; Chen, B., Anti-modularity and anti-community detecting in complex networks, Inform. Sci., 275, 293-313 (2014) · Zbl 1341.05234 |
| [12] | Leskovec, J.; Lang, K. J.; Dasgupta, A.; Mahoney, M. W., Statistical properties of community structure in large social and information networks, (Proc. 17th Int. Conf. World Wide Web (WWW’08) (2008)), 695-704 |
| [13] | Palla, G.; Derènyi, I.; Farkas, I.; Vicsek, T., Uncovering the overlapping community structure of complex networks in nature and society, Nature, 435, 814-818 (2005) |
| [14] | Raghavan, U. N.; Albert, R.; Kumara, S., Near linear time algorithm to detect community structures in large-scale networks, Phys. Rev. E, 76, Article 036106 pp. (2007) |
| [15] | Yang, B.; Cheung, W. K.; Liu, J. M., Community mining from signed social networks, IEEE Trans. Knowl. Data Eng., 19, 1333-1348 (2007) |
| [16] | Borgatti, S. P.; Everett, M. G., Models of core/periphery structures, Social Networks, 21, 375-395 (1999) |
| [17] | Rombach, M. P.; Porter, M. A.; Fowler, J. H.; Mucha, P. J., Core-periphery structure in networks, SIAM Rev., 59, 619-646 (2017) · Zbl 1368.62170 |
| [18] | Bapat, R. B., Graphs and Matrices (2010), Springer: Springer London · Zbl 1215.05028 |
| [19] | Golub, G. H.; Van Loan, C. F., Matrix Computations (2013), Johns Hopkins University Press: Johns Hopkins University Press Baltimore · Zbl 1268.65037 |
| [20] | Higham, N., Matrix nearness problems and applications, (Gover, M. J.C.; Barnett, S., Applications of Matrix Theory (1989), Oxford University Press: Oxford University Press Oxford), 1-27 · Zbl 0681.65029 |
| [21] | D. Gleich, MatlabBGL - A Matlab Graph Library, https://www.cs.purdue.edu/homes/dgleich/packages/matlab_bgl/. |
| [22] | Jeong, H.; Mason, S.; Barabási, A.-L.; Oltvai, Z. N., Lethality and centrality in protein networks, Nature, 411, 41-42 (2001) |
| [23] | V. Batagelj, A. Mrvar, Pajek data sets (2006). Available at http://vlado.fmf.uni-lj.si/pub/networks/data/. · Zbl 1054.68564 |
| [24] | Concas, A.; Fenu, C.; Rodriguez, G., PQser: A Matlab package for spectral seriation, Numer. Algorithms, 80, 879-902 (2019) · Zbl 1409.65117 |
| [25] | Sun, S.; Ling, L.; Zhang, N.; Li, G.; Chen, R., Topological structure analysis of the protein-protein interaction network in budding yeast, Nucleic Acids Res., 31, 2443-2450 (2003) |
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.
