联合子图模式和网络表征的路网链路预测模型

王 斌,李毅磊,盛津芳,孙泽军,2,卢 奔

1(中南大学 计算机学院,长沙 410083)2(平顶山学院 网络中心,河南 平顶山 467000)

1 引 言

交通路网是城市社会经济活动和货物运输的重要载体.从网络拓扑的角度看,网络结构能够在很大程度上影响道路的运营效率[1].近年来,具有小世界和无标度特性的复杂网络因为契合很多现实网络,比如社交网络,万维网等,受到了越来越多学者的青睐和研究.复杂网络在社团发现、关键节点检测以及链路预测等方面都有了比较大的研究进展[2,3].很多学者将复杂网络相关理论应用于路网结构分析,如通过复杂网络社团发现理论研究路网结构稳健性[4],通过引入节点重要性分析局部攻击策略对路网系统的影响等[5].

作为复杂网络研究的重要分支之一,链路预测的主要任务是根据网络的拓扑结构、节点属性等信息预测网络中尚未连边的节点之间连边的可能性[6].链路预测与网络的结构与演化有着密切的联系[7],通过对整个网络未知边的预测可以从宏观上衡量网络演化的方向.将其应用于路网结构特征挖掘,对路网未来的演化进行合理的推测,从而给路网设计者提供有价值的信息,这在城市路网规划[8]中有着重大的意义.

在路网上进行链路预测研究具有很大的挑战性.首先,路网具有其特殊的结构复杂性,不同城市的路网的结构特征因为地理位置、经济水平、设计理念等的不同往往有着巨大的差异,这导致简单的启发式链路预测方法(如LP[9]、Katz[10]、SimRank[11]等)不能适用于所有的路网.其次,相较于蛋白质相互作用网络(PPI)、美国航空网络(NS)等,路网具有高度的稀疏性,以何种方法提取有用的路网结构信息也是一个关键的问题.最后,路网还有一定的特殊结构,比如路网多为平行的横纵交错道路结构,道路交叉口相关的道路往往只有两三条等等,如何在模型中表示这样的结构,提取其中的有效信息也是至关重要的.

对于路网特殊的复杂性,Zhang[12]提出的WLNM模型给我们提供了一个可行的思路.WLNM将子图模式[13]应用到复杂网络链路预测中,将待测边作为目标边,通过既定的规则构建节点个数一定的封闭子图,然后将子图的邻接矩阵作为特征参与到分类模型训练中.基于封闭子图的链路预测模型能够学习不同的网络结构特征,但是仅用邻接矩阵表示子图特征只能表现子图邻域的连接特性,对一些其它比较重要的信息(如节点之间的高阶相似性,子图在全局中的角色等)无法保留,这种信息的缺失在稀疏网络中表现更为明显.

基于随机游走的网络表征技术[14]将网络映射到低维向量空间中,实现节点的向量化的同时保留着网络结构特性.一方面,向量化的节点融合了整个网络的结构信息,含义更加丰富;另一方面,有效的随机游走策略可以很好地保持网络特殊结构,使得网络表征更有针对性.

基于上述分析,本文提出了一种针对路网的链路预测模型GRSC(General Road Subgraph Classification),将子图模型和网络表征有机地结合起来,共同作用于路网的链路预测.如图1所示,在模型中,我们首先根据路网的特殊结构和实际意义提出了一种新的基于随机游走的网络表征算法road2vec,将网络映射到d维向量空间,然后将目标边按照既定的排序选取规则生成包含k个节点的封闭子图,并根据其邻接矩阵构建子图结构特征,随后根据表征结果和子图节点序列生成对应的游走距离特征,与子图结构特征一起构建封闭子图的总特征,称之为广义路网子图特征.最后,通过logistic回归分类模型学习广义路网子图特征与节点连边之间的关系,进而完成链路预测任务.

