基于电阻距离的图和复杂网络的相似度问题研究

Similarity of Graphs and Complex Networks Based on Resistance Distance

本文基于电阻距离提出了一种能有效衡量图和复杂网络相似性的度量指标,可适用于连通图和非连通图,并反映了网络动力系统的相互作用和动态特性。同时,还提出了一种高效的快速近似算法,用于计算动态图之间的相似性。动态网络模拟实验结果表明,相较于其他度量指标,该方法对检测网络内在结构变化具有较好的灵敏度,表现出更优的相似图的聚类识别能力。

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.