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

Advances in Applied Mathematics 应用数学进展应用数学进展,2024,13(4),1585-1598 Published Online April 2024 in Hans.https:/www.hanspub.org/journal/aam https:/doi.org/10.12677/aam.2024.134149 文章引用文章引用:蔡满乐,何伟骅.基于电阻距离的图和复杂网络的相似度问题研究J.应用数学进展,2024,13(4):1585-1598.DOI:10.12677/aam.2024.134149 基于电阻距离的图和复杂网络的相似度问题基于电阻距离的图和复杂网络的相似度问题 研究研究 蔡满乐蔡满乐，何伟骅何伟骅*广东工业大学数学与统计学院，广东 广州 收稿日期：2024年3月25日；录用日期：2024年4月22日；发布日期：2024年4月29日 摘摘 要要 本文基于电阻距离提出了一种能有效衡量图和复杂网络相似性的度量指标，可适用于连通图和非连通图，本文基于电阻距离提出了一种能有效衡量图和复杂网络相似性的度量指标，可适用于连通图和非连通图，并反映了网络动力系统的相互作用和动态特性。同时，还提出了一种高效的快速近似算法，用于计算动并反映了网络动力系统的相互作用和动态特性。同时，还提出了一种高效的快速近似算法，用于计算动态图之间的相似性。动态网络模拟实验结果表明，相较于其他度量指标，该方法对检测网络内在结构变态图之间的相似性。动态网络模拟实验结果表明，相较于其他度量指标，该方法对检测网络内在结构变化具有较好的灵敏度，表现出更优的相似图的聚类识别能力。化具有较好的灵敏度，表现出更优的相似图的聚类识别能力。关键词关键词 电阻距离，复杂网络，图距离电阻距离，复杂网络，图距离 Similarity of Graphs and Complex Networks Based on Resistance Distance Manle Cai,Weihua He*School of Mathematics and Statistic,Guangdong University of Technology,Guangzhou Guangdong Received:Mar.25th,2024;accepted:Apr.22nd,2024;published:Apr.29th,2024 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.Ad-ditionally,an efficient and fast approximate algorithm is introduced to compute the similarity between dynamic graphs.Results from dynamic network simulation experiments indicate that,*通讯作者。蔡满乐，何伟骅 DOI:10.12677/aam.2024.134149 1586 应用数学进展 compared to other metrics,this method exhibits better sensitivity in detecting intrinsic structural changes within networks and demonstrates superior clustering identification capabilities for sim-ilar graph.Keywords Resistance Distance,Complex Network,Graph Distance Copyright 2024 by author(s)and Hans Publishers Inc.This work is licensed under the Creative Commons Attribution International License(CC BY 4.0).http:/creativecommons.org/licenses/by/4.0/1.基本介绍基本介绍 1.1.电阻距离电阻距离 设图()()()(),GV GE GW G=的顶点集，边集和边上的权重集分别为()V G，()E G和()W G。记矩阵()()ijA Ga=为图 G 的邻接矩阵，如果 i 和 j 相邻则1ija=，否则0ija=。矩阵()()12,nD Gdiag d dd=为 G 的对角矩阵，其中id是 G 中顶点iv对应的度。G 的 Laplacian 矩阵为()()()L GD GA G=。1993 年，Klein 和 Randi 1提出了图的电阻距离的概念，把图 G 看作一个电网络，把 G 中的每条边都看作电阻，G 中任意两个顶点iv和jv之间的电阻距离定义为电网络中这两个节点根据欧姆定律计算出的有效电阻，记作ijR。类似图的邻接矩阵，可以给出图的电阻距离矩阵定义：ijRR=，ijR为图中任意两点的电阻距离。文献2中提出了基于图拉普拉斯矩阵 L 来计算图中任意节点的有效电阻距离，计算公式方法如下，其中L+表示 L 的 pseudo-逆，2ijiijjijRLLL+=+.基于电阻距离，Klein 和 Randi 1提出了一个类似于 Wiener 指标的新的拓扑指标Kirchhoff 基尔霍夫指数。在连通图中，G 的 Kirchhoff 指数()Kf G定义为 G 中所有点对之间的电阻距离之和，Kirchhoff指数表示如下，其中()1,iin=是图 G 拉普拉斯矩阵的特征值，()21nijijiiKf GRn=有效电阻距离在图上提供了一个距离，量化了任意两个顶点之间的连通性，而不仅仅是最短路径的长度，电阻距离用于研究图的拓扑变化具有天然的优势。1.2.图距离范式图距离范式 图和复杂网络之间的相似性或度量已经研究了几十年3 4，被广泛应用于社会科学、生物学等学科。在真实的情况下，网络是不断动态变化的，顶点之间的关系会随着时间的变化而变化：顶点之间的边会出现或消失，边的权重会改变。对于动态网络的研究通常涉及到将网络拓扑的变化与驱动网络连通性演化的潜在动态过程耦合起来。近年来，研究和量化复杂时变网络的不规则和动态结构演变，检测复杂网络异常行为是研究复杂网络的重要方向。因此，为复杂网络的两两比较设计相似度度量是非常重要的5。在已知顶点对应关系的情况下，本文关注于同一顶点集上的两个连续图之间的相似度。恰当的网络相似Open AccessOpen Access蔡满乐，何伟骅 DOI:10.12677/aam.2024.134149 1587 应用数学进展 性度量指标能够有效分类、识别复杂时变网络、检测网络结构的变化并准确预测其时间演化。文献6的作者将图和复杂网络的相似度度量概述为三个类别的图距离范式：局部距离，全局距离和中尺度距离。局部距离又称为结构距离，主要关注于每个节点周围的图结构的变化，比如 Hamming 距离和 Jaccard距离。Hamming 距离通过邻接矩阵测量边的删除和添加来测量图的演变；Jaccard 在 Hamming 距离的基础上做了改进7，对图的体积进行了归一化处理。全局距离又称作谱距离，通过追踪 Laplacian 矩阵或邻接矩阵的特征值的变化来测量全局的组织和交互的演变。Jurman 8系统地介绍了几种广泛使用的谱距离。此外，Kelman 9通过比较两个图的生成树数量来量化它们之间的差异，反映了图的相互连通性和鲁棒性的变化。多项式距离通过邻接矩阵的多项式，来描述两个节点的 k-阶拓扑结构的变化。Jurman 10首次提出中尺度距离，考虑了每个节点的特征并结合了整体图的交互性和连通性。Papadimitriou 及其合作者提出了基于连通性的图距离11，Koutra 等人12定义了 DeltaCon0相似度距离，受图信号处理13的启发，Donna 等人使用热谱小波来表示每个节点的拓扑特性的特征14。Nathen 2等人提出了一种基于电阻距离的动态复杂网络的度量即 p 阶电阻扰动距离，定义如下()()()()()()()1121212,1,pnprppijijpi jdGGRRRR=.该方法在度量连通图的相似性上有着较好的表现性能，但不能有效用于非连通图的度量。现阶段对图和复杂网络的相似度问题的研究已经有较为完善的体系和方法，包括基于图的邻接矩阵、拉普拉斯矩阵、电阻距离矩阵等指标的相似度度量方法。但目前大多数方法都适用于连通的图和网络，不能有效用于非连通图的度量。基于电阻距离的相似度度量在连通图的上有着很好的表现性能，本文将基于电阻距离的相似度度量方法拓展到非连通图上，并为其提供可行、高效的算法。2.基于电阻距离的非连通图相似度度量基于电阻距离的非连通图相似度度量 定义定义 1 基于电阻距离的概念，将 G 看作一个电网络，每条边看作一个电阻，G 中任意两点间的电导定义为在两点间施加的单位电压后，根据欧姆定律计算出的两点间的电流，记为(),C i j。当ij时，(),C i j为点iv和点jv之间的电阻距离的倒数；当ij=时，(),C i j为 0。两个不同顶点之间的电阻距离越大，电导则越小。对于一个连通图 G，(),C i j表示为如下，()()1,0ijR i jC i jij=对于非连通图 G，处于不同连通分支上的两个顶点iv和jv他们之间的电阻距离是无穷大的，且没有电流通过，因此不同连通分支上的两个顶点iv和jv的电导为 0。类比电阻距离矩阵，可以给出图的电导距离矩阵定义：ijCC=，ijC为图中任意两点的电导。我们将电流的强度理解为两个不同顶点之间的信息交流的强度，因此电导强调了两个不同顶点之间的“通信”的能力强弱。与电阻距离矩阵 R 相比，我们以一种有意义的方式来表示非连通图的电导矩阵，这对测量动态非连通图的相似性具有很大意义。定义定义 2 将图 G 的总电导定义为 G 中所有顶点对之间的电导的总和，记为()CI G，表示为()(),ijCI GC i j=。定义定义 3 设(),GV E W=和(),GV E W=是在同一个顶点集上的两个加权无向图，即VV=。G 和G的电导距离矩阵分别为 C 和C，现在定义 G 和G之间的 p 阶电导扰动距离为 G 和G电导距离矩阵之差蔡满乐，何伟骅 DOI:10.12677/aam.2024.134149 1588 应用数学进展 的矩阵 p-范数，记为(),pdG G，表示如下，()()()1,pnppPijdG GCCC i jC i j=。以上，我们得到了基于电阻距离的图相似度度量，即 p 阶电导扰动距离。对于非连通图，不同连通分支的顶点之间的电导能够以一种有意义的方式计算得到，因此 p 阶电导扰动距离可以同时适用于连通图和非连通图的相似度比较。定理定理 1 图空间中的距离应该满足以下条件：非负性、同一性、对称性和三角不等式，则 p 阶电导扰动距离是图空间中的距离。证明证明 对于1p，p是矩阵空间n上的范数，因此电导扰动距离具有非负性、对称性和三角形不等式性。现在证明同一性：当()()12GG=，则必有(),0pdG G=。那么还需要证明当(),0pdG G=，等价地当()()12CC=时，有()()12GG=。对于连通图，根据文献2的结果，如果()()12RR=，有()()12GG=。对于连通图当()()12CC=，则必有()()12RR=，所以()()12GG=。对于非连通图，如果有()()12CC=，则意味着对应的连通分支有相同的电导距离矩阵和相同的电阻距离矩阵，因此两图对应的连通分支是相同的，所以()()12GG=。引理引理 1 Don 和 Uriel 等人15给出电阻距离(),R i j的下界，()11,11ijR i jdd+当且仅当点 i 和 j 相邻且 i 和 j 在,Gi j中有相同的邻点时等号成立。引理引理 2 16若对图 G 的边00,ij添加一个扰动0 0i j得到图G，那么对于任意()(),i jV GV G=，有()()()()()()()0 00 02000000,4 1,i ji jR i iR j jR i jR j iR i jR i jR ij+=+定理定理 2 G 是一个简单的连通图，任意两个顶点 i 和 j 之间的电导距离满足，()()()11,2ijijddC i jdd+当且仅当点 i 和 j 相邻且 i 和 j 在,Gi j中有相同的邻点时等号成立。定理 2 由引理 1 电阻距离的下界可证得。定理定理 3 G 是一个简单的连通图，对图 G 的边00,ij添加一个扰动0 0i j得到图G，那么对于任意()(),i jV GV G=，有()()()()()()()()()0 00 00 000200000014,1,111114 1,0i ji ji jC i jC ijijC i jC i jC ijC i iC j jC i jC j iij+=+=由引理 2，对边00,ij添加扰动0 0i j后的电阻距离的公式可证得。定理定理 4 G 是一个简单的连通图，可以得到电导总和()CI G的上界，蔡满乐，何伟骅 DOI:10.12677/aam.2024.134149 1589 应用数学进展 ()()()124nmnCI G+n 和 m 分别是 G 的顶点个数和边的数量。当且仅当 G 为完全图时，等号成立。证明证明()()()()()()()()()()()21,112221144114214ijijijijijijijijniiCI GC i jddddddddddndn nmnn=+=+=由 由于对于任意顶点 i 和 j 相邻且 i 和 j 在,Gi j中有相同的邻点时等号成立，因此当且仅当 G 为完全图时等号成立。定理得证。定理定理 5 G 是一个简单的连通图，可以得到电导总和()CI G的下界，()()()2214nnCI GKf G()Kf G是图 G 的基尔霍夫指数。证明证明()()()()()()222,1,1Cauchy-Schwarz,14ijijijijCI GC i jR i jR i jnnKI G，总存在一个复杂度为()2logm 的线性算法，其中maxmin=，能够计算得到一个()224lognn阶矩阵Z，并保证至少以1 1 n的概率满足：()()()()2211,ijijijRZ eeRi jV+.蔡满乐，何伟骅 DOI:10.12677/aam.2024.134149 1592 应用数学进展 ie表示标准正交基的第 i 个向量，max和min分别是边的最大权值和最小权值。第一个方法是顶点可以嵌入到一个 m 维空间中，其中对应向量的欧氏距离的平方等于 G 中对应顶点之间的有效电阻，具体表示如下，()()()()()()()()()1 21TTT1 2222TijijijijijijijijReeLeeeeL LLeeeeL B WWBLeeWBLee+=其中m mWM为 G 的对角边权矩阵，对角元素为每条边对应的权重，即eeeW=。m nBM为 G 的边关联矩阵，即，110ieiiveBve=当是 的始点当是 的终点其他 第二个方法是用sn阶矩阵1 2YQWB=来替代1 2WB，224logsn=。其中 Q 是一个sm阶矩阵，矩阵的每个元素由随机数1s组成。将矩阵Z定义为TTZL Y+=，iy是TY的第 i 列，1,is=，那么我们可以通过求解线性系统iiLzy=来逼近求解TZ的第 i 列，而不需要求 Laplacian 矩阵的伪逆。下列为构造矩阵Z的基本算法步骤，其返回的矩阵Z能够满足以上 bi-Lipschitz 嵌入的条件，最后得到近似的电阻距离矩阵 R：输入：连通图(),G V E W 输出：G 的电阻距离矩阵 R 1)随机生成一个sm阶矩阵，要求矩阵元素为1s，其中224logsn=，记为 Q。2)计算1 2YQWB=。3)计算(),iizSTSolve L y=，这一步使用 Spielman 和 Teng 的拉普拉斯求解器17 18来求解。其 中 L 是 G 的 Laplacian 矩阵，iy表示矩阵TY的第 i 列(1,is=)。令min3max2131n=+，为相对误 差，满足LxL yL y+，TLyy Ly=。4)得到T1,sZzz=。5)得到电阻距离矩阵()()TTTTT2RRdiag Z Zdiag Z ZZ Z=+11。第二部分为根据求得的成对电阻距离，计算 p 阶电导扰动距离，使其同时适用于连通和非连通图。对于非连通图 G，定义 G 的电导距离矩阵为一个分块对角矩阵()C G，主对角线上的每个子块iC是对应第 i 个连通分支的电导距离矩阵(1,ir=)。()12rCCC GC=将图 G 的顶点集()V G标记为()1,n=。对于连通图 G，()C G的行和列按顶点顺序来排列，蔡满乐，何伟骅 DOI:10.12677/aam.2024.134149 1593 应用数学进展 即(),C i j表示顶点i和j之间的电导。对于非连通的图 G，()C G的每个子块对应不同的连通分支，因此()C G的行和列并不按顺序来排列，将()C G的行和列对应的顶点记录下来，并记为。但由于两个非连通图的电导距离矩阵的是不相同的，无法直接比较。因此我们提出了一种方法，通过重新排列()C G的行和列，使与一致。该算法首先通过计算各连通分支的电导距离矩阵来构造矩阵()C G，得到，记录()1,n在中的位置，表示为()12,nJjjj=。根据向量 J 构造一个置换矩阵 P：()1,1iP ijin=，其他元素为 0。重新排列矩阵 C：CPCP=，得到的电导距离矩阵C的与初始标记一样，显然，我们可以比较矩阵C来测量两个图之间的 p 阶电导扰动距离。算法的基本步骤描述如下：输入：()()12,GG 输出：()()()12,pdGG 1)计算图()1G的电导距离矩阵()1C：将图()1G的顶点集 V 标记为()1,n=对于()1G中的每个连通分支：记录当前所在连通分支对应的顶点标记，添加进 将当前连通分支看作一个子图，计算电阻距离矩阵iR 计算电导距离矩阵iC 得到电导距离矩阵()()112,rCdiag C CC=记录()1,n在中的位置，表示为()12,nJjjj=构造置换矩阵 P：()1,1iP ijin=，其他元素为 0 得到()()11CPCP=2)同理，计算图()2G的电导距离矩阵()2C 3)计算()()()()()()()()()1121212,pnppPijdGGCCCi jCi j=4.动态网络实证分析动态网络实证分析 本文的第一个实验，在 ER 随机网络，SBM 网络，WS 小世界网络，Island 网络进行模拟试验，比较电导扰动距离(pd)和标准化电阻扰动距离(rpd)对于检测结构网络变化的灵敏度。首先，生成节点个数为1080N=的初始网络()1G，保持节点个数不变，修改模型的结构参数来生成新的网络，设置修改步数21T=，每一步修改得到的网络记为()2G，再计算每步修改后的网络()2G与初始网络()1G的距离。为了避免偶然性，我们将实验重复 50 次，再计算距离的平均值。对于 ER 随机网络，以随机两个顶点连边的概率()10.01p=来生成()1G，将连边概率每次增加 0.02 得到()2p生成()2G，即()20.01,0.41p。对于 SBM 网络，设置三个节点个数相等的社区，社区内节点的链接概率0.9inp=，社区间节点的链接概率()10.005outp=，生成()1G，将社区间节点链接概率每次增加 0.0002得到()2outp生成()2G，即()20.005,0.009outp。对于 Island 网络，设置两个节点个数相等的岛屿(社区)，岛屿内节点的链接概率0.9inp=，岛屿间的连边数量()11outn=，生成()1G，将岛屿间的连边数量每次增加 1 得到()2outn生成()2G，即()21,21outn。对于 WS 小世界网络，设置()1G每个顶点平均度数为 20，即每个顶点都链接到它两侧最近的 10 个邻居顶点，重新连接图中生成的每条边，以()10.01=的概率重新连接到目标顶点。将每次增加 0.0005 得到()2，即()20.01,0.02。蔡满乐，何伟骅 DOI:10.12677/aam.2024.134149 1594 应用数学进展 实验通过比较两个图距离随模型的结构参数的变化趋势来表明图距离与参数演化是否有显著的相关关系。结果如图 1 所示，与标准化电阻扰动距离相比，电导扰动距离显示出与控制网络的参数演化更高的相关性，特别是在 ER 网络、SBM 网络和 Island 网络，表明电导扰动距离对于检测结构网络变化具有更好的灵敏度。虽然标准化电阻扰动距离在 SBM 网络中表现良好，但在 ER 模型和 Island 模型中与参数的演化没有显著的相关关系，原因是对于轻微的波动过于敏感，因此无法检测到连续的参数变化引起的网络变化。值得一提的是，本文在实验中使用的图模型涉及到非连通图，这表明电导扰动距离对于非连通图的异常检测也有不错的表现。Figure 1.Graph distance in relation to the variation of network structural 图图 1.图距离与网络结构参数变化关系图 本文的第二个实验，将电导扰动距离(pd)与 Hamming 距离，Jaccard 距离，谱距离(Eigen)，生成树距离(ST)，多项式距离(Poly)，热谱距离(Heat)和标准化电阻扰动距离(rpd)进行比较，来评估电导扰动距离对相似图的聚类识别能力。我们在 ER 随机模型、PA 模型，SBM 模型进行实验，这提供了一个受控的环境，并呈现了不同的全局和局部的聚集密度，使我们能够更全面评估拓扑结构对网络动力学分析的影响。为了观察图距离在不同规模网络上的适用性，我们设置了四组实验，每组分别为 240，540，1080 个节点。先设定三个模型的初始参数：ER 模型的连边概率0.1p=；PA 优先链接模型是通过将新节点倾向于连接到已有的、具有较高度数的节点，优先连接导致网络的度数分布遵循幂律分布，即存在少数高度连接的节点，大部分节点只连接少数其他节点，那么节点 u 具有度ud的概率为()uP dkk=，设置1=；SBM 网络设置大小相同的社区，社区间链接矩阵为 蔡满乐，何伟骅 DOI:10.12677/aam.2024.134149 1595 应用数学进展 0.40.10.0010.10.20.010.0010.010.5C=对前、中、后三个时间段设置不同的扰动机制：当1 7T=时，8.5%的边被随机重连，1.5%的边被随机删除或添加；当8 14T=时，边被随机重连的概率增加到 34%，边被随机删除或添加概率增加到6%；当15 21T=时，边被重连、随机删除或添加的概率恢复到第一阶段。由此，得到1 21T=每个时间点对应的图，将每个图之间的两两图距离表示为 21 21 阶矩阵 D，其中()()(),ijijd GGD=。a)实验通过矩阵 D 的热图来表示各图之间的相似性，热图中颜色越深则表示两个图之间的距离越小。根据实验设置的扰动机制，同时间段内的色块应该较深，不同时间段之间的色块应该较浅，那么热图应该沿对角线划分为三个清晰的颜色较深的子块。b)实验根据扰动机制将每个时间点的图分为 3 个类别，第一类是1 7T=对应的图，第二类是1 7T=对应的图，第三类是1 7T=对应的图。再对矩阵 D 进行聚类，还原出三个类别，计算聚类准确率。一个好的度量指标应能高精度地识别出属于同一时间阶段的图，因此聚类准确率也较高。实验结果如图 2图 4 和表 1 所示，热图结果表明相较于其他距离，电导扰动距离在 ER、PA 和 SBM网络中表现更好，沿对角线显示出三个较为清晰的深色子块。根据表 1 显示的不同距离在 ER、PA、SBM模型中的聚类准确率，可以看出，相较于其他传统的结构距离、谱距离和中尺度距离，电导扰动距离的聚类准确率更高，表明电导扰动距离能够较好地识别出属于同一时间阶段的图和网络。以上结果说明电导扰动距离在识别复杂网络之间地相似性方面有着更好地表现性能，并且对识别网络动态变化也有更好的灵敏度。Figure 2.Heat map for the Erds-Rnyi model 图图 2.ER 随机模型热图 蔡满乐，何伟骅 DOI:10.12677/aam.2024.134149 1596 应用数学进展 Figure 3.Heat map for the Preferential Attachment model 图图 3.PA 模型热图 Figure 4.Heat map for the Stochastic Block model 图图 4.SBM 模型热图 蔡满乐，何伟骅 DOI:10.12677/aam.2024.134149 1597 应用数学进展 Table 1.Clustering accuracy 表表 1.聚类准确率准 pd rpd Poly ST Eigen Hamming Jaccard Heat N=120 ER 0.814 0.477 0.828 0.727 0.472 0.764 0.769 0.465 PA 0.824 0.381 0.765 0.410 0.472 0.767 0.468 0.381 SBM 0.824 0.389 0.851 0.766 0.464 0.766 0.788 0.480 N=240 ER 0.843 0.472 0.857 0.754 0.469 0.762 0.760 0.474 PA 0.854 0.381 0.782 0.382 0.382 0.781 0.467 0.381 SBM 0.829 0.406 0.857 0.783 0.387 0.762 0.772 0.474 N=560 ER 0.856 0.476 0.857 0.758 0.382 0.762 0.762 0.476 PA 0.857 0.381 0.804 0.381 0.381 0.792 0.381 0.381 SBM 0.855 0.476 0.857 0.768 0.381 0.762 0.762 0.476 N=1080 ER 0.857 0.476 0.857 0.762 0.381 0.762 0.762 0.476 PA 0.857 0.381 0.810 0.381 0.381 0.810 0.810 0.381 SBM 0.857 0.476 0.857 0.810 0.381 0.762 0.762 0.476 5.结论结论 本文旨在将电阻距离度量连通图的相似度的方法拓展到非连通图上，使其在连通图和非连通图上同时适用，为研究非连通图的相似度提供了有意义的方法。而对于大型复杂网络，直接计算电阻距离则需要直接计算它的谱，所消耗时间成本是昂贵的，因此本文将在电阻距离的快速近似算法基础上，为大型的非连通图相似度的计算提供了一个可行、高效的算法。最后通过实验验证了改度量方法的可行性和有效性。本文提出的快速近似计算图距离仍然是一个多项式时间复杂度的算法，因此开发具有高度并行性的算法可能是未来改进这种算法的一个重要途径。基金项目基金项目 广东省自然科学基金面上项目(2021A1515012047)。参考文献参考文献 1 Klein,D.J.and Randi,M.(1993)Resistance Distance.Journal of Mathematical Chemistry,12,81-95.https:/doi.org/10.1007/BF01164627 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.https:/doi.org/10.1016/j.dam.2017.10.007 3 Berlingerio,M.,Koutra,D.,Eliassi-Rad,T.,et al.(2013)Network Similarity via Multiple Social Theories.Interna-tional Conference on Advances in Social Networks Analysis and Mining,Niagara,25-28 August 2013,1439-1440.https:/doi.org/10.1145/2492517.2492582 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 SetsA Survey.8 Jurman,G.,Visintainer,R.and Furlanello,C.(2011)An Introduction to Spectral Distances in Networks.Neural Nets WIRN10Proceedings of the 20th Italian Workshop on Neural Nets,Salerno,27-29 May 2010,227-234.蔡满乐，何伟骅 DOI:10.12677/aam.2024.134149 1598 应用数学进展 9 Kelmans,A.K.(1996)On Graphs with the Maximum Number of Spanning Trees.Random Structures&Algorithms,9,177-192.https:/doi.org/10.1002/(SICI)1098-2418(199608/09)9:1/23.0.CO;2-L 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.https:/doi.org/10.1109/DSAA.2015.7344816 11 Papadimitriou,P.,Dasdan,A.and Garcia-Molina,H.(2010)Web Graph Similarity for Anomaly Detection.Journal of Internet Services&Applications,1,19-30.https:/doi.org/10.1007/s13174-010-0003-x 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.https:/doi.org/10.1145/2824443 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.https:/doi.org/10.1109/MSP.2012.2235192 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.https:/doi.org/10.1137/S0895480193260595 16 Yang,Y.J.and Klein,D.J.(2013)A Recursion Formula for Resistance Distances and Its Applications.Discrete Ap-plied Mathematics,161,2702-2715.https:/doi.org/10.1016/j.dam.2012.07.015 17 FDLG(1984)Random Walks and Electric Networks.Carus Mathematical Monograph.18 Spielman,D.A.and Srivastava,N.(2008)Graph Sparsification by Effective Resistances.STOC08:Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing,Victoria,17-20 May 2008,563-568.https:/doi.org/10.1145/1374376.1374456 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&Applicati