一种有向复杂网络生成模型的建立方法

刘大伟，杨文峰，王海洋，3，刘 玮，3

1(中国科学院 计算技术研究所烟台分所 烟台中科网络技术研究所，山东 烟台 264005)

2(中移(苏州)软件技术有限公司，江苏 苏州 215000)

3(中国科学院 计算技术研究所 网络数据科学与技术重点实验室，北京 100090)

1 引 言

网络作为一种刻画复杂系统的方式，已经广泛应用于各种网络数据应用中.在一个网络中，节点通常表示个体，链路通常表示节点之间的关联关系.链路挖掘(Link Mining)[1]成为热门研究领域，特别是结合上下文的交互分析和探索交互结构特征的分析等.通过拓扑特征来揭示网络功能，理解网络演化的本质规律成为链路挖掘的重要基础.大量研究提出了一系列链路挖掘的结构和关系模型.周[2]总结了现有的网络生成机制并总结为三个类别：宏观机制，例如富者更富，稳定性约束等；微观机制，例如相近性，集聚性和平衡理论等；中观机制，例如群体和社区的生成和变换.近期，随着在线社交网络的发展，链接数据以更为复杂的方式进行表示，尤其是越来越多的应用对应的底层网络模型开始使用有向网络进行刻画[3].现有的机制更多的是针对无向网络的观察和总结，缺少对于链接数据方向性的考虑.因此，本文关注有向网络的微观生成机制，提出一种新的链路生成方法.

在现实世界中有向网络普遍存在，例如WWW，食物链网络，学术合作网络和微博等社交网络.将网络数据挖掘问题用有向链路的生成模式来抽象和表达能够获得更多的洞察与分析结果.本文中，我们结合现有的机制，研究了有向表示下的网络生成模型，提出了一种链路生成理论，称为局部相关位置方法(Local Relative Position，LRP)，用来对网络演化机制进行刻画，可应用于不同的链路挖掘问题.我们选择采用链路预测应用并构建了基于真实数据集的实验来检验提出的理论方法的有效性.

2 相关工作

在复杂网络领域，尤其是社交网络的研究方向中，有很多链路生成的理论方法，包括无向和有向的配置.同时，许多针对网络生成理论演化出来的相似性指标已经用于链路预测的任务中.

早期的一些研究工作的研究对象多为社交网络、生物化学网络、生态学网络、工程网络等，旨在提出网络底层结构的生成机制和设计原则.Milo等[4]提出一种网络图式(Network Motifs)模型，通过局部的网络图式来刻画网络的内部链路间典型的模式.例如，在19个真实有向网络中抽象出13种由3个节点构成的链路子图模式，即13中网络图式.值得注意的是，相比于无向网络，有向网络具有更多更复杂的局部结构类型.以两个节点A和B构成的模式为例，局部结构类型从无向配置的1种(A-B)增加到有向配置的3种(A→B，A←B和A<->B).在社交网络的应用中，有向网络的链路生成模式比无向网络得到更多的关注和研究，尤其是微博网络，网络中的关注关系是不对称的.Golder等[5]研究了Twitter数据，构建了基于Web的实验分析，发现在新链路生成的过程中，传递性(transitivity)和相互性(mutuality)起到了重要作用，可以用来作为链路的预测算子.Yin等[6]研究了社交网络和信息网络，总结了新链路的关系类型分布，发现90%以上的新链路是在两条之内的局部结构中产生的.Garlaschelli等[7]关注链路的互惠性(reciprocity)，提出了一种新的互惠性度量方法，利用相互连接计算相关度并对网络链路进行重排.近期，Zhu等[8]通过研究发现在线社交网络里互惠链路比非互惠链路在信息扩散过程中起到了更重要的作用，并从网络连通性和效率的角度给出了分析.LI等[13]研究了微信用户网络，提出了一种基于平均场方法的演化模型，来刻画网络链路生成和动态传播机理.

本文采用链路预测来检验链路生成理论的有效性.近年来，链路预测已经作为复杂网络应用的一个典型问题，应用于各个领域的多个实际场景中.Liben-Nowellet等[9]首先定义了链路预测问题并提出了一系列基于节点相似度的方法，他们认为未来链接的信息可以只通过现有的网络拓扑结构来获取，节点相似性指标具有较好的效果.Zhou等[10]总结了复杂网络中的链路预测算法体系，一些代表性的工作包括基于节点邻居的方法，如共同邻居、Jaccard相似度，Adamic-Adar指标等.本文中，为了验证网络生成理论，我们假定网络中的链路生成倾向于以高概率存在的子图模式进行，这样刻画链路优先级的链路生成理论就可以用链路预测的结果来进行检验.基于同样的理论与实验设计，Romero等[11]研究了有向闭合结构，给出了2步路径类型的形式化定义和网络生成方法，并在Twitter数据集中进行了证实.Schall[12]研究了节点间的三角模式并在有向网络中应用于链路预测，提出了三角相似度指标的新算法.Liu等[18]研究了局部结构，提出了局部差异融合算法，优化了基于共同邻居的相似性指标.Zhang等[2]提出了一种有向网络中链路生成的模式：位势理论，并应用于链路预测获得了较好的预测效果.

