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

Similarity of Graphs and Complex Networks Based on Resistance 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.

1. 基本介绍

1.1. 电阻距离

设图 $G=\left(V\left(G\right),E\left(G\right),W\left(G\right)\right)$ 的顶点集，边集和边上的权重集分别为 $V\left(G\right)$ ， $E\left(G\right)$ 和 $W\left(G\right)$ 。记矩阵 $A\left(G\right)=\left(a_{ij}\right)$ 为图G的邻接矩阵，如果i和j相邻则 $a_{ij}=1$ ，否则 $a_{ij}=0$ 。矩阵 $D\left(G\right)=diag\left(d_1,d_2,\cdots ,d_n\right)$ 为G的对角矩阵，其中 $d_i$ 是G中顶点 $v_i$ 对应的度。G的Laplacian矩阵为 $L\left(G\right)=D\left(G\right)-A\left(G\right)$ 。

1993年，Klein和Randić [1] 提出了图的电阻距离的概念，把图G看作一个电网络，把G中的每条边都看作电阻，G中任意两个顶点 $v_i$ 和 $v_j$ 之间的电阻距离定义为电网络中这两个节点根据欧姆定律计算出的有效电阻，记作 $R_{ij}$ 。类似图的邻接矩阵，可以给出图的电阻距离矩阵定义： $R=\left[R_{ij}\right]$ ， $R_{ij}$ 为图中任意两点的电阻距离。文献 [2] 中提出了基于图拉普拉斯矩阵L来计算图中任意节点的有效电阻距离，计算公式方法如下，其中 $L^{+}$ 表示L的pseudo-逆，

$R_{ij}=L_{ii}^{+}+L_{jj}^{+}-2L_{ij}^{+}$ .

基于电阻距离，Klein和Randić [1] 提出了一个类似于Wiener指标的新的拓扑指标——Kirchhoff基尔霍夫指数。在连通图中，G的Kirchhoff指数 $Kf\left(G\right)$ 定义为G中所有点对之间的电阻距离之和，Kirchhoff指数表示如下，其中 ${\lambda }_i\left(i=1,\cdots ,n\right)$ 是图G拉普拉斯矩阵的特征值，

$Kf\left(G\right)={\displaystyle \underset{i<j}{\sum }{R}_{ij}}=n{\displaystyle \underset{i=2}{\overset{n}{\sum }}\frac{1}{{\lambda }_i}}$

有效电阻距离在图上提供了一个距离，量化了任意两个顶点之间的连通性，而不仅仅是最短路径的长度，电阻距离用于研究图的拓扑变化具有天然的优势。

1.2. 图距离范式

图和复杂网络之间的相似性或度量已经研究了几十年 [3] [4] ，被广泛应用于社会科学、生物学等学科。在真实的情况下，网络是不断动态变化的，顶点之间的关系会随着时间的变化而变化：顶点之间的边会出现或消失，边的权重会改变。对于动态网络的研究通常涉及到将网络拓扑的变化与驱动网络连通性演化的潜在动态过程耦合起来。近年来，研究和量化复杂时变网络的不规则和动态结构演变，检测复杂网络异常行为是研究复杂网络的重要方向。因此，为复杂网络的两两比较设计相似度度量是非常重要的 [5] 。在已知顶点对应关系的情况下，本文关注于同一顶点集上的两个连续图之间的相似度。恰当的网络相似性度量指标能够有效分类、识别复杂时变网络、检测网络结构的变化并准确预测其时间演化。文献 [6] 的作者将图和复杂网络的相似度度量概述为三个类别的图距离范式：局部距离，全局距离和中尺度距离。

局部距离又称为结构距离，主要关注于每个节点周围的图结构的变化，比如Hamming距离和Jaccard距离。Hamming距离通过邻接矩阵测量边的删除和添加来测量图的演变；Jaccard在Hamming距离的基础上做了改进 [7] ，对图的体积进行了归一化处理。全局距离又称作谱距离，通过追踪Laplacian矩阵或邻接矩阵的特征值的变化来测量全局的组织和交互的演变。Jurman [8] 系统地介绍了几种广泛使用的谱距离。此外，Kelman [9] 通过比较两个图的生成树数量来量化它们之间的差异，反映了图的相互连通性和鲁棒性的变化。多项式距离通过邻接矩阵的多项式，来描述两个节点的k-阶拓扑结构的变化。Jurman [10] 首次提出中尺度距离，考虑了每个节点的特征并结合了整体图的交互性和连通性。Papadimitriou及其合作者提出了基于连通性的图距离 [11] ，Koutra等人 [12] 定义了DeltaCon₀相似度距离，受图信号处理 [13] 的启发，Donna等人使用热谱小波来表示每个节点的拓扑特性的特征 [14] 。Nathen [2] 等人提出了一种基于电阻距离的动态复杂网络的度量即p阶电阻扰动距离，定义如下

$d_{rp-p}\left(G^{\left(1\right)},G^{\left(2\right)}\right)={\Vert R^{\left(1\right)}-R^{\left(2\right)}\Vert }_p={\left[{\displaystyle \underset{i,j=1}{\overset{n}{\sum }}{\left|R_{ij}^{\left(1\right)}-R_{ij}^{\left(2\right)}\right|}^p}\right]}^{1/p}$ .

该方法在度量连通图的相似性上有着较好的表现性能，但不能有效用于非连通图的度量。

现阶段对图和复杂网络的相似度问题的研究已经有较为完善的体系和方法，包括基于图的邻接矩阵、拉普拉斯矩阵、电阻距离矩阵等指标的相似度度量方法。但目前大多数方法都适用于连通的图和网络，不能有效用于非连通图的度量。基于电阻距离的相似度度量在连通图的上有着很好的表现性能，本文将基于电阻距离的相似度度量方法拓展到非连通图上，并为其提供可行、高效的算法。

2. 基于电阻距离的非连通图相似度度量

定义1 基于电阻距离的概念，将G看作一个电网络，每条边看作一个电阻，G中任意两点间的电导定义为在两点间施加的单位电压后，根据欧姆定律计算出的两点间的电流，记为 $C\left(i,j\right)$ 。当 $i\ne j$ 时， $C\left(i,j\right)$ 为点 $v_i$ 和点 $v_j$ 之间的电阻距离的倒数；当 $i=j$ 时， $C\left(i,j\right)$ 为0。两个不同顶点之间的电阻距离越大，电导则越小。对于一个连通图G， $C\left(i,j\right)$ 表示为如下，

$C\left(i,j\right)=\{\begin{array}{ll}\frac{1}{R\left(i,j\right)}\hfill & i\ne j\hfill \\ 0\hfill & i=j\hfill \end{array}$

对于非连通图G，处于不同连通分支上的两个顶点 $v_i$ 和 $v_j$ 他们之间的电阻距离是无穷大的，且没有电流通过，因此不同连通分支上的两个顶点 $v_i$ 和 $v_j$ 的电导为0。类比电阻距离矩阵，可以给出图的电导距离矩阵定义： $C=\left[C_{ij}\right]$ ， $C_{ij}$ 为图中任意两点的电导。

我们将电流的强度理解为两个不同顶点之间的信息交流的强度，因此电导强调了两个不同顶点之间的“通信”的能力强弱。与电阻距离矩阵R相比，我们以一种有意义的方式来表示非连通图的电导矩阵，这对测量动态非连通图的相似性具有很大意义。

定义2 将图G的总电导定义为G中所有顶点对之间的电导的总和，记为 $CI\left(G\right)$ ，表示为 $CI\left(G\right)={\displaystyle \underset{i<j}{\sum }C\left(i,j\right)}$ 。

定义3 设 $G=\left(V,E,W\right)$ 和 $G^{\prime }=\left(V^{\prime },E^{\prime },W^{\prime }\right)$ 是在同一个顶点集上的两个加权无向图，即 $V=V^{\prime }$ 。G和 $G^{\prime }$ 的电导距离矩阵分别为C和 $C^{\prime }$ ，现在定义G和 $G^{\prime }$ 之间的p阶电导扰动距离为G和 $G^{\prime }$ 电导距离矩阵之差的矩阵p-范数，记为 $d_p\left(G,G^{\prime }\right)$ ，表示如下，

$d_p\left(G,G^{\prime }\right)={\Vert C-C^{\prime }\Vert }_P={\left[{\displaystyle \underset{i\ne j}{\overset{n}{\sum }}{\left|C\left(i,j\right)-C^{\prime }\left(i,j\right)\right|}^p}\right]}^{1/p}$ 。

以上，我们得到了基于电阻距离的图相似度度量，即p阶电导扰动距离。对于非连通图，不同连通分支的顶点之间的电导能够以一种有意义的方式计算得到，因此p阶电导扰动距离可以同时适用于连通图和非连通图的相似度比较。

定理1 图空间中的距离应该满足以下条件：非负性、同一性、对称性和三角不等式，则p阶电导扰动距离是图空间中的距离。

证明 对于 $1\le p\le \infty$ ， ${\Vert \cdot \Vert }_p$ 是矩阵空间 ${{\rm M}}_n$ 上的范数，因此电导扰动距离具有非负性、对称性和三角形不等式性。现在证明同一性：当 $G^{\left(1\right)}=G^{\left(2\right)}$ ，则必有 $d_p\left(G,G^{\prime }\right)=0$ 。那么还需要证明当 $d_p\left(G,G^{\prime }\right)=0$ ，等价地当 $C^{\left(1\right)}=C^{\left(2\right)}$ 时，有 $G^{\left(1\right)}=G^{\left(2\right)}$ 。

对于连通图，根据文献 [2] 的结果，如果 $R^{\left(1\right)}=R^{\left(2\right)}$ ，有 $G^{\left(1\right)}=G^{\left(2\right)}$ 。对于连通图当 $C^{\left(1\right)}=C^{\left(2\right)}$ ，则必有 $R^{\left(1\right)}=R^{\left(2\right)}$ ，所以 $G^{\left(1\right)}=G^{\left(2\right)}$ 。对于非连通图，如果有 $C^{\left(1\right)}=C^{\left(2\right)}$ ，则意味着对应的连通分支有相同的电导距离矩阵和相同的电阻距离矩阵，因此两图对应的连通分支是相同的，所以 $G^{\left(1\right)}=G^{\left(2\right)}$ 。

引理1 Don和Uriel等人 [15] 给出电阻距离 $R\left(i,j\right)$ 的下界，

$R\left(i,j\right)\ge \frac{1}{d_i+1}+\frac{1}{d_j+1}$

当且仅当点i和j相邻且i和j在 $G-\left\{i,j\right\}$ 中有相同的邻点时等号成立。

引理2 [16] 若对图G的边 $\left[i_0,j_0\right]$ 添加一个扰动 $\Delta {\omega }_{i_0{j}_0}$ 得到图 $G^{\prime }$ ，那么对于任意 $i,j\in V\left(G\right)=V\left(G^{\prime }\right)$ ，有

$R^{\prime }\left(i,j\right)=R\left(i,j\right)-\frac{\Delta {\omega }_{i_0{j}_0}{\left[R\left(i,i_0\right)+R\left(j,j_0\right)-R\left(i,j_0\right)-R\left(j,i_0\right)\right]}^2}{4\left[1+\Delta {\omega }_{i_0{j}_0}R\left(i_0,j_0\right)\right]}$

定理2 G是一个简单的连通图，任意两个顶点i和j之间的电导距离满足，

$C\left(i,j\right)\le \frac{\left(d_i+1\right)\left(d_j+1\right)}{d_i+d_j+2}$

当且仅当点i和j相邻且i和j在 $G-\left\{i,j\right\}$ 中有相同的邻点时等号成立。

定理2由引理1电阻距离的下界可证得。

定理3 G是一个简单的连通图，对图G的边 $\left[i_0,j_0\right]$ 添加一个扰动 $\Delta {\omega }_{i_0{j}_0}$ 得到图 $G^{\prime }$ ，那么对于任意 $i,j\in V\left(G\right)=V\left(G^{\prime }\right)$ ，有

$C^{\prime }\left(i,j\right)=\{\begin{array}{ll}\frac{4C\left(i,j\right)\left[1+\Delta {\omega }_{i_0{j}_0}\frac{1}{C\left(i_0,j_0\right)}\right]}{4\left[1+\Delta {\omega }_{i_0{j}_0}\frac{1}{C\left(i_0,j_0\right)}\right]-\Delta {\omega }_{i_0{j}_0}C\left(i,j\right){\left[\frac{1}{C\left(i,i_0\right)}+\frac{1}{C\left(j,j_0\right)}-\frac{1}{C\left(i,j_0\right)}-\frac{1}{C\left(j,i_0\right)}\right]}^2}\hfill & i\ne j\hfill \\ 0\hfill & i=j\hfill \end{array}$

由引理2，对边 $\left[i_0,j_0\right]$ 添加扰动 $\Delta {\omega }_{i_0{j}_0}$ 后的电阻距离的公式可证得。

定理4 G是一个简单的连通图，可以得到电导总和 $CI\left(G\right)$ 的上界，

$CI\left(G\right)\le \frac{\left(n-1\right)\left(2m+n\right)}{4}$

n和m分别是G的顶点个数和边的数量。当且仅当G为完全图时，等号成立。

证明

$\begin{array}{c}CI\left(G\right)={\displaystyle \underset{i<j}{\sum }C\left(i,j\right)}\\ \le {\displaystyle \underset{i<j}{\sum }\frac{\left(d_i+1\right)\left(d_j+1\right)}{d_i+d_j+2}}\\ \le {\displaystyle \underset{i<j}{\sum }\frac{d_i+d_j+2}{4}}\begin{array}{ccc}& & 由\left(d_i+1\right)\left(d_j+1\right)\le \frac{{\left(d_i+d_j+2\right)}^2}{4}\end{array}\\ =\frac{\left(n-1\right){\displaystyle \underset{i=1}{\overset{n}{\sum }}{d}_i+n\left(n-1\right)}}{4}\\ =\frac{\left(2m+n\right)\left(n-1\right)}{4}\end{array}$

由于对于任意顶点i和j相邻且i和j在 $G-\left\{i,j\right\}$ 中有相同的邻点时等号成立，因此当且仅当G为完全图时等号成立。定理得证。

定理5 G是一个简单的连通图，可以得到电导总和 $CI\left(G\right)$ 的下界，

$CI\left(G\right)\ge \frac{n^2{\left(n-1\right)}^2}{4Kf(\; G\; )}$

$Kf\left(G\right)$ 是图G的基尔霍夫指数。

证明

$\begin{array}{c}CI\left(G\right)={\displaystyle \underset{i<j}{\sum }C\left(i,j\right)}\\ ={\displaystyle \underset{i<j}{\sum }\frac{1}{R\left(i,j\right)}}\\ \ge \frac{{\left({\displaystyle \underset{i<j}{\sum }1}\right)}^2}{{\displaystyle \underset{i<j}{\sum }R\left(i,j\right)}}\begin{array}{ccc}& & 由\text{Cauchy-Schwarz}不等式\end{array}\\ =\frac{n^2{\left(n-1\right)}^2}{4KI(\; G\; )}\end{array}$

定理6 G是简单连通图，对图G的边 $\left[i_0,j_0\right]$ 添加一个扰动 $\Delta {\omega }_{i_0{j}_0}$ 得到图 $G^{\prime }$ ，1阶电导扰动距离的上界满足，

$\begin{array}{c}{d}_1\left(G,G^{\prime }\right)={\displaystyle \underset{i,j=1}{\overset{n}{\sum }}\left|C_{ij}-{C^{\prime }}_{ij}\right|}\\ \le 2\left|\Delta {\omega }_{i_0{j}_0}\right|R_{i_0{j}_0}CI\left(G\right)\\ \le \left|\Delta {\omega }_{i_0{j}_0}\right|R_{i_0{j}_0}\frac{\left(n-1\right)\left(2m+n\right)}{2}\end{array}$

证明

$\begin{array}{c}{d}_1\left(G,G^{\prime }\right)={\displaystyle \underset{i,j=1}{\overset{n}{\sum }}\left|C_{ij}-{C^{\prime }}_{ij}\right|}\\ ={\displaystyle \underset{i\ne j}{\overset{n}{\sum }}\left|C_{ij}-{C^{\prime }}_{ij}\right|}\\ ={\displaystyle \underset{i\ne j}{\overset{n}{\sum }}\left|\frac{-\Delta {\omega }_{i_0{j}_0}{\left[R_{i{i}_0}+R_{j{j}_0}-R_{i{j}_0}-R_{j{i}_0}\right]}^2}{4R_{ij}^2\left(1+\Delta {\omega }_{i_0{j}_0}{R}_{i_0{j}_0}\right)-\Delta {\omega }_{i_0{j}_0}{R}_{ij}{\left[R_{i{i}_0}+R_{j{j}_0}-R_{i{j}_0}-R_{j{i}_0}\right]}^2}\right|}\\ ={\displaystyle \underset{i\ne j}{\overset{n}{\sum }}\frac{\left|\Delta {\omega }_{i_0{j}_0}\right|}{\frac{4R_{ij}^2\left(1+\Delta {\omega }_{i_0{j}_0}{R}_{i_0{j}_0}\right)}{{\left[R_{i{i}_0}+R_{j{j}_0}-R_{i{j}_0}-R_{j{i}_0}\right]}^2}-\Delta {\omega }_{i_0{j}_0}{R}_{ij}}}\end{array}$ (1)

根据三角不等式，可以得到，

$\left|R_{i{i}_0}+R_{j{j}_0}-R_{i{j}_0}-R_{j{i}_0}\right|\le \left|R_{i{i}_0}-R_{j{i}_0}\right|+\left|R_{j{j}_0}-R_{i{j}_0}\right|\le 2R_{ij}$ (2)

$\left|R_{i{i}_0}+R_{j{j}_0}-R_{i{j}_0}-R_{j{i}_0}\right|\le \left|R_{i{i}_0}-R_{j_{0}i}\right|+\left|R_{j{j}_0}-R_{i_{0}j}\right|\le 2R_{i_0{j}_0}$ (3)

将(2)，(3)式代入(1)式，得到

$d_1\left(G,G^{\prime }\right)\le {\displaystyle \underset{i\ne j}{\overset{n}{\sum }}\frac{\left|\Delta {\omega }_{i_0{j}_0}\right|R_{i_0{j}_0}}{R_{ij}}}=2\left|\Delta {\omega }_{i_0{j}_0}\right|R_{i_0{j}_0}CI\left(G\right).$

结合定理4，证得结论。

定理7 G是简单连通图，对图G的边 $\left[i_0,j_0\right]$ 添加一个扰动 $\Delta {\omega }_{i_0{j}_0}$ 得到图 $G^{\prime }$ ，1阶电导扰动距离的下界满足，

$\begin{array}{c}{d}_1\left(G,G^{\prime }\right)={\displaystyle \underset{i,j=1}{\overset{n}{\sum }}\left|C_{ij}-{C^{\prime }}_{ij}\right|}\\ \ge \frac{\left|\Delta {\omega }_{i_0{j}_0}\right|C_{i_0{j}_0}^2{\Psi }_{\lambda }^2\left(i_0,j_0\right)}{{\displaystyle \underset{k-2}{\overset{n}{\sum }}\frac{1}{{\lambda }_k}\left[{\displaystyle \underset{k=2}{\overset{n}{\sum }}\frac{1}{{\lambda }_k}\left(1+\Delta {\omega }_{i_0{j}_0}\frac{1}{C_{i_0{j}_0}}\right)-\Delta {\omega }_{i_0{j}_0}{\Psi }_{\lambda }\left(i_0,j_0\right)}\right]}}.\end{array}$

其中， ${\Psi }_{\lambda }\left(i_0,j_0\right)={\displaystyle \underset{k=2}{\overset{n}{\sum }}\frac{1}{{\lambda }_k^2}{\left[{\varphi }_k\left(i_0\right)-{\varphi }_k\left(j_0\right)\right]}^2}$ 。

证明 由Cauchy-Buniakowsky-Schwarz不等式，有

$\begin{array}{c}{d}_1\left(G,G^{\prime }\right)={\displaystyle \underset{i,j=1}{\overset{n}{\sum }}\left|C_{ij}-{C^{\prime }}_{ij}\right|}\\ ={\displaystyle \underset{i\ne j}{\overset{n}{\sum }}\frac{\left|\Delta {\omega }_{i_0{j}_0}\right|{\left(R_{i{i}_0}+R_{j{j}_0}-R_{i{j}_0}-R_{j{i}_0}\right)}^2}{4R_{ij}^2\left(1+\Delta {\omega }_{i_0{j}_0}{R}_{i_0{j}_0}\right)-\Delta {\omega }_{i_0{j}_0}{R}_{ij}{\left(R_{i{i}_0}+R_{j{j}_0}-R_{i{j}_0}-R_{j{i}_0}\right)}^2}}\\ \ge \frac{{\left[{\displaystyle \underset{i\ne j}{\overset{n}{\sum }}\left|\Delta {\omega }_{i_0{j}_0}\right|}{\left(R_{i{i}_0}+R_{j{j}_0}-R_{i{j}_0}-R_{j{i}_0}\right)}^2\right]}^2}{{\displaystyle \underset{i\ne j}{\overset{n}{\sum }}\left[4R_{ij}^2\left(1+\Delta {\omega }_{i_0{j}_0}{R}_{i_0{j}_0}\right)-\Delta {\omega }_{i_0{j}_0}{R}_{ij}{\left(R_{i{i}_0}+R_{j{j}_0}-R_{i{j}_0}-R_{j{i}_0}\right)}^2\right]\left|\Delta {\omega }_{i_0{j}_0}\right|{\left(R_{i{i}_0}+R_{j{j}_0}-R_{i{j}_0}-R_{j{i}_0}\right)}^2}}.\end{array}$

又由于

${\displaystyle \underset{i\ne j}{\overset{n}{\sum }}\left|\Delta {\omega }_{i_0{j}_0}\right|}{\left(R_{i{i}_0}+R_{j{j}_0}-R_{i{j}_0}-R_{j{i}_0}\right)}^2=8n\left|\Delta {\omega }_{i_0{j}_0}\right|{\displaystyle \underset{k=2}{\overset{n}{\sum }}\frac{1}{{\lambda }_k^2}}{\left({\varphi }_k\left(i_0\right)-{\varphi }_k\left(j_0\right)\right)}^2.$ (5)

${\left(R_{i{i}_0}+R_{j{j}_0}-R_{i{j}_0}-R_{j{i}_0}\right)}^2\le 4R_{i_0{j}_0}^2.$ (6)

$\begin{array}{l}{\displaystyle \underset{i\ne j}{\overset{n}{\sum }}\left[4R_{ij}^2\left(1+\Delta {\omega }_{i_0{j}_0}{R}_{i_0{j}_0}\right)-\Delta {\omega }_{i_0{j}_0}{R}_{ij}{\left(R_{i{i}_0}+R_{j{j}_0}-R_{i{j}_0}-R_{j{i}_0}\right)}^2\right]}\\ \le {\displaystyle \underset{i\ne j}{\overset{n}{\sum }}{R}_{ij}{\displaystyle \underset{i\ne j}{\overset{n}{\sum }}\left[4R_{ij}\left(1+\Delta {\omega }_{i_0{j}_0}{R}_{i_0{j}_0}\right)-\Delta {\omega }_{i_0{j}_0}{\left(R_{i{i}_0}+R_{j{j}_0}-R_{i{j}_0}-R_{j{i}_0}\right)}^2\right]}}.\end{array}$ (7)

${\displaystyle \underset{i\ne j}{\overset{n}{\sum }}{R}_{ij}=}{\displaystyle \underset{i,j=1}{\overset{n}{\sum }}{R}_{ij}=2n}{\displaystyle \underset{k=2}{\overset{n}{\sum }}\frac{1}{{\lambda }_k}}.$ (8)

将(5)，(6)，(7)，(8)式代入(4)式，得到

$\begin{array}{c}{d}_1\left(G,G^{\prime }\right)\ge \frac{{\left[8n\left|\Delta {\omega }_{i_0{j}_0}\right|{\displaystyle \underset{k=2}{\overset{n}{\sum }}\frac{1}{{\lambda }_k^2}{\left({\varphi }_k\left(i_0\right)-{\varphi }_k\left(j_0\right)\right)}^2}\right]}^2}{4\left|\Delta {\omega }_{i_0{j}_0}\right|R_{i_0{j}_0}^{2}2n{\displaystyle \underset{k=2}{\overset{n}{\sum }}\frac{1}{{\lambda }_k}\left[8n{\displaystyle \underset{k=2}{\overset{n}{\sum }}\frac{1}{{\lambda }_k}}\left(1+\Delta {\omega }_{i_0{j}_0}{R}_{i_0{j}_0}\right)-8n\Delta {\omega }_{i_0{j}_0}{\displaystyle \underset{k=2}{\overset{n}{\sum }}\frac{1}{{\lambda }_k}{\left({\varphi }_k\left(i_0\right)-{\varphi }_k\left(j_0\right)\right)}^2}\right]}}\\ =\frac{\left|\Delta {\omega }_{i_0{j}_0}\right|C_{i_0{j}_0}^2{\Psi }_{\lambda }^2\left(i_0,j_0\right)}{{\displaystyle \underset{k-2}{\overset{n}{\sum }}\frac{1}{{\lambda }_k}\left[{\displaystyle \underset{k=2}{\overset{n}{\sum }}\frac{1}{{\lambda }_k}\left(1+\Delta {\omega }_{i_0{j}_0}\frac{1}{C_{i_0{j}_0}}\right)-\Delta {\omega }_{i_0{j}_0}{\Psi }_{\lambda }\left(i_0,j_0\right)}\right]}}.\end{array}$

定理得证。

3. 快速近似算法

本节介绍了一种快速近似算法来近似计算两个图之间的p阶电导扰动距离。该近似算法是以Nathen [2] 和Spielman [17] [18] 等人对连通图上的成对电阻距离的快速近似计算为前提来实现的。通过在线性时间内近似计算两点间的电阻距离，可以得到连通图中两点间的电导。对于非连通图G，它的电导距离矩阵是一个分块对角矩阵(在非主对角线上的子块皆为零矩阵，主对角线上的子块都是方阵，主对角线上的每个子块是对应连通分支的电导距离矩阵)，通过计算每个连通分支的电导距离矩阵，组成分块对角矩阵，得到G的电导距离矩阵，最后得到两图之间电导距离矩阵之差的p-范数。

整个算法可以分为两部分：

第一部分为Nathen [2] 和Spielman [16] 等人提出的快速计算成对近似电阻距离算法，计算得到图中任意两点间的电阻。我们知道，求任意两点间的电阻距离，需要求Laplacian矩阵的伪逆，在复杂网络中，所耗费的时间复杂度是非常大的，该算法利用bi-Lipschitz顶点嵌入进行降维，再通过Spielman和Teng的拉普拉斯求解器 [19] [20] 来近似逼近结果。

该算法依赖于一个顶点bi-Lipschitz嵌入来保持成对的有效电阻距离，以达到降维的效果。给定一个连通图G，记顶点数量为n，边的数量为m [21] 。给定 $\epsilon >0$ ，总存在一个复杂度为 $\widetilde{{\rm O}}\left(m\log \bar{\omega }/{\epsilon }^2\right)$ 的线性算法，其中 $\bar{\omega }={\omega }_{\max }/{\omega }_{\min }$ ，能够计算得到一个 $\left(24\log n/{\epsilon }^2\right)\times n$ 阶矩阵 $\tilde{Z}$ ，并保证至少以 $1-1/n$ 的概率满足：

$\left(1-\epsilon \right)R_{ij}\le {\left(\tilde{Z}\left(e_i-e_j\right)\right)}_2^2\le \left(1+\epsilon \right)R_{ij},\forall i,j\in V$ .

$e_i$ 表示标准正交基的第i个向量， ${\omega }_{\max }$ 和 ${\omega }_{\min }$ 分别是边的最大权值和最小权值。

第一个方法是顶点可以嵌入到一个m维空间中，其中对应向量的欧氏距离的平方等于G中对应顶点之间的有效电阻，具体表示如下，

$\begin{array}{c}{R}_{ij}={\left(e_i-e_j\right)}^{\text{T}}{L}^{+}\left(e_i-e_j\right)\\ ={\left(e_i-e_j\right)}^{\text{T}}{L}^{+}L{L}^{+}\left(e_i-e_j\right)\\ =\left({\left(e_i-e_j\right)}^{\text{T}}{L}^{+}{B}^{\text{T}}{W}^{1/2}\right)\left(W^{1/2}B{L}^{+}\left(e_i-e_j\right)\right)\\ ={\Vert W^{1/2}B{L}^{+}\left(e_i-e_j\right)\Vert }_2^2\end{array}$

其中 $W\in M_{m\times m}$ 为G的对角边权矩阵，对角元素为每条边对应的权重，即 $W_{ee}={\omega }_e$ 。 $B\in M_{m\times n}$ 为G的边关联矩阵，即，

$B_{ei}=\{\begin{array}{ll}1\hfill & 当v_i是e的始点\hfill \\ -1\hfill & 当v_i是e的终点\hfill \\ 0\hfill & 其他\hfill \end{array}$

第二个方法是用 $s\times n$ 阶矩阵 $Y=Q{W}^{1/2}B$ 来替代 $W^{1/2}B$ ， $s=24\log n/{\epsilon }^2$ 。其中Q是一个 $s\times m$ 阶矩阵，矩阵的每个元素由随机数 $\pm 1/\sqrt{s}$ 组成。将矩阵 $\tilde{Z}$ 定义为 ${\tilde{Z}}^{\text{T}}=L^{+}{Y}^{\text{T}}$ ， $y_i$ 是 $Y^{\text{T}}$ 的第i列， $i=1,\cdots ,s$ ，那么我们可以通过求解线性系统 $L{\tilde{z}}_i=y_i$ 来逼近求解 ${\tilde{Z}}^{\text{T}}$ 的第i列，而不需要求Laplacian矩阵的伪逆。下列为构造矩阵 $\tilde{Z}$ 的基本算法步骤，其返回的矩阵 $\tilde{Z}$ 能够满足以上bi-Lipschitz嵌入的条件，最后得到近似的电阻距离矩阵R：

输入：连通图 $G\left(V,E,W\right)$

输出：G的电阻距离矩阵R

1) 随机生成一个 $s\times m$ 阶矩阵，要求矩阵元素为 $\pm 1/\sqrt{s}$ ，其中 $s=24\log n/{\epsilon }^2$ ，记为Q。

2) 计算 $Y=Q{W}^{1/2}B$ 。

3) 计算 ${\tilde{z}}_i=STSolve\left(L,y_i,\delta \right)$ ，这一步使用Spielman和Teng的拉普拉斯求解器 [17] [18] 来求解。其中L是G的Laplacian矩阵， $y_i$ 表示矩阵 $Y^{\text{T}}$ 的第i列( $i=1,\cdots ,s$ )。令 $\delta =\frac{\epsilon }{3}\sqrt{\frac{2}{n^3}\left(\frac{1-\epsilon }{1+\epsilon }\right)\frac{{\omega }_{\min }}{{\omega }_{\max }}}$ ， $\delta$ 为相对误差，满足 ${\Vert x-L^{+}y\Vert }_L\le \delta \Vert L^{+}y\Vert$ ， ${\Vert y\Vert }_L=\sqrt{y^{\text{T}}Ly}$ 。

