Research article Special Issues

Network bipartitioning in the anti-communicability Euclidean space

  • 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.

    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:

  • 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.


    加载中


    [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
  • © 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)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(3633) PDF downloads(122) Cited by(1)

Article outline

Figures and Tables

Figures(10)  /  Tables(1)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog