Comparing large-scale graphs based on quantum probability theory. (English) Zbl 1428.05186
Summary: In this paper, a new measurement to compare two large-scale graphs based on the theory of quantum probability is proposed. An explicit form for the spectral distribution of the corresponding adjacency matrix of a graph is established. Our proposed distance between two graphs is defined as the distance between the corresponding moment matrices of their spectral distributions. It is shown that the spectral distributions of their adjacency matrices in a vector state includes information not only about their eigenvalues, but also about the corresponding eigenvectors. Moreover, we prove that the proposed distance is graph invariant and sub-structure invariant. Examples with various graphs are given, and distances between graphs with few vertices are checked. Computational results for real large-scale graphs show that its accuracy is better than any existing methods and time cost is extensively cheap.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 81P45 | Quantum information, communication, networks (quantum-theoretic aspects) |
References:
| [1] | Abdollahi, A.; Janbaz, S.; Oboudi, M. R., Distance between spectra of graphs, Linear Algebra Appl., 466, 401-408 (2015) · Zbl 1303.05110 |
| [2] | Ali, W.; Wegner, A. E.; Gaunt, R. E.; Deane, C. M.; Reinert, G., Comparison of large networks with sub-sampling strategies, Scie. Rep., 6, 38955 (2016) |
| [3] | Basak, S. C.; Magnuson, V. R.; Niemi, G. J.; Regal, R. R., Determining structural similarity of chemicals using graph-theoretic indices, Discrete Appl. Math., 19, 1-3, 17-44 (1988) |
| [4] | Berg, C.; Szwarc, R., A determinant characterization of moment sequences with finitely many mass points, Linear Multilinear Algebra, 63, 8, 1568-1576 (2015) · Zbl 1332.44004 |
| [5] | Butler, S., A note about cospectral graphs for the adjacency and normalized Laplacian matrices, Linear Multilinear Algebra, 58, 3-4, 387-390 (2010) · Zbl 1187.05046 |
| [6] | Calderone, A.; Formenti, M.; Aprea, F.; Papa, M.; Alberghina, L.; Colangelo, A. M.; Bertolazzi, P., Comparing alzheimer’s and parkinson’s diseases networks using graph communities structure, BMC Syst. Biol., 10, 1, 25-34 (2016) |
| [7] | Chen, X.; Qian, J., Bounds on the number of closed walks in a graph and its applications, J. Inequal. Appl., 2014:199,9 (2014) · Zbl 1371.05161 |
| [8] | Chung, J. K.; Kannappan, P.; Ng, C. T.; Sahoo, P. K., Measures of distance between probability distributions, J. Math. Anal. Appl., 138, 1, 280-292 (1989) · Zbl 0669.60025 |
| [9] | Das, K. C.; Sun, S., Distance between the normalized Laplacian spectra of two graphs, Linear Algebra Appl., 530, 305-321 (2017) · Zbl 1367.05126 |
| [10] | Dehmer, M.; Emmert-Streib, F., Comparing large graphs efficiently by margins of feature vectors, Appl. Math. Comput., 188, 2, 1699-1710 (2007) · Zbl 1120.68080 |
| [11] | Dehmer, M.; Emmert-Streib, F.; Kilian, J., A similarity measure for graphs with low computational complexity, Appl. Math. Comput., 182, 1, 447-459 (2006) · Zbl 1111.05019 |
| [12] | Dehmer, M.; Emmert-Streib, F.; Shi, Y., Graph distance measures based on topological indices revisited, Appl. Math. Comput., 266, 623-633 (2015) · Zbl 1410.05041 |
| [13] | Dehmer, M.; Varmuza, K., A comparative analysis of the Tanimoto index and graph edit distance for measuring the topological similarity of trees, Appl. Math. Comput., 259, 242-250 (2015) · Zbl 1390.05053 |
| [14] | Emmert-Streib, F.; Dehmer, M.; Shi, Y., Fifty years of graph matching, network alignment and network comparison, Inf. Sci., 346/347, 180-197 (2016) · Zbl 1398.68393 |
| [15] | ERDdS, P.; R&WI, A., On random graphs I, Publ. Math. Debrecen, 6, 290-297 (1959) · Zbl 0092.15705 |
| [16] | Fiol, M. A.; Garriga, E., Number of walks and degree powers in a graph, Discrete Math., 309, 8, 2613-2614 (2009) · Zbl 1228.05171 |
| [17] | French, J. B., Elementary principles of spectral distributions, (Dalton, B. J.; Grimes, S. M.; Vary, J. P.; Williams, S. A., Theory and Applications of Moment Methods in Many-Fermion Systems (1980), Springer US: Springer US Boston, MA), 1-16 |
| [18] | Fujii, H.; Katsuda, A., Isospectral graphs and isoperimetric constants, Discrete Math., 207, 1-3, 33-52 (1999) · Zbl 1131.05309 |
| [19] | Gao, X.; Xiao, B.; Tao, D.; Li, X., A survey of graph edit distance, IEEE Pattern Anal. Applicat., 13, 1, 113-129 (2010) · Zbl 1422.68211 |
| [20] | Gavriliadis, P.; Athanassoulis, G., Moment data can be analytically completed, Probabilistic Eng. Mech., 18, 4, 329-338 (2003) |
| [21] | Gu, J.; Hua, B.; Liu, S., Spectral distances on graphs, Discrete Appl. Math., 190/191, 56-74 (2015) · Zbl 1316.05086 |
| [22] | Haemers, W. H.; Spence, E., Enumeration of cospectral graphs, European J. Combin., 25, 2, 199-211 (2004) · Zbl 1033.05070 |
| [23] | Hsieh, S.-Y.; Huang, C.-W.; Chou, H.-H., A DNA-based graph encoding scheme with its applications to graph isomorphism problems, Appl. Math. Comput., 203, 2, 502-512 (2008) · Zbl 1228.68020 |
| [24] | Jovanović, I.; Stanić, Z., Spectral distances of graphs, Linear Algebra Appl., 436, 5, 1425-1435 (2012) · Zbl 1236.05123 |
| [25] | Kullback, S.; Leibler, R. A., On information and sufficiency, Ann. Math. Stat., 22, 79-86 (1951) · Zbl 0042.38403 |
| [26] | Lin, H.; Li, D.; Das, K. C., Distance between distance spectra of graphs, Linear Multilinear Algebra, 65, 12, 2538-2550 (2017) · Zbl 1387.05158 |
| [27] | Mukherjee, S. S.; Sarkar, P.; Lin, L., On clustering network-valued data, (Guyon, I.; Luxburg, U. V.; Bengio, S.; Wallach, H.; Fergus, R.; Vishwanathan, S.; Garnett, R., Advances in Neural Information Processing Systems 30 (2017), Curran Associates, Inc.), 7071-7081 |
| [28] | Obata, N., Spectral analysis of growing graphs, SpringerBriefs in Mathematical Physics, 20 (2017), Springer, Singapore · Zbl 1366.81005 |
| [29] | Rossi, R. A.; Ahmed, N. K., The network data repository with interactive graph analytics and visualization, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI’15, 4292-4293 (2015), AAAI Press |
| [30] | Schieber, T. A.; Carpi, L.; Díaz-Guilera, A.; Pardalos, P. M.; Masoller, C.; Ravetti, M. G., Quantification of network structural dissimilarities, Nature Commun., 8, 13928 (2017) |
| [31] | Shervashidze, N.; Vishwanathan, S.; Petri, T.; Mehlhorn, K.; Borgwardt, K., Efficient graphlet kernels for large graph comparison, (van Dyk, D.; Welling, M., Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics. Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, 5 (2009), PMLR: PMLR Hilton Clearwater Beach Resort, Clearwater Beach, Florida USA), 488-495 |
| [32] | Shimada, Y.; Hirata, Y.; Ikeguchi, T.; Aihara, K., Graph distance for complex networks, Scient. Rep., 6, 34944 (2016) |
| [33] | Shrivastava, A.; Li, P., A new space for comparing graphs, Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM ’14, 62-71 (2014), IEEE Press: IEEE Press Piscataway, NJ, USA |
| [34] | Tan, H.; Peng, M.; Tse, C. K.; Wu, F., Global similarity tests of physical designs of circuits: a complex network approach, Appl. Math. Comput., 230, 96-103 (2014) · Zbl 1410.94125 |
| [35] | Täubig, H.; Weihmann, J.; Kosub, S.; Hemmecke, R.; Mayr, E. W., Inequalities for the number of walks in graphs, Algorithmica, 66, 4, 804-828 (2013) · Zbl 1275.05028 |
| [36] | Ugander, J.; Backstrom, L.; Kleinberg, J., Subgraph frequencies: Mapping the empirical and extremal geography of large graph collections, Proceedings of the International Conference World Wide Web, 1307-1318 (May 2013) |
| [37] | van Dam, E. R.; Haemers, W. H.; Koolen, J. H., Cospectral graphs and the generalized adjacency matrix, Linear Algebra Appl., 423, 1, 33-41 (2007) · Zbl 1118.05066 |
| [38] | R. Vemulapalli, D.W. Jacobs, Riemannian metric learning for symmetric positive definite matrices. CoRR, abs/1501.02393http://arxiv.org/abs/1501.02393; R. Vemulapalli, D.W. Jacobs, Riemannian metric learning for symmetric positive definite matrices. CoRR, abs/1501.02393http://arxiv.org/abs/1501.02393 |
| [39] | Wicker, N.; Nguyen, C. H.; Mamitsuka, H., A new dissimilarity measure for comparing labeled graphs, Linear Algebra Appl., 438, 5, 2331-2338 (2013) · Zbl 1258.05076 |
| [40] | Wilson, R. C.; Zhu, P., A study of graph spectra for comparing graphs and trees, Pattern Recogn., 41, 9, 2833-2841 (2008) · Zbl 1154.68505 |
| [41] | Zager, L., Graph Similarity and Matching (2005), Massachusetts Institute of Technology, Ph.D. thesis |
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.