相比于其它的链路预测方法,GRSC主要有以下几点优势:1)适应性强.模型在不同国家,不同结构的路网中均表现出良好的预测精度;2)稳定性高.当模型中的超参数达到一定阈值后,预测精度能够稳定地在一个小区间波动;3)可扩展性好.虽然整个构建过程比较复杂,但是对于每一个阶段,甚至某些阶段的各个步骤(如rode2vec),都是可以并行执行的,这大大提高了整体的可扩展性.

图1 GRSC模型原理图Fig.1 Schematic of GRSC

2 相关工作

2.1 网络表征技术

链路预测作为复杂网络研究热点之一,有着很多成熟的模型与方法.吕[7]等人在文献中对前人工作进行了总结,包含基于局部相似性指标方法(如基于一阶相似性的CN、PA指标等)、基于路径相似性指标方法(如基于高阶相似性的katz指标等)、基于随机游走的方法(如基于余弦相似性的CosPlus)等.这些经典的启发式方法在特定的网络中有着十分良好的表现,但往往适应性不强.

网络表征技术(又称网络嵌入技术)旨在将网络映射到低维向量空间中,使节点能够向量化表示,进而进行数据挖掘任务.复杂网络的网络表征算法主要分为三种:基于矩阵分解的方法、基于神经网络的方法和基于随机游走的方法.基于矩阵分解的网络嵌入技术主要对矩阵进行线性或者非线性的转化,从而将特征矩阵降维,如SVD[15]通过奇异值分解进行特征分解、SPC[16]通过谱聚类的方式进行相似变换等.基于神经网络的方法则是利用神经网络或者深度学习技术,学习网络特征,如LINE[17]利用机器学习方法、SDNE[18]利用深度学习方法学习网络的一阶和二阶邻域结构特征.特别地,自然语言处理技术的快速发展为复杂网络表征学习提供了新的思路,促使了基于随机游走的表征方法的产生.DeepWalk[19]采用了深度优先遍历算法进行随机游走,使用word2vec[20]算法进行表征嵌入,得到了节点在d维向量空间中的映射;Node2vec[21]对DeepWalk算法进一步优化,通过调节初始化的偏移概率增加探索邻域的灵活性.网络表征通常作为普适方法应用于不同的网络中,在多数情况下,将其直接用于路网链路预测优于一些经典的启发式算法,但针对性较差,需要额外的措施来提升效果.

2.2 子图排序算法

在基于子图模式的复杂网络相关研究中,基本思路是通过特定的选取规则和排序算法,从原始网络中生成一系列子图,继而对子图进行特征提取与分类,实现数据挖掘任务.在此过程中,子图排序算法至关重要,排序的好坏直接影响着子图对网络结构的刻画程度.一般情况下子图排序算法是一个迭代收敛的过程.Weisfeiler-Lehman[22]算法在每一次迭代中根据节点自身原有标签以及邻居标签来更新自身的标签,之后通过字典序对整个子图进行重新排序.Hashing-based WL[23]算法通过一个哈希函数对节点的标签赋予权重值以降低复杂度,但是容易出现迭代不收敛问题.最近,Palette-WL算法[12]结合了WL算法收敛性和Hashing-based WL时间复杂性低的优点,但其选取Nauty算法[24]作为最后的排序,从子图提取的有效信息较少.

3 模型的设计与实现

GRSC模型的主要思想是将目标边通过一定的规则生成一个包含k个节点的子图,结合路网表征算法road2vec,构建对应的广义路网子图特征,然后参与到链路预测分类训练算法中.整个模型的构建可以分为以下三个阶段:

1)通过road2vec进行路网表征.首先根据我们提出的随机游走概率模型获得路网游走序列,进而通过SGD算法学习到每个顶点的d维向量表示.

2)构建广义路网子图特征.根据一定的选取规则和提出的排序算法得到有序k个节点,生成封闭子图对应的子图结构特征,结合1)中学习得到的表征向量,生成游走距离特征,构建总特征.

3)通过logistic回归模型对广义子图特征进行训练,学习节点连边与广义路网子图特征之间的关系.

