邓 莉, 刘士虎

(云南民族大学 数学与计算机科学学院, 昆明 650504)

在现实生活中，许多诸如Facebook社交网络[1]、蛋白质相互作用网络[2-3]、航空网络[4]、疾病传播网络[5]等都可以抽象为图数据.图数据不仅仅刻画了样本点的特征，还包含刻画样本点之间关联情况的信息，即拓扑信息.鉴于图数据在理论层面和市场需求具有的巨大应用价值，近年来其在各行各业掀起了研究高潮，并且取得了一系列卓有成效的研究成果[6-8].不难发现，图数据中样本点的相似性度量是一个重要的研究课题，在字符和图形识别[9]、目标跟踪[10]、城市交通网络[11-12]等领域发挥着重要的作用.

随机游走方法被广泛用于度量样本点的相似性，该方法无需图数据的全局信息，衡量从特定样本点出发，通过多步随机游走到达另一个样本点的过程.为了更好地使用此方法度量样本点的相似性，研究者们相继提出了多种随机游走模型：如有偏的随机游走模型(biased random walk，BRW)[13-14]，最大熵随机游走模型(maximal entropy random walk，MERW)[15]，局部随机游走模型(local random walk，LRW)[16]等.不足的是，这些随机游走模型的样本点相似性度量方法存在大度样本点依赖问题.同时，这些方法从拓扑信息出发来度量样本点基于结构的相似性，使其难以广泛运用于度量属性图数据中样本点相似性.文献[17]针对属性图数据样本点相似性的度量问题，提出了一种样本点基于随机游走的相似性度量方法:LLRWSMM-PCO.该方法充分讨论了任意两个样本点关于拓扑结构的可达性，在样本点可达的基础上，度量样本点基于拓扑信息的相似性，从而得到一种综合的相似性度量方法.不足的是，该方法只针对无权无向图数据.

除了基于随机游走的样本点相似性方法，大量的研究从样本点共享邻居的角度对样本点相似性进行了研究[18-23].Salton[21]和Jaccard[22]分别提出了基于余弦距离和共享邻居Jaccard指标，该指标认为样本点的共享邻居越多，其相似性程度越高.在文献[23]中，Lada等从共享邻居度的角度，提出了Adamic-Adar指标，该指标认为，共享邻居的度越小，样本点间潜在的相似性越大.然而，真实网络中存在许多样本点没有共同的邻居，但是在属性信息方面有极高的相似性，从而导致从共享邻居角度度量样本点相似性存在一定的局限.除了这些研究，文献[24-28]中还提出了许多其它的度量方法.

对于图数据中样本点的相似性度量问题，无向无权的图数据已有了较多的研究.但随着研究的不断深入，无向无权图数据已经不能涵盖大部分的网络特性.大部分真实图数据的链接是带有权重的，比如共同作者网络、航空网络等.因此，带权图数据中样本点的相似性度量逐渐受到重视.针对这类问题的研究，本文从属性信息和拓扑信息2个角度出发，按以下2个步骤来展开工作：①提出基于改进的度中心性指导的随机游走的方法，度量样本点基于拓扑信息的相似性；②针对欧式距离在度量相似性方面的不足，通过融合欧式距离和余弦距离来度量样本点基于属性信息的相似性，进而得到样本点间的综合相似性.

1 预备知识

为了行文简洁及后文叙述的需要，这里给出文中需要用到的一些基本知识以及相关数学表示.

1.1 带权图数据

通常情况下，带权图数据可表示为G=(X,R,W)，其中X={x1,x2,…,xn}是一个非空有限集，表示带权图数据中样本点的集合，xi=(xi1,xi2,…,xim)表示有m个属性的样本点，即|X|=n,X的矩阵形式表示为

R={rij|i,j=1,2,...,n}表示图数据中样本点之间关联信息的集合，rij表示样本点xi与xj间的拓扑信息(本文使用样本点xi与xj基于共享邻居与非共享邻居的相异性来刻画rij)，R也可使用矩阵的形式表示

