一种基于网络拓扑结构的社交网络链接预测方法研究文献综述

1. 文献综述（或调研报告）：

基于拓扑结构的链接预测方法是指利用两个节点共有的拓扑结构信息来计算它们之间的相似性，认为两个节点间的相似性越大，它们之间存在链接的可能性就越大。研究者们主要从以下三个角度(共同邻居，路径，随机游走)来研究基于拓扑结构的链接预测方法。

• 1. 基于共同邻居的链接预测方法

此类方法主要使用共同邻居信息来计算两个节点之间的相似性。CN[1]指标(Common Neighbors)是其中最为简单的指标之一。CN指标认为两个节点如果有更多的共同邻居，则它们更倾向于连边。在共同邻居的基础上考虑两端节点度的影响，从不同的角度以不同的方式又可产生6种相似性指标，分别是Salton指标、Jaccard指标、Sorenson指标、HPI指标(hub promoted index)、HDI指标(hub depressed index)和LHN-Ⅰ指标。此外，Adamic和Adar[2]提出了著名的AA指标，其思想是度小的共同邻居节点的贡献大于度大的共同邻居节点，因此根据共同邻居节点的度为每个节点赋予一个权重值。该权重等于该节点的度的对数分之一，即1/logk。受网络资源分配过程的启发，周涛[3]等人提出了资源分配指标RA (Resource Allocation),此方法与AA指标有异曲同工之妙，只是赋予共同邻居节点权重的方式不同，前者以1/k的形成递减，后者以1/log k的形式递减。我们称这一类指标为基于共同邻居的相似性。

• 1. 基于路径的链接预测方法

此类方法主要利用两个节点间的路径信息来计算它们的相似性。周涛等人[3,4]在共同邻居指标(节点间路径长度为2)的基础上考虑了三阶邻居(节点间路径长度为3)的贡献，提出了局部路径指标LP (Local Path)，提高了CN指标的预测精度。Katz[5]等人考虑了两节点间所有可能的路径数，提出了著名的Katz指标。Chen[6]等人定义了两节点间各路径的相对强度，提出了相对强度相似性指标RSS (Relation Strength Similarity)，适用于加权网络。此外，Papadimitriou [7]等人提出了FL指标(FriendLink)，通过遍历两节点间所有有界的路径长度，计算节点对的相似度。

• 1. 基于随机游走的链接预测方法

这类方法利用节点到邻居节点的转移概率来表示当前节点的随机游走到达目的地的概率。HT[8]指标(Hitting Time)定义HT(vx,vy)为一个随机游走粒子从节点vx到节点vy需要走的平均步数，认为HT(vx,vy)越小，节点vx和vy就越相近。SimRank指标描述了两个从节点vx,vy出发的粒子所需的平均相遇时间。RPR[9]指标(Rooted PageRank)可以看成是网页排序算法PageRank的拓展应用，它利用PageRank算法对两个节点之间的边形成概率进行排名，认为节点对(vx,vy)的排名与从节点vx出发到达节点vy的概率成正比，排名越高，形成链接的可能性就越大。此外，基于随机游走的链接预测方法还包括平均通勤时间(average commute time)、Cos 指标、RWR(random walk with restart)指标、SimRank指标等。

1. 方案（设计方案、或研究方案、研制方案）论证：

Katz[10]指标考虑的是两节点间所有可能的路径数，其定义为

其中为控制路径权重的可调参数，表示连接节点和的路径长度为的路径数量。显然，当参数非常小时，高阶路径的贡献就很小了，使得Katz指标的预测效果接近于局部路径指标。

Katz指标作为经典的相似性指标，考虑了节点间信息传递的所有路径，具有不错的预测效果。但是它并未考虑到路径上的节点之间的依赖关系(相互链接关系)，而这种依赖关系会导致信息传递时的偏差，也就是说在某种依赖关系下，信息不会通过某条路径进行传递。这时，若我们还是同样认为这条路径对某节点对的链接形成有贡献，那么势必降低链接预测的准确性。例如，在社交网络中，节点可能不会通过一条长度为5且路径上的节点的度都为2的路径传递信息到节点，而是更倾向于选择一条同样长度为5且路径上的节点之间相关度更高的路径。因为只有这样，信息才能更有效地从节点传递到节点。

本文将子图与Katz方法相结合，着重考虑路径上节点之间的依赖关系对链接形成的影响，即利用子图来保留信息传递时的结构信息，而不是只考虑路径的数量，该方法所选取的路径与Katz方法所选取的相同，我们称这种方法为Gkatz方法。该方法并不人为地设定某些路径的权重，而是通过监督学习方法，得到实验网络真实的信息传递偏好，即怎样的路径更容易传递信息。本文还将引入一个新的概念“7-子图”，用于记录路径上节点之间的依赖关系。此方法可以分为两个部分：引入子图和特征向量的获取和监督学习。

