软件学报  2014, Vol. 25 Issue (11): 2602-2615   PDF    
信息网络中一个有效的基于链接的结点相似度度量
张应龙1,2, 李翠平1, 陈红1    
1. 数据工程与知识工程教育部重点实验室(中国人民大学), 北京 100872;
2. 华东交通大学 软件学院, 江西 南昌 330045
摘要:信息网络无处不在.通过把网络中的对象抽象为点,把对象之间的关系刻画为边,相应的信息网络就可以用图来表示.图中结点相似度计算是图数据管理中的基本问题,在很多领域都有运用,比如社会网络分析、信息检索和推荐系统等.其中,著名的相似度度量是以Personalized PageRank和SimRank为代表.这两种度量本质都是以图中的路径来定义,然而它们侧重的路径截然不同.为此,提出了一个度量SuperSimRank.它不仅涵盖了这些路径,而且考虑了Personalized PageRank和SimRank两者都没有考虑的路径,从而能够更加体现出这种链接关系的本质.在此基础上对SuperSimRank进行了理论分析,从而提出了相应的优化算法,使得计算性能从最坏情况O(kn4)提高到O(knl).这里,k是迭代次数,n是结点数,l是边数.最后,通过实验验证了SuperSimRank优于SimRank和Personalized PageRank,同时验证了优化算法在各种情况下都是有效的.
关键词随机游走     相似度度量     SimRank     Personalized PageRank    
Effective Link-Based Measure of Node Similarity on Information Networks
ZHANG Ying-Long1,2, LI Cui-Ping1, CHEN Hong1    
1. Key Laboratory of Data Engineering and Knowledge Engineering of Ministry of Education of China (Renmin University of China), Beijing 100872, China;
2. School of Software, East China Jiaotong University, Nanchang 330045, China
Corresponding author: LI Cui-Ping, E-mail: cuiping_li@263.net
Abstract: Information networks are ubiquitous. These networks can be modeled by graphs where nodes refer to objects and edges are relationships between objects in the networks. Measuring nodes similarity in a graph is a fundamental problem of graph data management. There are many real-world applications based on similarity between objects, such as networks analyses, information retrieval and recommendation systems. A number of link-based similarity measures have been proposed. Both SimRank and personalized PageRank are the most popular and influential similarity measures. The two measures differ from each other because they depend on different paths. This paper proposes a similarity measure that takes advantages of both SimRank and personalized PageRank. The new measure strengthens the principle of SimRank: "Two objects are similar if they are referenced by similar objects". The paper also analyzes the new similarity measure in theory and proposes an optimization algorithm which reduces the time cost from O(kn4) to O(knl) where k is the number of iteration, n is the number of nodes and l is the number of edges. Experimental results demonstrate the effectiveness of the new similarity measure and efficiency of the optimization algorithm.
Key words: random walk     similarity measure     SimRank     personalized PageRank    

图数据管理与挖掘是当前数据管理的研究热点之一,基于链接的相似度度量是其中研究的一个基本问题.它在现实中有很多应用,比如链接预测[1]、协同过滤[2]、角色分析[3]、异常检测[4]和个性化推荐[5]等.现已提出许多基于链接的结点相似度度量,比如Random Walk With restart(RWR)[6],Personalized PageRank(PPR)[7], SimRank(SR)[8]以及Hitting time[9].其中,PPR和SR最有影响力的.

PPR算法源于促使搜索引擎巨大成功的关键技术之一的PageRank算法,它也应用在Twitter公司的朋友推荐服务中[5].PPR近两年在学术界得到了广泛的研究,例如对它进行优化计算[10, 11, 12].RWR是PPR的特殊形式:当PPR感兴趣的点的集合只有1个点时,PPR就是RWR.而SR也有很多应用——社会网络的链接预测[1]和推荐系统[13]等.最近,SR也得到了较多的研究——图上的基于SR相似连接(similarity join)查询[14, 15]以及SR的优化计算[16, 17].既然PPR和SR无论在应用还是在研究当中受到这么多的关注,能不能参考这两个度量的优点,设计出一个更优秀的基于链接的相似度量呢?为此,我们首先对这些度量进行分析.

根据对两点间的路径侧重点不同,把这些度量分为两大类:

· 一类是以SR为代表的度量.SR计算图中两点相似度是基于人们这样的直觉:如果两个对象同时被相同或相似的对象所引用,那么这两个对象是相似的[8].反映在网络上,实际上是考虑了如图 1所示的路径,用随机游走模型解释为:点a和点b的相似度是指两个冲浪者分别在点a和点b出发同步逆向游走当且仅当第1次相遇的期望值[8].为了文中叙述方便,把如图 1所示的路径称为逆向共同引用路径.

Fig. 1 Reverse symmetric paths图 1 逆向共同引用路径

· 另一类是以PPR为代表的包括RWR,Hitting time的度量.它们考虑了如图 2所示的路径,点a和点b的相似度越高表示从点a出发随机游走遇到点b的概率越大.文中把如图 2所示的路径称为单向路径.

Fig. 2 Unidirectional paths图 2 单向路径

现通过一个具体例子来说明.图 3给出了一个文献引用图,有向边áa,bñ表示论文a引用了论文b,该文献引用图对应的部分结点对的相似度的值见表 1.

Fig. 3 Citation graph图 3 文献引用图

Table 1 Similarity scores of some node-pairs in the citation graph (Fig. 3) 表 1 文献引用图(图 3)部分结点对对应的相似度

表 1中可以看出:(b,d)的SR值为0.25,这是因为bd之间存在一条逆向共同引用路径:b¬c®d,表中的其他结点对之间不存在类似这样的逆向共同引用路径,因此,它们的SR值都为0.表中第3列对应的是PPR的值,与SR不同的是,PPR的值不具有对称性,即,(a,b)和(b,a)的PPR值是不同的;从cb之间存在单向路径,所以对应的PPR值是0.133,而其他的结点对之间不存在这样的单向路径,所以对应的PPR值为0.

从上面这个例子发现:SR和PPR考虑的路径是不同的,有些结点对的SR值非0而PPR值却是0;反之亦然.有些结点对的SR和PPR值同时为0,比如(a,f )和(b,f ),但是从图中可以观察到:d引用了e,那么de是相似的;而ed又分别引用了af,所以af被相似的cd分别引用.根据“如果两个对象同时被相同或相似的对象所引用,那么这两个对象是相似的”这一原理,得出结论af是相似的;类似地,也可以得出bf相似.而这样的路径也符合人们的基本认识,例如,儿子(小明)¬父亲¬祖父®叔叔(张三),小明和张三具有血缘关系是因为小明的父亲和张三的父亲是父子关系.但是这些本应相似的结点对对应的SR和PPR值却都为0.

通过以上分析和讨论可知,这些度量要么侧重于逆向共同引用路径,要么侧重于单向路径.虽然实践应用表明这两大类路径对结点间的相似度都很重要,但是分析发现,它们仍然对一些符合人们基本认识且有用的路径没有考虑到,导致一些结点对相似度为0.因此,能不能提出一个新的度量,把PPR和SR的优点有机的结合起来,同时能够考虑到更多的路径从而更加全面地体现出链接关系的本质呢?这个问题就是本文研究的出发点.

本文针对上述问题提出一个新的相似度度量.该度量有机地结合了逆向共同引用路径和单向路径,进一步加强SR原理,并从理论上分析该度量的合理性(第1节).对新公式进行变换,变换过程实际是对新公式深入分析的过程,同时发现,新度量涵盖3大类不同的路径.在此基础上,设计优化算法(第2节).然后,通过实验对该度量的质量和算法的效率进行验证(第3节).最后给出相关工作(第4节)和结论(第5节).

1 SuperSimRank

给定有向图G=áV,Eñ,I(v)={u|áu,vñÎE}表示图中结点v的入度邻居集合,Ii(v)(1≤i≤|I(v)|)为该集合中的一个元素;O(v)={u|áv,uñÎE}表示图中结点v的出度邻居集合,Oi(v)(1≤i≤|O(v)|)为该集合中的一个元素.为了方便理解,首先对SR和PPR做一个简介.

1.1 SR和PPR简介

SR相似度公式规定:结点对结点本身的相似度最大,例如S(a,a)=1.从公式中可以知道:两个结点的相似度,是它们的入度邻居之间相似度的平均值.关于SR的详细信息可参见文献[8].

与PageRank不同的是,PPR强调的是个性化,随机冲浪者以概率c沿着链接游走,在每一步游走的同时,以概率1-c跳到他感兴趣的点,如果他感兴趣的点的集合只包含1个点q,那么对应的PPR公式为

这里,t表示点qv的单向路径:(q,w1,…,wn,v),表示该单向路径的概率,l(t)表示该路径的长度;r(q,v)的值表示在点q观点下,它与v的相似度值.

而在实际中,利用公式来快速计算,详情见文献[7].

1.2 SuperSimRank公式

文中把点a和点b的SuperSimRank值表示为M(a,b),并把SuperSimRank简记为SSR,对应的公式为

(1)

这里,

在上述公式中,c为常数取值0.5,且a¹b,t:a®bab的单向路径,l(t)为该路径的长度,p(t)是为ab的单向路径的概率.规定:结点对结点本身的相似度最大为1.

规定初始值M0(a,b):当a=b时为1,否则为0.

SSR对应的公式(1)是迭代公式,公式分为两部分:第1部分与SR公式形式相同;第2部分TK+1实际是abba的PPR值的平均值,取平均值的原因是为了度量值具有对称性,即abba的SSR值相同.所以,TK+1的值同时参考了ab的观点.

公式(1)给人的错觉就是简单地把SR和PPR求和,其实不然.公式(1)除了考虑了图 1的逆向共同引用路径和图 2的单向路径以外,还考虑了如图 4所示的路径.在图 4中,路径长度分别为3和4,椭圆虚线框起来的路径对应的值包含在上一次迭代的TK中,而TK值加在对应的MK上,因此在下一次迭代中,通过公式(1)的第1部分把相似性扩散到ab上.这加强了SR的原理:两个对象是相似的,是因为它们被相似的对象所引用.与SR不同的是,这里相似的对象是通过单向路径得到的(图中虚线内的部分).

Fig. 4 New paths that SuperSimRank considers图 4 SuperSimRank所额外考虑的路径

综上所述,SSR不仅考虑了逆向共同引用路径和单向路径,而且扩展了SR原理,考虑了更多的SR和PPR之前没有考虑过的路径.表 1的第4列就是对应的SSR值,可以看出,公式(1)很好地解决了之前存在的问题.

1.3 SuperSimRank性质

公式(1)是一个迭代的公式,它作为一个度量必须保证是收敛有极限,因此用如下定理描述:

定理1. SSR迭代公式(公式(1))具有以下性质:

1. 对称性:Mk(a,b)=Mk(b,a).

2. 单调性:Mk(a,b)≤Mk+1(a,b).

3. 极限存在且唯一.

证明:

1. 从公式定义可以看出,显然其具有对称性.

2. 单调性:Mk+1(a,b)在Mk(a,b)考虑的路径基础上,又考虑了长度为k+1的路径,因此,Mk+1(a,b)比Mk(a,b)多了长度为k+1的路径的贡献值.第2.2节中的公式(4)很好地反映了SSR是单调递增的.

3. 极限存在且唯一:假设a¹b:

· k=1:

因为文中M0(c,d)(当c=d时)取值为1,表示自己对自己完全相似,因此,为了使M1(a,b)小于1,对c的取值是0.5.在以下的证明中,假设Mk(Ii(a),Ij(b))能够取到最大值1,而且单向路径的概率是小于1,所以有以下不等式 成立:

· k=2:

· k=n:

因此,数列{Mk(a,b)}单调递增有上界,所以,数列收敛且极限唯一.证毕.

公式(1)的上述属性确保了它能够作为相似度的度量.证明中发现Mk(a,b)<2c,因此,为了使度量值不超过1,文中对c取常数0.5.

2 SuperSimRank计算算法 2.1 Naïve方法

直接计算SSR度量实际上是在每次迭代中对公式(1)中的两部分分别计算,然后求和.假设图Gn个结点,每个结点的平均入度(出度)为D,共有n2个结点对.第1部分和SR形式一致,因此,根据文献[18]计算第1部分值的时间复杂度是O(n2D2),最坏情况是O(kn4);第2部分实际上是求单向路径的概率,我们可以在上一次迭代的长度为k的路径(最多有n2)的基础上再随机游走一步,可得到当前路径的值,那么第2部分的时间代价是O(n2D).因此,总的时间复杂度是O(kn2D2),k为迭代次数.当D的值接近n时,时间复杂度变为O(kn4).Naïve 方法代价太高,需要更好的方法去计算它.

2.2 优化方法

为了引入优化算法,我们将公式(1)变换为如下形式:

(2)

这里,当x=y时,t¢表示冲浪者分别从ab逆向同步游走且第1次在点x相遇,路径长度l(t¢)为逆向同步游走步数且d为0;否则,(x,y)表示xyyx的单向路径且对应路径长度是d;同时,(x,y)®(a,b)表示冲浪者分别从ab逆向同步游走且同时分别抵达点xy,逆向游走步数是m,则对应的l(t¢)取值是m,dm满足d+mk+1.t¢图 5所示,图中只画了从xy的单向路径,对应的路径概率为

(3)

这里,

下面通过引理1来说明公式(1)和公式(2)相同.

引理1. SuperSimRank迭代公式(1)与公式(2)相同:

详细证明见附录1.

由上述公式变换可知,新度量涵盖了3大类路径:逆向共同引用路径、单向路径和如图 5所示的路径.图 5所示路径加强了SR的原理:两个对象是相似的,是因为它们被相似的对象所引用;同时,这也符合人们的基本认识.

Fig. 5 Paths of t¢ (x¹y)图 5 t¢对应的路径(x¹y)

利用公式(2)可以把SSR迭代公式写成

(4)

其中,d表示从xy或从yx的单向路径的长度,如果x=y,则d为0.

从公式(4)知:第k+1步的SSR值实际上就是把对应长度为k+1的路径的贡献值累加在上次的结果上(这里,我们把满足(d+l(t¢))=k+1的路径也称为长度为k+1的路径),优化方法就是基于公式(4)的,从公式中可知,计算第k+1步SSR值的关键就是如何有效地计算出对应长度为k+1的路径的贡献值.

计算长度为k+1的路径的值的有效方式是,在长度为k的路径基础上再走一步即可.为此,我们采取以下 措施:

1. 每次保留上一步长度为k的路径t¢和单向路径;

2. 原来采取逆向游走的,现采取同向游走,原因是方便在长度为k的路径的基础上得到长度为k+1的路径的值;

3. 路径t¢:(x,y)®(a,b)只用(a,b)表示(规定ab),目的是合并路径:每一次迭代把结点对(a,b)相同的t¢合并在一起,同时,把当前的从ab或从ba单向路径加在(a,b)上.

假设e,f分别是a,b入度邻居结点,从e,f顺向出发走一步可分别到达a,b,长度为k的合并后单向路径和路径t¢分别表示为

那么,

这时,公式(4)可以写成

Mk+1(a,b)=Mk(a,b)+wk+1(a,b) (5)

通过以上分析得到了优化算法,见算法1.

算法1是优化算法,第1行~第10行是计算u1w1的值;第13行~第17行假设e,f分别是a,b入度邻居结点,每一行中是对所有可能的结点对进行相应的操作,其中,第15行和第16行的计算代价最高,wm(e,f)(pwm(f,a))共有n2个,对e(f)的每个出度邻居a(b),计算pwm(f,a)(wm+1(a,b)),所以时间代价是O(n2D).因此,算法1的时间代价是O(knl).这里,l=nD.

Fig. 6 Algorithm 1图 6 算法1
3 实 验

实验的运行环境为i7-2620MCPU,8GB内存和Windows 7操作系统.文中算法采用C++实现.

实验主要考察3个方面:一是评估SSR度量的质量,即通过与SR和PPR相比较,SSR度量是不是具有优势;二是效率的比较,将优化算法和Naïve算法进行比较;三是考察SSR度量的收敛速度.

为了使所有实验都能重复实现且真实可信,所有的真实数据都可以从网上下载,生成数据是用开源软件生成的.