4) 得到 $\tilde{Z}={\left[{\tilde{z}}_1,\cdots ,{\tilde{z}}_s\right]}^{\text{T}}$ 。

5) 得到电阻距离矩阵 $R\approx \tilde{R}=diag\left({\tilde{Z}}^{\text{T}}\tilde{Z}\right)1^{\text{T}}+1diag{\left({\tilde{Z}}^{\text{T}}\tilde{Z}\right)}^{\text{T}}-2{\tilde{Z}}^{\text{T}}\tilde{Z}$ 。

第二部分为根据求得的成对电阻距离，计算p阶电导扰动距离，使其同时适用于连通和非连通图。

对于非连通图G，定义G的电导距离矩阵为一个分块对角矩阵 $C\left(G\right)$ ，主对角线上的每个子块 $C_i$ 是对应第i个连通分支的电导距离矩阵( $i=1,\cdots ,r$ )。

$C\left(G\right)=\left[\begin{array}{cccc}{C}_1& & & \\ & C_2& & \\ & & \ddots & \\ & & & C_r\end{array}\right]$

将图G的顶点集 $V\left(G\right)$ 标记为 $\sigma =\left({\sigma }_1,\cdots ,{\sigma }_n\right)$ 。对于连通图G， $C\left(G\right)$ 的行和列按顶点顺序 $\sigma$ 来排列，即 $C\left(i,j\right)$ 表示顶点 ${\sigma }_i$ 和 ${\sigma }_j$ 之间的电导。对于非连通的图G， $C\left(G\right)$ 的每个子块对应不同的连通分支，因此 $C\left(G\right)$ 的行和列并不按顺序 $\sigma$ 来排列，将 $C\left(G\right)$ 的行和列对应的顶点记录下来，并记为 ${\sigma }^{\prime }$ 。但由于两个非连通图的电导距离矩阵的 ${\sigma }^{\prime }$ 是不相同的，无法直接比较。因此我们提出了一种方法，通过重新排列 $C\left(G\right)$ 的行和列，使 ${\sigma }^{\prime }$ 与 $\sigma$ 一致。该算法首先通过计算各连通分支的电导距离矩阵来构造矩阵 $C\left(G\right)$ ，得到 ${\sigma }^{\prime }$ ，记录 $\left({\sigma }_1,\cdots ,{\sigma }_n\right)$ 在 ${\sigma }^{\prime }$ 中的位置，表示为 $J=\left(j_1,j_2,\cdots ,j_n\right)$ 。根据向量J构造一个置换矩阵P： $P\left[i\right]\left[j_i\right]=1,\left(1\le i\le n\right)$ ，其他元素为0。重新排列矩阵C： $\hat{C}=PC{P}^{\prime }$ ，得到的电导距离矩阵 $\hat{C}$ 的 ${\sigma }^{\prime }$ 与初始标记 $\sigma$ 一样，显然，我们可以比较矩阵 $\hat{C}$ 来测量两个图之间的p阶电导扰动距离。