3.1 路网分析与定义

在GIS领域,对实际路网进行抽象通常会有两种方法:一种是广义拓扑方法,即将道路作为边,道路交叉口作为节点,如图2(b);一种是对偶拓扑方法,即将道路按名称映射为节点,道路的交叉口映射为边,如图2(c).相较于广义拓扑,对偶拓扑能更加深入地分析路网结构和道路特性,如道路间的连接关系,路网的连通性等.此外,对偶拓扑抽象出来的路网模型更加契合复杂网络的输入要求,因此采用路网对偶图作为研究目标.

通过对路网的分析,发现不同地域、不同城市的路网在很多方面差异明显,如一线大城市更多为环状方格状网络,而三线城市更多为放射状网络[25].与此同时,不同类型的路网在结构上又有着类似的特征,比如局部结构多为平行的横纵交错道路,道路交叉口相关的道路往往只有两三条等,而这些特征在对偶图里面以一种十分有趣的方式表现出来,称之为路网三角结构的特殊性.一方面,两个相邻的横(纵)干道(如图2(b)中的3,9),虽然与其共同相交的道路很多,但是两者基本不会有交叉口,这一特点阻碍了路网对偶图中三角结构的建立;另一方面路网对偶图虽然具有一定量的三角结构,但是基本是由三条路与其交叉口构成的,也就是类似图2(b)中的7,9,10三条路构成的.这一发现给我们的后续工作提供了重要参考价值.

图2 路网表示方式Fig.2 Urban road network representation

定义图G=(V,E)为一个无向连通图,其中V={v1,v2,…,vn}为顶点集合,E⊆V×V为图中无向边的集合,定义N=|V|为图G节点个数,M=|E|为边的个数.用邻接矩阵A来表示图G,如果vi与vj有连边则Aij=1,否则Aij=0.具体描述为:

(1)

定义d(vi,vj)为节点vi与vj之间最短路径长度,即从节点vi到节点vj之间所有路径的边数长度最小值.degree(c)代表节点的度.Γ(c)或者Γ1(c)代表节点c(c∈V)的所有路径长度为1的节点集合,即一阶邻居集合,Γn(c)代表节点c的所有路径长度为n的节点集合,即n阶邻居集合.特别的,Γ0(c)代表节点c本身.定义e=(vpair-0,vpair-1)为目标边,v={vpair-0,vpair-1}为目标节点对集合.

3.2 网络表征模型road2vec

本小节提出了一种新的基于随机游走的网络表征模型road2vec,将应用在路网上的随机游走策略赋予了具体的意义:模拟物体在真实路网上的行走过程.road2vec首先根据随机游走策略生成一系列的游走序列,然后根据游走序列对路网进行网络表征,将其嵌入到d维的向量空间中,最后根据表征结果定义节点与节点间的随机游走距离,作为子图特征的参照指标.

3.2.1 随机游走策略

为了模拟物体在实际路网上的行走过程,更好地使物体探索整个网络,设定了两个基本行走规则:

1)单方向行走.单方向行走有两个方面的表现:一是在单条路上行走过程不能折返;二是行走到某个交叉路口时,以很小概率选择原路作为行走目标.

2)有倾向性地选择.在选择下一条路的时候,倾向选择交叉口数目更多的路作为下一个目标,这样可以保证下次选择道路时有更多的选择,即有更大的可能对城市进行探索.

显然,根据这样的策略进行随机游走,我们会尽可能地远离起始点,对城市道路进行深度探索.

接下来探讨游走策略在路网对偶图中的具体实现.当行走到网络中某一个节点时,需要从当前节点的所有一阶邻居中选择一个节点作为下一个行走对象.如图3(a)所示,t为行走前一个节点,v为当前节点,Γ(v)={X1,X2,X3,t}构成了节点v一阶邻居集合.定义wvx(x∈Γ(v))为节点v与节点x的偏向权重,权重与行走的选择概率成正比,即权重越大则选择x为行走下一站的概率就越大.wvx的计算公式如下:

(2)

图3 随机游走策略在对偶图的实现Fig.3 Implementation of random walk strategy in dual graph

其中ε为常量,通常取很小的值,代表“返回权重”,即行走过程中折返的权重.d(t,x)表示节点t与节点x的最短路径长度,易知当d(t,x)取值为0时,x节点为t节点;d(t,x)取值为1时,说明t、v、x三个顶点构成三角结构,由三角结构的特殊性可知,此时选择x作为下一节点需要返回,违反了单向行走原则;当d(t,x)取值为2时将x的度作为偏向权重.定义px(x∈Γ(v))为选取x为下一行走节点的概率,可以得出:

(3)

图3(b)展示了当ε取0.01时的概率分布.

3.2.2 网络表征

通过游走策略得到一系列游走序列后,需要将路网表征到一个d维向量空间中,本文采用了与node2vec相同的方式,将特征学习表示为最大似然优化问题.

算法1.路网表征算法road2vec

输入:路网G=(V,E)、返回权重ε、表征维度d、每个节点游走次数n、游走长度l、上下文窗口大小w

输出:|V|×d矩阵W,代表所有节点的表征向量

1. Initializewalksto Empty

2. 根据式(3)计算概率集合P=calculate(G,ε)

3. foriter←1 tondo

4. for all nodesu∈Vdo

5.walk=rode2vecWalk(G,u,P,l)

6. appendwalktowalks

end for

end for

7.W=SGD(walks,w,d)

8. returnW

9.road2vecWalk(GraphG,nodeu,mapP,lengthl)

10. Initializewalktou

11. foriter←1 toldo

12.cur_node=walk[-1]

13.neighbors=GetNeighbors(cur_node)

14. Ifcur_node=u

15.next_node=find_next(cur_node,P,neighbors)

16. else

17.pre_node=walk[-2]

18.next_node=find_next(cur_node,P,pre_node,neighbors)

19. appendnext_nodetowalk

20. end for

21. Returnwalk

定义g:V→Rd作为网络节点到d维空间的映射函数.对于任意一个节点c∈V,Λ(c)⊂V代表以节点c作为行走起点,根据游走策略生成的游走序列节点集合,条件概率P(Λ(c)|g(c))代表节点c的特征向量出现其邻居节点的可能性,定义目标函数:

(4)

同样,为了使目标函数更容易处理,假设概率分布具有条件独立性,对于每个节点向量出现其邻近点的概率等于邻近点中每个点出现概率的乘积,可以得到如下式子:

(5)

另外,根据节点的对称性,源节点和图中其它节点在特征空间中具有彼此对称的效果.可以得出:

(6)

根据上式,我们可以将目标函数进一步优化为以下形式

(7)

其中,Zu=∑u∈Vexp(g(u)·g(v)).随后利用梯度下降算法stochastic gradient ascent(SGD)最优化目标函数,不难看出,Zu的计算需要遍历图中的所有节点,当图的规模非常大时需要很高的时间开销,因此采用负采样算法[26]提高效率.road2vec整体过程如算法1所示,其中road2vecWalk表示根据随机游走策略生成游走序列的过程.

通过road2vec将网络嵌入到d维空间,得到节点的向量表示,在此基础上,定义节点与节点之间的游走距离:

(8)

其中x,y∈V,代表图中任意两个节点,x、y代表x、y在d维空间上的表征向量.根据本节提出的游走策略和表征方法的目标函数可以得到一个合理的猜测:两个节点的游走距离越小,表明节点在向量空间上的距离越近,在路网上表示为两条道路出现在同一条游走序列的概率越大,两条路之间的关系对彼此越重要.

3.3 广义路网子图构建

3.3.1 子图结构特征构建

GRSC中目标边的子图结构特征为其封闭子图邻接矩阵的线性表示.封闭子图指的是从图的结构层面出发,结合路网表征算法,得到与待测节点对关系最紧密的k个节点,并按照特定的顺序重新构成的子图.显然,构建子图需要解决两个问题:一是以何种规则选取目标边相关的子图节点;二是如何对选取的节点进行排序,从而使子图特征更具代表性和普适性.

对于第一点,GRSC以目标节点对为中心,向外扩散的方式选取节点.具体方法为:首先选取目标节点对v的所有一阶邻居节点,判断此时选取节点数量是否大于k;不大于k则继续选取所有二阶邻居节点,以此类推.直到选出距离目标边距离最近的m(m≥k-2)个节点,与目标节点对共同构成子图节点集合Ψ(v).

得到了子图节点集合后,我们需要对子图节点进行结构化编号.此外,如果子图节点集合的节点数量大于k,还需要根据一定的规则淘汰掉一些节点,从而保证封闭子图是一个固定的包含k个节点的子图.这本质是一个迭代排序的过程.

定义rank(c)代表节点c此时的编号,节点的rank值越小代表节点排序越靠前,最后子图节点排序结果是按照rank值从小到大排列(没有重复的rank值).如果此时节点数量大于k,则取前k个rank值最小的元素作为边对应的封闭子图.

整个结构化编号过程可以分为初始标号、迭代排序和最终排序三个步骤,具体描述如下:

1)初始标号.为了保留节点选取规则的方向性,通过初始化rank值来保持节点选取顺序,对于子图中的所有节点c∈Ψ(v),用节点c与vpair-0和vpair-1的最短路径长度乘积作为点c的初始权重值:

d(c)=d(c,vpair-0)·d(c,vpair-1)

(9)

其中d(c)表示节点c的初始权重,d(c,v)表示节点c与节点v之间的最短路径长度.随后根据权重值序列对节点赋予初始rank值.直观地可以看出,待测节点对的初始权重都为0,故其初始rank值为1.距离待测节点对越远,其初始权重值就越大,对应的初始rank值越大.

2)迭代排序.根据PALETTE-WL算法对子图进行迭代排序,每次迭代中节点权重的更新公式为:

(10)

其中rank(c)代表当前节点c的rank值,φ(n)为第n个素数值.文献[12]证明了PALETTE-WL算法同时具有稳定性和一致性,且在子图节点数范围之内能够快速收敛.

3)最终排序.根据式(10)迭代收敛后,可能还有一些节点rank值相等,需要在保证rank值不同的节点序列不变的情况下对rank值相同的节点进行最后的排序.类比节点与节点间的游走距离,定义节点c与目标边e的随机游走距离:

wd(e,c)=sqrt(wd(c,vpair-0)·wd(c,vpair-1))

(11)

权重更新公式为:

(12)

根据此规则更新权重后,对子图节点进行最后一次排序,如果此时节点个数大于k,淘汰节点序列中的前k个之外的节点,得到个数为k且rank值从小到大的节点序列χ.最后,根据χ构建封闭子图,将子图邻接矩阵按行连接线性表示,作为子图结构特征s_feature.无论是否连边,我们都将邻接矩阵中目标节点对相应位置置0,这样可以在构造过程中去除目标边的影响.

3.3.2 游走距离特征

本节根据χ对子图结构特征进行拓展,将χ中所有节点(除了目标节点对)与目标节点对的游走距离作为新的特征加入到总特征的构建过程中,称之为游走距离特征(wd_feature).由节点排序算法的规则可以得出,目标节点对{vpair-0,vpair-1}在χ中始终占据着第一和第二的位置,所以构建游走距离特征的方法可以描述为,定义一个初始化为空的数组,从χ的第三个顶点依次向后遍历,对每次遍历的节点c∈χ,计算c在游走向量空间中与目标节点对之间的游走距离{wd(c,χ(0)),wd(c,χ(1))},计算完毕后将结果追加到数组的尾部.迭代k-2次,即遍历整个节点序列,此时数组就是我们所求的游走距离特征,特征所含元素为2k-4个.

随机游走距离的加入具有两方面的意义,一是从网络表征层面刻画了子图节点与目标节点对之间的相对位置关系,弥补了仅由子图结构特征所含信息的局限性.二是该特征的引入对应了在排序编号过程中式(12)的排序规则,使得排序和扩展具有形式和意义上的一致性.

至此,目标边的子图结构特征、游走距离特征已经构建完毕,两者结合构成了广义子图特征,即general_feature.整个构建过程如算法2所示,其中s函数的作用是根据权重大小重新调整节点序列顺序.

算法2.广义子图特征构建算法

输入:路网G=(V,E)、节点对v={vpair-0,vpair-1},子图节点个数k、表征矩阵W

输出:广义子图特征general_feature

1. 通过节点对扩散方法得到子图节点集合Ψ(v)

2. define Ψ(v) as χ

3. calculated(c) by(9)for allc∈χ

4.rank(χ)=s(d(χ))

5. whilerank(χ) has not converged do

6. calculate hashing valuesh(c) for allc∈χ

7. update allrank(χ)=s(h(χ))

8. end while

9. finally calculatewalking-distancel(c)

10. then updaterank(χ)=s(l(c))

11. 根据最终排序结果取前k个节点χ=pickTopK(χ,k)

12. 取封闭子图邻接矩阵线性表示作为子图结构特征:

s_feature=build-s-feature(G,χ)

13. 根据3.3.2描述计算游走距离特征wd_feature

14. 将两种特征线性结合得到广义路网子图特征

general_feature=combine(s_feature,wd_feature)

15. returngeneral_feature

3.3 训练分类模型

将得到的一系列目标边的广义路网子图特征作为输入,结合目标边的实际连边情况,训练logistic回归分类模型,从而学习连边与广义路网子图特征之间的关系,随后将训练好的模型用于路网链路预测任务中.

4 实 验

4.1 数据集构建

本文收集了包含中国和美国境内的6个城市路网作为数据集,每个路网对应的节点、边、平均度和聚类系数如表1所示.从表中可以看出,不同地区的城市路网规模具有明显的层次性差异.此外,虽然网络规模不同,但是数据集中路网的平均度基本稳定分布在在4左右,相对于政治博客网络PB(平均度31.2),UsAir网络(平均度12.8),蛋白质相互作用网络(平均度9.1),路网是比较稀疏的,这也从一定层面上反映出在路网上,子图结构特征所包含的信息量是比较少的.聚类系数代表网络的集聚程度,从表中明显可以看出路网集聚程度普遍较低.

表1 城市路网数据集
Table 1 Urban road network datasets

城市名称节点边平均度聚类系数HengYang.China72614303.930.192ChangSha.China5018104974.180.221BeiJing.China11319213223.770.203Rockford.USA4767105594.430.294Seattle.USA8191177324.320.244SanFrancisco.USA11669240674.120.242

4.2 评价指标

链路预测模型的预测效果评价方法一般都采用AUC[4]评价指标,AUC指标主要从模型的整体上来衡量预测的准确性,可以理解为在测试集中边的分数值比随机选择的一个不存在的边的分数值高的概率.当训练集中所有分数都是随机产生的时候,AUC的值会近似等于0.5,AUC超过0.5的大小代表链路预测模型比较随机模型的优越性强度,差值越大,说明预测效果越好.

4.3 实验对比

实验环境为:centOS 7,4核cpu,128G内存,实验方式为单线程顺序执行,无并发处理机制.

4.3.1 预测精度与时间耗费

本文将GRSC算法与5种类型,共15种链路预测方法进行比较.主要包括:

1)基于局部信息相似性指标的方法.这里相似性指标只考虑一阶相似性,选取了共同邻居指标CN、Jaccard指标、Adamic-Adar(AA)指标、优先链接指标PA四种;

2)基于路径相似性指标的方法.这里选取了考虑三阶邻居的LP(LocalPath),考虑高阶相似性的Katz指标以及考虑节点间路径期望值的LHN-II指标三种;

3)基于随机游走的方法.该类方法指定不同的随机游走策略评价节点之间的连边相似度,该类对比试验包括余弦相似性指标CosPlus,带重启的随机游走算法RWR,SimRank算法和局部随机游走算法LRW;

4)基于网络表征的方法.选取了三种不同类型的网络表征算法,分别为LINE,node2vec,SPC;

5)基于子图模式的方法WLNM.

在参数方面,设置katz的权重因子为0.001,LHNII的参数φ=0.9,RWR的返回概率为0.85,SimRank的衰减参数为0.6,LRW的有限步数为5.对于所有的网络表征算法,设置嵌入维度为128,对于Node2vec,设置其随机游走步长为50,节点遍历次数为10,Node2vec的概率值p=2,q=1.WLNMm表示子图节点个数选择为m.

对于GRSC,为了对比的公平性,设置表征维度d=128,节点游走次数n=10,游走长度l=50,返回权重默认设置为0.01.同WLNM类似,GRSC10代表子图节点个数为10,GRSC20代表子图节点个数为20,以此类推.

表2 对比算法在路网上的表现
Table 2 Comparison algorithm performance on the datasets

MethodHengYangChangShaBeiJingRockfordSeattleSanFranciscoTimeAUCTimeAUCTimeAUCTimeAUCTimeAUCTimeAUCCN0.020.6020.040.6970.100.7150.040.6880.060.6900.120.701Jaccard0.040.6042.350.69712.670.7162.350.6876.430.69113.050.701AA0.010.6040.450.6973.540.7160.410.6891.350.6913.630.702PA0.020.5940.220.5810.990.6030.190.6330.630.6051.020.674LP0.010.8110.050.8690.180.8530.060.9180.100.8670.210.872Katz0.030.8061.120.9036.280.8701.160.9283.190.8976.160.863LHNⅡ0.220.7734.940.90572.440.8824.560.87316.120.879105.370.836CosPlus1.390.873449.870.9532772.420.940249.090.9651219.680.9452957.170.944RWR0.130.8627.340.92141.330.8798.110.94820.650.91845.970.882SimRank0.140.8175.30.92540.280.9139.690.92332.590.919281.580.878LRW0.040.8600.70.9202.850.8931.430.9582.850.9286.380.915LINE1.230.8917.460.94717.550.92612.560.95014.390.94444.140.922Node2vec1.180.8678.40.94018.810.92311.960.95120.730.94120.840.931SPC1.290.830106.030.9521203.390.950102.440.955475.090.9601116.270.938WLNM10196.940.7181446.330.9492951.700.9591457.570.9532470.370.9503419.200.940WLNM20198.270.7041485.350.9353018.220.9381494.370.9482576.630.9483583.920.916GRSC107.790.90174.230.961230.230.96484.600.971158.180.966259.520.969GRSC2011.740.911115.520.968331.800.970122.950.973226.810.976354.450.977

图4 对比算法在路网上的平均表现Fig.4 Average performance on the datasets

各对比方法在时间耗费AUC准确度上的表现如表2所示.从表中可以看出,与对比算法相比,GRSC模型在所有数据集中都有着最好的表现,特别是在子图节点个数取到20时,在北京、Rockford、Seattle、SanFrancisco等4个城市路网中AUC指标在97%之上,而表现次优的方法在不同城市中不尽相同,如衡阳为LINE(89.1%)、长沙为CosPlus(95.3%)、北京为WLNM(95.9%)等.表明GRSC在不同路网的适应性更强,更能有效挖掘不同路网的结构特征.