其中，不妨假设，若rij≠0，则表示样本点xi与xj有边相连,反之，rij=0.

带权图数据G中样本点的可达性可作如下定义：若样本点xi与xj是零步可达，即xi与xj是相同样本点；若样本点xi与xj间接连接，即rij=0，但rik0≠0,rk0k1≠0,…,rkl-1j≠0，则称样本点xi与xj是l步可达的；若样本点xi与xj是l步不可达的，则称为它们恒不可达或者绝对不可达.

1.2 度中心性

在带权图数据中，度中心性是衡量一个样本点与所有其它样本点相关联的程度.对于一个样本点规模为n的带权图数据，样本点xi的度中心性定义为其直接相连邻居n(xi)所对应的权重之和，可用CD(xi)表示，具体计算方法如下:

其中，T(x)={y|rxy≠0}.

1.3 几类相似性度量方法

Jaccard相似度是一种从拓扑信息出发，考虑从共享邻居的数量的角度，度量两样本点之间相似性的方法，其具体定义如下

(2)

该指标在缩短计算时间以及寻找最相似样本点有很好的效果.遗憾的是，该指标着重从最近邻居考虑样本点基于拓扑信息的相似性，使得在度量过程中丢失非最近邻居样本点的信息.

欧式距离如公式(3)所示，被广泛应用于的各种相似性度量研究.其优点在于可以克服变量之间的相关性干扰，并且消除各变量量纲的影响.但是该方法易受指标不同单位刻度影响，难以刻画具有相同欧式距离的属性信息之间的散度.

(3)

余弦距离如公式(4)所示，是通过计算2个样本点基于属性信息的夹角余弦值来评估相似程度.有别于欧氏距离，该方法更加注重度量样本点基于属性信息在方向上的差异，但对具体数值的绝对值大小不敏感，使得相似性得分不具有区分性.

(4)

LLRWSMM-PCO方法是一种从属性信息和拓扑信息2个角度出发，结合随机游走，进而度量图数据中两样本点相似性的方法.在拓扑信息的相似性度量方面，该方法充分研究了样本点基于拓扑信息的可达性，并在可达的基础上，利用随机游走计算样本点基于拓扑信息的相似性.在利用余弦相似度计算到属性信息相似性后，该方法将属性信息和拓扑信息进行加权，得到最终的相似性，其主要计算公式如下.

(5)

(6)

-SX(xi,xj)表示样本点xi与xj关于属性信息的相似性.

-sij(xi,xj)表示样本点xi与xj的综合相似性.

-τ:xi→xko→…→xkl-1→xj表示样本点xi与xj间的一条随机游走路径.

2 基于拓扑信息的相似性度量

针对带权图数据中样本点基于拓扑信息的相似性度量问题，文中从共享邻居与改进度中心性的角度出发，利用随机游走的方法，构建了ICSMMP算法.该算法从以下2个方面对拓扑信息进行相似性度量.首先改进了共享邻居的定义，利用共享邻居与非共享邻居的比值构造相邻样本点关于拓扑信息的相异性.在此基础之上，利用改进度中心性指导随机游走的方法，选择最优路径，进而度量带权图数据中任意样本点基于拓扑信息的相似性.

2.1 基于共享邻居的相似性度量方法

在讨论样本点相似性的算法中，计算样本点间的连边概率通常是基于它们的共同邻居样本点的信息.从样本点的共享邻居的角度出发，2样本点的共享邻居越多，共享邻居对样本点相似性所做出的贡献就越大.相反，若2样本点的共享邻居越少，则2样本点潜在的相似性越小.对任意样本点xi与xj，现有的共享邻居T(xi,xj)定义为

T(xi,xj)=T(xi)∩T(xj).

(8)

在解决实际问题中，如图1所示，(a)、(b)中T(x1,x2)={x3}，但 (b)中x1与x3之间的关联信息比(a)多，所以其在拓扑信息方面潜在的相似性更大.为此，文中在公式(8)的基础上改进共享邻居的计算方法，具体公式如下:

T(xi,xj)*=T(xi)+T(xj)-(O(xi)+O(xj))+T(xi,xj),

(9)

其中，O(xi)表示与xi连接的邻居中与xj不连接的邻居.

(10)

其中，|T(xi,xj)*|表示共享邻居的数目.公式(10)表明，样本点的非共享邻居越多，其共享邻居所占的比例越小，样本点间潜在的关系越少，进而拓扑信息相似性就越低.

2.2 改进度中心性

在带权图数据中，样本点的度中心性是衡量样本点重要性的重要指标.现有计算带权图数据中样本点度中心性的方法单方面考虑了其邻居权重，没有考虑样本点邻居个数对度中心性的影响.由公式(1)计算不难发现，图2中x2与x3的度中心性的值都为1.8，但x2拥有更多的邻居，在游走的过程中，x2作为游走过程的中间样本点的可能性更大.为此，在公式(1)的基础上，本文提出了一种改进的度中心性的计算方法如下

(11)

改进后的度中心性综合考虑样本点的邻居个数、连边的权重，能够更加全面的反映这2个因素对样本点重要性的影响.

图1 样本点x2的共享邻居 图2 邻居个数不同但权重之和相同的样本点

2.3 基于改进度中心性指导的随机游走方法

在充分研究了样本点的度中心性后，本文以改进度中心性指导样本点的随机游走，度量带权图数据G中任意样本点基于拓扑信息的相似性.一般的，在G中拓扑结构是连通的时候，从样本点xi出发，经过有限次的游走可达样本点xj，两样本点通过有限中间样本点连接，在拓扑信息方面具有潜在的相似性.而在游走的过程中，会产生多条随机游走路径，且基于不同路径计算相似性的结果不同.为此，我们提出了公式(12)来选择最优路径进行相似性度量

(12)

(13)

其矩阵项表示图数据中样本点的相异性，具体计算方式如下

(14)

不难发现，基于改进度中心性指导随机游走的方法不仅考虑样本点自身的信息，而且将样本点邻居蕴含的潜在信息和一定范围内共享邻居与非共享邻居的信息作为因素考虑在相似性的度量过程中，避免度量过程仅仅考虑最近邻相似性，使得相似性难以区分.在解决实际问题中，利用随机游走度量方法最关注的游走路径长度是3步，通过3步游走可达的2个样本点具有很高的相似性.相反，游走路径超过3步的样本点，其潜在的拓扑相似性减少.为此，文中定义若游走路径长度超过3步，则2样本点不可达.

3 样本点的综合相似性度量

针对欧式距离和余弦距离这2种度量方法在单一使用中的不足，构建了一种融合方法来计算样本点属性信息的相似性.具体如公式(15)所示，

(15)

分别对样本点的属性信息和样本点间的拓扑信息的相异性进行全面的讨论后，文中综合样本点基于属性信息和样本点间拓扑信息的相异性，给出公式(16)来定义带权图数据G中样本点的综合相异性矩阵D=(dij)n×n，其中

(16)

最后，将相异性矩阵转化为相似性矩阵S=(Simij)n×n，进而得出综合性的样本点相似性度量方法，相似性矩阵S的矩阵项的计算方式如下：

(17)

由可达的相关知识不难发现，本文研究相似性度量问题可分为3类进行研究：0步可达，l 步可达和不可达，处于不同类别的样本点的相似性计算方式不同.针对本文的研究目的，“基于改进度中心性的样本点相似性度量方法”可以总结为ICSMMP算法.

4 ICSMMP算法

输入 无向带权图数据G=(X,R,W).

输出 带权图数据G的相似性矩阵S=(Simij)n×n.

步骤1 由公式(10)计算相邻样本点基于共享邻居的相异性.

步骤2 由公式(11)计算带权图数据G中各样本点的改进度中心性.

步骤3 调用随机游走算法，基于公式(12)，选择最优路径.

步骤4 基于最优路径，使用公式(14)计算样本点基于拓扑信息的相异性.