3 有向网络生成模型

3.1 问题与定义

有向网络的链路数据表示为一个有向图G=(N，E)，其中N={x1，x2，…，xn}表示节点集合，E={eij}表示连边集合.相应的，每个元素eij=1代表一条从节点xi到节点xj的有向链路.基于有向图表示的网络，有如下概念定义：

定义1.一个图G=(N，E)被称为连通的当且仅当其不能被表示为两个图的组合，即不存在两个图G1=(N1，E1)和G2=(N2，E2)使得节点集合N1和N2不相交，其中N=N1∪N2，E=E1∪E2.

图的连通性表明节点集合N中的每两个不同的节点都通过至少一个节点序列连接在一起.本文研究的网络链路生成模式基于连通的图，不考虑非连通有向图的情况.

定义2.在图G中一个节点xi被称为支配另一个节点xy，则有eij=1且eji=0.

定义3.在图G中两个不同的节点xi和xy被称为等价，则有eij=1且eji=1.

定义4.在图G中节点xi支配的所有节点集合称为节点xi的后继.所有支配节点xi的节点集合称为节点xi的前趋.

根据支配状态和等价状态，我们能够区分有向图中两个节点的区别，进而可以对有向图中一个路径序列进行描述，为不同的节点生成刻画角色的分数.相应的，在我们的体系中节点有三种角色，分别定义如下：

定义5.一个节点xi∈N被称为头节点，当且仅当xi支配了至少一个节点xj∈N，即eij=1且不被任何一个节点支配，即不存在xj∈N，eji=1.

定义6.一个节点xi∈N被称为尾节点当且仅当xi被至少一个节点xj∈N支配，即eji=1且不支配任何一个节点，即不存在xj∈N，eij=1.

定义7.一个节点xi∈N被称为中间节点，当且仅当存在xj，xk∈N使得eij=1且eki=1，即节点xi支配其他节点且被其他节点支配.

图1 三节点模式的不同角色示意图Fig.1 Different roles of 3-node patterns

以三个节点构成的有向网络为例说明三种角色的定义，如图1所示，在A，B，C三个有向网络例子中，节点1始终是头节点，节点3始终是尾节点，节点2的角色有变化，在A网络中节点2是中间节点，在B网络中节点2是头节点，在C网络中，节点2是尾节点.

3.2 局部相关位置方法

根据以上定义，我们提出一种复杂网络链路生成模型的建立方法：局部相关位置方法.该模型基于如下思路：在有向网络中，存在某些特定的典型的模式；相比于其他模式，这些模式有较高概率在网络中重现.通过分析不同尺度的局部结构，我们能够得到一系列局部相关位置集合，可以用来度量节点之间的相似度.我们首先描述成成局部相关位置集合的通用过程，然后将模型应用于3节点模式和4节点模式并通过链路预测来验证方法的有效性.

在有向网络中，具有不同功能、能量或者作用的节点具有不对等的位置信息，从而导致边的有向性和不对称性，这也是有向网络与无向网络的主要区别之一.我们定义一种特殊的度量(局部相关位置)来提取这种因为方向造成的不对等信息，进而通过子图中所有节点的位置和所有有向链路来刻画每个节点的特征.令S⊂N为节点集N的一个子集，GS=(S，ES)是有向图G的一个子图，那么对应于子图GS中一个节点xi的局部相关位置度量为一个向量lrpi，定义为：

(1)

其中c∈R是一个由子图确定的常量.D(xi)是节点xi的后继节点集合，P(xi)是节点xi的前趋节点集合.对于整个图来说，以矩阵形式描述为：

MS·lrp=cIS

(2)

其中lrp是对应于节点集合xi∈S的向量，IS是单元向量，MS是参数矩阵，其构成元素确定如下：

Mii=1 对角线置1

图2 3节点模式的有向网络链路模式Fig.2 Link pattern of 3 nodes directed network

作为一种链路生成机制，我们相信局部相关位置理论能够揭示一些底层网络演化过程中隐含的规律.参考文献[2]的思路，我们考察了3节点和4节点构成的所有模式，并设计对应的链路预测方法.如图2所示，3节点有向网络能够构成的链路模式一共有9种，其中下标代表连接的方向性，包括接入i，接出o，和双向m.相比于文献[2]，我们考虑了双向链路，因此在我们的定义下，链路具有更为复杂的类型.对每一个模式，移除其中一个链路，如图2中虚线所示，可以得到新的子图，通过计算移除前后子图结构的局部相对位置度量的变化，可以得到每种模式生成所对应的权重.具体的，在3节点模式下，分别计算该链路存在和不存在对应的局部相关位置方法计算的节点位置向量，节点位置向量的差值即为对应的权重变化.

如表1所示，为3节点网络中所有9种模式对应的权重分数.

一个新产生的链路对于网络整体的贡献作用可以通过局部相关位置方法来确定.可以利用某一种类型的模式，如3节点模式，也可以利用多种类型模式的组合，如3节点和4节点模式，来生成一个该链路用于预测的分数.当前未连接的链路预测分数定义为这个链路产生后带来的分数之和.在3节点模式定义下的链路预测分数为：

表1 3节点模式权重分数表Table 1 Weights of 3-Node patterns

(3)

其中Slink表示链路的预测分数，Si表示特定类型模式中不同的权重分数，如Soo，Tnew是所有新产生的相关模式的总和.具体的，统计得到每个节点在该链路不存在时对应的9种链路模式个数，再统计得到每个节点在该链路存在时对应的9中链路模式个数，差值即为每种模式所对应的权重总和，用来刻画该链路存在与否对全网的影响.

同理，4节点模式的权重分数表(如表2所示).

表2 4节点模式权重分数表Table 2 Weights of 4-Node patterns

相应的，在4节点模式定义下的链路预测分数为：

(4)

4 实验及验证

4.1 评估方法和实验数据

我们用链路预测来检验所提出的网络链路生成方法.采用标准的评估指标AUC(Area Under the receiver operating Characteristic)来表示链路预测的准确性[14].在具体计算过程中，我们随机选择一个存在的链路，与另一个随机选取的不存在的链路比较链路预测分数.在n次独立实验对比后，得到nad次该链路的预测分数大于随机选取的不存在链路，neq次该链路的预测分数小于随机选取的不存在链路，那么AUC指标定义如下：

(5)

在随机方法下AUC指标值为0.5，实验中AUC指标值超过0.5的程度表示了对应的链路预测算法的有效程度，AUC指标值最高为1.我们选取了4种经典方法[15]来与本文提出的方法进行对比实验.选取的算法包括：

1)CN(Common Neighbors)：Scn=|D(xi)∩P(xj)|

4)PA(Preferential Attachment)：SPA=kout(xi)×kin(xj)

其中Γ(xi)=D(xi)∪P(xi)表示节点xi的邻居集合，kin(xj)和kout(xi)分别表示节点xi的入度和出度.

我们选择了4类有代表性的真实世界中不同领域的有向网络数据集作为实验数据.其中，Wikivote是从英文百科网对2794次选举产生的有向网络[16];Political Blogs是由美国政治博客间的网页超链接构成的有向网络[17]；Celegans是由一种线虫的神经网络构成的有向网络[19];Sina Weibo是通过爬取得到的新浪微博数据，我们随机选择了1000个VIP用户及其之间的关注关系构成有向网络.

4.2 实验结果分析

对于每种个数据集，我们采用3节点模式和4节点模式两种方法，与四种现有算法进行AUC指标的对比.链路预测的实验结果如图3所示.从三个方面进行分析：

图3 链路预测AUC指标Fig.3 AUC of link prediction methods

1)基于局部相关位置度量的方法在Wikivote，Political Blogs和SinaWeibo三个社交网络数据集的实验结果优于其他最好的方法，3节点模式AUC指标提升7%以上，4节点模式指标提升12%以上.但在Celegans生物网络数据集的实验中，本文提出的方法结果不如CN和AA方法，这说明局部相关位置理论更适用社交网络，对于刻画生物网络底生成机制不适合.

2)计算复杂度方面，传统方法中CN算法复杂度为O(n2)，其中n为网络节点数.AA算法复杂度为O(2n2)，RA算法复杂度为O(2n2)，PA算法复杂度为O(2n).对应于本文给出的两种模式，3节点模式的计算需要统计每个节点2跳相通的节点集合，可得计算复杂度为O(9n2)，同理4节点模式的复杂度为O(27n3).相比于传统方法，本文提出的方法在计算性能方面都具有非监督相似性指标的计算复杂度较低的优势.

3)在所有的4种数据集的实验结果中，4节点模式AUC指标都优于3节点模式AUC指标.这说明考虑子图模式类型时，包含更多的节点，更多的链路，更多的模式会提升网络表达的效果，进而提升链路预测的AUC指标.但考虑包含更多节点的模式会导致模型复杂度提升，节点模式类型过多增加了计算量，处理效率会显著降低，因此，理解网络微观机制仍然是一个具有挑战性的问题.

4)局部相关位置方法在新浪微博数据集SinaWeibo中相比其他方法AUC指标提升更为显著.原因是我们在设计链路生成理论时时，采用了一些与微博网络机制一致的假设，如互惠性，传递性(Soo)，共同关注(Soi)，共同粉丝(Sio)等.局部相关位置方法整合了以上常见的模式，所以能够在社交网络领域取得更高的预测准确率.

5 总 结

本文中我们提出一种链路生成理论，称为局部相关位置方法，在微观组织机理刻画有向复杂网络链路生成的模式.结合现有的链路预测算法，我们设计了两种链路预测指标，分别基于3节点模式和4节点模式.在4种真实世界的有向网络数据集上的实验证明了局部相关位置方法在新生成链路预测方面的有效性.作为一种底层网络生成机制的理论，局部相关位置方法可以扩展应用到社交网络分析，朋友推荐，社区发现等多种应用场景.发现有向网络生成的影响因素，总结链路生成模式是一个具有挑战性的研究问题，在未来的研究中，我们将扩展所分析的子图的规模，并结合应用领域的特点，在更复杂的假设下提出新的链路生成理论.