0 引言
网络可以很好地描述社会结构、生物系统和信息系统等,其中节点表示社会中的个人或团体、基因、蛋白质等生物学元素、网络用户、网络站点等,节点之间的链接表示它们所代表的对象之间的通讯或某种关系.对复杂网络的研究已成为计算机科学、物理学、系统科学等许多学科的研究热点.近年来,已经有很多学者致力于研究网络的演化机制、网络拓扑和功能之间的关系以及网络特征等.在这些研究中会涉及到链接挖掘中的许多问题,而链接预测是其中最基本的问题.该问题旨在根据网络的拓扑结构来预测节点之间可能存在的链接.也就是说,链接预测的任务是要探测潜在的但尚未被观察到的链接,或者是要预测现在尚未存在但未来可能会新产生的链接[1].链接预测在当代网络分析中是一个极其重要的工具.在社会网络和生物网络中,人与人之间、生物体之间的关系和相互作用随时间在不断演化,在这样的动态演化的网络中预测未来的关系和相互作用,有着重要的应用价值.
在生物信息学领域的研究中,链接预测在研究生物的基因与疾病的关系、分析蛋白质相互作用网络等生物网络的结构,有着很重要的实用价值,有利于预防和治疗人类的疾病.譬如,在蛋白质相互作用网络的研究中[2],需要观测蛋白质之间是否发生相互作用,这就要进行大量的生物学实验.而这样的生物学实验将会耗费巨额的资金和很长的时间.而应用链接预测的技术可以分析蛋白质相互作用网络的拓扑结构来预测一些疑似的链接,在此基础上再对这些疑似的链接进行生物实验,这样,不但可以降低实验费用,还可以提高预测的准确率[3].又譬如,应用链接预测技术探测疾病—基因网络中的潜在链接,对于研究疾病发生的原因、设计相应的治疗手段和药物[4]有着重要的意义.
链接预测的思想和方法在社会网络的分析中也有着广泛的应用.近几年来,社交网络的迅速发展吸引了越来越多的用户.通过链接预测算法可以将那些很有可能是好友但是还未结交的人,以及部分兴趣爱好相同、用户可能会感兴趣的人推荐给在线的用户[5-6].如果预测的结果足够精准,可以提高该网站在用户心中的地位,保证用户对该网站的参与度.在学术网络中,可以通过链接预测来向学者推荐相关的学术论文以及可能的合作者[7].
链接预测在电子商务中也有着重要的应用.随着互联网技术的发展和人们消费习惯的变革,电子商务网站[8]也迅速普及.这些电子商务网站分析消费者过去的交易情况和他们对不同商品的喜好,利用链接预测技术来向用户推荐他很可能购买的商品[9-10].用这样的促销手段可以增加现有客户的黏着性,还能招来更广泛的新客户.为防止手机客户流失,无线通讯运营商可以通过链接预测的技术在用户网络中预测某些用户更换运营商的意图.
链接预测技术在社会网络分析和社会安全中也有着重要的作用.链接预测技术有助于探测社会关系网络中人与人之间潜在的关系[11],在犯罪网络中探测恐怖分子之间暗藏的联系[12],从而发现隐蔽的恐怖分子[13].借助链接预测技术,可以检测识别嫌疑人的行为[14],预防和制止犯罪行为的实施.
除了具有广泛的实际应用背景,链接预测技术在网络理论研究中也具有重要的价值.利用链接预测的技术作为辅助工具,可以衡量描述复杂网络演化机制模型的优劣[15].对于一个网络,可能有多种模型来描述它的演化机制.因此这些模型使用了很多统计参数来描述网络的拓扑特征,如何客观公正地衡量他们是否准确反映网络真实的拓扑特征是比较困难的.而使用链接预测技术可以为比较不同模型提供一个较客观公平的平台,有益于复杂网络演化模型的理论研究.
1 复杂网络的链接预测方法目前,常用的链接预测方法主要有基于相似性、基于机器学习、基于矩阵运算和基于概率模型的方法等.
1.1 基于相似性的方法基于相似性的链接预测方法有这样的假设前提:如果两个节点领域的拓扑结构越相似,它们之间越有可能被一条边所链接.该类方法对每对节点x和y分配一个得分sxy,表示x和y之间的相似性.将所有未观察到的链接根据其得分进行排名,相似度越高的节点之间存在链接的可能性较大.如果相似性得分能准确地反映网络的拓扑特征,则利用该相似性方法得到的预测结果的精度就会比较高.由于基于相似性的方法比较简单,它是最常用的一种链接预测方法.根据所使用的相似性指标的不同特点,此类方法可以分为基于局部信息、基于路径信息、基于随机游走和基于社会理论的相似性方法.
1.1.1 基于局部信息的节点相似性指标1) 共同邻居(CN)指标
CN指标因其简单性成为链接预测中使用的最多的指标之一[16].网络中两个节点x和y的CN指标是指x和y都具有直接链接的节点(称为共同邻居)的个数.共同邻居的个数越多,x和y之间越有可能存在链接.该指标可用下列公式表示:
(1) |
这里,Γ(x)为节点x的邻居集合,Γ(x)为节点x的邻居数.由于CN指标未进行标准化,所以它仅仅反映了节点对之间的相对相似性.
2) Jaccard (JC)指标
Jaccard指标对CN指标根据共同邻居的规模进行了标准化.若节点对之间拥有的共同邻居的个数与节点对拥有的所有邻居个数之比越大,则该节点对的JC值就越大.具体定义如下:
(2) |
3) Sorensen(SI)指标
SI指标除了考虑公共邻居的规模,还认为具有较低度数的节点具有较高的链接可能性.定义如下:
(3) |
4) Salton(SC)指标
SC指标是度量节点x和y之间的余弦相似性的指标,它的定义为
(4) |
5) 大度节点有利(HP)指标
HP指标定义了节点x和y的拓扑重叠性.具体定义如式(5)所示,HP值由度数较低的节点决定.
(5) |
6) 大度节点不利(HD)指标
HD指标由周涛等人提出[17].与HP不同,它的值由度数较高的节点决定.定义如下:
(6) |
7) Leicht-Holme-Nerman(LHN)指标
由Leicht、Holme和Newman提出而得名,定义如下:
(7) |
8) Parameter-Dependent(PD)指标
该指标由周涛等人提出[17].设λ是一个自由参数,PD指标的定义如式(8)所示.由定义可见,当λ=0时,PD指标退化为CN指标.当λ=0.5和λ=1时,PD指标分别退化为Salton和LHN指标.
(8) |
9) Adamic-Adar(AA)指标
Adamic和Adar提出了AA指标,最开始是用于衡量网页之间的相似度,后来被用到了网络的链接预测. AA指标与Jaccard指标类似,但在AA指标中,度小的共同邻居节点的权重更大.它的定义如下:
(9) |
10) 优先链接(PA)指标
PA指标的基本思想是,新的链接更可能链接具有较高度数的节点而不是低度数节点.它的定义如下:
(10) |
11) 资源分配(RA)
该指标由周涛等人[17]受资源分配的物理过程的驱动提出. RA指标与AA指标很类似,它们都抑制了具有较高度数的共同邻居的贡献.但是RA指标对于具有高度数的共同邻居的惩罚力度要高于AA指标.因此,当网络的平均度较小时RA和AA指标具有很接近的预测结果,但是当平均度较大时,RA指标的性能更好. RA指标的定义如下:
(11) |
我们分别就标准化、时间复杂度和特征三方面对上述相似性指标进行了比较,结果如表 1所示[18].从表 1可以发现:CN、AA、PA和RA这四种指标未进行标准化.这意味着这些指标下的相似性仅具有排名含义,且不容易与其他标准化的指标进行组合.此外,在选择相似性指标时,时间复杂度也是一个需要考虑的重要因素,尤其是对于大规模社交网络.设网络的顶点数为n,基于局部的相似性指标的时间复杂度为O(n2).这在基于相似性的链接预测方法中是最低的,因为我们至少要计算n(n-1)/2个顶点对之间的相似度.
指标 | 标准化 | 时间复杂度 | 特征 |
CN | 否 | O(n2) | 简单直观 |
JC | 是 | O(2n2) | 共同邻居个数相对于总的邻居个数的比例 |
SI | 是 | O(n2) | 度较低的节点将具有更大的链接可能性 |
SC | 是 | O(n2) | 余弦相似性 |
HP | 是 | O(n2) | 链接可能性由度较低的节点决定 |
HD | 是 | O(n2) | 链接可能性由度较高的节点决定 |
LHN | 是 | O(n2) | 具有许多共同邻居的节点对之间具有更高的链接可能性 |
PD | 是 | O(n2) | 为CN、Saltonhe、LHN等指标的一般形式 |
AA | 否 | O(2n2) | 具有较低度的共同邻居的权重更大 |
PA | 否 | O(2n) | 简单的和新的链接将更有可能链接高度的节点 |
RA | 否 | O(2n2) | 与AA类似,但更严重地惩罚具有高度的共同邻居 |
1) 局部路径(LP)指标
LP指标[19]利用了节点对之间长度为2和3的局部路径的信息定义他们的相似度.由于长度为2的路径比长度为3的路径更重要,在该指标中设置了调节系数α,使长度为2的路径有较高的权重.该指标的定义如式(12)所示,其中A2和A3分别表示二阶邻居和三阶邻居节点的邻接矩阵.
(12) |
2) Katz指标
Katz指标计算了两个节点之间的所有路径.为了使路径随着长度而指数级衰减,该指标将为较短路径赋予较大的权重.该指标定义如式(13)所示,其中pathx,yl表示从节点x到y长度为l的所有路径的集合,调节参数β>0使较长的路径有较高的权重.当β非常小时,Katz指标就与CN指标非常相近.
(13) |
3) 关系强度相似性(RSS)指标
RSS[20]是一种非对称指标,适用于边上具有权重的网络.设有L条从x到y的长度小于r的简单路径p1,p2,…,pL且路径pl由K个节点z1,z2,…,zk-1,zk组成,边(x,y)上的权重表示为关系强度R(x,y),则从x到y的RSS指标定义为
(14) |
(15) |
4) 友情链接(FL)指标
FL指标[21]假设社交网络中顶点所代表的个体可以通过他们之间的所有路径进行交流. x和y之间的FL指标定义为从x到y的不同长度l的路径计数:
(16) |
其中,n是网络中顶点的数量,pathsx,yi是从x到y的所有长度为i的路径的集合,l是x和y之间一条简单路径的长度. l值越大并不意味着RSS指标越高,相反,对于太大的l,RSS指标反而会降低.
5) 顶点搭配轮廓图(VCP)指标
VCP(vertex collocation profile)指标[22-23]通常写成VCPx,yn,r,它是一个描述两个节点x和y之间关系的向量,用它们在包含r个关系的n个顶点的所有可能子图中的共同出现的次数来表示.虽然VCP不能直接表达节点之间的相似性,但它可以作为监督学习方法的分类特征向量.由于VCP中的子图可以被视为多个路径的组合,因此我们将VCP归类为基于路径的度量方法.
大部分基于路径的相似性指标的时间复杂度为O(n3).在实际应用中,这样的复杂度对于大规模社交网络是难以实时处理的.
我们分别就标准化、时间复杂度和特征三方面对上述基于路径的节点相似性指标进行了比较,结果如表 2所示.
指标 | 标准化 | 时间复杂度 | 特征 |
LP | 否 | O(n3) | 利用节点对之间长度为2和3的路径的信息计算相似度 |
Katz | 否 | O(n3) | 计算两个节点之间的所有路径,并为较短路径赋予较大权重 |
RSS | 否 | O(r.L.n2) | 非对称指标,适用于边上具有权重的网络 |
FL | 是 | O(n3) | 假设网络中顶点可以通过他们之间的所有路径进行交流 |
VCP | 否 | O(n3) | 其结果是一个描述节点之间关系的向量,可以作为监督学习方法的分类特征向量 |
1) 击中时间(HT)指标[24]
击中时间指标HT(x,y)是从节点x到y的随机游走所需的预期步数.设矩阵P = DA-1A,其中DA为与A相关的对角矩阵,定义为(DA)i,i= ∑jAi,j,P的元素Pi,j是从节点i游走到节点j的概率. HT指标的定义如下:
(17) |
2) 通勤时间(CT)指标
由于HT指标不是对称的,为了得到对称的相似性指标,可采用通勤时间(CT)指标,该指标同时考虑从x到y和从y到x的预期步长. CT指标可以通过下式得到:
(18) |
其中L+是矩阵L = DA - A的伪逆,m是网络中的边的数目.
3) 余弦相似性时间(CST)
余弦相似性时间指标在L+的基础上通过计算两个向量的相似性得到,具体定义如下:
(19) |
4) SimRank指标
SimRank指标[25]以一种递归的方式定义,它基于这样一个假设:如果两个节点链接到相似的节点,则这两个节点相似.设参数γ用于控制链接节点的权重随着距离增大而衰退的速度,SimRank指标定义如下:
(20) |
SimRank指标可以用随机游走模型来解释:该指标反映了两个分别从顶点x和y出发的粒子,通过在逆向图的边上进行随机游走,在某一顶点相遇的时间. SimRank的最差计算复杂度为O(n4),其中n是顶点数.如此高的计算成本限制了其在大规模网络中的广泛使用.为此,王春磊等[26]提出了异步SimRank算法,使其可以进行分布式计算,并避免了大量同步开销.
5) Rooted PageRank(RPR)指标
RPR[27]是PageRank的一种改进. PageRank是搜索引擎对搜索结果进行排名的核心算法.该算法对节点的排名与通过图上的随机游走到达节点的概率成比例.在RPR指标中,定义ε为随机游走的粒子访问节点邻居可能性,而1-ε是粒子重新回到该节点的可能性.令D为对角元素Di,i= ∑jAi,j的对角矩阵,该指标定义如下:
(21) |
6) PropFlow指标
PropFlow指标[28]类似于Rooted PageRank,但它更加局部化.它与从x开始并在y结束的不超过l步的随机游走的概率成正比.粒子在随机游走时根据边上的权重来选择路径,并在到达y时或重新回到某个已访问的节点时终止.最后,将随机游走路线的概率作为新链接存在的概率估计.若x和y是直接链接的,则它们的PropFlow指标PF(x,y)可用下式计算:
(22) |
其中,k是x的邻居,其表示离开始节点的距离大于x的距离,ωxy表示节点x和y之间链接的权重,a是随机游走路径上x的前一个节点.如果x是开始节点,则PF(a,x)=1.如果x和y是间接链接,则PF(x,y)表示通过从x到y的所有最短路径的PropFlow的总和.
与RPR不同,计算PropFlow的随机游走中不需要重新回到原来节点,也无需等到收敛,而只是简单的采用长度在l之内的广度优先搜索策略.
大部分基于随机游走的相似性指标的时间复杂度为O(n3),有的甚至到O(n4),这使得该相似性指标难以实际应用到大规模社交网络的实时链接预测之中.
我们分别就标准化、时间复杂度和特征三方面对上述基于随机游走的节点相似性指标进行了比较,结果如表 3所示.
指标 | 标准化 | 时间复杂度 | 特点 |
HT | 否 | O(n3) | 非对称指标,从节点x到y的随机游走所需的预期步数 |
CT | 否 | O(n3) | 对称指标,同时考虑从x到y和从y到x的预期步长 |
CST | 是 | O(n3) | 在L+的基础上通过计算两个向量的相似性得到, |
SimRank | 是 | O(n4) | 两个分别从顶点x和y出发的粒子进行随机游走,在某一顶点相遇的时间 |
RPR | 是 | O(n3) | 是PageRank的一种改进,假设粒子可重新回到原节点 |
PropFlow | 是 | O(n3) | 随机游走中不需要重新回到原节点,而且限制路径的长度 |
近年来,越来越多的研究采用社区结构、三元封闭、强弱链接、同质性和结构平衡等经典社会理论来解决社会网络中的挖掘和分析问题.与仅使用拓扑结构的相似性指标不同,基于社会理论的链接预测指标还可以利用社会成员之间的交互行为、社区结构、社会成员的中心性、社会事件等信息来提高预测性能.在兴趣网络中,还可以利用用户的同质性来预测用户和他感兴趣的服务之间的链接,以及具有共同兴趣的用户之间的链接[29].此外,度分布、社会平衡和微观机制等也有助于发现不同社交网络的社交模式[30],而这些模式可用于设计复杂的链接预测方法.
例如,Liu等人[31]提出了一种链接预测指标,该指标基于弱链接和共同邻居节点的度、紧密度和介度等三种中心性.每个共同邻居根据其中心性的大小对节点链接的可能性起到不同的作用.该指标定义如下:
(23) |
其中,ω(z)表示节点中心性的权重,f(z)是指示函数,β用于调整每个共同邻居对两个节点间的链接可能性的贡献.当β>1时,它使中心性较大的顶点比中心性较低的作用更显著.当β < 0时,它对中心性较大的顶点的作用进行了抑制.当β∈(0,1)时,它均匀地抑制了所有的节点.
近年来所提出的一些基于社会理论的相似性指标的原理、特征以及适用范围如表 4所示.
对于以上所述的基于局部信息、基于路径、基于随机游走和基于社会理论的节点相似性指标,它们的各自特点和适用范围如表 5所示.
指标 | 特点 | 适用范围 | |
基于局部信息的指标 | 只用到顶点一阶邻居的拓扑信息,预测的精确度较低,时间复杂度不高 | 对实时性要求较高、精度要求较低的应用问题 | |
基基于全局信息的指标 | 基于路径的指标 | 考虑了全局拓扑结构.精度较高,但时间复杂度较高 | 对实时性要求较低、精度要求较高的应用问题 |
基于随机游走的指标 | |||
基于社会理论的相似性指标 | 利用社会成员之间的交互行为、社区结构、社会成员的中心性、社会事件等社会信息来提高预测性能 | 适用于具有符号的、有向的、社区结构明显的、以及提供丰富的感知信息的社会网络 |
还有一些工作[23, 35]系统地比较了各种相似度量指标在链接预测中的准确性,他们在链接非常稀疏的以及包含不准确的链接信息的网络上进行试验,结果发现这些相似性度量可以根据它们的表现分为几个群,不同群的相似性度量可用于不同性质的网络.
此外,有许多链接预测方法[26, 36-40]根据网络的具体应用领域,使用顶点的属性作为各类非拓扑特征,显著提高了链接预测的性能.
需要指出的是,虽然与基于局部信息的节点相似性指标相比,基于路径的相似性指标考虑了更多的拓扑信息,精确度在一定程度上会有所提高,但这并不意味着路径越长,效果会越好.在较长的路径上预测结果并不一定比使用较短的路径更加精确.理论分析证明,考虑较长路径的指标仅在较短路径不够多时才有效.如果网络中具有足够多的短路径,基于路径的指标可以通过移除太长的路径来优化其性能.
1.2 基于机器学习的方法近年来有不少学者提出了许多基于机器学习的链接预测方法,这些方法有的是将链接预测问题转化为分类问题来解决,也有的是将网络描述为具有某种内在的结构模型,然后用最大似然方法找出与已知网络具有最大似然的具体的该种结构.
1.2.1 基于分类的方法设x,y∈V是图G(V,E)中的一对节点,l(x,y)是节点对(x,y)的标签.如果两节点间存在链接,则该对节点的标签为正;否则,标签为负. x和y的标签定义如下:
(24) |
基于分类方法的基本原理如图 1所示.在链接预测中,可将每个节点对看成具有类标签和描述该对节点特征的实例.首先要进行特征的抽取,节点对的特征可以包括以上所述的链接预测的相似性指标、内部属性和外部信息.这样就构成了一个典型的二元分类问题.然后可以使用有监督的分类学习方法解决该问题.例如决策树、支持向量机、朴素贝叶斯网络等.
为了构建用于链接预测的有效分类器,需要从社交网络中定义并提取一组适当的特征.在链接预测中常用的特征包含节点特征、网络特征、拓扑特征和非拓扑特征.对于一般链接预测学习模型的训练,通常仅考虑一些一般特征,如:节点的入度和出度、网络的顶点数、边数、平均聚类系数、平均度、强连通分量数等特征,以及上述用相似度指标描述的各种拓扑特征,如基于局部或全局路径、基于随机游走和基于社会理论的相似性指标等.例如,上节所述的VCP指标可以看作是描述本地拓扑信息的一种特殊特征[18].但是对于实际链接预测的应用,还应考虑非拓扑特征.如,共同作者网络中的共同作者、关键字计数、关键字匹配计数、聚类指数、论文发表日期、论文题目、作者单位等属性.有许多链接预测方法[41-45]根据网络的具体应用邻域,使用顶点的属性作为各类非拓扑特征,显著提高了链接预测的性能.但并非所有的非拓扑特征对链接预测都有用,由于大多数非拓扑特征都与应用领域相关,这需要通过领域知识来识别和发现对链接预测有用的特征.
像许多学习问题一样,使用何种方法进行特征选择,是基于机器学习链接预测方法的关键所在.我们可以将机器学习领域中的许多特征选择算法应用到这一问题上来.例如,伍杰华等[46]提出一种RRelief F算法对特征进行选择,RRelief F特征选择模型的多维社交网络链接分类算法,有效处理了特征间的冗余信息和噪音信息.
基于机器学习的链接预测方法将存在的和不存在的链接看成两个类.由于在实际网络中,已存在的链接数量通常会远小于不存在的链接数量,这就导致了类别之间的不平衡.在对类间不平衡的数据的训练过程中,所得到的模型会对数据量多的类别的分布拟合得更好.这就导致了对不存在的链接的预测性能较好,而对存在链接的预测性能较差.因此这种不平衡性会降低链接预测方法的有效性.此外,在不平衡的网络中,链接数据非常稀疏,使得链接的先验概率通常会非常小,难以建立链接预测的统计模型,难以进行模型的评估和量化预测的置信水平.因此,有必要在基于机器学习的链接预测中考虑克服这种不平衡性对链接预测的干扰.
近年来出现了不少采用分类技术的链接预测方法.一些主要的分类技术,如主成分分析[47]、学习自动机[48]、决策树[49]、神经网络[50]、贝叶斯网络[51]、skyline查询[52]、监督秩聚合[53]、交互式学习[54]、判别分析[55]、逻辑回归[56]等都用于网络链接预测,取得了较好的预测效果. 表 6展示了基于分类的链接预测主要方法,比较了它们所使用的特征、分类方法,以及它们的特点和适用范围.
方法 | 使用的特征 | 机器学习算法 | 适用范围 | 特点 |
Pujari and Kanawati[57] | 拓扑特征 | 监督排名聚合,决策树,朴素贝叶斯分类,k-近邻 | 一般网络 | 可以聚合尽可能多的特征,时间复杂度较高 |
Scripps等人[55] | 顶点属性,邻居节点的拓扑特征 | 判别分析 | 一般网络 | 能自动确定最具预测性的特征,具有灵活性 |
伍杰华,等[46] | 拓扑特征和属性特征,并对特征进行了选择 | 主成分分析,偏最小二乘回归 | 多维社交网络 | 有效处理了特征间的冗余信息和噪音信息 |
Lichtenwalter[58] | 从顶点的配置文件抽取的特征 | WEKA中的有监督的分类方法 | 有向、带权、时序、多关系等网络 | 能较多地保留拓扑信息,特征选取和训练的性能较差 |
李志宇,等[59] | 节点的结构特征,动态特征 | 基于局部搜索的增量学习,正采样算法,动态逻辑回归 | 大规模动态网络 | 在预测准确率以及时间效率上都取得了较大的提升 |
Li[60] | 拓扑特征,随机游走的路径,反映用户意愿的顶点特征 | 核支持向量机 | 用户—项目二分网络 | 无需产生显式的特征,性能依赖于核函数 |
Cao,等[61] | 用户与不同类型项目之间的关系 | 迁移学习,非参数贝叶斯方法 | 来自异构域的多个链接预测 | 允许信息在异构任务中自适应地迁移,同时还考虑了任务之间的相似性 |
Sa and Prudencio[62] | 拓扑特征 | J48算法,朴素贝叶斯分类IBk,libSVM,LibLinear等算法 | 带权网络 | 使用权重以提高预测精度 |
Lu,等[56] | 基于路径的特征 | 逻辑回归 | 具有多个辅助网络的社交网络 | 提高了预测精度 |
Chiang,等[63] | 较长回路的特征 | 逻辑回归 | 符号网络 | 不仅能较好地预测边上的符号,而且能有效地降低结果的假阳性率 |
Pujari和Kanawati[64] | 拓扑特征和属性特征,根据每个属性的预测能力来决定其权重 | 基于有监督学习的社会选择算法 | 顶点具有属性的社会网络 | 引入加权社会选择规则改进经典的投票方法,应用排名聚合方法来组合各个拓扑度量的预测能力,具有较高的预测精度 |
Leskovec,等[65] | 顶点的度,三角结构 | 逻辑回归 | 符号网络 | 能较好精确地预测边上的符号 |
Kashima,等[66] | 节点相似性等辅助信息 | 张量完全,标签传播 | 多关系网络 | 有较好的预测结果,但由于计算时间和空间限制,很难应用到较大规模的网络中 |
Wu,等[67] | 共同发明人的统计,连接同质性,兴趣同质性和相关性 | 排序因子图模型,交互式学习 | 企业社交网络 | 显著提高了合作发明关系推荐的性能 |
Li,等[68] | 网络元路径的特征 | BP神经网络模型MPBP | 多种链接的异构网络 | 不但可预测链接的存在,也可预测其类型 |
Raymond,等[69] | 顶点的Kronecker和以及Kronecker积相似度特征 | 连接传播,矩阵分解与近似 | 多关系网络、大型动态网络 | 能够在保持准确性的同时降低计算成本 |
Kunegis,等[70] | 邻接矩阵,路径的长度与条数 | 拉普拉斯核、降维 | 无向,带权或无权网络,大型单部和二部网络 | 应用了图核与降维技术,运行时仅依赖于所降到的维数,而与原网络的大小无关 |
通过比较上述各类方法,我们可以得到以下结论:1)大部分链接预测方法是基于基本分类模型或改进的分类模型[66].这说明了分类模型不是链接预测学习的关键. 2)实际上,特征的选择或构建才是链接预测学习的核心任务,这也恰恰是链接预测学习方法的关键所在.基于机器学习的链接预测算法大都抽取网络的拓扑特征,然而,在解决一些应用领域的链接预测问题时,应该构建和使用特定领域的特征[54, 71]. 3)基于监督学习的链接预测方法可以提高预测的精度,但它同时还会导致特征选择和模型训练的高计算成本[22, 64].
1.2.2 基于最大似然的方法链接预测的最大似然方法首先假设网络具有某种内在的结构框架,然后找出与已知网络具有最大似然的具体的该种结构,最后根据所得到的具体结构估计顶点对之间出现链接的可能性.常用的结构模型有层次结构、分块结构等.
1) 层次结构模型
研究表明,社会网络往往呈现出层次结构. Clause[72]等人提出了一个层次结构的概率模型,该模型将顶点划分为若干组,这些组又进一步细分为更小的组,等等.如此划分下去可从网络数据中推导出层次结构,学习算法的任务是利用观察到的网络数据,通过统计推断,结合最大似然方法和蒙特卡罗采样算法,拟合出最可能的层次结构.
设网络G有n个顶点,它可以由一个树状图D表示. D中含有n-1个内部节点和n个叶子节点.如果我们给D中每个内部节点上都赋予一个概率值pr∈(0,1),则G上两个节点之间存在链接的概率就等于它们最低共同祖先上的概率.例如,一个用树形结构表示的含有5个节点的网络层次结构如图 2所示[18].由图可见节点1和节点2连接的概率为0.5,节点1和节点3连接的概率为0.3,节点3与节点4连接的概率为0.4.
学习算法的任务是找出最适合所观察到的真实网络数据的树状图.假设所有的树状图都是先验等概率的,根据贝叶斯理论,给定模型(D,{pr}),对观察到的网络最优的刻画是使似然估计值最大的结构.
设树状图中以内部节点r为根的右子树和左子树的叶子节点数目分别为Rr和Lr;设r为根的子树的叶子节点在G中形成连边的条数为Er,那么网络的似然估计值为
(25) |
对于给定的模型(D,{pr}),使似然估计值最大的最优概率为
2) 概率分块模型
随机块模型[56]将网络的节点分成许多组,任意两个未链接的节点所属的组的情况决定了他们之间是否可能存在链接.随机块模型M=(P,Q)由两部分组成:P为划分的方法,Q为两组节点间链接的概率矩阵.设Qαβ为α和β组之间的链接概率,A为被观察到的网络的邻接矩阵,则该网络结构的似然为
(26) |
式中,rαβ为原网络中α组内与β组内的节点之间连边的条数;lαβ为α组内与β组内的节点之间连边的条数.使似然估计值最大的最优概率为
(27) |
设Ω为对网络所有可能分组的集合.某一节点对(x,y)存在链接的可信度可根据贝叶斯定理计算:
(28) |
可信度越高表示x,y之间越可能存在连边.为方便计算,可将p(M)设定为一个常数.
在应用最大似然方法进行链接预测时,要生成最优的模型结构,就要进行大量抽样考察,这样需要较多的计算时间,不太适合处理规模较大的网络.
1.2.3 基于集成的方法目前有很多链接预测算法是基于局部信息的,这类算法能够以较低的时间消耗获得可接受的预测精度[73-74],但研究表明基于局部信息的算法的稳定性较差,它们的预测性能变化很大.为此,可以将多个基于局部信息的预测结果进行集成,以获得更稳定、效果更好的链接预测器.
近年来,关于集成学习的研究已经获得了许多令人满意的理论和实践结果[70, 75-79].出现了许多基于集成的连接预测方法.这些基于集成的方法[53, 80-81]将链接预测视为监督学习问题来构造多个学习器,然后对他们构建集成.
例如,Comar等人[82]所提出了一种社区级网络中,基于成本敏感的Boosting集成的链接预测算法.受到Lü等人工作的启发[83],He等人[84]设计了基于OWA(有序加权平均)局部信息的链接预测算法的集成策略,实验结果证明了该方法的可行性和有效性.吴祖峰等[85]采用基于AdaBoosting的集成学习方法,选择若干具有代表性的链路预测算法作为弱分类器进行集成,使得算法的准确率以及召回率显著提高.
1.2.4 基于机器学习的链接预测方法比较对于以上所述的三类基于机器学习的链接预测方法,即基于分类的方法、基于最大似然的方法和集成的方法,它们所需的信息、预测结果的形式、各自的特点和适用范围如表 7所示.
方法 | 所需的信息 | 预测结果的形式 | 特点适用范围 |
基于分类 的方法 |
网络的拓扑特征、顶点的属性特征等 | 未知边上的类别,即存在或不存在的标签 | 拓扑、属性特征比较明显的网络 |
基于最大 似然的方法 |
网络的结构模型 | 由似然最大的结构模型所得到的未知边存在的概率 | 拓扑结构比较明显的网络 |
集成的方法 | 多个学习器得到的预测结果 | 依赖于所集成的学习的预测结果的形式 | 对实时性要求较低、精度要求较高的应用问题 |
基于矩阵运算的连接预测方法将链接预测问题转换为矩阵运算问题,它们将图的邻接矩阵、拉普拉斯矩阵等描述拓扑结构的矩阵进行变换、分解、填充等运算,从而得到一个反映潜在链接的隐空间,最后在隐空间得到连接预测的结果.基于矩阵运算的连接预测方法的基本原理如图 3所示.
从图 3中可以看出,将网络的邻接矩阵、拉普拉斯矩阵进行变换、分解、填充等运算的过程可以看成是将网络的拓扑结构向一个隐空间映射的过程.由隐空间所反映的边上的隐特征可以得到未知边的预测得分.根据采用的矩阵运算方法的不同,基于矩阵运算的连接预测方法分为基于图的核函数方法、基于矩阵分解的方法和基于矩阵完全的方法.
1.3.1 基于图的核函数方法Kunegis等人[86]提出了一种利用图的核函数的方法来解决链接预测问题.这种方法训练学习一种核函数,可直接作用于图的邻接矩阵或图的拉普拉斯矩阵,从而得到反映顶点对之间存在链接可能性的指标.
设A和B分别为链接预测的训练集和测试集上的两个邻接矩阵,设它们具有相同的顶点集.现在要找到一个谱变换函数F,它以最小误差将A映射到B,该误差可由以下优化问题的解给出:
(29) |
其中‖·‖F表示Frobenius范数.这里的约束条件要求函数F属于谱变换函数族S.设对称矩阵A的特征分解为A = UΛUT,其中U为正交阵,Λ为对角阵.对于谱变换函数F,有F(A)= UF (Λ) UT.式(29)中的优化问题可以通过计算A=UΛUT的特征值分解,并利用矩阵的Frobenius范数在正交变换下的不变性来解决.即:
(30) |
由于表达式(30)中的非对角线元素与函数F的计算无关,因此优化问题(29)可以转换为如下所示的实数体上的优化:
(31) |
这样,链接预测问题就转化为一维最小二乘法的曲线拟合问题.
为了解决链接预测问题,我们要寻找函数F,它以网络的邻接矩阵为输入,输出矩阵中的元素标志着相应的顶点对之间的相似性.目前已经有如下图的核函数可用作为函数F:
1) 指数核.对于未加权图的邻接矩阵A,幂An表示链接所有节点对长度为n的路径的数量.由于较多个路径链接的节点应该比较少路径链接的节点更相似,用于链接预测的函数F可定义如下:
(32) |
随着i变大,常数αi的值将会减小,以减小较长的路径的影响.这样,指数核函数可以表示如下:
(33) |
2) 冯·诺依曼核.它的定义类似于指数核:
(34) |
它也是一个基于路径计数的核函数.
3) 拉普拉斯核.在该方法中的核函数的变量不限于邻接矩阵,也可以使用拉普拉斯矩阵L = D - A,其中D是对角度矩阵.归一化的拉普拉斯矩阵L可定义为L ′= I-D-1/2LD-1/2.许多图上的核方法都是在拉普拉斯矩阵上定义的.例如,通过拉普拉斯算子的Moore-Penrose伪逆,可以得到通勤时间核:
(35) |
通过应用正则化,我们可以获得正则化的通勤时间核:
(36) |
我们还可以获得如下的热扩散核:
(37) |
基于矩阵分解的方法视链接预测为矩阵变换问题,它们将图的邻接矩阵A分解成A=UΣUT,其中,U∈Rn×k,Σ∈Rk×k,其中n是节点数,k是隐特征的数量.这样,每个节点x具有相应的隐向量ux∈Rk.定义一个链接函数L(·),对于节点对(x,y),模型的预测得分为L(uxTΣuy).对于有向网络,其邻接矩阵是一个非对称阵,此时可将其分解为A=UVT的形式.这个分解过程可以看成是将A向一个隐空间映射的过程,而隐空间反映了潜在的链接.
近年来出现了不少采用矩阵分解技术的链接预测方法[87-94],取得了较好的预测效果. 表 8显示了基于矩阵分解的链接预测主要方法,比较它们所使用的矩阵分解形式,以及它们的特点和适用范围.
方法 | 矩阵分解形式 | 特点及适用范围 |
Menon,等[87] | 将对称邻接矩阵A进行分解 | 该方法将隐特征与节点和链接的显式特征通过双线性回归模型相结合,适用于一般网络. |
Nahla Mohamed Ahmed,等[88] | 对邻接矩阵A进行非负矩阵分解 | 该方法从动态网络的时序和拓扑结构中学习隐特征,以获得更高的预测结果,适用于动态网络链接预测问题. |
Wang,等[89] | 将邻接矩阵和一些其他拓扑矩阵进行联合分解 | 不仅考虑了对称度量,而且还考虑了非对称度量,适用于一般的有向和无向网络 |
郝占刚[91]等 | 把链接预测看作一个有监督的矩阵“去噪”问题 | 通过社交网络的链接矩阵获取所需的相似度矩阵,提高了链接预测的质量.适用于社交网络. |
Ma,等[92] | 对时序邻接矩阵进行联合非负矩阵分解 | 对每个时域的网络进行分解,利用图的可通信性获取特征,然后对特征矩阵进行分解,以预测各个时域链接.适用于时序网络. |
Meng,[93]等 | 矩阵的截断奇异值分解 | 通过网络演化过程中节点的行为来识别网络中节点活动水平,将稳定节点作为噪声处理,排除稳定节点的干扰.适用于动态网络. |
Gao[97] | 对时序网络的链接矩阵序列进行张量分解 | 适用于多关系时序网络 |
矩阵完全又称为矩阵填充或矩阵重构等,它可从稀疏的测量值中,近似或完全地重构出缺失数据和未知数据.由于网络数据具有稀疏性,难免会影响和降低预测的准确性,而基于低秩矩阵完全的网络链接预测算法可以在不改变原有数据的情况下恢复缺失数据并进行填充,从而对未链接的边进行预测.
高曼等人[95-96]提出了一种基于矩阵完全技术的网络链接预测算法.该算法将网络的邻接矩阵看成是稀疏的带噪声的测量值,通过矩阵完全得到恢复后的低秩矩阵,以此来求解顶点间的相似度值.他们提出了一种求解矩阵完全的迭代算法,使用前向—后向分裂来同时极小化核范数、和L2,1范数.他们定义了奇异值上的一个随机投影收缩算法,大大降低了基于相似度的链接预测算法的时间复杂度.他们还将基于矩阵完全的算法用于多关系网络的链接预测中[95],有效地预测社会网络中的潜在的人际关系.
Hsieh等人[97]基于正样本和无标签样本(PU)的学习方法,研究了基于矩阵完全的链接预测,使用了核范数规范化了的加权目标函数.尽管加权目标函数改进了预测结果,但是,由于随后得到优化是非凸的,因此会受到不稳定性的影响.文[98]引入了特定节点的度先验,并使用Lovasz extension学习由高斯模型形成的无标度网络. Mohtashemi等人[99]提出了一种基于对数正态矩阵完全的大规模链接预测方法,并采用交替方向方法解决了复杂优化问题,获得了高质量的预测结果.刘冶等提出基于低秩和稀疏矩阵分解的多源融合链接预测算法[100],以及基于低秩和局部约束矩阵估计链接预测算法[101].以上各种算法都证明了矩阵完全是链接预测的有效方法.
1.3.4 基于矩阵运算的链接预测方法比较对于以上所述的三类基于矩阵运算的链接预测方法,即基于图的核函数的方法、基于矩阵分解的方法和基于矩阵完全的方法,它们的各自特点和适用范围如表 9所示.
方法 | 特点 | 适用范围 |
基于图的核函数的方法 | 具有通用性和简单性,要学习的参数数量较少.但是,该模型不能集成顶点的属性.计算成本主要取决于矩阵A的特征分解,其计算时间代价较高 | 适用于网络规模较小、顶点无属性特征的网络 |
基于矩阵分解的方法 | 可以对邻接矩阵、拉普拉斯矩阵、属性矩阵等进行联合分解,也可对动态网络、多关系网络的邻接矩阵序列进行分解 | 适用于一般网络、动态网络、多关系网络 |
基于矩阵完全的方法 | 能够克服网络数据的稀疏性,可以在不改变原有数据的情况下恢复缺失数据,从而提高预测精度 | 适用于稀疏网络、精度要求较高的应用问题 |
概率关系模型(PRM)是一种对网络的建模工具,它提供了一种系统的方法来合并顶点和边的属性以建模一组实体和它们链接的联合概率分布. PRM的优点在于它可以通过捕获实体和链接本身之间的概率交互来反映网络中的对象—关系的结构. PRM有多种构建模型的方法.例如,基于贝叶斯网络模型,它考虑有向的关系链接[102]; 基于关系马尔可夫网络模型,它考虑无向的关系链接[103];关系依赖网络模型[82],它用有向图表示属性之间的依赖关系.虽然上述三者都适用于链接预测任务,但无向模型由于其灵活性更合适大多数实际网络.
PRM模型中的顶点可以表示混合异构实体.以共同作者网络中的链接预测问题为例,顶点可以表示作者,也可以代表其他相关对象,例如论文、出版商和学校等.在模型PRM中,每个实体都可以具有属性.这样,模型可以包括类似于对象关系数据库的完整关系模式.
对于链接预测任务,可以对关系模式进行扩展[102-103],使得链接成为模型中的一级对象,因此在关系模式中添加了名为链接对象的附加对象,该对象涉及两个个体,它有一个二元属性exist,如果关联的个体之间存在链接,则为true,否则为false.链接预测的任务就归纳为预测这些链接对象的exist属性的问题.在模型的训练过程中,在整个链接图上定义一个概率模型,包括对象标签和对象之间的链接.然后通过训练来得到模型的参数,以最大化对象和给定已知属性的链接标签的概率.最后根据所学习到的模型来进行链接预测.
1.4.1 关系贝叶斯网络关系贝叶斯网络(RBN)是基于贝叶斯网络的关系表达,它是一组基于条件概率分布的有向无环图G=(V,E,p),V的每个节点代表一个变量,即网络中对应实体的属性变量,E为有向边集合,表示变量之间的关系;p为一组条件概率,对应于顶点v的条件概率,表示为P(v|pa(v)),表示节点v的父亲节点pa(v)对v的影响.与一般贝叶斯网络一样,RBN联合概率分布可以根据无环图结构中的依赖性进行分解,这样,该贝叶斯网络的联合概率分布为
(38) |
对RBN的学习过程与对一般贝叶斯网络的学习过程大体上相同.
Wu等人[104]改进了已有的朴素贝叶斯方法,提出了一种新的基于相似性的朴素贝叶斯网络的链接预测方法,他们引入了树增广朴素贝叶斯概率模型.该模型减轻了共享近邻之间的强自主性假设,使之与实际网络更符合,因此具有较好的链接预测能力.
1.4.2 关系马尔可夫网络关系马尔可夫网络(RMN)是基于无向图模型或马尔可夫网络的关系表达[105].设V表示一组离散随机变量,v是V中的一个变量实例,则V的马尔可夫网络可以通过无向关系网络和一组参数定义为V上的联合分布.对于图G,如果C(G)是G的完全子图的集合,则马尔可夫网络联合概率分布为
在具有大量关系属性的大型网络中,网络数据的规模通常较大,因此通常不能求得精确解,可使用置信传播进行训练.
1.4.3 关系依赖网络模型关系依赖网络模型(RDN)[82]与上述两个模型不同,它运用伪似然估计方法分别对每个变量的条件概率进行估计,而无需优化整个联合概率分布.关系依赖网络模型在估计条件概率Pv|pa(v)时,并不考虑条件概率P(pa(v)|v).由于对变量的估计是独立的,相比关系贝叶斯网络和关系马尔可夫网络模型,其计算复杂度要低很多.与关系贝叶斯网络相似,关系依赖网络模型也是用有向图表示属性之间的依赖关系,但是它允许环的存在.
除了上述三个模型之外,还有一些可用于链接预测的其他关系模型[107-111].如有向无环概率实体关系模型DAPER[108],层次参数贝叶斯关系模型[109],层次化非参数贝叶斯关系模型[110]和随机关系模型[111]等.
1.5 各类链接预测方法的比较对于以上所述的四类链接预测方法,即基于相似性指标的方法、基于机器学习的方法、基于矩阵运算的方法和基于概率模型的方法,它们的各自特点和适用范围如表 10所示.
方法 | 特点 | 适用范围 |
基于相似性指标的方法 | 1)通过得出未知边上的相似性指标来确定该边出现的概率; 2)仅依赖拓扑信息,不与顶点或边的属性相结合; 3)大部分指标的计算量较小. |
对实时性要求较高、精度要求较低、不考虑边和顶点属性的应用问题 |
基于机器学习的方法 | 1)需要通过训练一个模型,然后通过该模型对未知边进行预测; 2)可以结合顶点或边的属性特征来建立模型; 3)大部分的训练方法的计算量较大. |
拓扑、属性特征比较明显的网络,包括静态和动态网络 |
基于矩阵运算的方法 | 1)通过对邻接矩阵等进行变换、分解、填充等运算,将其映射到一个隐空间上,然后通过该隐空间对未知边进行预测; 2)可以结合顶点或边的属性信息; 3)大部分矩阵运算的计算量较大. |
由矩阵表示拓扑、属性特征的网络,包括动态网络、多关系网络、带权网络 |
基于概率模型的方法 | 1)能够合并顶点和边的属性以建模来反映链接的联合概率分布. 2)可以通过捕获实体和链接本身之间的概率来反映网络中的对象—关系的结构. 3)对模型的训练的计算量较大. |
已知顶点拓扑、属性特征以及它们所代表的对象之间的关系的分布的网络 |
大多数现有的链接预测工作主要集中在同构网络上,即网络中仅存在一种类型的节点或链接.然而,许多社交网络包含不同的链接类型和不同类型的节点,这些节点可能具有不同的拓扑结构或链接形成机制,并且它们之间会相互影响.我们称此类网络为多关系网络或异质网络.现实世界中的大多数网络都是异质的,例如在多关系社交网络中,个体之间存在着诸如朋友、亲戚、同事等异构关系.因此,对这种异构社交网络的链接预测也是一项非常重要的任务.近年来,相继出现了一些异构信息网络上的多关系链接预测(MRLP)方法[28, 94, 112-113].这些方法大致上可归为如下三类:
1) 基于相似度指标的方法
这是异构社交网络链接预测的基本方法.这类方法将相似度指标扩展到异构社交网络之中,结合多个网络的拓扑信息建立各种不同的相似度.例如,Ströele等[114]提出了一个基于3个基本指标的综合指标:节点度、共同邻域和Katz指标,以预测科学社交网络中的新关系. Shakibian等人[115]提出了一种基于元路径的相似度度量方法,其主要思想是在遵循元路径的访问节点之间发生的多个共现矩阵中发现一些共现事件.从能量、惯性、局部同质性、相关性信息等方面分析提取的共现矩阵,以确定各种信息的测度.
2) 基于机器学习的方法
这也是进行异构社交网络链接预测的常用方法.这种方法首先提取异构社交网络的拓扑结构信息作为特征,如三角形结构、路径、影响力的传播等,然后训练适当的模型进行链接预测.例如,Wang等人[116]发现人员流动性信息有助于预测异构网络中的多种类型的链接,具有与基于传统网络指标相当的预测能力.通过将流动性和网络指标相结合,他们发现利用监督学习进行的预测,其结果的准确性可以得到显著提高. Li等人[68]提出了一种基于元路径特征的BP神经网络模型MPBP,用于预测异构网络中的多种链接类型.他们引入元路径的概念,然后提取异构网络中元路径的特征,利用三层BP神经网络建立了有监督的链接预测模型.然后,通过对网络进行迭代训练得到预测结果.
3) 基于矩阵运算的方法
此类方法将异构社交网络及其顶点和边的属性转化为矩阵表达,通过对矩阵的变换、分解、填充等运算得到隐空间,在隐空间中进行链接预测.例如,戴彩艳等人[112]提出了一种基于矩阵分解的方法,用于检测多关系网络中给定类型的潜在链接.该方法考虑了不同类型关系之间的相似性和影响力.利用不同类型关系之间的相似性和影响力,该方法通过非负矩阵分解来预测目标类型的链接.
然而,异构网络中的链接预测的研究中仍然还有一些尚待研究的问题.例如,异构社交网络中链接预测的可扩展性问题[117]等.
2.2 时序网络在实际应用中,网络的链接往往是动态变化的,我们在链接预测时,需要考虑时间的因素,这就是时序链接预测[117-119]问题.具有N个顶点的时序社交网络可以表示为三阶张量或多维阵列.规模为N×N×T的张量Ζ可以定义为
(39) |
由Z给出了从时间1到T的社交网络链接的变化,时序链接预测就是要预测该网络在时间T+1时的链接.近年来,相继出现了一些时序网络上的链接预测方法[120-125].这些方法大致上可归为如下三类:
1) 基于相似度指标的方法
这是时序社交网络链接预测的基本方法.这类方法将相似度指标扩展到时序网络之中,结合多个时间点的拓扑信息建立各种不同的相似度. Soares和Prudêncio等人对每对非链接节点计算它们在过去不同时间上的相似性得分,建立了时间序列[120].随后,他们设计了一个基于时间序列的预报模型,以获得节点对的最终链接预测得分.他们[121]还提出了一种基于时序事件的相似度指标的链接预测方法.在该方法中,基于事件的指标将随着时间而更新.更新过程主要通过奖励观察到的节点对和它们的邻域之间时序事件而实现.该方法根据网络链接的动态性变化来更新节点对的指标,即奖励形成或保留链接的节点对,并惩罚不再链接的节点对.陈莎等[122]提出一种基于网络局部信息的混合相似性指标,进而根据该混合相似性指标预测网络动态链路.
2) 基于机器学习的方法
这也是时序网络链接预测的主要方法之一.这种方法提取时序网络的拓扑结构的变化信息作为特征,然后训练适当的模型进行链接预测.如何提取时序社交网络的特征,是该类方法的关键问题. Richard等人[123]研究了时序网络的链接演化规律,指出,随时间推移而变化的拓扑特征有助于预测未来的链接.他们认为,网络的某些少量的特征,可以捕获网络的演化动态并有助于预测未来的链接.他们方法的主要思想是,学习网络中的局部特征在各个时间点上的值,然后使用这些特征值预测下一个时间段的相应特征值,并用来发现缺失的链接.陈德华等[126]提出一种面向时序知识图谱的链接预测模型,并利用递归神经网络提取时序知识图谱中的三元组时序特征,从而实现对时序知识图谱的链接预测.
3) 基于矩阵运算的方法
此类方法将时序网络的拓扑和属性的矩阵表达进行运算得到隐空间,在隐空间中进行链接预测.例如Dunlavy等人[118]将基于矩阵和基于张量的技术相结合,提出了一种时序网络链接预测方法.对于基于矩阵的部分,该方法将张量表示的网络数据通过将不同时间上的所有实体求和,从而将网络折叠为一个矩阵.然后,链接预测的得分矩阵可以通过截断SVD计算得到. Gao等人[127]提出了一种基于隐空间矩阵分解和图形正则化技术的模型,该模型集成了顶点属性和结构信息,以获取网络中链接的时序演化模式.该方法利用交替迭代算法来得到网络中节点在隐空间的映射,从而进行链接预测. Ma等人[128]提出了一种正则化非负矩阵分解算法(GrNMF). GrNMF通过对与网络相关的矩阵进行分解,从而得到网络在每个时刻的特征.然后,GrNMF算法对特征矩阵进行分解,以预测未来链接.
2.3 带权网络带权网络是一种常见的社交网络[27],其中的每个链接都赋予一个权重用来表示相应链接的强度.在这样的网络中进行链接预测,需要在已有的链接预测方法的基础上考虑网络中的链接强度对预测结果的影响.
对于链接强度对链接的影响,有两种观点:有一些研究[129]表明,强链接在链接预测中很重要;而另一些研究[130]表明,弱链接在链接预测中很重要.陈旭等人[131]对强、弱链接进行了这样的假设:(x,z)为强链接而(z,y)为弱链接时,链路〈x,z,y〉对节点x和y之间形成链接的贡献最低.因此,链路〈x,z,y〉对节点x和节点y之间的相似性得分S(x,y)的贡献度的削弱程度最大.吕琳媛和周涛[130, 132]的研究发现,弱关系理论在链接预测中起着比强关系更重要的作用,即链接预测中的弱链接效应:给原来权重较低的边赋予较大的权重,而原来权重大的边赋予较小的权重,用新的权重会得到更好的预测效果.近年来,相继出现了一些带权网络上的链接预测方法[124, 133-138].这些方法大致上可归为如下四类:
1) 基于相似度指标的方法
该类方法将一般网络上的相似性指标推广到带权网络中.例如,Lin等人[133]利用网络的权重和结构信息,定义了一种根据权重值对节点权限进行评级的机制,称为BenefitRank.该机制可以灵活地收集不同阶邻居的节点信息,以确定加权网络中每个节点的评级权限.同时,他们利用BenefitRank结合弱关系理论,提出了相似性指标来估计加权网络中节点之间未来链接出现的可能性.在实际加权网络上进行的实验结果表明,该方法可以提高加权网络中的链接预测的精度. Chen[134]等人将相似度度量SimRank推广到带权网络中,提出了非对称的SimRank指标用于带权网络的链接预测.
2) 基于机器学习的方法
基于机器学习的方法将权重融入拓扑结构的特征中,然后训练适当的模型进行链接预测.例如,Sa和Prudencio等人[139]在抽取带权图的拓扑特征的基础上,使用链接权重表示关系的强度,使用朴素贝叶斯分类、支持向量机等方法训练预测模型.他们的实验结果表明,当考虑权重时,该方法对共同作者网络的预测显示出令人满意的结果. Kunegis等人[70]对带权图的邻接矩阵应用了图的拉普拉斯核函数与降维技术,对带权网络进行链接预测,使得运行时间仅依赖于所降到的维数,而与原网络的大小无关. Moradabadi等人[135]提出了一种基于学习自动机的加权链接预测方法,该方法使用连续动作集学习自动机来学习每个测试链接的最佳权重,再根据当前网络的权重信息来预测每个链路的出现可能.
3) 基于矩阵运算的方法
此类方法将加权网络中的带权拓扑和属性矩阵表达进行运算,在所得到的隐空间中进行链接预测.例如Pech等人[124]使用主成分分析引入了一种基于矩阵低秩表示的带权网络链接预测方法.在该方法中,目标网络的带权邻接矩阵被分解成低秩矩阵和稀疏矩阵.其中低秩矩阵表示包含真实链接网络的空间,而稀疏矩阵则包含了网络中的损坏或虚假链接.
4) 基于概率模型的方法
该类方法合并顶点和边的权重等属性以建模来反映链接的联合概率分布.例如,Wind等人[136]按照局部概率模型研究了在带权网络中恢复的缺失边时使用权重信息的效果.他们将基于泊松分布的模型用于加权单部和二部网络之中,但是他们发现权重信息并没有改善链接预测结果.这说明复杂的模型对边的过度拟合,导致了恢复真实的边权重的能力较差.
2.4 不确定网络一些社交网络中的链接往往具有不确定性,这些网络被称为不确定社交网络.由于在实际应用中所采集的数据往往存在不准确性、不完整性和噪声,所以不确定性应该是现实世界网络中的自然特征.例如,在生物信息学领域,有一些工作将蛋白质—蛋白质相互作用(PPI)网络建模为不确定网络[3, 140-141],然后在不完整的蛋白质复合物中利用链接预测的技术预测蛋白质的存在性.在社交网络中,社交互动和社会关系的可能性会受信任和影响力问题的影响[142-144].在电信或电子邮件网络中,社会组织或个人之间的交流可能是随机发生的[145-146].
不确定图[147-148]是描述这种不确定网络最合适的模型[149-153].在该模型中,每条边被赋予一个概率以表示其在网络中存在的可能性.通常,一个网络的结构特征可以由表示边的不确定性的概率函数和网络的拓扑特征来表示.由于在不确定网络中存在大量可能的实例[149-150],我们称其为可能世界.为了计算所有节点对之间的相似性,需要大量时间来枚举所有可能的世界.因此基于这种模型的链接预测将极其复杂.例如,在确定性网络中顶点之间的可达性问题只需要线性时间,但在不确定的网络中,它是一个#P完全问题[149].因此,有必要设计有效的方法来预测不确定网络中的潜在链接.
常用的不确定网络的连接预测方法有:基于相似性指标和基于机器学习的方法,但在实际应用中,由于不确定网络链接预测问题的复杂性,常常需将二者相结合使用.
1) 基于相似性指标的方法
为了对不确定网络中的链接进行预测,可以为每对节点分配一个相似性指标,该相似性指标与两个节点之间链接的可能性成比例.该指数可以从图上的边的不确定性计算得到.例如,Ahmed等人[154]提出了一种在不确定网络中进行链接预测的方法.该算法首先将不确定网络中的链接预测问题转换为确定性网络中的随机游走.然后,在该节点周围的子图内计算节点与其邻居之间的相似性得分,避免了枚举所有的可能世界.
2) 基于机器学习的方法
该方法从不确定网络中提取各类特征的期望值,并训练适当的模型进行链接预测.例如,Kang[155]提出了一种时空不确定性网络(STUN)模型来定义不确定社交网络,并提出了STUN子图匹配查询的方法.在文[156]中,Potamias等人提出了一种用于计算不确定网络中的K-近邻的方法,以减少计算节点对之间相似性的时间. Behnaz Moradabadi等人[157]提出了一种基于学习自动机的不确定社交网络链接预测方法.他们首先重新定义了一些用于不确定图中链接预测的相似度度量,然后提出了一种基于学习自动机的方法.该方法假设链接上的概率的分布是未知的,从而计算所提出的相似度度量的分布.
2.5 带有活跃/不活跃状态链接的网络在动态网络中,为了区分链接出现的新旧程度,我们可对每个链接定义一个活跃或不活跃的状态,这就构成了带有活跃/不活跃状态链接的网络. Munasinghe和Ichise[158]对此给出了一个假设:如果两个节点之间最近发生了相互作用,那么它们之间的链接就会变为活跃状态.可见最后一次链接的时间戳是决定链接活跃性的重要信息.因此,节点之间交互的最新时间戳可用于链接预测计算.他们提出了基于PropFlow度量的T_Flow指标.该指标考虑了链接权重以及链接活跃性来计算转移概率,同时引入了衰减函数来描述信息的衰减.对于两个相邻节点x和y,衰减函数可以定义为d(x,y)=(1-α)|tx-ty|,0 < α < 1.则由直接链接从节点x到y的T_Flow指标可以计算如下:
(40) |
如果节点x和y是间接链接的,则可以通过从节点x到y的所有最短路径递归地计算T_Flow并求和.两个节点之间的总流量被视为它们之间的T_Flow. T_Flow在具有活跃和非活跃链接的社交网络中的性能优于PropFlow.
Chen等人[159]在FOAF社交网络中观察到,最近的链接在链接预测中比旧的链接更重要.基于这一观察结果,他们提出了关系强度相似性(RSS)度量,并应用于共同作者网络的链接预测中. RSS度量是为加权网络设计的少数几个相似度量之一,并且可以轻松地模拟FOAF网络.它根据作者的共同创作历史为链接分配不同的权重,结果表明新关系强度有助于预测新链接.新关系强度同时考虑了合著论文数量以及vi与vj之间的权重,具体定义为
(41) |
其中,ni,j(tnow)是在时间tnow上的边权重. Chen等人[160]在几个真实世界数据集上的实验结果表明,在预测未知链接时,较新的链接比旧链接更具有价值.由于较旧的链接对链接预测的作用较小,因此在研究网络演化时可以适当地将它们删除.
2.6 符号网络在很多真实的社会网络体系中,两个节点之间的链接可能呈现出截然相反的性质,这就形成了带符号的网络.在带符号网络中,用户之间的关系可以是正的,即表示用户之间的关系是信任、友好、支持或者相爱的;用户之间的关系也可以是负的,即表示用户之间是不信任、不友好、不喜欢或者是敌对的.由于在带符号网络中有两种类型的符号,所以带符号网络中的链接预测不仅要预测出未知链接的符号,还要根据网络的拓扑信息和网络中现存的链接的符号,预测出潜在链接符号为正或者为负的概率.自Guha等人[143]提出了在带符号的社交网络中进行信任度传播的工作后,有关带符号网络的研究已经引起了广泛关注[161].对于符号网络的链接预测,常用的方法由基于社会平衡理论、基于社会地位理论、基于社区划分等方法.
1) 基于社会平衡理论的方法
在带符号网络中,带符号的链接反映了用户之间的社交关系,如朋友、敌人或竞争对手等.但是这样的关系受着社会平衡理论的约束.社会平衡理论实际上是对社会稳态结构的一种描述,它遵循所谓“敌人的敌人是朋友”、“朋友的敌人是敌人”等规律.根据这样的规律,可以很容易地判断未知边的符号,因此许多带符号网络的链接预测算法借助了社会平衡理论.
例如,Chiang等人[162]使用路径长度为k的环来衡量网络的不平衡性,使用分类算法来预测潜在链接的符号和链接存在的概率. Patidar等人[163]基于用户的属性信息,首先训练出一个分类器来预测未知的链接,然后再根据社会平衡理论预测未知链接的符号.赵衎衎等[164]提出了一种基于端到端分布式框架的预测算法,应用于社交网络正负符号预测.
2) 基于社会地位理论的方法
社会地位理论是针对有向社会网络的,它企图将社会网络中的个体的关系映射到一个有向无环图,从而对所有个体定义一个偏序关系.这样的映射需要参考边上的方向和符号等信息,根据这样的关系,很容易判断未知边的符号.因此许多带符号网络的链接预测算法借助了社会地位理论.例如王鑫等[165]利用社交网络中的交互意见和地位理论构建了符号网络链接预测模型,实现符号网络链接预测.
3) 基于社区划分的方法
由于带符号网络中顶点之间存在着正负关系,这就自然地将顶点划分为若干社区,使得在同一个社区内的顶点间是正的链接,这种将网络顶点划分为社区的过程又称为网络聚类.社区结构无疑为带符号网络的链接预测提供了有益的信息.因此,出现了很多基于网络聚类的带符号网络链接预测的方法.
例如,Javari等人[166]提出了一种使用聚类和协同过滤技术的基于相似度的方法来预测带符号网络中的正负链接.他们定义了带符号网络中衡量类之间相对相似性的指标.基于类间相对相似性,将网络中的节点分为一定数量的社区,而且每个社区都是平衡的.然后,使用基于用户的协同过滤算法在每个社区内来预测网络中潜在的链接.他们的方法有效地解决了带符号网络数据集的稀疏性问题.
此外,一些研究工作发现,带符号网络中符号为负的链接在链接预测的过程中,比符号为正的链接起着更大的作用.很少数量的符号为负的链接对网络的拓扑结构的影响要比正链接大得多,它们能够提高对符号为正的链接预测准确度和社交网络中推荐系统的性能.
2.7 二分网络许多社交网络是二分网络,例如用户—产品网络、作者—论文网络等.然而,常见的链接预测方法通常是为单分网络设计的,这些方法往往对网络有如下假设:1)具有三角形闭合性,即新的边倾向于形成三角形;2)聚合性:即新的边倾向于使得节点在网络中形成链接稠密的聚类.但是在二分网络中不会出现三角形和团结构,这些假设并不成立.因此,虽然可以将二分网络看成一般网络,将一些单分网络上的链接预测方法直接应用于二分网络,但它们的性能往往不会很好.因此,要将二分网络的连接预测问题转化为单分网络上的链接预测,其转化的方法有:
1) 将单部图上的相似性指标扩展到二部图的链接预测之中.
例如,Kunegis等人[167]发现,在基于局部的相似性指标中,只有PA指标可以用于二分网络.利用图的核函数的链接预测方法可以用于二分网络,但是需要通过将谱变换限制为奇函数,使用矩阵双曲正弦作为链接预测函数.也有人将基于CN、Jaccard、AA和PA等相似度指标的经典链接预测方法扩展到二分网络[168-170].这些方法的核心思想是使用邻居的邻居来取代直接邻居.
2) 用单部图或带权图来模拟二部图.
例如,Allia等人[169]通过投影将二分图转换为单部图,然后引入了内部链接的概念,通过检测内部链接在二分图中进行链接预测.高曼等人[171]将二部图投影到一个单部图,在此基础上定义了潜在边的概念,定义了潜在边所覆盖的模式以及模式的权重,通过潜在边所覆盖的模式的权重来计算潜在边的可信度,作为该潜在边上存在实际链接的评分. Liu和Deng基于资源分配方法,提出了一个时间加权网络来模拟用户—对象网络的演化[172].他们的分析表明,时间衰减和转移延迟在用户—对象网络中的链接预测中起了关键作用.
2.8 具有地理信息的网络近年来,基于地理位置的在线社交网络已经吸引了数百万用户.人们开始越来越多地与他们的朋友分享他们的位置,他们通过在线签到并广播给朋友,以生成和共享与地点相关的消息、提示或其他信息.与许多其他在线社交服务一样,基于地理位置的网络链接预测可以向用户推荐新的朋友[124].
社交网络可能拥有数百万个节点,但同时它们通常稀疏,导致这些节点之间的链接密度较低.因此,链接空间高度的不平衡性会导致许多预测方法仅仅集中于在2跳社交邻域中找到朋友,即用户朋友的朋友.如果将预测工作扩展到3跳邻域以致更远,可能会得到指数级的候选集合.因此,链接预测问题受用户之间的网络距离的影响很大,而网络距离往往与地理位置密切相关.
在基于地理位置的社交网络中,每个用户访问的位置是非常重要的信息.可以利用有关用户签到场所的数据来预测未来的链接[4, 71, 173].例如,Scellato等人[71]提出了一种预测模型,他们结合物理距离和签到数据等地理特征进行链接预测. Lee[4]等人设计了一个基于地理和社会属性的链接预测模型.他们通过使用社会、地理和人口统计的新特征,和拓扑特征一起并采用学习算法进行链接预测,提高了预测质量.
3 复杂网络的链接预测结果的评价 3.1 交叉验证(Cross-Validation)法为了对复杂网络链接预测的结果进行评价,常将已知边划分为两组,一部分作为训练集(train set)供预测算法使用,另一部分作为验证集或测试集(validation set or test set)用来评估该算法结果的精确度.
划分训练集和测试集的常见方法有三种:
1) 简单交叉验证(Hold-Out Method)
将已有边随机分为两组,一组作为训练集,一组作为验证集.这种方法处理简单,只需随机地把边的集合分为两组即可,同时由于测试集和训练集是分开的,就避免了过拟合的现象.但是在验证集上预测的准确率的高低与原始数据的分组有很大的关系,所以这种方法得到的结果往往不具有可靠性.
2) K折交叉验证(K-fold Cross Validation,记为K-CV)
将已有边均匀分成K个子集,每次将其中一个子集作为验证集,其余的K-1组子集作为训练集,这样会得到K种结果,用这K个结果在验证集上的分类准确率的平均数作为此K-CV下的性能指标.这种方法可以有效地避免过学习以及欠学习状态的发生,最后得到的结果也比较可靠.
此外,还有其他的基于抽样的划分训练集和测试集的方法,如滚雪球抽样、熟识者抽样、随机游走抽样、基于路径的抽样等.
3.2 评测指标对于复杂网络的链接预测结果评价的常见标准度量有AUC指标、精确率(Precision)和排序分(Ranking Score)等.
3.2.1 AUC指标令ET为训练集,EP为测试集,EN为不存在链接的顶点对的集合,U为所有可能的顶点对的集合,记H=U-ET=EP∪EN为测试集中EP的边和不存在边的集合EN的并集.给定一种链接预测的方法,需要对H中每个节点对(x,y)赋予一个分数值Sxy,如果根据它们的得分对H中节点对进行排名,则AUC度量可以被解释为在测试集EP中随机选择的一条边比在EN中随机选择的不存在的边具有更高分数的概率.在算法实现中,每次通常以随机方式选择测试集EP中的链接和EN中不存在的链接并比较它们的分数.如果在n次独立比较中,有n′次EP中的链接得分较高,而n″次得分相同,则AUC值
(42) |
如果所有得分均来自独立且相同分布的随机取值,则AUC值应为约0.5.因此,如果AUC的值大于0.5,则优于随机链接预测算法;该值超过0.5的程度越大,表明该算法越准确.
3.2.2 精确率精确率定义为:在得分最高的前L个预测边中被预测准确的比例.如果有m个预测准确,即排在前L的边中有m个为存在的边,则精确率定义为
(43) |
对于给定的L,precision越大则预测结果越准确.如果两个算法AUC相同,则precision较大的算法更准确,因为它将具有连边的节点对具有较高的得分.
3.2.3 排序分排序分主要考虑测试集中的边的得分在排序中的位置.记H=EP∪EN为测试集中EP的边和不存在的边EN的并集,re表示测试集中的边e∈EP在排序中的排名,那么这条测试边的排名分为
(44) |
将测试集中所有的边的排序分求和,就得到整个结果的排序分为
(45) |
排序分RS的值越小说明算法的预测质量越高.
上述三种评价指标对预测精确度衡量的侧重点不同,AUC指标从整体上衡量算法的精确度,精确率只考虑对排在前L位的边是否预测准确,而排序分偏重于考虑对所预测边的排序情况.
4 复杂网络的链接预测的新课题尽管目前在链接预测研究方面已经有了很多成果,但是依然存在许多潜在的挑战,一些新的问题仍需要进一步研究.
1) 消失的链接预测问题
大多数现有的链接预测工作都集中在对于可能出现的链接进行预测,只有少数工作研究将来可能消失的链接的预测[174]问题.预测未来可能消失的链接也有非常重要的实际意义,但要解决这个问题其实并不容易.预测消失的链接不是预测出现或缺失链接的逆问题.因为链接消失的机理与链接形成的机制不同,所以,我们不能将当前的链接预测方法直接应用于预测消失的链接.例如,找到具有低相似性的节点对的方法并不适用于这个新问题.
要解决这个问题,首先要理解链接消失的机制,然后才能设计合理的方法.解决这个问题的关键在于建立适当的模型来描述链接消失的机制.这往往需要具体应用领域的知识.例如,在蛋白质相互作用网络中,要揭示蛋白质之间相互作用的消失机制,这就需要对蛋白质相互作用的产生、演化、消失过程的生物学原理做深入的了解,找出促使相互作用消失的因素,在此基础上预测哪些作用将会消失.
2) 链接的不平衡问题
链接预测问题总是会受到极端不平衡的影响,即:已知存在的链接数量通常会远小于已知的不存在的链接数量,这种不平衡会降低许多链接预测方法的有效性.因此,有必要在未来的工作中克服这种不平衡性对链接预测的干扰.此外,在实际数据集中,大多数有用的链接数据非常稀疏,使得链接的先验概率通常会非常小,难以建立链接预测的统计模型,难以进行模型的评估和量化预测的置信水平.
在处理这个问题时,我们不能简单地使用在分类问题中处理训练集中不平衡问题的方法,如欠采样或过采样等方法.这是因为网络的链接预测问题与通常的二元分类问题实际上是不一样的.在链接预测中,若将存在的边看成是正类,则不存在的边不能都看成是反类,它们实际上是不能确定类别的.因此链接预测问题更像PU(positive-unlabeled)学习问题.可参照PU学习问题中解决正样本不足的方法来解决链接的不平衡问题.
3) 融入社会理论
目前社交网络中的大量链接预测方法仅考虑拓扑特征和属性,很少有工作考虑基于社会理论的网络特征.因此,它们只是传统的基于数据挖掘和机器学习技术的解决方案,未能利用社交网络自身的特征.而社会理论反映了社交网络人际交往的特征,对于解释社会活动的机制很有用.因此有必要将社会理论纳入链接预测方法.例如,社会平衡理论、社会地位理论等社会理论可以为有向网络、带符号网络的基于机器学习的链接预测方法提供合理的特征.有研究表明,将现有社会理论纳入链接预测方法可以提高预测精度.然而,计算机科学、物理学等领域的研究人员还未注意到这一点.
社会平衡理论实际上是对社会结构的一种理想状态的描述.然而,在实际的社会网络中,由于人与人之间的关系的复杂性,绝对的平衡关系是不存在的,所谓“敌人的敌人是朋友”、“朋友的敌人是敌人”等规律并不绝对存在.社会地位理论企图将社会网络中的个体的关系映射到一个有向无环图,从而对所有个体定义一个偏序关系.但在实际的社会网络中是很难找到这样的关系结构的.因此,我们在预测中不是要找到完全符合这些社会理论的理想状态的结构,而是要找到最接近这些理想状态的结构,使之最大程度上符合社会平衡理论和社会地位理论,从而利用这种结构进行链接预测.
4) 公平评估和基准数据集
到目前为止,已经有许多方法来解决链接预测问题.然而,如何客观公正地评估这些算法的预测结果的质量,仍然是一个需要研究的问题.因此,需要有更加客观公正的评估方法和标准.此外,我们还缺乏用于链接预测的基准数据集.几乎所有链接预测的研究工作都需要收集实验数据集,但数据集的收集过程非常耗费时间,而且这些数据集在网络规模和网络特征方面会有很大差异.因此,很难公平、系统地比较各种方法的性能.因为链接预测算法的性能在某些数据集中会很好,但在其他数据集中可能会令人很不满意.所以,有些研究人员会选择特定的数据集来支持他们的预测算法,这样会隐藏这些链接预测方法的缺陷.对于计算机科学中的许多问题,人们已经建立了许多基准数据集.对于链接预测问题建立类似的基准数据集,将有助于促进链接预测的研究.
“没有免费的午餐”定理告诉我们,由于算法在所有可能数据集上的性能会相互补偿,所有优化算法的性能在总体上都是等价的.类似地,在链接预测问题中,没有一个算法可以对所有的数据集都能取得最好的预测结果.这是因为每个算法对不同的数据集有不同程度的偏好(bias).正是由于算法对于数据集的这种偏好性,也导致了数据集对算法的偏好性,即,一个数据集用某个算法可以得出很高的预测效果,而用另一个算法却不能.因此,我们很难找出对所有算法都没有偏好的数据集来公正地测试算法的性能.我们只能要求数据集对某一类算法进行客观公正的测试,或者是对某一类问题提供较客观公正的测试数据集,例如,在生物信息领域的蛋白质—蛋白质相互作用网络等.此外,目前大多数的算法评价都是基于离线的数据测试,但是真实系统中的用户行为往往受到多种因素的影响,因此获得真实系统中用户的反馈对于评价算法的性能更加重要.而且,对算法优劣的评价标准也应该根据应用问题的需要来确定.
5) 链接的可预测性问题
真实网络的组织结构通常既有规律性,也有非规律性,原则上,规律性是可以建模的.对网络规律性的可解释程度决定了它的缺失链接的可预测性.为了理解网络组织结构,我们需要估计链接的可预测性,这可以用来提高社交网络链接预测的精度.吕琳媛和周涛[175]等人研究了链接的可预测性问题,他们假设网络的规律性反映在随机去除一小组链接前后网络的结构特征的一致性上.他们提出了一种基于对邻接矩阵摄动的结构一致性指标,该指标无需对网络组织结构的先验知识.在不同的真实网络上进行的大量实验表明,结构一致性是一种很好的链接可预测性估计方法.但是,上述方法是在假设网络的规律性反映在结构特征的一致性上的前提下的.是否有更好、更精确地衡量链接可预测性的指标,还需进一步研究.
上述的结构一致性指标仅能帮助我们比较两个网络的链路可预测性的高低,并不能给出一个可预测性的上界.如何得到一个不依赖于预测算法的链路可预测性上界仍是一个悬而未决的问题.虽然许小可等人[176]通过分析网络演化过程中形成连边的两个节点之间的拓扑距离分布,提出了一种基于此分布概率的方法来刻画基于共同邻居相似性指标的预测上界,但是这一上界是依赖于算法的.如何计算不依赖特定算法的链路可预测性上界,这是一个需要进一步研究的问题.
5 结论链接预测是网络信息挖掘和分析中最基础和最本质的问题,通过对已经观察到的网络结构和其他外部信息的分析,挖掘其中潜在的链接和预测未来的链接.链接预测算法综合应用了相似性分析、机器学习、最大似然分析、贝叶斯模型等多种学科方法和技术,在生物网络分析、个性化推荐、社会关系分析、网络演化模型评价、网络重构等问题上有着广泛的应用.近年来,新的链接预测技术、问题和应用迅速出现,本文总结了社会网络中链接预测主要典型的研究工作,并介绍了对几类特殊网络的链接预测技术和链接预测问题.我们介绍了链接预测结果的评价指标,最后讨论了链接预测领域未来的研究方向和挑战.
[1] |
吕琳媛, 周涛.
链接预测[M]. 北京: 高等教育出版社, 2013.
Lü L Y, Zhou T. Link prediction[M]. Beijing: Higher Education Press, 2013. |
[2] | Zhang L, Hu K, Tang Y. Predicting disease-related genes by topological similarity in human protein-protein interaction network[J]. Central European Journal of Physics, 2010, 8(4): 672–682. |
[3] |
洪海燕, 刘维.
基于空间映射的蛋白质相互作用网络链接预测算法[J]. 计算机科学, 2016, 43(Z6): 413–417.
Hong H Y, Liu W. Link prediction algorithm in protein-protein interaction network based on spatial mapping[J]. Computer Science, 2016, 43(Z6): 413–417. |
[4] | Guimerà R, Salespardo M. Missing and spurious interactions and the reconstruction of complex networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2009, 106(52): 22073–22078. DOI:10.1073/pnas.0908366106 |
[5] | Papadimitriou A, Symeonidis P, Manolopoulos Y. Fast and accurate link prediction in social networking systems[J]. Journal of Systems and Software, 2012, 85(9): 10–20. |
[6] |
尚燕敏, 张鹏, 曹亚男.
融合链接拓扑结构和用户兴趣的朋友推荐方法[J]. 通信学报, 2015, 36(2): 117–125.
Shang Y M, Zhang P, Cao Y N. New interest-sensitive and network-sensitive method for user recommendation[J]. Journal on Communications, 2015, 36(2): 117–125. |
[7] | Vecharynski E, Saad Y, Sosonkina M. Co-author relationship prediction in heterogeneous bibliographic networks[C]//International Conference on Advances in Social Networks Analysis & Mining. Piscataway, NJ, USA: IEEE, 2011. https://www.researchgate.net/publication/221273605_Co-author_Relationship_Prediction_in_Heterogeneous_Bibliographic_Networks |
[8] | Kumar R, Novak J, Tomkins A. Structure and evolution of online social networks[C]//Proceedings of Link Mining: Models, Algorithms, and Applications Conference. New York, NJ, USA: ACM, 2010: 337-357. |
[9] | Li X, Chen H. Recommendation as link prediction in bipartite graphs:A graph kernel-based machine learning approach[J]. Decision Support Systems, 2013, 54(2): 880–890. DOI:10.1016/j.dss.2012.09.019 |
[10] |
李博, 陈志刚, 黄瑞.
用于在线社交网络的链路预测好友推荐算法JAFLink[J]. 小型微型计算机系统, 2017, 38(8): 1741–174.
Li B, Chen Z G, Huang R. Link prediction friends recommendation algorithm for online social networks named JAFLink[J]. Journal of Chinese Computer Systems, 2017, 38(8): 1741–174. DOI:10.3969/j.issn.1000-1220.2017.08.016 |
[11] | Hossmann T, Nomikos G, Spyropoulos T, et al. Collection and analysis of multi-dimensional network data for opportunistic networking research[J]. Computer Communications, 2012, 35(13): 1613–1625. DOI:10.1016/j.comcom.2012.05.003 |
[12] | Jahanbakhsh K, King V, Shoja G C. Predicting missing contacts in mobile social networks[J]. Pervasive & Mobile Computing, 2012, 8(5): 698–716. |
[13] | Lu L, Zhou T. Link Prediction in complex networks:A Survey[J]. Physica A:Statistical Mechanics & Its Applications, 2011, 390(6): 1150–1170. |
[14] | Ahmed H S, Faouzi B M, Caelen J. Detection and classification of the behavior of people in an intelligent building by camera[J]. International Journal on Smart Sensing and Intelligent Systems, 2013, 6(4): 1317–1342. DOI:10.21307/ijssis-2017-592 |
[15] |
刘宏鲲, 吕琳媛, 周涛.
利用链路预测推断网络演化机制[J]. 中国科学:物理学力学天文学, 2011(7): 816–823.
Liu H K, Lü L Y, Zhou T. Uncovering the network evolution mechanism by link prediction[J]. Scientia Sinica:Phys, Mech & Astron, 2011(7): 816–823. |
[16] | Newman M E J. Clustering and preferential attachment in growing networks[J]. Phys Rev E:Stat Nonlin Soft Matter Phys, 2001, 64(2): 025102. DOI:10.1103/PhysRevE.64.025102 |
[17] | Zhou T, Lü L, Zhang Y C. Predicting missing links via local information[J]. European Physical:Journal B, 2009, 71(4): 623–630. DOI:10.1140/epjb/e2009-00335-8 |
[18] | Wang P, Xu B W, Wu Y R, et al. Link prediction in social networks:The state-of-the-art[J]. Science China Information Sciences, 2015, 58(1): 1–38. |
[19] | Lü L, Jin C H, Zhou T. Similarity index based on local paths for link prediction of complex networks[J]. Physical Review E, 2009, 80: 046122. DOI:10.1103/PhysRevE.80.046122 |
[20] | Chen H H, Gou L, Zhang X L, et al. Discovering missing links in networks using vertex similarity measures[C]//Proceedings of the Twenty-Seventh Annual ACM Symposium on Applied Computing (SAC'12). New York, NJ, USA: ACM, 2012: 138-143. |
[21] | Papadimitriou A, Symeonidis P, Manolopoulos Y. Fast and accurate link prediction in social networking systems[J]. Journal of Systems and Software, 2012, 85: 2119–2132. DOI:10.1016/j.jss.2012.04.019 |
[22] | Lichtenwalter R N, Chawla N V. Vertex collocation profiles: Subgraph counting for link analysis and prediction[C]//Proceedings of the 21st World Wide Web Conference (WWW'12). Piscataway, NJ, USA: IEEE, 2012: 1019-1028. https://www.researchgate.net/publication/254008836_Vertex_collocation_profiles_Subgraph_counting_for_link_analysis_and_prediction |
[23] | Lichtenwalter R N, Chawla N V. Vertex collocation profiles:Theory, computation, and results[J]. Springer Plus, 2014, 3(1): 1–27. DOI:10.1186/2193-1801-3-1 |
[24] | Fouss F, Pirotte A, Renders J M, et al. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation[J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(3): 355–369. DOI:10.1109/TKDE.2007.46 |
[25] | Jeh G, Widom J. SimRank: a measure of structural-context similarity[C]//Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'02). New York, NJ, USA: ACM, 2002: 538-543. https://www.researchgate.net/publication/2558295_SimRank_A_Measure_of_Structural-Context_Similarity |
[26] |
王春磊, 张岩峰, 鲍玉斌, 等.
Asyn-SimRank:一种可异步执行的大规模SimRank算法[J]. 计算机研究与发展, 2015, 52(7): 1567–1579.
Zhang C L, Zhang Y F, Bao Y B, et al. Asyn-SimRank:An asynchronous large-scale simrank algorithm[J]. Journal of Computer Research and Development, 2015, 52(7): 1567–1579. |
[27] | Liben-Nowell D, Kleinberg J M. The link-prediction problem for social networks[J]. Journal of the American Society for Information Science and Technology, 2007, 58: 1019–1031. DOI:10.1002/asi.20591 |
[28] | Lichtenwalter R N, Lussier J T, Chawla N V. New perspectives and methods in link prediction[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Piscataway, NJ, USA: ACM, 2010: 243-252. |
[29] | Yang S H, Long B, Smola A, et al. Like like alike: Joint friendship and interest propagation in social networks[C]//Proceedings of the 20th International Conference on World Wide Web (WWW'11). Piscataway, NJ, USA: IEEE, 2011: 537-546. https://www.researchgate.net/publication/221023264_Like_like_alike_-_Joint_friendship_and_interest_propagation_in_social_networks |
[30] | Dong Y, Tang J, Wu S, et al. Link prediction and recommendation across heterogeneous social networks[C]//Proceedings of IEEE 12th International Conference on Data Mining. Piscataway, NJ, USA: IEEE, 2012: 181-190. https://www.researchgate.net/publication/261040931_Link_Prediction_and_Recommendation_across_Heterogeneous_Social_Networks |
[31] | Liu H, Hu Z, Haddadi H, et al. Hidden link prediction based on node centrality and weak ties[J]. EPL (Europhysics Letters), 2013, 101(1): 18004. DOI:10.1209/0295-5075/101/18004 |
[32] | Valverde-Rebaza J, Lopes A A. Exploiting behaviors of communities of twitter users for link prediction[J]. Social Network Analysis and Mining, 2013, 3(4): 1063–1074. DOI:10.1007/s13278-013-0142-8 |
[33] | Li R H, Yu J X, Liu J. Link prediction: The power of maximal entropy random walk[C]//Proceedings of the 20th ACM international Conference on Information and Knowledge Management. Piscataway, NJ, USA: IEEE, 2011: 1147-1156. https://www.researchgate.net/publication/221613366_Link_prediction_the_power_of_maximal_entropy_random_walk |
[34] | Qiu B, Ivanova K, Yen J, et al. Behavior evolution and event-driven growth dynamics in social networks[C]//Proceedings of IEEE Second International Conference on Social Computing (SocialCom). Piscataway, NJ, USA: IEEE, 2010: 217-224. https://www.researchgate.net/publication/220876034_Behavior_Evolution_and_Event-Driven_Growth_Dynamics_in_Social_Networks |
[35] | Zhang P, Qiu D, Zeng A, et al. A comprehensive comparison of network similarities for link prediction and spurious link elimination[J]. Physica A:Statistical Mechanics and its Applications, 2018, 500(15): 97–105. |
[36] | Yang Y J, Zhang J H, Zhu X Z. Link prediction via significant influence[J]. Physica A:Statistical Mechanics & Its Applications, 2018, 492. |
[37] | Yabing Y, Ruisheng Z, Fan Y, et al. Link prediction in complex networks based on the interactions among paths[J]. Physica A:Statistical Mechanics and its Applications, 2018: S0378437118307751. |
[38] |
张志刚, 李世宝, 马文丽, 等.
一种改进共同邻居的节点遍历链路预测算法[J]. 小型微型计算机系统, 2018, 39(2): 207–213.
Zhang Z G, Li S B, Ma W L. Improved common neighbors algorithm for link prediction based on node traversal[J]. Journal of Chinese Computer Systems, 2018, 39(2): 207–213. DOI:10.3969/j.issn.1000-1220.2018.02.004 |
[39] |
高杨, 张燕平, 钱付兰, 等.
结合节点度和节点聚类系数的链路预测算法[J]. 小型微型计算机系统, 2017, 38(7): 1436–1441.
Gao Y, Zhang Y P, Qian F L, et al. Combined with node degree and node clustering coefficient of link prediction algorithm[J]. Journal of Chinese Computer Systems, 2017, 38(7): 1436–1441. DOI:10.3969/j.issn.1000-1220.2017.07.003 |
[40] | Bütün E, Kaya M, Alhajj R. Extension of neighbor-based link prediction methods for directed, weighted and temporal social networks[J]. Information Sciences, 2018(463/464): 152–165. |
[41] |
姜卯生, 葛剑飞, 陈崚.
基于空间映射的顶点带属性网络的链接预测[J]. 小型微型计算机系统, 2017, 44(7): 257–261.
Jiang M S, Ge J F, Chen L. Link prediction in networks with node attributes based on space mapping[J]. Journal of Chinese Computer Systems, 2017, 44(7): 257–261. |
[42] |
姜卯生, 葛剑飞, 陈崚.
顶点带属性网络链接预测的参数选择方法[J]. 小型微型计算机系统, 2017, 38(6): 1278–1283.
Jiang M S, Ge J F, Chen L. Parameter selection algorithm for link prediction in networks with node attributes[J]. Journal of Chinese Computer Systems, 2017, 38(6): 1278–1283. DOI:10.3969/j.issn.1000-1220.2017.06.020 |
[43] |
张昱, 高克宁, 于戈.
一种融合节点属性信息的社会网络链接预测方法[J]. 计算机科学, 2018, 45(6): 41–45.
Zhang Y, Cao K N, Yu G. Method of link prediction in social networks using node attribute information[J]. Computer Science, 2018, 45(6): 41–45. |
[44] |
陈永祥, 陈崚.
基于随机游走的带有属性网络的链接预测[J]. 计算机科学, 2016, 43(6): 199–203.
Chen Y X, Chen L. Link prediction in network with node attributes based on random walks algorithm[J]. Computer Science, 2016, 43(6): 199–203. |
[45] |
姜卯生, 葛剑飞, 陈崚.
基于空间映射的顶点带属性网络的链接预测[J]. 计算机科学, 2017, 44(7): 257–261.
Jiang M S, Ge J F, Chen L. Link prediction in networks with node attributes based on space mapping[J]. Computer Science, 2017, 44(7): 257–261. |
[46] |
伍杰华, 沈静, 周蓓.
多维相似度特征的社交网络链接分类[J]. 小型微型计算机系统, 2017, 38(6): 1323–13285.
Wu J H, Shen J, Zhou B. Multidimensional similarity feature link classification in social networks[J]. Journal of Chinese Computer Systems, 2017, 38(6): 1323–13285. DOI:10.3969/j.issn.1000-1220.2017.06.028 |
[47] | Bao Z, Zeng Y, Tay Y C. sonLP: Social network link prediction by principal component regression[C]//IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Piscataway, NJ, USA: IEEE, 2013: 364-371. https://www.researchgate.net/publication/262204974_sonLP_social_network_link_prediction_by_principal_component_regression |
[48] | Moradabadi B, Meybodi M R. Link prediction in weighted social networks using learning automata[J]. Engineering Applications of Artificial Intelligence, 2018, 70: 16–24. DOI:10.1016/j.engappai.2017.12.006 |
[49] |
杨妮亚, 彭涛, 刘露.
基于聚类和决策树的链路预测方法[J]. 计算机研究与发展, 2017, 54(8): 1795–1803.
Yang N Y, Peng T, Liu L. Link prediction method based on clustering and decision tree[J]. Journal of Computer Research and Development, 2017, 54(8): 1795–1803. |
[50] |
张艳红, 王宝会.
基于深度神经网络的社会媒体网络分析[J]. 计算机科学, 2016, 43(4): 252–255.
Zhang Y H, Wang B H. Analysis of social media networks based on deep neural networks[J]. Computer Science, 2016, 43(4): 252–255. |
[51] |
韩路, 尹子都, 王钰杰, 等.
基于贝叶斯网的知识图谱链接预测[J]. 计算机科学与探索, 2017, 11(5): 742–751.
Han L, Yin Z D, Wang Y J, et al. Link prediction of knowledge graph based on bayesian network[J]. Journal of Frontiers of Computer Science and Technology, 2017, 11(5): 742–751. |
[52] |
许烁娜, 曾碧卿.
基于Skyline查询的社会网络链接预测[J]. 计算机科学, 2014, 41(1): 258–261.
Xu S N, Zeng B Q. Skyline based link prediction on social networks[J]. Computer Science, 2014, 41(1): 258–261. DOI:10.3969/j.issn.1002-137X.2014.01.049 |
[53] | Pujari M, Kanawati R. Supervised rank aggregation approach for link prediction in complex networks[C]//New York, NJ, USA: ACM, 2012: 1189-1196. https://dl.acm.org/doi/10.1145/2187980.2188260?dl=GUIDE&coll=DL&CFTOKEN=17087201&CFID=417313635 |
[54] | Wu S, Sun J, Tang J. Patent partner recommendation in enterprise social networks[C]//Proceedings of the 6th ACM International Conference on Web Search and Data Mining (WSDM'13). New York, NJ, USA: ACM, 2013: 43-52. https://www.researchgate.net/publication/262327455_Patent_partner_recommendation_in_enterprise_social_networks |
[55] | Scripps J, Tan P N, Chen F, et al. A matrix alignment approach for link prediction[C]//Proceedings of the 19th International Conference on Pattern Recognition (ICPR'08). Piscataway, NJ, USA: IEEE, 2008: 1-4 https://www.researchgate.net/publication/220929679_A_Matrix_Alignment_Approach_for_Link_Prediction |
[56] | Guimeràa R, Sales-Pardo M. Missing and spurious interactions and the reconstruction of complex networks[J]. Proceedings of the National Academy of Sciences, 2009, 106: 22073–22078. DOI:10.1073/pnas.0908366106 |
[57] | Pujari M, Kanawati R. Link prediction in complex networks by supervised rank aggregation[C]//International Conference on TOOLS with Artificial Intelligence. Piscataway, NJ, USA: IEEE, 2012: 782-789. |
[58] | Lichtenwalter R N, Chawla N V. Vertex collocation pro_les: Subgraph counting for link analysis and prediction[C]//Proceedings of the 21st World Wide Web Conference (WWW'12). Piscataway, NJ, USA: IEEE, 2012: 1019-1028. https://www.researchgate.net/publication/254008836_Vertex_collocation_profiles_Subgraph_counting_for_link_analysis_and_prediction |
[59] |
李志宇, 梁循, 徐志明, 等.
DNPS:基于阻尼采样的大规模动态社会网络结构特征表示学习[J]. 计算机学报, 2017, 40(4): 805–523.
Li Z Y, Liang X, Xu Z M, et al. DNPS:Damping based negative-positive sampling of large-scale dynamic social network embedding[J]. Chinese Journal of Computers, 2017, 40(4): 805–523. |
[60] | Li X, Chen H. Recommendation as link prediction in bipartite graphs:A graph kernel-based machine learning approach[J]. Decision Support Systems, 2013, 54: 880–890. DOI:10.1016/j.dss.2012.09.019 |
[61] | Cao B, Liu N N, Yang Q. Transfer learning for collective link prediction in multiple heterogeneous domains[C]//Proceedings of the 27th International Conference on Machine Learning. Piscataway, NJ, USA: IEEE, 2010: 159-166. https://www.researchgate.net/publication/221345394_Transfer_Learning_for_Collective_Link_Prediction_in_Multiple_Heterogenous_Domains |
[62] | de S_a H R, Prud.encio R B C. Supervised link prediction in weighted networks[C]//Proceedings of the 2011 International Joint Conference on Neural Networks (IJCNN). Piscataway, NJ, USA: IEEE, 2011: 2281-2288. https://www.researchgate.net/publication/224260324_Supervised_link_prediction_in_weighted_networks |
[63] | Chiang K Y, Natarajan N, Tewari A, et al. Exploiting longer cycles for link prediction in signed networks[C]//Proceedings of the 20th ACM International Conference on Information and Knowledge Management. New York, NJ, USA: ACM, 2011: 1157-1162. https://www.researchgate.net/publication/221614099_Exploiting_Longer_Cycles_for_Link_Prediction_in_Signed_Networks |
[64] | Pujari M, Kanawati R. Link prediction in complex networks by supervised rank aggregation[C]//Proceedings of IEEE 24th International Conference on Tools with Artificial Intelligence. Piscataway, NJ, USA: IEEE, 2012: 782-789. |
[65] | Leskovec J, Huttenlocher D, Kleinberg J. Predicting positive and negative links in online social networks[C]//Proceedings of the 19th International Conference on World Wide Web (WWW'10). Piscataway, NJ, USA: IEEE, 2010: 641-650. https://www.researchgate.net/publication/45905816_Predicting_Positive_and_Negative_Links_in_Online_Social_Networks |
[66] | Kashima H, Kato T, Yamanishi Y, et al. Link propagation: A fast semi-supervised learning algorithm for link prediction[C]//Proceedings of the 9th SIAM International Conference on Data Mining (SDM'09). Piscataway, NJ, USA: IEEE, 2009: 1099-1110. |
[67] | Wu S, Sun J, Tang J. Patent partner recommendation in enterprise social networks[C]//Proceedings of the 6th ACM International Conference on Web Search and Data Mining (WSDM'13). New York, NJ, USA: ACM, 2013: 43-52 https://www.researchgate.net/publication/262327455_Patent_partner_recommendation_in_enterprise_social_networks |
[68] | Li J C, Zhao D L, Ge B F, et al. A link prediction method for heterogeneous networks based on BP neural network[J]. Physica A:Statistical Mechanics and Its Applications, 2018, 495(1): 1–17. |
[69] | Raymond R, Kashima H. Fast and scalable algorithms for semi-supervised link prediction on static and dynamic graphs[C]//Proceedings of ECML/PKDD'10. Berlin, Germany: Springer, 2010: 131-147. |
[70] | Seni G, Elder J. Ensemble methods in data mining:Improving accuracy through combining predictions[M]. New York, USA: Morgan and Claypool Publishers, 2010. |
[71] | Scellato S, Noulas A, Mascolo C. Exploiting place features in link prediction on location-based social networks[C]//Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, NJ, USA: ACM, 2011: 1046-1054. https://www.researchgate.net/publication/221653291_Exploiting_Place_Features_in_Link_Prediction_on_Location-based_Social_Networks |
[72] | Clauset A, Moore C, Newman M E. Hierarchical structure and the prediction of missing links in networks[J]. Nature, 2008, 453(7191): 98. DOI:10.1038/nature06830 |
[73] | Lü L Y, Jin C H, Zhou T. Similarity index based on local paths for link prediction of complex networks[J]. Physical Review E, 2009, 80(4): 046122. DOI:10.1103/PhysRevE.80.046122 |
[74] | Zhao J C, Feng X, Dong L, et al. Performance of local information-based link prediction:A sampling perspective[J]. Journal of Physics A:Mathematical and Theoretical, 2012, 45(34): 345001. DOI:10.1088/1751-8113/45/34/345001 |
[75] | Zhang C, Ma Y Q. Ensemble machine learning[C]//Methods and applications. Berlin, Germany: Springer, 2012: 2776. |
[76] | Baumgartner D, Serpen G. Performance of global-local hybrid ensemble versus boosting and bagging ensembles[J]. The International Journal of Machine Learning and Cybernetics, 2013, 4(4): 301–317. DOI:10.1007/s13042-012-0094-8 |
[77] | Christou I T, Gekas G, Kyrikou A. A classifier ensemble approach to the TV-viewer profile adaptation problem[J]. The International Journal of Machine Learning and Cybernetics, 2012, 3(4): 313–326. DOI:10.1007/s13042-011-0066-4 |
[78] | Zhang L, Yang J W, Wang X Q, et al. Cascaded cluster ensembles[J]. International Journal of Machine Learning & Cybernetics, 2012, 3(4): 335–343. |
[79] | Zhou Z H. Ensemble methods:Foundations and algorithms[M]. Boca Raton, USA: Chapman & Hall, 2012. |
[80] | Comar P M, Tan P N, Jain A K. LinkBoost: A novel cost-sensitive boosting framework for community-level network link prediction[C]//International Conference on Data Mining. Piscataway, NJ, USA: IEEE, 2011: 131-140. https://www.researchgate.net/publication/220766677_LinkBoost_A_Novel_Cost-Sensitive_Boosting_Framework_for_Community-Level_Network_Link_Prediction |
[81] | Heckerman D, Chickering D M, Meek C, et al. Dependency networks for inference, collaborative filtering, and data visualization[J]. Journal of Machine Learning Research, 2001, 1(1): 49–75. |
[82] | Lü L, Zhou T. Link prediction in complex networks:A survey[J]. Physica A Statistical Mechanics & Its Applications, 2011, 390(6): 1150–1170. |
[83] | He Y L, Liu J N K, Hu Y X, et al. OWA operator based link prediction ensemble for social network[J]. Expert Systems with Applications An International Journal, 2015, 42(1): 21–50. DOI:10.1016/j.eswa.2014.07.018 |
[84] |
吴祖峰, 梁棋, 刘峤, 等.
基于AdaBoost的链路预测优化算法[J]. 通信学报, 2014, 36(3): 116–123.
Wu Z F, Liang Q, Liu Q, et al. , An optimization algorithm for link prediction based on adaBoost[J]. Chinese Journal of Communication, 2014, 36(3): 116–123. |
[85] | Jerome K, Andreas L. Learning spectral graph transformations for link prediction[C]//Proceedings of the International Conference on Machine Learning. Piscataway, NJ, USA: IEEE, 2009: 561-568. |
[86] | Menon A K, Elkan C. Link prediction via matrix factorization[C]//European Conference on Machine Learning and Knowledge Discovery in Databases. Berlin, Germany: Springer-Verlag, 2011: 437-452. |
[87] | Ahmed N M, Chen L, Wang Y L, et al. DeepEye:Link prediction in dynamic networks based on non-negative matrix factorization[J]. Big Data Mining and Analytics, 2018, 1(1): 19–33. |
[88] | Wang Z Q, Liang J Y, Li R. A fusion probability matrix factorization framework for link prediction[J]. Knowledge-Based Systems, 2018, 159: 72–85. DOI:10.1016/j.knosys.2018.06.005 |
[89] |
王萌萌, 左万利, 王英.
基于加权非负矩阵分解的链接预测算法[J]. 电子学报, 2016, 44(10): 2391–2397.
Wang M M, Zuo W L, Wang Y. Link prediction modei based on weighted nonnegative matrix factorization[J]. Acta Electronica Sinica, 2016, 44(10): 2391–2397. DOI:10.3969/j.issn.0372-2112.2016.10.016 |
[90] |
郝占刚, 章伟雄, 陈政.
基于监督联合去噪模型的社交网络链接预测[J]. 中国科学(信息科学), 2017, 47(11): 1551–1565.
Hao Z G, Zhang W X, Chen Z. Link prediction in online social networks based on supervised joint denoising model[J]. Scientia Sinica Informationis, 2017, 47(11): 1551–1565. |
[91] | Ma X K, Sun P G, Qin G M. Nonnegative matrix factorization algorithms for link prediction in temporal networks using graph communicability[J]. Pattern Recognition, 2017, 71: 361–374. DOI:10.1016/j.patcog.2017.06.025 |
[92] | Meng Q X, Kennedy P J. Using network evolution theory and singular value decomposition method to improve accuracy of link prediction in social networks[C]//Proceedings of the Tenth Australasian Data Mining Conference (AusDM 2012). Berlin, Germany: Springer, 2012: 175-182. https://www.researchgate.net/publication/262246971_Using_network_evolution_theory_and_singular_value_decomposition_method_to_improve_accuracy_of_link_prediction_in_social_networks |
[93] | Gao S, Denoyer L, Gallinari P, et al. Probabilistic latent tensor factorization model for link pattern prediction in multi-relational networks[C]//IEEE International Conference on Network Infrastructure and Digital Content. Piscataway, NJ, USA: IEEE, 2013: 172-181. |
[94] | Chen L, Gao M, Li B, et al. Detect potential relations by link prediction in multi-relational social networks[J]. Decision Support Systems, 2018, 115: 78–91. DOI:10.1016/j.dss.2018.09.006 |
[95] | Gao M, Chen L, Li B, et al. A link prediction algorithm based on low-rank matrix completion[J]. Applied Intelligence, 2018, 48(12): 4531–4550. DOI:10.1007/s10489-018-1220-4 |
[96] | Hsieh C J, Natarajan N, Dhillon I. PU learning for matrix completion[C]//Proceedings of the 32nd International Conference on International Conference on Machine Learning. Piscataway, NJ, USA: IEEE, 2015: 2445-2453. https://www.researchgate.net/publication/268748280_PU_Learning_for_Matrix_Completion |
[97] | Tang Q, Sun S, Yang C, et al. Learning scale free network by node specific degree prior[J]. Computer Science, 2015: 2247–2255. |
[98] | Mohtashemi B, Ketseoglou T, Log-normal matrix completion for large scale link prediction[EB/OL]. arXiv: 1601. 07714v1, 2016: 1-6. https://www.researchgate.net/publication/292148287_Log-Normal_Matrix_Completion_for_Large_Scale_Link_Prediction |
[99] |
刘冶, 朱蔚恒, 潘炎, 等.
基于低秩和稀疏矩阵分解的多源融合链接预测算法[J]. 计算机研究与发展, 2015, 52(2): 423–436.
Liu Y, Zhu W H, Pan Y, et al. Multiple sourdes fusion for link prediction via low-rank and sparse matrix decomposition[J]. Journal of Computer Research and Development, 2015, 52(2): 423–436. |
[100] |
刘冶, 印鉴, 邓泽亚, 等.
基于低秩和局部约束矩阵估计的链接预测方法[J]. 计算机科学与探索, 2015, 9(3): 279–291.
Liu Y, Yin J, Deng Z Y, et al. Link prediction with low-rank and local constraint matrix esti mation[J]. Journal of Frontiers of Computer Science and Technology, 2015, 9(3): 279–291. |
[101] | Getoor L, Friedman N, Koller D, et al. Learning probabilistic models of link structure[J]. Journal of Machine Learning Research, 2003, 3(4): 679–707. |
[102] | Taskar B, Wong M F, Abbeel P, et al. Link prediction in relational data[C]//International Conference on Neural Information Processing Systems. Cambridge, MA, USA: MIT Press, 2003: 659-666. |
[103] | Wu J H. A generalized tree augmented naive Bayes link predictionmodel[J]. Journal of Computational Science, 2018, 27: 206–217. DOI:10.1016/j.jocs.2018.04.006 |
[104] | Pearl J. Probabilistic reasoning in intelligent systems[M]. New York, NJ, USA: Morgan Kaufmann Publishers Inc, 1988. |
[105] | Taskar B, Abbeel P, Koller D. Discriminative probabilistic models for relational data[C]//Eighteenth Conference on Uncertainty in Artificial Intelligence. New York, NJ, USA: Morgan Kaufmann Publishers Inc, 2012: 485-492. https://www.researchgate.net/publication/277288971_Discriminative_probabilistic_models_for_relational_data |
[107] | Zhang X J, Pang W B, Xia Y X. An intermediary probability model for link prediction[J]. Physica A:Statistical Mechanics and Its Applications, 2018, 512(15): 902–912. |
[108] | Heckerman D, Meek C, Koller D. Probabilistic models for relational data[R]. Technical Report, MSR-TR-2004-30, Microsoft, 2004: 1-45. |
[109] | Xu Z, Tresp V, Yu K, et al. Dirichlet enhanced relational learning[C]//International Conference of DBLP. Piscataway, NJ, USA: IEEE, 2005: 1004-1011. |
[110] | Zhao X, Volker T. Nonparametric relational learning for social network analysis[C]//The 2nd SNA-KDD Workshop at the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining: SNA-KDD'08. New York, NJ, USA: ACM, 2008: 1-10. |
[111] | Schölkopf B, Platt J, Hofmann T. Stochastic relational models for discriminative link prediction[J]. Advances in Neural Information Processing Systems, 2006, 19: 1553–1560. |
[112] | Dai C, Chen L, Li B, et al. Link prediction in multi-relational networks based on relational similarity[J]. Information Sciences, 2017(394/395): 198–216. |
[113] | Gao S, Denoyer L, Gallinari P. Link pattern prediction with tensor decomposition in multi-relational networks[C]//Computational Intelligence and Data Mining. Piscataway, NJ, USA: IEEE, 2012: 333-340. https://www.researchgate.net/publication/221312173_Link_Pattern_Prediction_with_tensor_decomposition_in_multi-relational_networks |
[114] | Ströele V, Zimbrão G, Souza J M. Group and link analysis of multi-relational scientific social networks[J]. Journal of Systems and Software, 2013, 86: 1819–1830. DOI:10.1016/j.jss.2013.02.024 |
[115] | Shakibian H, Charkari N M. Statistical similarity measures for link prediction in heterogeneous complex networks[J]. Physica A:Statistical Mechanics and its Applications, 2018, 501(1): 248–263. |
[116] | Wang D, Pedreschi D, Song C, et al. Human mobility, social ties, and link prediction[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, NJ, USA: ACM, 2011: 1100-1108. https://www.researchgate.net/publication/221654073_Human_mobility_social_ties_and_link_prediction |
[117] | Rossetti G, Berlingerio M, Giannotti F. Scalable link prediction on multidimensional networks[C]//International Conference on Data Mining Workshops. Piscataway, NJ, USA: IEEE, 2012: 979-986. https://www.researchgate.net/publication/220766638_Scalable_Link_Prediction_on_Multidimensional_Networks |
[118] | Dunlavy D M, Kolda T G, Acar E. Temporal link prediction using matrix and tensor factorizations[J]. ACM Transactions on Knowledge Discovery from Data, 2011, 5(2): 1–27. |
[119] | O'Madadhain J, Hutchins J, Smyth P. Prediction and ranking algorithms for event-based network data[J]. ACM SIGKDD Explorations Newsletter, 2005, 7(2): 23–30. DOI:10.1145/1117454.1117458 |
[120] | da Soares P R S, Prudêncio R B C. Time series based link prediction[C]//Proceedings of 2012 International Joint Conference on Neural Networks (IJCNN'12). Berlin, Germany: Springer, 2012: 1-7. https://www.researchgate.net/publication/237091637_Time_Series_Based_Link_Prediction |
[121] | da Soares P R S, Prudêncio R B C. Proximity measures for link prediction based on temporal events[J]. Expert Systems with Applications, 2013, 40(16): 6652–6660. DOI:10.1016/j.eswa.2013.06.016 |
[122] |
陈莎, 朱福喜, 阳小兰, 等.
一种基于混合相似性指标的网络动态链路预测方法[J]. 小型微型计算机系统, 2016, 37(8): 1798–1801.
Chen S, Zhu F X, Yang X L. Dynamic link prediction method of social network based on the mixed similarity index[J]. Journal of Chinese Computer Systems, 2016, 37(8): 1798–1801. DOI:10.3969/j.issn.1000-1220.2016.08.033 |
[123] | Richard E, Baskiotis N, Evgeniou T, et al. Link discovery using graph feature tracking[C]//Proceedings of the 24th Annual Conference on Neural Information Processing Systems 2010. New York, NJ, USA: ACM, 2010: 1966-1974. |
[124] | Pech R, Hao D, Pan L, et al. Link prediction via matrix completion[J]. Europhysics Letters, 2016, 117(3). DOI:10.1209/0295-5075/117/38002 |
[125] | Muniz C P, Goldschmidt R, Choren R. Combining contextual, temporal and topological information for unsupervised link prediction in social networks[J]. Knowledge-Based Systems, 2018, 156(15): 129–137. |
[126] |
陈德华, 殷苏娜, 乐嘉锦, 等.
一种面向临床领域时序知识图谱的链接预测模型[J]. 计算机研究与发展, 2017, 54(12): 2687–2697.
Chen D H, Yin S N, Le J J, et al. A link prediction model for clinical temporal knowledge graph[J]. Journal of Computer Research and Development, 2017, 54(12): 2687–2697. DOI:10.7544/issn1000-1239.2017.20170640 |
[127] | Gao S, Denoyer L, Gallinari P. Temporal link prediction by integrating content and structure information[C]//Proceedings of the 20th ACM International Conference on Information and Knowledge Management (CIKM'11). New York, NJ, USA: ACM, 2011: 1169-1174. https://www.researchgate.net/publication/221614002_Temporal_link_prediction_by_integrating_content_and_structure_information |
[128] | Ma X K, Sun P G, Wang Y. Graph regularized nonnegative matrix factorization for temporal link prediction in dynamic networks[J]. Physica A:Statistical Mechanics and its Applications, 2018, 496(15): 121–136. |
[129] | Murata T, Moriyasu S. Link prediction of social networks based on weighted proximity measures[C]//IEEE/WIC/ACM International Conference on Web Intelligence. Piscataway, NJ, USA: IEEE, 2007: 85-88. https://www.researchgate.net/publication/4309797_Link_Prediction_of_Social_Networks_Based_on_Weighted_Proximity_Measures |
[130] | Lü L, Zhou T. Link prediction in weighted networks:The role of weak ties[J]. Europhys Letters, 2010, 89(1): 18001. DOI:10.1209/0295-5075/89/18001 |
[131] |
陈旭, 陈可佳.
一种改进的加权网络链接预测方法[J]. 计算机科学, 2017, 44(10): 96–108.
Chen X, Chen K J. Improved link prediction method for weighted networks[J]. Computer Science, 2017, 44(10): 96–108. DOI:10.11896/j.issn.1002-137X.2017.10.018 |
[132] |
吕琳媛.
复杂网络链接预测[J]. 电子科技大学学报, 2010, 39(5): 651–661.
Lü L Y. Link prediction in complex networks[J]. Journal of University of Electronic Science and Technology, 2010, 39(5): 651–661. DOI:10.3969/j.issn.1001-0548.2010.05.002 |
[133] | Lin Z, Yun X, Zhu Y. Link prediction using benefitranks in weighted networks[C]//IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology. Piscataway, NJ, USA: IEEE, 2012: 423-430. https://www.researchgate.net/publication/262253285_Link_Prediction_Using_BenefitRanks_in_Weighted_Networks |
[134] | Chen H H, Giles C L. ASCOS++:An asymmetric similarity measure for weighted networks to address the problem of SimRank[J]. ACM Transactions on Knowledge Discovery from Data, 2015, 10(2): 1–26. |
[135] | Moradabadi B, Meybodi M R. Link prediction in weighted social networks using learning automata[J]. Engineering Applications of Artificial Intelligence, 2018, 70: 16–24. DOI:10.1016/j.engappai.2017.12.006 |
[136] | Wind D K, MØrup M. Link prediction in weighted networks[C]//IEEE International Workshop on Machine Learning for Signal Processing. Piscataway, NJ, USA: IEEE, 2012: 1-6. https://www.researchgate.net/publication/261418628_Link_prediction_in_weighted_networks |
[137] | Moradabadi B, Meybodi M R. Link prediction in weighted social networks using learning automata[J]. Engineering Applications of Artificial Intelligence, 2018, 70: 16–24. DOI:10.1016/j.engappai.2017.12.006 |
[138] |
白杨, 邓贵仕.
结合用户互动加权图的社交网络链接预测[J]. 小型微型计算机系统, 2018, 39(9): 1988–1992.
Bai Y, Deng G S. Social network link prediction based on user interaction weighted graph[J]. Journal of Chinese Computer Systems, 2018, 39(9): 1988–1992. DOI:10.3969/j.issn.1000-1220.2018.09.017 |
[139] | de Sá H R, Prudêncio R B C. Supervised link prediction in weighted networks[C]//Proceedings of the 2011 International Joint Conference on Neural Networks (IJCNN). Piscataway, NJ, USA: IEEE, 2011: 2281-2288. https://www.researchgate.net/publication/224260324_Supervised_link_prediction_in_weighted_networks |
[140] | Asthana S, King O D, Gibbons F D, et al. Predicting protein complex membership using probabilistic network reliability[J]. Genome Research, 2004, 14(6): 1170. DOI:10.1101/gr.2203804 |
[141] |
章月阳, 刘维.
不确定性PPI网络链接预测[J]. 计算机科学, 2014, 41(z2): 399–402.
Zhang Y Y, Liu W. Link prediction in uncertain protein-protein interaction network[J]. Computer Science, 2014, 41(z2): 399–402. |
[142] | Adar E, Re C. Managing uncertainty in social networks[J]. Data Engineering Bulletin, 2007, 30(2): 23–31. |
[143] | Guha R, Kumar R, Raghavan P, et al. Propagation of trust and distrust[C]//International Conference on World Wide Web. Berlin, Germany: Springer, 2004: 403-412. https://www.researchgate.net/publication/200110993_Propagation_of_Trust_and_Distrust |
[144] | Kempe D, Kleinberg J. Maximizing the spread of influence through a social network[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, NJ, USA: ACM, 2003: 137-146. |
[145] | Ghosh J, Ngo H Q, Yoon S, et al. On a routing problem within probabilistic graphs and its application to intermittently connected networks[C]//INFOCOM 2007 IEEE International Conference on Computer Communications. Piscataway, NJ, USA: IEEE, 2007: 1721-1729. https://www.researchgate.net/publication/224710841_On_a_Routing_Problem_Within_Probabilistic_Graphs_and_its_Application_to_Intermittently_Connected_Networks |
[146] | Rubino G. Network reliability evaluation[J]. State, 1999, 37(8): 275–302. |
[147] | Aggarwal C C. Managing and mining uncertain data[M]. Berlin, Germany: Springer, 2009. |
[148] | Hintsanen P, Toivonen H. Finding reliable subgraphs from large probabilistic graphs[M]. Norwell, MA, USA: Kluwer Academic Publishers, 2008. |
[149] | Ball M O. Computational complexity of network reliability analysis:An overview[J]. IEEE Transactions on Reliability, 1986, 35(3): 230–239. DOI:10.1109/TR.1986.4335422 |
[150] | Valiant L G. The complexity of enumeration and reliability problems[J]. SIAM Journal on Computing, 1979, 8(3): 410–421. DOI:10.1137/0208032 |
[151] | Yuan Y, Chen L, Wang G. Efficiently answering probability threshold-based shortest path queries over uncertain graphs[C]//International Conference on Database Systems for Advanced Applications. Berlin, Germany: Springer-Verlag, 2010: 155-170. |
[152] | Zou Z, Gao H, Li J. Discovering frequent subgraphs over uncertain graph databases under probabilistic semantics[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington. New York, NJ, USA: ACM, 2010: 633-642. |
[153] | Zou Z, Li J, Gao H, et al. Mining frequent subgraph patterns from uncertain graph data[J]. Journal of Software, 2009, 22(9): 1203–1218. |
[154] | Ahmed N M, Chen L. An efficient algorithm for link prediction in temporal uncertain social networks[J]. Information Sciences, 2016, 331: 120–136. DOI:10.1016/j.ins.2015.10.036 |
[155] | Kang C, Pugliese A, Grant J, et al. STUN: Spatio-Temporal uncertain (social) networks[C]//IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Piscataway, NJ, USA: IEEE, 2012: 543-550. https://www.researchgate.net/publication/261088206_STUN_Spatio-Temporal_Uncertain_Social_Networks |
[156] | Potamias M. K-nearest neighbors in uncertain networks[J]. Proceedings of the VLDB Endowment, 2010, 3(1/2): 997–1008. |
[157] | Moradabadi B, Meybodi M R. Link prediction in stochastic social networks:Learning automata approach[J]. Journal of Computational Science, 2018, 24: 313–328. DOI:10.1016/j.jocs.2017.08.007 |
[158] | Munasinghe L, Ichise R. Link prediction in social networks using information flow via active links[J]. IEICE Transactions on Information & Systems, 2013, E96. D(7): 1495–1502. |
[159] | Chen H H, Gou L, Zhang X, et al. Predicting recent links in FOAF networks[C]//International Conference on Social Computing, Behavioral-Cultural Modeling and Prediction. Berlin, Germany: Springer-Verlag, 2012: 156-163. |
[160] | Chen H H, Miller D J, Giles C L. The predictive value of young and old links in a social network[C]//ACM SIGMOD Workshop on Databases and Social Networks. New York, NJ, USA: ACM, 2013: 43-48. |
[161] |
蓝梦微, 李翠平, 王绍卿, 等.
符号社会网络中正负关系预测算法研究综述[J]. 计算机研究与发展, 2015, 52(2): 410–422.
Lan M W, Li C P, Wang S Q, et al. Survey of sign prediction algorithms in signed social networks[J]. Journal of Computer Research and Development, 2015, 52(2): 410–422. |
[162] | Chiang K Y, Natarajan N, Tewari A, et al. Exploiting longer cycles for link prediction in signed networks[C]//ACM International Conference on Information & Knowledge ManagementNew York, NJ, USA: ACM, 2011. https://www.researchgate.net/publication/221614099_Exploiting_Longer_Cycles_for_Link_Prediction_in_Signed_Networks |
[163] | Patidar A, Agarwal V, Bharadwaj K K. Predicting friends and foes in signed networks using inductive inference and social balance theory[C]//IEEE/ACM International Conference on Advances in Social Networks Analysis & Mining. Piscataway, NJ, USA: IEEE, 2013. |
[164] |
赵衎衎, 张静, 张良富, 等.
基于端到端分布式框架的符号网络预测方法[J]. 软件学报, 2017, 29(3): 614–626.
Zhao K K, Zhang J, Zhang L F, et al. Signed network prediction method based on the client-to-client distributed framework[J]. Journal of Software, 2017, 29(3): 614–626. |
[165] |
王鑫, 王英, 左万利.
基于交互意见和地位理论的符号网络链接预测模型[J]. 计算机研究与发展, 2016, 53(4): 764–775.
Wang X, Wang Y, Zuo W L. Exploring interactional opinions and status theory for predicting links in signed network[J]. Journal of Computer Research and Development, 2016, 53(4): 764–775. |
[166] | Javari A, Jalili M. Cluster-based collaborative filtering for sign prediction in social networks with positive and negative links[J]. ACM Transaction on Intelligent Systems and Technology, 2013. |
[167] | Kunegis J, De Luca E W, Albayrak S. The link prediction problem in bipartite networks[C]//Proceedings of the 13th International Conference on Information Processing and Management of Uncertainty. Berlin, Germany: Springer, 2010: 380-389. |
[168] | Chang Y J, Kao H Y. Link prediction in a bipartite network using Wikipedia revision information[C]//Proceedings of 2012 Conference on Technologies and Applications of Artificial Intelligence. Piscataway, NJ, USA: IEEE, 2012: 50-55. |
[169] | Allali O, Magnien C, Latapy M. Link prediction in bipartite graphs using internal links and weighted projection[C]//INFOCOM Workshop on Network Science for Computer Communications. Piscataway, NJ, USA: IEEE, 2011: 936-941. |
[170] |
姚飞亚, 陈崚.
基于相似度传播的二分网络链接预测[J]. 计算机科学, 2016, 43(4): 86–91.
Yao F Y, Chen L. Similarity propagation based link prediction in bipartite networks[J]. Computer Science, 2016, 43(4): 86–91. |
[171] | Gao M, Chen L, Li B, et al. A projection based algorithm for link prediction in bipartite network[J]. Infprmation Science, 2017, 376: 158–171. DOI:10.1016/j.ins.2016.10.015 |
[172] | Liu J, Deng G. Link prediction in a user-object network based on time-weighted resource allocation[J]. Physica A:Statistical Mechanics and its Applications, 2009, 388: 3643–3650. DOI:10.1016/j.physa.2009.05.021 |
[173] | Valverde-Rebaza J C, Mathieu R, Poncelet P, et al. The role of location and social strength for friendship prediction in location-based social networks[J]. Information Processing & Management, 2018, 54(4): 475–489. |
[174] | Almansoori W, Gao S, Jarada T N, et al. Link prediction and classification in social networks and its application in healthcare and systems biology[J]. Network Modeling Analysis Health Informatics Bioinformatics, 2012, 1: 27–36. DOI:10.1007/s13721-012-0005-7 |
[175] | Lü L Y, Pan L M, Zhou T, et al. Toward link predictability of complex networks[J]. Proceedings of the National Academy of Sciences, DOI: www.pnas.org/cgi/doi/10.1073/pnas.1424644112. |
[176] |
许小可, 许爽, 朱郁筱, 等.
复杂网络中链路的可预测性[J]. 复杂系统与复杂性科学, 2014, 11(1): 42–47.
Xu X K, Xu S, Zhu Y X, et al. Link prediction in complex networks[J]. Complex Systems and Complexity Science, 2014, 11(1): 42–47. |