算法的基本步骤描述如下：

输入： $G^{\left(1\right)},G^{(\; 2\; )}$

输出： $d_p\left(G^{\left(1\right)},G^{(\; 2\; )}\right)$

1) 计算图 $G^{\left(1\right)}$ 的电导距离矩阵 ${\hat{C}}^{\left(1\right)}$ ：

将图 $G^{\left(1\right)}$ 的顶点集V标记为 $\sigma =\left({\sigma }_1,\cdots ,{\sigma }_n\right)$

${\sigma }^{\prime }\leftarrow \left[\right]$

对于 $G^{\left(1\right)}$ 中的每个连通分支：

记录当前所在连通分支对应的顶点标记，添加进 ${\sigma }^{\prime }$

将当前连通分支看作一个子图，计算电阻距离矩阵 ${\tilde{R}}_i$

计算电导距离矩阵 ${\tilde{C}}_i$

得到电导距离矩阵 ${\tilde{C}}^{\left(1\right)}=diag\left({\tilde{C}}_1,{\tilde{C}}_2,\cdots ,{\tilde{C}}_r\right)$

记录 $\left({\sigma }_1,\cdots ,{\sigma }_n\right)$ 在 ${\sigma }^{\prime }$ 中的位置，表示为 $J=\left(j_1,j_2,\cdots ,j_n\right)$

构造置换矩阵P： $P\left[i\right]\left[j_i\right]=1,\left(1\le i\le n\right)$ ，其他元素为0

得到 ${\hat{C}}^{\left(1\right)}=P{\tilde{C}}^{\left(1\right)}{P}^{\prime }$

2) 同理，计算图 $G^{\left(2\right)}$ 的电导距离矩阵 ${\hat{C}}^{(\; 2\; )}$

3) 计算 $d_p\left(G^{\left(1\right)},G^{\left(2\right)}\right)={\Vert {\hat{C}}^{\left(1\right)}-{\hat{C}}^{\left(2\right)}\Vert }_P={\left[{\displaystyle \underset{i\ne j}{\overset{n}{\sum }}{\left|{\hat{C}}^{\left(1\right)}\left(i,j\right)-{\hat{C}}^{\left(2\right)}\left(i,j\right)\right|}^p}\right]}^{1/p}$

4. 动态网络实证分析

本文的第一个实验，在ER随机网络，SBM网络，WS小世界网络，Island网络进行模拟试验，比较电导扰动距离( $d_p$ )和标准化电阻扰动距离( $d_{rp}$ )对于检测结构网络变化的灵敏度。首先，生成节点个数为 $N=1080$ 的初始网络 $G^{\left(1\right)}$ ，保持节点个数不变，修改模型的结构参数来生成新的网络，设置修改步数 $T=21$ ，每一步修改得到的网络记为 $G^{\left(2\right)}$ ，再计算每步修改后的网络 $G^{\left(2\right)}$ 与初始网络 $G^{\left(1\right)}$ 的距离。为了避免偶然性，我们将实验重复50次，再计算距离的平均值。

