Framework based on communicability to measure the similarity of nodes in complex networks. (English) Zbl 1457.05102
Summary: The structural properties of network system components often display strikingly similar behavior when probed at a macroscopic perspective. Those structural properties, largely determining their dynamic behavior, are revealed by the mesoscopic structure of the underlying networks. To demonstrate this empirical conclusion, it is necessary to develop a set of tools to accurately quantify the structural similarity between network nodes. In this paper, we propose a method to measure nodes’ similarity based on network communicability. Precisely, the approach takes Jensen-Shannon divergence between the communicability sequences of nodes as the difference measure and then obtains the similarity between nodes. We use some real-world networks and artificial networks as test objects, and evaluate the rationality of the method through the topological structure behavior and dynamical behavior of similar nodes respectively. Interestingly, the similar nodes obtained in our framework have very similar dynamical behaviors, which is crucial because the dynamic behaviors of nodes are highly dependent on the mesoscopic structure of the underlying networks. Furthermore, compared with previous methods, the method presented in this paper can more accurately quantify the similarity between nodes from a global perspective.
MSC:
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 94A17 | Measures of information, entropy |
References:
| [1] | Arenas, A.; Díaz-Guilera, A.; Kurths, J.; Moreno, Y.; Zhou, C., Synchronization in complex networks, Phys. Rep., 469, 93-153 (2008) |
| [2] | Ahajjam, S.; Haddad, M. E.; Badir, H., A new scalable leader-community detection approach for community detection in social networks, Soc. Netw., 54, 41-49 (2018) |
| [3] | Barabási, A.-L.; Albert, R., Emergence of scaling in random networks, Science, 286, 509-512 (1999) · Zbl 1226.05223 |
| [4] | Barthélemy, M.; Barrat, A.; Pastor-Satorras, R.; Vespignani, A., Dynamical patterns of epidemic outbreaks in complex heterogeneous networks, J. Theor. Biol., 235, 275-288 (2005) · Zbl 1445.92262 |
| [5] | Boccaletti, S.; Latora, V.; Moreno, Y.; Chavez, M.; Hwang, D. U., Complex networks: structure and dynamics, Phys. Rep., 424, 175-308 (2006) · Zbl 1371.82002 |
| [6] | Barabási, A. L., Network Science (2016), Cambridge University Press · Zbl 1353.94001 |
| [7] | Bu, Z.; Wang, Y. Y.; Li, H.-J.; Jiang, J. C.; Wu, Z. A.; Cao, J., Link prediction in temporal networks: integrating survival analysis and game theory, Inf. Sci., 498, 41-61 (2019) · Zbl 1454.91155 |
| [8] | Colizza, V.; Pastor-Satorras, R.; Vespignani, A., Reaction-diffusion processes and metapopulation models in heterogeneous networks, Nat. Phys., 3, 276-282 (2007) |
| [9] | Cohen, R.; Havlin, S., Complex Networks: Structure, Robustness and Function (2010), Cambridge University Press · Zbl 1196.05092 |
| [10] | Chen, D. B.; Lü, L. Y.; Shang, M.-S.; Zhang, Y.-C.; Zhou, T., Identifying influential nodes in complex networks, Physica A, 391, 1777-1787 (2012) |
| [11] | Chen, D.; Shi, D.-D.; Qin, M.; Xu, . S.-M.; Pan, G.-J., Complex network comparison based on communicability sequence entropy, Phys. Rev. E, 98, 1, 12319 (2018) |
| [12] | Chen, D.; Niu, R.-W.; Pan, G.-J., Correlations between communicability sequence entropy and transport performance in spatially embedded networks, Phys. Rev. E, 99, 6, 62310 (2019) |
| [13] | Cristian, V.; Suciu, G.; Pasat, A., A new method to help the human resources staff to find the right candidates, based on deep learning, eLearn. Softw. Educ., 3, 240-246 (2019) |
| [14] | De Domenico, M.; Biamonte, J., Spectral entropies as information-theoretic tools for complex network comparison, Phys. Rev. X, 6, 4, 041062 (2016) |
| [15] | IEEE |
| [16] | Estrada, E.; Hatano, N., Communicability in complex networks, Phys. Rev. E, 77, 3, 036111 (2008) |
| [17] | Estrada, E.; Hatano, N.; Benzi, M., The physics of communicability in complex networks, Phys. Rep., 514, 89-119 (2012) |
| [18] | Gleiser, P.; Danon, L., Community structure in jazz, Adv. Complex Syst., 6, 565-573 (2003) |
| [19] | Gómez, S.; Díaz-Guilera, A.; Gómez-Gardeńes, J.; Pérez-Vicente, C. J.; Moreno, Y.; Arenas, A., Diffusion dynamics on multiplex networks, Phys. Rev. Lett., 110, 2, 028701 (2013) |
| [20] | García-Pérez, G.; M. Boguná, M.; Serrano, A., Multiscale unfolding of real networks by geometric renormalization, Nat. Phys., 14, 583-589 (2018) |
| [21] | Katz, L., A new status index derived from sociometric analysis, Psychometrika, 18, 39-43 (1953) · Zbl 0053.27606 |
| [22] | Kleinberg, J. M., Navigation in a small world, Nature, 406, 845 (2000) |
| [23] | p. 7 |
| [24] | Lorrain, F.; White, H. C., Structural equivalence of individuals in social networks, J. Math. Sociol., 1, 49-80 (1971) |
| [25] | Lamberti, P. W.; Majtey, A. P.; Borras, A.; Casas, M.; Plastino, A., Metric character of the quantum Jensen-Shannon divergence, Phys. Rev. A, 77, 5, 052311 (2008) |
| [26] | Lü, L. Y.; Jin, C.-H.; Zhou, T., Similarity index based on local paths for link prediction of complex networks, Phys. Rev. E, 80, 4, 046122 (2009) |
| [27] | Li, G.; Reis, S. D.S.; Moreira, A. A.; Havlin, S.; Stanley, H. E.; Andrade, J. S., Towards design principles for optimal transport networks, Phys. Rev. Lett., 104, 1, 018701 (2010) |
| [28] | Liu, W. P.; Lü, L. Y., Link prediction based on local random walk, Epl, 89, 58007 (2010) |
| [29] | Newman, M. E.J., Finding community structure in networks using the eigenvectors of matrices, Phys. Rev. E, 74, 3, 036104 (2006) |
| [30] | Nicosia, V.; Valencia, M.; Chavez, M.; Díaz-Guilera, A.; Latora, V., Remote synchronization reveals network symmetries and functional modules, Phys. Rev. Lett., 110, 17, 174102 (2013) |
| [31] | Oliveira, C. L.N.; Morais, P. A.; Moreira, A. A.; Andrade, J. S., Enhanced flow in small-world networks, Phys. Rev. Lett., 112, 14, 148701 (2014) |
| [32] | Pastor-Satorras, R.; Vespignani, A., Epidemic spreading in scale-free networks, Phys. Rev. Lett., 86, 14, 3200 (2001) |
| [33] | Perra, N.; Fortunato, S., Spectral centrality measures in complex networks, Phys. Rev. E, 78, 3, 036107 (2008) |
| [34] | Pecora, L. M.; Sorrentino, F.; Hagerstrom, A. M.; Murphy, T. E.; Roy, R., Cluster synchronization and isolated desynchronization in complex networks with symmetries, Nat. Commun., 5, 4079 (2014) |
| [35] | Roberson, M. R.; ben Avraham, D., Kleinberg navigation in fractal small-world networks, Phys. Rev. E, 74, 1, 017101 (2006) |
| [36] | Salton, G., Automatic text analysis, Science, 168, 335-343 (1970) |
| [37] | Song, C. M.; Havlin, S.; Makse, H. A., Self-similarity of complex networks, Nature, 433, 392-395 (2005) |
| [38] | Serrano, M. A.; Krioukov, D.; Boguná, M., Self-similarity of complex networks and hidden metric spaces, Phys. Rev. Lett., 100, 7, 078701 (2008) |
| [39] | Serrano, M. A.; Boguná, M.; Sagues, F., Uncovering the hidden geometry behind metabolic networks, Mol. BioSyst., 8, 843-850 (2012) |
| [40] | Skardal, P. S.; Taylor, D.; Sun, J., Optimal synchronization of complex networks, Phys. Rev. Lett., 113, 14, 144101 (2014) |
| [41] | Sun, P. G., Controllability and modularity of complex networks, Inf. Sci., 325, 20-32 (2015) · Zbl 1395.90050 |
| [42] | Schieber, T. A.; Carpi, L.; Diaz-Guilera, A.; Pardalos, P. M.; Masoller, C.; Ravetti, M. G., Quantification of network structural dissimilarities, Nat. Commun., 8, 13928 (2017) |
| [43] | Tang, Y.-N.; Xiang, J.; Gao, Y.-Y.; Wang, Z.-Z.; Li, H.-J.; Chen, S.; Zhang, Y.; Li, J.-M.; Tang, Y.-H.; Chen, Y. J., An effective algorithm for optimizing surprise in network community detection, IEEE Access, 7, 148814-148827 (2019) |
| [44] | van Erven, T.; Harremoës, P., Rényi divergence and Kullback-Leibler divergence, IEEE Trans. Inf. Theory, 60, 3797-3820 (2014) · Zbl 1360.94180 |
| [45] | Watts, D. J.; Strogatz, S. H., Collective dynamics of ‘small-world’ networks, Nature, 393, 440-442 (1998) · Zbl 1368.05139 |
| [46] | Whalen, A. J.; Brennan, S. N.; Sauer, T. D.; Schiff, S. J., Observability and controllability of nonlinear networks: the role of symmetry, Phys. Rev. X, 5, 1, 11005 (2015) |
| [47] | Xing, W.; Shi, P.; Song, H. Y.; Zhao, Y. X.; Li, L. Y., Global pinning synchronization of stochastic delayed complex networks, Inf. Sci., 490, 113-125 (2019) · Zbl 1454.93094 |
| [48] | Zachary, W. W., An information flow model for conflict and fission in small groups1, J. Anthropol. Res., 33, 452-473 (1977) |
| [49] | Zhang, Q.; Li, M. Z.; Deng, Y., Measure the structure similarity of nodes in complex networks based on relative entropy, Physica A, 491, 749-763 (2018) · Zbl 1514.05166 |
| [50] | Zareie, A.; Sheikhahmadi, A.; Jalili, M., Identification of influential users in social networks based on users’ interest, Inf. Sci., 493, 217-231 (2019) · Zbl 1451.91158 |
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.
