Network bipartitioning in the anti-communicability Euclidean space

Jesús Gómez-Gardeñes; Ernesto Estrada; Jesús Gómez-Gardeñes; Ernesto Estrada

doi:10.3934/math.2021070

AIMS Mathematics

2021, Volume 6, Issue 2: 1153-1174. doi: 10.3934/math.2021070

Previous Article Next Article

Research article Special Issues

Network bipartitioning in the anti-communicability Euclidean space

Jesús Gómez-Gardeñes ^1,2,
Ernesto Estrada ^{3,4
,
,}

1.
Department of Condensed Matter Physics, Universidad de Zaragoza, 50009 Zaragoza, Spain
2.
GOTHAM lab., Institute for Biocomputation and Physics of Complex Systems (BIFI), Universidad de Zaragoza, 50018 Zaragoza, Spain
3.
Institute of Mathematics and Applications (IUMA), Universidad de Zaragoza, Pedro Cerbuna 12, E-50009 Zaragoza, Spain
4.
ARAID Foundation, Government of Aragon, 50018 Zaragoza, Spain

Received: 14 January 2020 Accepted: 11 June 2020 Published: 11 November 2020
MSC : 05C82, 05C50, 05C69, 68R10

We define the anti-communicability function for the nodes of a simple graph as the nondiagonal entries of exp (-A). We prove that it induces an embedding of the nodes into a Euclidean space. The anti-communicability angle is then defined as the angle spanned by the position vectors of the corresponding nodes in the anti-communicability Euclidean space. We prove analytically that in a given k-partite graph, the anti-communicability angle is larger than 90° for every pair of nodes in different partitions and smaller than 90° for those in the same partition. This angle is then used as a similarity metric to detect the "best" k-partitions in networks where certain level of edge frustration exists. We apply this method to detect the "best" k-partitions in 15 real-world networks, finding partitions with a very low level of "edge frustration". Most of these partitions correspond to bipartitions but tri- and pentapartite structures of real-world networks are also reported.
- network theory,
- complex networks,
- communicability,
- bipartite graphs
Citation: Jesús Gómez-Gardeñes, Ernesto Estrada. Network bipartitioning in the anti-communicability Euclidean space[J]. AIMS Mathematics, 2021, 6(2): 1153-1174. doi: 10.3934/math.2021070

Related Papers:

Abstract

We define the anti-communicability function for the nodes of a simple graph as the nondiagonal entries of exp (-A). We prove that it induces an embedding of the nodes into a Euclidean space. The anti-communicability angle is then defined as the angle spanned by the position vectors of the corresponding nodes in the anti-communicability Euclidean space. We prove analytically that in a given k-partite graph, the anti-communicability angle is larger than 90° for every pair of nodes in different partitions and smaller than 90° for those in the same partition. This angle is then used as a similarity metric to detect the "best" k-partitions in networks where certain level of edge frustration exists. We apply this method to detect the "best" k-partitions in 15 real-world networks, finding partitions with a very low level of "edge frustration". Most of these partitions correspond to bipartitions but tri- and pentapartite structures of real-world networks are also reported.

References

[1]	A. Pothen, Graph Partitioning Algorithms with Applications to Scientific Computing, Technical Report TR-97-03, Old Dominion University, Norfolk, Virginia, 1997.
[2]	D. A. Spielman, S.-H. Teng, Spectral Partitioning Works: Planar Graphs and Finite Element Meshes. In 37th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, New York, New York, (1997), 96-105.
[3]	T. Bui, C. Leland, Finding good approximate vertex and edge partitions is NP-hard, Inform. Proces. Lett., 42 (1992), 153-159. doi: 10.1016/0020-0190(92)90140-Q
[4]	C. J. Alpert, A. B. Kahng, Recent directions in netlist partitioning, Integration, 19 (1995), 1-81. doi: 10.1016/0167-9260(95)00008-4
[5]	B. Kernighan, S. Lin, An effective heuristic algorithm for partitioning graphs, Bell Syst. Tech J., 49 (1972), 291-307.
[6]	R. Battiti, A. Bertossi, Differential Greedy for the 0-1 Equicut Problem. In D. Du and P. Pardalos, Editors, Proceedings of the DIMACS Workshop on Network Design: Connectivity and Facilities Location, Volume 40 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, Providence, Rhode Island, (1998), 3-21.
[7]	H. D. Simon, Partitioning of Unstructured Problems for Parallel Processing, Comput. Syst. Eng., 2 (1991), 135-148. doi: 10.1016/0956-0521(91)90014-V
[8]	B. Hendrickson, R. Leland, An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations, SIAM J. Scient. Comput., 16 (1995), 452-469. doi: 10.1137/0916028
[9]	G. Karypis, V. Kumar, MultilevelGraph Partitioning Schemes. In Proceedings of the Twenty- fourth International Conference on Parallel Processing, Oconomowoc, Wisconsin, (1995), 113-122.
[10]	D. S. Johnson, C. R. Aragon, L. A. McGeoch, C. Schevon, Optimization by Simulated Annealing; Part Ⅰ, Graph Partitioning, Oper. Res., 37 (1989), 865-892. doi: 10.1287/opre.37.6.865
[11]	R. Battiti, A. Bertossi, Greedy, Prohibition, and Reactive Heuristics for Graph- Partitioning, IEEE Trans. Comput., 48 (1997), 361-385.
[12]	T. N. Bui, B. R. Moon, Genetic Algorithm and Graph Partitioning, IEEE Trans. Comput., 45 (1996), 841-855. doi: 10.1109/12.508322
[13]	A. G. Steenbeek, E. Marchiori, A. E. Eiben, Finding Balanced Graph Bi-Partitions Using a Hybrid Genetic Algorithm. In: Proceedings of the IEEE International Conference on Evolutionary Computation ICEC'98, IEEE Press, Piscataway, New Jersey, (1998), 90-95.
[14]	C. Hohn, C. Reeves, Graph Partitioning Using Genetic Algorithms. In Sechi, G. R., Editor, Proceedings of the Second International Conference on Massively Parallel Computing Systems, IEEE Computer Society Press, Piscataway, New Jersey, (1996), 27-43.
[15]	H. Inayoshi, B. Manderick, The Weighted Graph Bi-Partitioning Problem: A Look at GA Performance, Lect. Notes Comput. Sci., 866 (1994), 617-625. doi: 10.1007/3-540-58484-6_304
[16]	G. Laszewski, H. Muhlenbein, Partitioning a Graph with a Parallel Genetic Algorithm, Lect. Notes Comput. Sci., 496 (1991), 165-169. doi: 10.1007/BFb0029748
[17]	J. C. Angles D'Auriac, M. Preissmann, A. Sebő. Optimal Cuts in Graphs and Statistical Mechanics, Math. Comput. Model., 26 (1997), 1-11.
[18]	S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, Optimization by Simulated Annealing, Science, 220 (1983), 671-680. doi: 10.1126/science.220.4598.671
[19]	M. Mezard, G. Parisi, M. A. Virasoro, Spin Glass Theory and Beyond, World Scientific, Singapore, 1987.
[20]	Y. Fu, P. W. Anderson, Application of statistical mechanics to NP-complete problems in combinatorial optimisation, J. Phys. A: Math. Gen., 19 (1986), 1605. doi: 10.1088/0305-4470/19/9/033
[21]	W. Wietheget, D. Sherrington, Bipartitioning of random graphs of fixed extensive valence, J. Phys. A: Math. Gen., 20 (1987), L9-L11.
[22]	W. Liao, Graph-Bipartitioning Problem, Phys. Rev. Lett., 59 (1987), 1625. doi: 10.1103/PhysRevLett.59.1625
[23]	P. Facchi, G. Florio, U. Marzolino, G. Parisi, S. Pascazio, Multipartite entanglement and frustration, New. J. Phys., 12 (2010), 025015. doi: 10.1088/1367-2630/12/2/025015
[24]	E. Estrada, The structure of complex networks: theory and applications, Oxford University Press, 2012.
[25]	M. E. Newman, The structure and function of complex networks, SIAM Rev., 45 (2003), 167-256. doi: 10.1137/S003614450342480
[26]	M. E. Newman, Finding community structure in networks using the eigenvectors of matrices, Phys. Rev. E, 74 (2006), 036104. doi: 10.1103/PhysRevE.74.036104
[27]	A. Concas, S. Noschese, L. Reichel, G. Rodriguez, A spectral method for bipartizing a network and detecting a large anti-community, J. Comput. Appl. Math., (2019), in press.
[28]	M. Zarei, K. A. Samani, Eigenvectors of network complement reveal community structure more accurately, Physica A, 388 (2009), 1721-1730. doi: 10.1016/j.physa.2009.01.007
[29]	Q. Yu, L. Chen, A new method for detecting anti-community structures in complex networks, J. Phys.: Conf. Ser., 410 (2013), 012103. doi: 10.1088/1742-6596/410/1/012103
[30]	L. Chen, Q. Yu, B. Chen, Anti-modularity and anti-community detecting in complex networks, Inform. Sci., 275 (2014), 293-313. doi: 10.1016/j.ins.2014.02.040
[31]	K. N. Bales, Z. D. Eager, A. A. Harkin, Efficiency-modularity for finding communities and anticommunities in networks, J. Complex Net., 5 (2016), 70-83.
[32]	P. Holme, F. Liljeros, C. R. Edling, B. J. Kim, Network bipartivity, Phys. Rev. E, 68 (2003), 056107. doi: 10.1103/PhysRevE.68.056107
[33]	E. Estrada, J. A. Rodriguez-Velazquez, Spectral measures of bipartivity in complex networks, Phys. Rev. E, 72 (2005), 046105. doi: 10.1103/PhysRevE.72.046105
[34]	E. Estrada, J. Gomez-Gardenes, Network bipartivity and the transportation efficiency of european passenger airlines, Physica D, 323 (2016), 57-63.
[35]	T. Pisanski, M. Randić, Use of the Szeged index and the revised Szeged index for measuring network bipartivity, Discr. Appl. Math., 158 (2010), 1936-1944. doi: 10.1016/j.dam.2010.08.004
[36]	E. Estrada, N. Hatano, Communicability in complex networks, Phys. Rev. E, 77 (2008), 036111. doi: 10.1103/PhysRevE.77.036111
[37]	E. Estrada, N. Hatano, Statistical-mechanical approach to subgraph centrality in complex networks, Chem. Phys. Lett., 439 (2007), 247-251. doi: 10.1016/j.cplett.2007.03.098
[38]	E. Estrada, N. Hatano, M. Benzi, The physics of communicability in complex networks, Phys. Rep., 514 (2012), 89-119. doi: 10.1016/j.physrep.2012.01.006
[39]	E. Estrada, The communicability distance in graphs, Lin. Algebra Appl., 436 (2012), 4317-4328. doi: 10.1016/j.laa.2012.01.017
[40]	E. Estrada, Complex networks in the Euclidean space of communicability distances, Phys. Rev. E, 85 (2012), 066122. doi: 10.1103/PhysRevE.85.066122
[41]	E. Estrada, N. Hatano, Communicability angle and the spatial efficiency of networks, SIAM Rev., 58 (2016), 692-715. doi: 10.1137/141000555
[42]	E. Estrada, M. G. Sanchez-Lirola, J. A. de la Pena, Hyperspherical Embedding of Graphs and Networks in Communicability Spaces, Discr. Appl. Math., 176 (2014), 53-77. doi: 10.1016/j.dam.2013.05.032
[43]	M. Pereda, E. Estrada, Visualization and machine learning analysis of complex networks in hyperspherical space, Pattern Recog., 86 (2019), 320-331. doi: 10.1016/j.patcog.2018.09.018
[44]	A. K. Jain, Data clustering: 50 years beyond k-means, Patt. Recog. Lett., 31 (2010), 651-666. doi: 10.1016/j.patrec.2009.09.011
[45]	D. Steinley, K-means clustering: A half-century synthesis, Brit. J. Math. Stat. Psychol., 59 (2006), 1-34. doi: 10.1348/000711005X48266
[46]	M. Halkidi, Y. Batistakis, M. Vazirgiannis, On clustering validation techniques, J. Intel. Inform. Syst., 17 (2001), 107-145. doi: 10.1023/A:1012801612483
[47]	Y. Liu, Z. Li, H. Xiong, X. Gao, J. Wu, Understanding of internal clustering validation measures. In: 2010 IEEE International Conference on Data Mining, IEEE, (2010), 911-916.
[48]	T. Calinski, J. Harabasz, A dendrite method for cluster analysis, Commu. Stat. Theor. Meth., 3 (1974), 1-27. doi: 10.1080/03610927408827109
[49]	P. J. Rousseeuw, Silhouettes: A graphical aid to the interpretation and validation of cluster analysis, J. Comput. Appl. Math., 20 (1987), 53-65. doi: 10.1016/0377-0427(87)90125-7
[50]	D. L. Davies, D. W. Bouldin, A cluster separation measure, IEEE Trans. Patt. Anal. Mach. Intel., 2 (1979), 224-227.
[51]	D. Aloise, A. Deshpande, P. Hansen, P. Popat, NP-hardness of Euclidean sum-of-squares clustering, Mach. Learn., 75 (2009), 245-249. doi: 10.1007/s10994-009-5103-0

Reader Comments

Your name:*

Email:*
© 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)