对于ER随机网络，以随机两个顶点连边的概率 $p^{\left(1\right)}=0.01$ 来生成 $G^{\left(1\right)}$ ，将连边概率每次增加0.02得到 $p^{\left(2\right)}$ 生成 $G^{\left(2\right)}$ ，即 $p^{\left(2\right)}\in \left[0.01,0.41\right]$ 。对于SBM网络，设置三个节点个数相等的社区，社区内节点的链接概率 $p_{in}=0.9$ ，社区间节点的链接概率 $p_{out}^{\left(1\right)}=0.005$ ，生成 $G^{\left(1\right)}$ ，将社区间节点链接概率每次增加0.0002得到 $p_{out}^{\left(2\right)}$ 生成 $G^{\left(2\right)}$ ，即 $p_{out}^{\left(2\right)}\in \left[0.005,0.009\right]$ 。对于Island网络，设置两个节点个数相等的岛屿(社区)，岛屿内节点的链接概率 $p_{in}=0.9$ ，岛屿间的连边数量 $n_{out}^{\left(1\right)}=1$ ，生成 $G^{\left(1\right)}$ ，将岛屿间的连边数量每次增加1得到 $n_{out}^{\left(2\right)}$ 生成 $G^{\left(2\right)}$ ，即 $n_{out}^{\left(2\right)}\in \left[1,21\right]$ 。对于WS小世界网络，设置 $G^{\left(1\right)}$ 每个顶点平均度数为20，即每个顶点都链接到它两侧最近的10个邻居顶点，重新连接图中生成的每条边，以 ${\beta }^{\left(1\right)}=0.01$ 的概率重新连接到目标顶点。将 $\beta$ 每次增加0.0005得到 ${\beta }^{\left(2\right)}$ ，即 ${\beta }^{\left(2\right)}\in \left[0.01,0.02\right]$ 。