真实数据集1:真实数据集采用CiteSeer和Cora数据集(http://www.cs.umd.edu/projects/linqs/projects/lbc/ index.html),数据集记录了文献引用关系,组成了文献引用网络,数据集中的论文已根据主题分了类,具体信息见表 2;CiteSeer共有3 312个结点,4 715条有向边;而Cora共有2 708个结点,5 429条有向边.在文献引用关系中,如果论文i引用了论文j,那么存在一条有向边ái,jñ.

Table 2 Distribution of papers over topics 表 2 基于主题的论文分布

文献引用图具有一定的代表性:(1) 在文献引用图中,论文之间引用是因为它们有某些共同点或有借鉴之处,这与其他网络类似.其他网络结点间具有关系也是因为它们具有某些相似处或借鉴之处,例如社交网络用户相互关注是因为他们有某些共同兴趣或某些方面吸引到对方.(2) 在实验中,两个文献引用图在对主题的划分粒度上不太一样,CiteSeer划分为大方向的主题,而Cora划分为小而具体的主题.这两个真实数据集具有不同的特点.

真实数据集2:Twitter社会网络数据集(http://snap.stanford.edu/data/egonets-Twitter.html).在这个数据集中,分别选择了编号为2363991和819800的Twitter图.图中如果用户a关注用户b(a follow b),就存在一条从ab的有向边.编号为2363991的Twitter图共有214个点,4 462条边,这些点被划分在9个不同的圈子(circles),有的点可以属于多个圈子(下同).编号为819800的Twitter图共有91个点,2 400条边,这些点被划分在10个不同的圈子.

这4个真实数据集是用于评估SSR质量的.我们采用文献[19]中类似的公式来进行评估:

这里,符号topA,N(v)表示用算法A求出关于结点vN个最相似的点的集合,similar(v)作为ground truth,表示与v属于同一个主题的论文的集合或与v属于同一个圈子的用户的集合.

图 7~图 12是分别在文献引用图这两个数据集上各随机取了200个点后算出的平均值.从图中可以看出:SSR明显好于SR和PPR;PPR在Cora数据集上优于SR,SR在CiteSeer数据集上优于PPR.

Fig. 7 Average precision over Citeseer图 7 在CiteSeer上的平均precision

Fig. 8 Average recall over Citeseer图 8 Average recall over Citeseer

Fig. 9 Average F-score over Citeseer 图 9 在CiteSeer上的平均F-score

Fig. 10 Average precision over Cora图 10 在Cora上的平均precision

Fig. 11 Average recall over Cora图 11 在Cora上的平均recall

Fig. 12 Average F-score over Cora图 12 在Cora上的平均F-score

因为Twitter图上有的点可以属于多个圈子,所以为了计算方便,我们找出所有只属于1个圈子的点.编号为2363991和819800的Twitter图中,这样的点的数目分别为158和32,图 13图 14就是这些符合条件的所有点算出的平均值.因为两个数据集上recall,F-Score变化趋势与对应的 precision图一致,所以为了节省空间没有列出.从图中可以看出,在两个不同的数据集上,SSR均优于PPR和SR.

Fig. 13 Average precision over Twitter graph of No.2363991图 13 在编号为2363991的Twitter图上的平均precision

Fig. 14 Average precision over Twitter graph of No.819800 图 14 在编号为8198001的Twitter图上的平均precision

以上实验迭代次数都是20,经验证,在这些数据集上,SR和PPR经过20次迭代都已收敛.通过在4个不同真实数据集上的比较,尽管SR和PPR在不同数据集上变化较大,然而SSR整体上始终优于SR和PPR.

本文的着眼点是度量的准确性,而不是计算速度.优化后,三者的计算复杂度一致,但SSR的值包含了对应的PPR和SR的值,理论上,在相同迭代次数下,计算SSR比计算PPR和SR要稍慢一些,采用文中介绍的优化方法对3个度量在Cora和CiteSeer上进行计算,图 15图 16是在不同迭代次数下,三者的对应运行时间,在最坏情况下,SSR要比另外两个慢0.5s,而这样的差距是很小的.因此,SSR的计算速度是可以接受的.

Fig. 15 Runtime of SSR, SR and PPR over Cora图 15 Cora上的SSR,SR和PPR的运行时间

Fig. 16 Runtime of SSR, SR and PPR over CiterSeer图 16 CiterSeer上的SSR,SR和PPR的运行时间

然后进行效率的比较.优化算法和Naïve算法除了在上述文献引用图的两个真实数据集外(因为Twitter图结点数比较少,所以以下实验没有采用这些数据集),又人工生成一系列数据进行了比较.所有的迭代次数都是8.

图 17是在这两个真实数据集上运行时间的比较,图 18是在不同生成数据集(使用networkX(http:// networkx.lanl.gov/index.html#)生成,下同)上的运行时间,在这些数据集中,结点的平均出度是3.图 19是1 000个结点上不同平均出度下的运行时间.从图中可以看出:无论何种情况,优化算法都明显快于Naïve方法.

Fig. 17 Runtime of optimize algorithm versus runtime of Naïve algorithm over Cora and CiteSeer图 17 优化算法和Naïve方法在Cora和CiteSeer上的运行时间比较

Fig. 18 Runtime on generated dataset of varying size图 18 不同规模的生成数据集上的运行时间

Fig. 19 Runtime on dataset of varying average degree图 19 平均度数不同的数据集上的运行时间

接下来,在生成数据和真实数据集上考察SSR的收敛性.这里,通过当前迭代的值与上次迭代值的差值来表示收敛性.如果差值为0,则说明迭代并没有使值发生变化.在实验中,我们选取了所有在第1次迭代后SSR值非0的结点对,然后在每一次迭代中,利用这些结点对算出一个平均SSR值,求出相应的差值.图 20是我们在不同生成数据集上的一组实验.这些数据集结点数都是1 000,出度分别从3增加到7.从图中可以看出,第8次迭代的结果值与第9次值的差值已经很小了.图 21是在两个真实数据集上的结果,从图中我们可以看出,只需迭代5次就足够了.因此,我们建议一般情况下迭代8次即可.

Fig. 20 SSR convergence over generated dataset of varying degree图 20 SSR在度数不同的生成数据集上的收敛情况

Fig. 21 SSR convergence over real dataset图 21 SSR在真实数据集上的收敛情况
4 相关工作

图数据管理与挖掘得到了广泛的研究,例如最短距离(shortest path)[20]、可达性(reachability)[21]、图聚类(graph clustering)[22]和图模式匹配(graph pattern matching)[23]等.基于链接的相似度度量,是图数据挖掘中的基本问题之一[19].

相似度度量可以划分为两大类[18]:基于文本(内容)的和基于链接的度量.本文提出的SSR以及RWR,PPR, SR和Hitting time都是基于链接的相似度度量.

除了上述度量之外,P-rank[24]是SR的扩展,但它同时考虑了入度和出度链接.然而,如果两点之间的路径只是如图 2所示那样,那么P-rank会把这样结点对的相似性也视为0;而我们的SSR却能算出这样的结点对的相似性.另外, SimRank++[2]增加了一个叫evidence的权重.MatchSim[19]定义两个结点的相似度,是通过它们的最大匹配的相似邻居对的平均相似度来定义的.这种相似度定义的最大问题是运算代价比较高.SimFusion[25]和PathSim[26]都是定义在异构网络上的相似度,而我们的SSR和SR都是定义在同构网络上的.最近提出的RoundTripRank[27]与上述度量不同的是,把specificity和importance有机结合在一起.Lee等人提出了一种算法,求与给定结点SimRank值最高的top-k查询[28].

有许多工作集中在如何有效而快速地计算PPR和SR.Jeh等人提出了计算PPR的可扩展方案:任何一个personalized PageRank vectors都可以表达成基本向量的线性组合[7].而比较快的方法是通过蒙特卡洛的方法来模拟随机游走,从而估算PPR的值[29, 30].文献[10]通过基于上下界的方法来避免没必要的计算开支,去求给定结点的top-k相关的点.文献[12]进一步提出了基于PPR的支持即时查询的更为快速的Top-k查询.

文献[31]提出了一个基于蒙特卡洛计算SR的框架:预计算了随机的fingerprints的索引,查询时根据这些fingerprints来估算SR值.该方法是基于外存的算法.文献[18]提出了一种有效的计算SR的算法,使得算法性能从最坏情况O(kn4)提高到O(knl);同时给出了一种阈值过滤的方法,能够过滤许多小而无用的值,从而提高计算速度.Li等人提出了增量更新相似度值估量算法[32].文献[33]提出了无需计算其他结点对的SR值,能够直接计算出指定结点对的SR值.

5 结 论

本文首先分析了两种代表性的图上相似度度量SR和PPR.这两种度量建立在图上的不同路径上.在此基础上提出了一个新的度量SSR,它不仅同时考虑了SR和PPR的优点,而且加强了SR的原理——两个对象相似是因为它们引用了相似的对象.然后,对SSR进行理论分析.接着,对新公式进行了变换,变换过程实际上是对新公式深入分析的过程.在此基础上设计了优化算法,使得算法性能从最坏情况O(kn4)提高到O(knl).最后,通过实验验证了SSR优于SR和PPR,同时验证了优化算法的有效性.

大图上的SSR优化计算不是本文的重点.未来我们的工作主要是进行这方面的研究.

致谢 感谢审稿专家和编辑老师对本文提出的宝贵意见和建议.

附录1. 引理1的证明

证明:显然,假设成立,证明当k+1时公式也相同.

两个公式对应的第2部分相同,现证明对应的第1部分也相同,即

我们把t¢路径分为两大类:

· 一类是x¹y,且l(t¢)取值是1.也就是说,x,y分别属于I(a)和I(b),分别从ab逆向走一步就到达了xy,(x,y)表示从xy或从yx的单向路径且路径长度是d(1≤dk);

· 剩下的路径划为另一类,我们记为(x,y)®(I(a),I(b))®(a,b).

因此,无论哪一类路径,t¢都可以看作由两部分组成:

· 一部分是从ab逆向走一步就到达了它们对应的入度邻居结点,这部分对p(t¢)的贡献值是

· 剩下的部分要么是单向路径(x,y),由公式(3)可知,它对p(t¢)的贡献值是td(x,y);要么是(x,y)®(I(a),I(b)),对p(t¢)的贡献值是

所以,把路径分为两部分后,得到如下式子:

我们已假设第k步时公式成立:

因此,成立.

由此得出得证.

参考文献
[1] Liben-Nowell D, Kleinberg J. The link prediction problem for social networks. Journal of the American Society for Information Science and Technology, 2007,58(7):1019-1031 .
[2] Antonellis I, Molina HG, Chang CC. Simrank++: Query rewriting through link analysis of the click graph. Proc.Proc. of the VLDB Endowment, 2008,1(1):408-421 .
[3] Jin R, Lee VE, Hong H. Axiomatic ranking of network role similarity. In: Proc. of the 17th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining (KDD 2011). New York: ACM Press, 2011. 922-930 .
[4] Gyöngyi Z, Garcia-Molina H, Pedersen J. Combating Web spam with trustrank. In: Proc. of the 30st Int’l Conf. on Very Large Data Bases (VLDB 2004). New York: ACM Press, 2004. 576-587.
[5] Gupta P, Goel A, Lin J, Sharma A, Wang D, Zadeh R. WTF: The who to follow service at Twitter. In: Proc. of the 22Nd Int’l Conf. on World Wide Web (WWW 2013). New York: ACM Press, 2013. 505-514.
[6] Fujiwara Y, Nakatsuji M, Onizuka M, Kitsuregawa M. Fast and exact top-k search for random walk with restart. Proc. of the VLDB Endowment, 2012,5(5):442-453.
[7] Jeh G, Widom J. Scaling personalized Web search. In: Proc. of the 12th Int’l Conf. on World Wide Web (WWW 2003). New York: ACM Press, 2003. 271-279 .
[8] Jeh G, Widom J. SimRank: A measure of structural-context similarity. In: Proc. of the 8th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining (KDD 2002). New York: ACM Press, 2002. 536-543 .
[9] Sarkar P, Moore AW, Prakash A. Fast incremental proximity search in large graphs. In: Proc. of the 25th Internet Conf. on Machine Learning (ICML 2008). New York: ACM Press, 2008. 896-903 .
[10] Fujiwara Y, Nakatsuji M, Yamamuro M, Shiokawa H, Onizuka M. Efficient personalized PageRank with accuracy assurance. In: Proc. of the 18th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining (KDD 2012). New York: ACM Press, 2012. 15-23 .
[11] Zhu F, Fang Y, Jing Y. Incremental and accuracy-aware personalized PageRank through scheduled approximation. Proc. of the VLDB Endowment, 2013,6(6):481-492 .
[12] Fujiwara Y, Nakatsuji M, Yamamuro M, Shiokawa H, Onizuka M. Efficient ad-hoc search for personalized PageRank. In: Proc. of the 2013 ACM SIGMOD Int’l Conf. on Management of Data. New York: ACM Press, 2013. 445-456 .
[13] Abbassi Z, Mirrokni VS. A recommender system based on local random walks and spectral methods. In: Proc. of the 9th WebKDD and 1st SNA-KDD 2007 Workshop on Web Mining and Social Network Analysis. New York: ACM Press, 2007. 102-108 .
[14] Sun L, Cheng R, Li X, Cheung DW, Han J. On link-based similarity join. Proc. of the VLDB Endowment, 2011,4(11):714-725.
[15] Zheng W, Zou L, Feng Y, Chen L, Zhao D. Efficient SimRank-based similarity join over large graphs. Proc. of the VLDB Endowment, 2011,4(11):493-504 .
[16] Fujiwara Y, Nakatsuji M, Shiokawa H, Onizuka M. Efficient search algorithm for SimRank. In: Proc. of the 29th Int’l Conf. on Data Engineering (ICDE 2013). Washington: IEEE Computer Society, 2013. 589-600 .
[17] Yu W, Lin X, Zhang W. Towards efficient SimRank computation on large networks. In: Proc. of the 29th Int’l Conf. on Data Engineering (ICDE 2013). Washington: IEEE Computer Society, 2013. 601-612 .
[18] Lizorkin D, Velikhov P. Accuracy estimate and optimization techniques for simrank computation. The VLDB Journal, 2010,19(1): 45-66 .
[19] Lin ZJ, Lyu MR, King I. MatchSim: A novel similarity measure based on maximum neighborhood matching. Knowledge and Information Systems, 2012,32(1):141-166 .
[20] Xiao Y, Wu W, Pei J, Wang W, He Z. Efficiently indexing shortest paths by exploiting symmetry in graphs. In: Proc. of the 12th Int’l Conf. on Extending Database Technology (EDBT 2009). New York: ACM Press, 2009. 493-504 .
[21] Tribl S, Leser U. Fast and practical indexing and querying of very large graphs. In: Proc. of the 2007 ACM SIGMOD Int’l Conf. on Management of Data. New York: ACM Press, 2007. 845-856 .
[22] Schloegel K, Karypis G, Kumar V. Parallel static and dynamic multi-constraint graph partitioning. Concurrency and Computation: Practice and Experience, 2002,14(3):219-240 .
[23] Fan W, Li, Ma S, Tang N, Wu Y. Graph pattern matching: From intractable to polynomial time. Proc. of the VLDB Endowment, 2010,3(1):264-275.
[24] Zhao P, Han J, Sun Y. P-Rank: A comprehensive structural similarity measure over information networks. In: Proc. of the 18th ACM Conf. on Information and Knowledge Management. New York: ACM Press, 2009. 553-562 .
[25] Xi WS, Fox EA, Fan B. SimFusion: Measuring similarity using unified relationship matrix. In: Proc. of the 28th Annual Int’l ACM SIGIR Conf. on Research and Development in Information Retrieval. New York: ACM Press, 2005. 130-137 .
[26] Sun Y, Han J. Pathsim: Meta path-based top-k similarity search in heterogeneous information networks. Proc. of the VLDB Endowment, 2011,4(11):992-1003.
[27] Fang Y, Chang KCC, Lauw HW. RoundTripRank: Graph-Based proximity with importance and specificity. In: Proc. of the 29th Int’l Conf. on Data Engineering (ICDE 2013). Washington: IEEE Computer Society, 2013. 613-624 .
[28] Lee P, Lakshmanan LVS, Yu JX. On top-k structural similarity search. In: Proc. of the 28th Int’l Conf. on Data Engineering (ICDE 2012). Washington: IEEE Computer Society, 2012. 774-785 .
[29] Fogaras D, Csalogany K, Racz B, Sarlos T. Towards scaling fully personalized PageRank: Algorithms, lower bounds, and experiments. Internet Mathematics, 2005,17(2):333-358 .
[30] Bahman B, Chakrabarti K, Xin D. Fast personalized PageRank on MapReduce. In: Proc. of the 2011 ACM SIGMOD Int’l Conf. on Management of Data. New York: ACM Press, 2011. 973-984 .
[31] Fogara D, Racz B. Practical algorithms and lower bounds for similarity search in massive graphs. IEEE Trans. on Knowledge and Data Engineering, 2007,19(5):585-598 .
[32] Li C, Han J, He G. Fast computation of simrank for static and dynamic information networks. In: Proc. of the 13th Int’l Conf. on Extending Database Technology (EDBT 2010). New York: ACM Press, 2010. 465-476 .
[33] Li P, Liu H, Yu JX, He J, Du X. Fast single-pair simrank computation. In: Proc. of the SIAM Int’l Conf. on Data Mining. Philadelphia: SIAM, 2010. 571-582.
信息网络中一个有效的基于链接的结点相似度度量
张应龙, 李翠平, 陈红