图4(a)展示了对比实验的平均AUC指标.可以看出,基于局部相似性指标的方法精确度远远低于其他算法,其中表现最差的为PA算法,平均精确度不到65%,说明共同邻居相关的相似性对路网连边影响不大.基于路径相似性指标的方法表现仅优于基于局部相似性算法,其中Katz优于LP和LHN-II,表明基于高阶相似性的方法优于基于低阶相似性的方法.基于游走的方法、基于网络表征方法和基于子图模式的方法表现相对较好,且三者AUC指标相差不大,均处于90%-95%的范围内,说明随机游走方法和网络表征方法在路网上是有效的.在基于随机游走的方法中,CosPlus算法的平均AUC表现最好,同时超过了基于表征和基于子图的方法,在所有对比方法中排名第三.此外,基于网络表征的的方法精确度表现排序为SPC、LINE、Node2vec,效果微低于Cosplus与GRSC.GRSC模型在子图节点个数为10和20的时候平均AUC分别为95.5%和96.3%,领先于其它的对比算法.

图4(b)展示了对比试验的平均时间消耗.在所有对比实验中,耗时最短的是基于局部相似性指标的方法.耗时最长的为基于子图的WLNM模型,但其在预测精度上并没有展现出太大的优势,且在规模较小的城市衡阳中的AUC表现甚至低于基于路径相似性指标的方法,印证了单靠子图模式在稀疏路网上进行链路预测的局限性.GRSC模型在时间耗费上远低于精确度排名第3的CosPlus和排名第4的SPC.总之,无论是在预测精度还是时间耗费上,GRSC都表现良好.

4.3.2 超参数对结果的影响

本节主要探索GRSC模型的超参数对结果的影响,超参数主要包含子图节点数k、表征维度d、游走步长l.用控制变量法进行测试比较.图5展示了在嵌入维度为4,返回权重取0.01时子图节点数k对结果的影响.从图中可以看出,当k从3到9的过程中,AUC随着k的增加变化较快,但增加率一直变小,在k=12后趋于稳定.这一特点说明在其它参数固定条件下预测精度会随着k收敛.同样,我们采用类似的方法探究了表征维度d,游走步长l对结果的影响,结果如图6、图7所示.图中都表明在参数比较小的时候预测精度对参数变化十分敏感,但在参数超过某一阈值(图6中d=32,图7中l=64)后,AUC比较稳定地在一定区间内上下波动.这些现象说明GRSC具有一定意义上的稳定性.

图5 子图节点个数k对结果的影响Fig.5 Effect of k on the results

图6 表征维度d对结果的影响Fig.6 Effect of d on the results

此外,图7展示了不同返回权重ε对实验结果的影响,其中ε取4代表路网平均度.可以看出ε小于1时AUC明显高于大于1的表现,印证了随机游走策略规则的有效性.在取0.1和0.001时结果相近,表明相对较小的返回权重已经能够刻画路网结构.

图7 游走步数l对结果的影响Fig.7 Effect of l on the results

4.4 分析与讨论

实验展示了GRSC模型在路网数据集中有着十分好的表现,表明在模型实现上的一些假设和规则对路网链路预测是有着积极作用的.本节从一个新的角度解释模型的有效性.一方面,GRSC是根据广度扩散的方式选取目标边子图节点的,这样构建的子图结构特征维持着目标边在广度方面的邻域结构;另一方面,road2vec设定了比较小的返回权重ε,在图搜索层面相当于限制了广度游走的途径,更多地让节点深度游走,使得节点的表征更有全局特性.两者结合共同构建的广义路网子图特征兼顾目标边子图的广度和深度特性,将子图刻画地更有立体性,从而提升了子图表达的精确度.

5 结 论

本文提出的GRSC模型将复杂网络链路预测方法应用到路网中.在GRSC中,提出了一种新的针对路网特性的网络嵌入模型,使得游走策略在路网上更有意义.同时,将子图特征与网络嵌入有机地结合在一起,共同组成了广义路网子图特征,弥补了子图模式在稀疏路网中信息保留过少的缺点.在实验评估阶段,GRSC模型在不同国家,不同层次类型的路网上都有着比较良好的表现,超过了一些最近提出的网络表征和基于子图的方法.但是,该模型因为步骤稍显复杂,在无并行措施下消耗的时间比较久,不能很好地应对海量的路网数据.因此,设计一套可靠的并行方案以节省更多的时间是我们接下来研究的重点.