1. 子图的引入

Katz方法考虑了网络中所有长度的路径，这使得Katz方法获得了更高于共同邻居方法(Common Neighbor)的预测精度，但也使得Katz方法的计算效率相对低下——考虑长路径需要很大的时间开销。然而在真实网络中，并非所有长度的路径都会对节点对链接形成产生影响，非常长的路径基本不会对节点对和之间形成链接带来影响。Corlette[11]等人就通过实验分析了社交网络LiveJournal中路径距离对链接形成的影响，并得到了以下结论：97%的链接形成于距离小于等于6的节点之间。因此本文认为当节点之间的距离超过6时，节点之间不会形成链接。也就是此方法只考虑路径距离小于等于6的节点和节点之间形成链接的可能性。这样的话，就可以缩小需要计算链接形成的节点对的数量，减少节点层面上时间复杂度。

因此，根据Corlette等人的研究以及本文的假定，我们只需要考虑所有路径距离小于等于6的节点对。GKatz的第一步就是要记录这些节点对，同时保留每一个节点对的过渡节点(定义1)。

定义1(过渡节点)：若节点和之间可能形成链接，同时节点k到节点的距离为，节点k到节点的距离为，满足，那么我们就称节点k为节点和节点的过渡节点。

因为GKatz方法考虑到了信息传递过程中过渡节点之间的依赖关系，而子图正是记录这种依赖关系的载体，同时考虑到路径距离小于等于6的节点之间才可能形成链接。所以，这里使用考虑7-子图(定义2)来记录这种依赖关系。

定义2(7-子图)：若节点和之间可能形成链接，同时满足节点和之间的过渡节点个数小于等于5，那么我们就称由节点和以及过渡节点组成的子图为7-子图。这里的7指的是子图中节点的个数，不满7个节点的子图我们将人为地补上相应个数的游离节点。

通常情况下，子图是用邻接矩阵的形式来存储的，因此这里的7-子图同样使用邻接矩阵(定义3)来存储。

定义3(7-子图的邻接矩阵)： 7-子图g的邻接矩阵D是阶矩阵，矩阵中元素为

为了使每个7-子图都拥有独一无二的地址，本文还定义了值矩阵(定义4)，用于区分7-子图中的边，使得每条边都有不同的权重。然后将7-子图的邻接矩阵与值矩阵做内积，得到7-子图的地址(定义5)。这样做，不仅能够让我们区分不同的7-子图，同时还可以根据7-子图的地址倒推出7-子图中边的情况。

定义4(7-子图的值矩阵)：具有7个节点的无权无向图g，其值矩阵V是阶矩阵，

用另一种形式表示，

定义5(7-子图的地址)：7-子图g的地址可以用邻接矩阵与值矩阵做内积得到，即

通过计算可以得到，对于只有一种关系的无向网络，满足条件的7-子图共有2097152种，能用作特征的子图有1048576种（去除了包含需要预测边的子图）。这个数字太过庞大，以至于每个节点对都需要考虑1048576种子图的存在。然而对于某些7-子图来说，虽然他们的地址是不同的，但是他们所拥有的边是相同的(节点在邻接矩阵中的位置不同所导致的最终子图地址的不同)。受到图同构(定义6)的概念的启发，本文提出了7-子图同构的定义(定义7)，认为所有同构的7-子图都是等价的。

定义6(图同构)：所谓图与同构，是指两个图的拓扑结构完全相同，即它们的顶点之间保持一一对应，边之间保持一一对应，而且对应顶点与对应边之间保持相同的链接关系，记为。

定义7(7-子图与同构的充要条件)：若任意交换7-子图G中过渡节点的身份，从而得到7-子图G的最小地址，同理得到7-子图的最小地址。

那么， 7-子图与同构的充要条件是。

1. 特征向量的获取和监督学习

我们为每一个可能形成链接的节点对和设置一个向量(Vector)，向量的每一维表示每一类7-子图在节点对和之间的路径上出现的次数，用于保存过渡节点之间以及过渡节点与节点和的依赖关系。然后统计7-子图出现的次数，形成特征向量。我们将一段特定时间内形成链接的节点对作为正例，未形成链接的节点对作为反例，然后再将正例和反例的特征向量通过监督学习方法进行训练并生成模型，最后再用该模型预测测试集。

1. 进度安排：

2014.12~2015.2 阅读文献

2015.3.1~2015.3.20 算法设计

2015.3.21~2015.3.31实验设计

2015.4.1~2015.4.25 算法实现

2015.4.25~2015.4.30 实验评估

2015.5.1~2015.5.25 论文撰写

六、指导教师意见：

签名： 年 月 日

七、开题审查小组意见：

签名： 年 月 日