基于电阻距离的图和复杂网络的相似度问题研究
Similarity of Graphs and Complex Networks Based on Resistance Distance
DOI: 10.12677/aam.2024.134149, PDF,    科研立项经费支持
作者: 蔡满乐, 何伟骅*:广东工业大学数学与统计学院,广东 广州
关键词: 电阻距离复杂网络图距离Resistance Distance Complex Network Graph Distance
摘要: 本文基于电阻距离提出了一种能有效衡量图和复杂网络相似性的度量指标,可适用于连通图和非连通图,并反映了网络动力系统的相互作用和动态特性。同时,还提出了一种高效的快速近似算法,用于计算动态图之间的相似性。动态网络模拟实验结果表明,相较于其他度量指标,该方法对检测网络内在结构变化具有较好的灵敏度,表现出更优的相似图的聚类识别能力。
Abstract: This paper proposes a metric based on resistance distance that effectively measures the similarity of graphs and complex networks. This metric can be applied to both connected and disconnected graphs, reflecting the interaction and dynamic characteristics of network dynamical systems. Additionally, an efficient and fast approximate algorithm is introduced to compute the similarity between dynamic graphs. Results from dynamic network simulation experiments indicate that, compared to other metrics, this method exhibits better sensitivity in detecting intrinsic structural changes within networks and demonstrates superior clustering identification capabilities for similar graph.
文章引用:蔡满乐, 何伟骅. 基于电阻距离的图和复杂网络的相似度问题研究[J]. 应用数学进展, 2024, 13(4): 1585-1598. https://doi.org/10.12677/aam.2024.134149

参考文献

[1] Klein, D.J. and Randi, M. (1993) Resistance Distance. Journal of Mathematical Chemistry, 12, 81-95. [Google Scholar] [CrossRef
[2] Monnig, N.D. and Meyer, F.G. (2016) The Resistance Perturbation Distance: A Metric for the Analysis of Dynamic Networks. Discrete Applied Mathematics, 236, 347-386. [Google Scholar] [CrossRef
[3] Berlingerio, M., Koutra, D., Eliassi-Rad, T., et al. (2013) Network Similarity via Multiple Social Theories. International Conference on Advances in Social Networks Analysis and Mining, Niagara, 25-28 August 2013, 1439-1440. [Google Scholar] [CrossRef
[4] Soundarajan, S., Eliassirad, T. and Gallagher, B. (2014) A Guide to Selecting a Network Similarity Method.
[5] Ahmed, N.K., Neville, J., Rossi, R.A., et al. (2015) Fast Parallel Graphlet Counting for Large Networks. Knowledge & Information Systems, 1-34.
[6] Donnat, C. and Holmes, S. (2018) Tracking Network Dynamics: A Review of Distances and Similarity Metrics.
[7] Conci, A. and Kubrusly, C.S. (2018) Distance between Sets—A Survey.
[8] Jurman, G., Visintainer, R. and Furlanello, C. (2011) An Introduction to Spectral Distances in Networks. Neural Nets WIRN10—Proceedings of the 20th Italian Workshop on Neural Nets, Salerno, 27-29 May 2010, 227-234.
[9] Kelmans, A.K. (1996) On Graphs with the Maximum Number of Spanning Trees. Random Structures & Algorithms, 9, 177-192. [Google Scholar] [CrossRef
[10] Jurman, G., Visintainer, R., Filosi, M., et al. (2015) The HIM Glocal Metric and Kernel for Network Comparison and Classification. 2015 IEEE International Conference on Data Science and Advanced Analytics (DSAA), Paris, 19-21 October 2015, 1-10. [Google Scholar] [CrossRef
[11] Papadimitriou, P., Dasdan, A. and Garcia-Molina, H. (2010) Web Graph Similarity for Anomaly Detection. Journal of Internet Services & Applications, 1, 19-30. [Google Scholar] [CrossRef
[12] Koutra, D., Shah, N., Vogelstein, J.T., et al. (2016) Delta C on: Principled Massive-Graph Similarity Function with Attribution. ACM Transactions on Knowledge Discovery from Data, 10, 1-43. [Google Scholar] [CrossRef
[13] Shuman, D.I., Narang, S.K., Frossard, P., et al. (2013) The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains. IEEE Signal Processing Magazine, 30, 83-98. [Google Scholar] [CrossRef
[14] Donnat, C., Zitnik, M., Hallac, D., et al. (2018) Spectral Graph Wavelets for Structural Role Similarity in Networks.
[15] Coppersmith, D., Feige, U. and Shearer, J. (1996) Random Walks on Regular and Irregular Graphs. SIAM Journal on Discrete Mathematics, 9, 301-308. [Google Scholar] [CrossRef
[16] Yang, Y.J. and Klein, D.J. (2013) A Recursion Formula for Resistance Distances and Its Applications. Discrete Applied Mathematics, 161, 2702-2715. [Google Scholar] [CrossRef
[17] FDLG (1984) Random Walks and Electric Networks. Carus Mathematical Monograph.
[18] Spielman, D.A. and Srivastava, N. (2008) Graph Sparsification by Effective Resistances. STOC’08: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, Victoria, 17-20 May 2008, 563-568. [Google Scholar] [CrossRef
[19] Spielman, D.A. and Teng, S.H. (2014) Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems. SIAM Journal on Matrix Analysis & Applications, 35, 835-885. [Google Scholar] [CrossRef
[20] Orecchia, L. and Vishnoi, N.K. (2010) Towards an SDP-Based Approach to Spectral Methods: A Nearly-Linear-Time Algorithm for Graph Partitioning and Decomposition.
[21] Srivastava, N. (2010) Spectral Sparsification and Restricted Invertibility. Yale University, New Haven.