实验通过比较两个图距离随模型的结构参数的变化趋势来表明图距离与参数演化是否有显著的相关关系。结果如图1所示，与标准化电阻扰动距离相比，电导扰动距离显示出与控制网络的参数演化更高的相关性，特别是在ER网络、SBM网络和Island网络，表明电导扰动距离对于检测结构网络变化具有更好的灵敏度。虽然标准化电阻扰动距离在SBM网络中表现良好，但在ER模型和Island模型中与参数的演化没有显著的相关关系，原因是对于轻微的波动过于敏感，因此无法检测到连续的参数变化引起的网络变化。值得一提的是，本文在实验中使用的图模型涉及到非连通图，这表明电导扰动距离对于非连通图的异常检测也有不错的表现。

Figure 1. Graph distance in relation to the variation of network structural

图1. 图距离与网络结构参数变化关系图

本文的第二个实验，将电导扰动距离( $d_p$ )与Hamming距离，Jaccard距离，谱距离(Eigen)，生成树距离(ST)，多项式距离(Poly)，热谱距离(Heat)和标准化电阻扰动距离( $d_{rp}$ )进行比较，来评估电导扰动距离对相似图的聚类识别能力。我们在ER随机模型、PA模型，SBM模型进行实验，这提供了一个受控的环境，并呈现了不同的全局和局部的聚集密度，使我们能够更全面评估拓扑结构对网络动力学分析的影响。为了观察图距离在不同规模网络上的适用性，我们设置了四组实验，每组分别为240，540，1080个节点。