步骤5 由公式(15)计算样本点属性信息的距离.

步骤6 由公式(16)、(17)计算G中各样本点的综合相似度.

5 算例分析

本文使用了随机生成的带权图数据G，该图数据有10个样本点，12条边，为了更好的说明本文所提出的ICSMMP算法，本文将G进行可视化，其结果如图3所示，并在改进度中心性指导的随机游走方法下度量样本点相似性.图4中样本点大小表示该样本点的改进度中心性大小，样本点越大表示改进度中心性越大(蓝色样本点代表当前样本点，黄色、灰色、绿色、橙色分别代表从当前样本点出发游走1步、2步、3步和4步到达的样本点).表1为G中10个样本点的属性信息.

图3 带权图数据G的拓扑结构

图5与图6展示了在带权图数据G中的样本点基于ICSMMP方法与LLRWSMM-PCO方法下的相似性矩阵的热图.鉴于样本点间的相似性存在对称性，所得到的相似性为关于对角线对称的矩阵.从图5、6易知，ICSMMP方法与LLRWSMM-PCO方法在区分样本点间拓扑信息的相似性，捕获样本点间的邻居相似性方面有不错的效果，且2种方法也能够从数值上明显的区分样本点间拓扑信息的相似性.但从表2分析，不难发现，在识别最相似样本点方面，基于ICSMMP方法，x2最相似的样本点为x1，而在LLRWSMM-PCO方法下，x2最相似的样本点为x4.很明显x2与x1不仅在属性信息方面有更高的相似性，在拓扑信息方面，x2与x1有更多的共享邻居和更相似的拓扑结构，所以它们具有更多潜在的相似性.

图4 x1与其它样本点的游走路径长度

表1 样本点的属性信息

图5 基于ICSMMP的相似性度量方法

图6 基于LLRWSMM-PCO的相似性度量方法

表2 G中样本点最相似的2个样本点

图7与图8分别是基于余弦距离方法与Jaccard相似性方法下的相似性矩阵的热图.从图中分析，余弦距离方法从单一属性信息的角度出发，未考虑拓扑信息的相似性，使距离较远，拓扑信息相似度较小的样本点可能被识别为高相似样本点.如表2的数据可知，在余弦距离方法下，样本点x1与x8，x2与x10，2组样本点对利用余弦距离方法计算得出的相似度很高，但是两样本点没有共同邻居，且拓扑结构的相似性也很低.Jaccard相似性方法是从拓扑信息角度出发，计算样本点的相似性.该方法能够很好的捕获邻居样本点的相似性，不足的是，该方法从邻居样本点的单一角度出发，损失了很多非邻居样本点的信息，即没有共同邻居的样本点对相似度为0，并且没有考虑属性信息，使得大部分样本点成为一般样本点.

图7 基于余弦距离的相似性度量方法

图8 基于Jaccard相似度的相似性度量方法

图9是分别通过4种相似性度量方法计算所得的拥有相同相似度值的样本点对所占比值.不难看出，通过ICSMMP的相似性度量方法计算得出的100组相似值中，相似度值相同样本点对所占比值最低，说明该方法得出的相似度值中，不存在多对样本点拥有相同的相似性得分，从而能很好的识别最相似样本点.但是在LLRWSMM-PCO方法、余弦距离方法和Jaccard相似性方法下，存在多对样本点拥有相同的相似性得分，这样可能使得处于同一阶段相似性的样本点不易区分，不利于后续图数据聚类或识别图数据中重要样本点的工作的进行.

图9 同一阶段相似度占总相似度比值示意图

6 结语

针对带权图数据中样本点的相似性度量问题，从样本点的属性信息和拓扑信息角度出发，构建了一种基于改进度中心性的样本点相似性度量方法.实验结果表明，该方法不仅能很好的区分样本点间关于拓扑信息的相似性，捕获样本点间邻居的拓扑相似性，而且在数值上能够明显的区分各个样本点间的相似性得分.