先设定三个模型的初始参数：ER模型的连边概率 $p=0.1$ ；PA优先链接模型是通过将新节点倾向于连接到已有的、具有较高度数的节点，优先连接导致网络的度数分布遵循幂律分布，即存在少数高度连接的节点，大部分节点只连接少数其他节点，那么节点u具有度 $d_u$ 的概率为 $P\left(d_u=k\right)\propto k^{-\alpha }$ ，设置 $\alpha =1$ ；SBM网络设置大小相同的社区，社区间链接矩阵为

$C=\left[\begin{array}{ccc}0.4& 0.1& 0.001\\ 0.1& 0.2& 0.01\\ 0.001& 0.01& 0.5\end{array}\right]$

对前、中、后三个时间段设置不同的扰动机制：当 $T=1~7$ 时，8.5%的边被随机重连，1.5%的边被随机删除或添加；当 $T=8~14$ 时，边被随机重连的概率增加到34%，边被随机删除或添加概率增加到6%；当 $T=15~21$ 时，边被重连、随机删除或添加的概率恢复到第一阶段。由此，得到 $T=1~21$ 每个时间点对应的图，将每个图之间的两两图距离表示为21 × 21阶矩阵D，其中 $D_{ij}=d\left(G^{\left(i\right)},G^{\left(j\right)}\right)$ 。

a) 实验通过矩阵D的热图来表示各图之间的相似性，热图中颜色越深则表示两个图之间的距离越小。根据实验设置的扰动机制，同时间段内的色块应该较深，不同时间段之间的色块应该较浅，那么热图应该沿对角线划分为三个清晰的颜色较深的子块。

b) 实验根据扰动机制将每个时间点的图分为3个类别，第一类是 $T=1~7$ 对应的图，第二类是 $T=1~7$ 对应的图，第三类是 $T=1~7$ 对应的图。再对矩阵D进行聚类，还原出三个类别，计算聚类准确率。一个好的度量指标应能高精度地识别出属于同一时间阶段的图，因此聚类准确率也较高。

实验结果如图2~图4和表1所示，热图结果表明相较于其他距离，电导扰动距离在ER、PA和SBM网络中表现更好，沿对角线显示出三个较为清晰的深色子块。根据表1显示的不同距离在ER、PA、SBM模型中的聚类准确率，可以看出，相较于其他传统的结构距离、谱距离和中尺度距离，电导扰动距离的聚类准确率更高，表明电导扰动距离能够较好地识别出属于同一时间阶段的图和网络。以上结果说明电导扰动距离在识别复杂网络之间地相似性方面有着更好地表现性能，并且对识别网络动态变化也有更好的灵敏度。

Figure 2. Heat map for the Erdős-Rényi model

图2. ER随机模型热图

Figure 3. Heat map for the Preferential Attachment model

图3. PA模型热图

Figure 4. Heat map for the Stochastic Block model

图4. SBM模型热图

Table 1. Clustering accuracy

表1. 聚类准确率准

5. 结论

本文旨在将电阻距离度量连通图的相似度的方法拓展到非连通图上，使其在连通图和非连通图上同时适用，为研究非连通图的相似度提供了有意义的方法。而对于大型复杂网络，直接计算电阻距离则需要直接计算它的谱，所消耗时间成本是昂贵的，因此本文将在电阻距离的快速近似算法基础上，为大型的非连通图相似度的计算提供了一个可行、高效的算法。最后通过实验验证了改度量方法的可行性和有效性。本文提出的快速近似计算图距离仍然是一个多项式时间复杂度的算法，因此开发具有高度并行性的算法可能是未来改进这种算法的一个重要途径。

基金项目

广东省自然科学基金面上项目(2021A1515012047)。

NOTES

^*通讯作者。