一种改进的代价敏感型链路预测算法_袁芳芳

of Liaoning Technical University（Natural Science） Nov. 2015 Vol.34 No.11 Journal

袁芳芳,肖晓.一种改进的代价敏感型链路预测算法[J].辽宁工程技术大学学报:自然科学版,2015,34(11):1285-1291.

doi:10.11956/j.issn.1008-0562.2015.11.014

Yuan Fangfang, Xiao Xiao.An improved cost-sensitive link prediction algorithm[J].Journal of Liaoning Technical University:Natural Science,2015,34(11):1285-1291. doi:10.11956/j.issn.1008-0562.2015.11.014

一种改进的代价敏感型链路预测算法

袁芳芳1，肖 晓2

（1. 太原学院 计算机工程系，山西 太原 030001；2. 湖南大学 软件学院，湖南 长沙 410082）

摘 要：为解决因网络数据分布不均匀性而造成的链路预测问题，提出一种改进的代价敏感型链路预测算法（LinkBoost）.设计一种有监督链路预测可变代价损失函数，该函数对低节点度有链路节点对出现分类错误时的惩罚大于高节点度有链路节点对，解决了节点度的分布偏差.考虑到以损失函数优化为目标的链路预测算法将导致社区内预测链路数量大于社区间的链路数量，进而设计一种Boosting算法来实现损失函数最小化.通过将网络分为多个分区，并对各个分区构建的弱学习器进行融合，提高了算法的可伸缩性.利用4个真实网络数据集进行性能评估.研究结果表明：LinkBoost算法的性能与许多当前算法的性能相当或者优于当前算法. 关键词：链路预测；惩罚；节点度；损失函数；弱学习器

中图分类号：TP 393 文献标志码：A 文章编号：1008-0562(2015)11-1285-07

An improved cost-sensitive link prediction algorithm

YUAN Fangfang1, XIAO Xiao2

(1.Department of Computer Engineering, Taiyuan College, Taiyuan 030001, China;

2. Software College, Hunan University, Changsha 410082, China）

Abstract: In order to solve the Link prediction problem due to the uneven distribution of network data, this paper proposed an improved cost sensitive link prediction algorithm. Firstly, a variable-cost loss function for supervised link prediction was proposed, which addressed the bias in degree distribution by penalizing the misclassification of low-degree linked node pairs more than misclassification of high-degree linked node pairs. In addition, taking link prediction method designed to optimize the loss function into account would result in more links being predicted within a community than that of between communities. And then a boosting algorithm was designed to minimize the loss function and an approach was presented to scale-up the algorithm by decomposing the network into smaller partitions and aggregating the weak learners constructed from each partition. Experimental results show that the proposed LinkBoost algorithm consistently performs as good as or better than many existing methods based on the evaluating of the 4 real-world network datasets.

Key words: link prediction; penalization; node degree; loss function; weak learners

0 引言

对网络链路的形成情况进行预测是网络分析的重要方面[1].可靠的链路预测模型有助于发现静态网络中的缺失链路，或者预测动态网络中新链路的形成.链路预测的精度水平随着应用场景的不同而不同.例如，FOF（朋友的朋友）算法的精度较低，但仍广泛用于预测大型社交网络中用户间的未来链路.然而，在生物监视和反恐网络监控等关键领域，链路预测对代价的敏感度较高，算法导致的错误预测关联了一个非常严重的惩罚因子.

链路预测算法的精度较低，主要是因为网络数据分布不均匀[2].而数据分布不均匀情况主要分两种.一种是类别分布不均匀，主要是指网络中无链路（阴性类别）节点对与有链路（阳性类别）节点对的比例失衡.一般来讲，该比值的数量级为O(1/N).如此高的不均匀性将导致有偏决策边界，并要求链路预测算法采用偏斜校正策略.另一种类别在链路预测文献中较少关注，主要是指节点的节点度分布.许多网络为无尺度网络，这将导致（少量）高节点度节点对阳性类别的预测产生重大影响.于是，大多

收稿日期：2014-10-26

基金项目：国家自然科学基金项目（61300218/F020806） 作者简介：袁芳芳（1982-），女，山西 太原人，硕士，讲师，主要从事无线传感网、数据库技术等方面的研究. 本文编校：朱艳华

1286辽宁工程技术大学学报（自然科学版） 第34卷

否则为-1.当C1=C2=1时，对应于0-1损失函数.有监督链路预测算法的目标是生成一个可使下述0-1实证损失函数最小化的分类器，

1n

ˆR0−1=2∑I[Aijsgn(f(eij))≤0]，

ni,j=1式中，I(⋅)为指示函数，如果参数为真则为1，否则为0.该二元分类任务的主要困难在于类别失衡问题.在社交网络数据中，阴性示例（无链路节点对）的数量往往远大于阳性示例.解决数据分类失衡问题的两种主要方法是采样法和代价敏感型学习法.在前一种方法中，通过下采样阴性示例或过采样阳性示例来获得均衡的训练集.该方法有多种缺陷.首先，下采样阴性示例会降低可用于准确训练模型的数据量.此外，必须不断地进行下采样，以避免采样偏差.另一方面，过采样社交网络数据的阳性示例会显著增加训练数据规模，进而显著增加训练时间.

代价敏感型学习方法以如下假设为基础：不同类型的样本（阳性或阴性）导致不同程度的分类惩罚.如果C1≠C2，则式（1）中定义的损失函数属代价敏感型，其中C1表示将有链路节点对错分为无链路节点对时的代价，C2表示将无链路节点对错分为有链路节点对时的代价.

式（1）中的损失函数及相关风险函数不可微，因此设计分类器时的灵活性较差.可使用与指数损失相关联的风险作为替代，

ˆ=1∑exp[−Af(e)]. （2） Rexpijij

n2ij指数风险为一个连续可微函数，并使上文0-1损失风险受到边界约束.可以看出，可对式（1）代价敏感型损失函数进行边界约束的等价表达式为

ˆRcost−sens=

数链路预测模型往往在预测大多数低节点度节点

时失效. 文献[3]将链路预测问题定义为二分类问题，基于AdaBoost算法提出并实现了一个新型链路预测算法.但是，该方法仅仅只能抓住一些局部信息，而且其有效性依赖于某些特定的网络，另外，其计算复杂度太高、不够灵活.文献[4]提出了一种基于节点贡献权重的链路预测模型.这种方法受限于特征的构造，而且计算的过程非常费时.文献[5]通过一组关系连接了多种节点类型的路径，来描述异质信息网络中不同类型对象之间各种连接的不同语义，从而提出一种异质信息网络链路预测模型，通过组合对象之间在不同元路径上建立连接的概率来进行链路预测.文献[6]确定了链路预测时的多种节点和拓扑结构特征，并使用支持向量机和决策树等多种分类器来预测书目数据库中的链路.Taskar[7]等使用关系型马尔科夫网络来联合模拟节点属性和链路.然而，链路预测的主要困难之一在于类别不均匀性太大，导致检测率较低.Clauset[8]等人提出基于最大似然概率的链路预测算法.然而，该方法是对已知网络内社区的所有可能分区计算均值，因此即使是对小规模网络，其部署代价也较高.为此，本文提出一种基于节点度的代价敏感型链路预测算法.设计损失函数，强调基于社区的链路预测、模块度指标和Boosting算法间的关系.利用4个真实的网络数据集进行性能评估，实验结果表明，本文LinkBoost算法的性能与许多当前算法的性能相当或者优于当前算法.

1 问题分析

将链路预测任务看成是一种二元分类问题，如果两个节点间存在链路，则认为节点对属于阳性类别，否则属于阴性类别.设V={1,2,\",n}表示网络中

ε=V×V表示所有节点对组成的集合.的节点集合，

用A表示网络的邻接矩阵，Aij={+1,-1}表示链路存在或不存在.每个节点i∈V具有d维节点属性，且属性xi={xi1,xi2,\",xid}.本文的目标是学习一个可将每个节点对映射到链路位势的目标函数f:V×V→R.如果对任意已知的节点对e∈ε，如果该函数可以实现期望风险R=Eε,A[L(f(e),a)]最小化，则认为函数最优，其中L[f(e),a]表示损失函数.损失函数的一般形式为 ⎧0⎪

L[f(eij),Aij]=⎨C1

⎪C⎩2

如果sgn(f(eij))=Aij

如果sgn(f(eij))≠Aij=1，（1） 如果sgn(f(eij))≠Aij=−1

（3） 1

IA=−Cfe+IA=−Cfe[(1)exp(())(1)exp(())].∑ij1ijij2ij

n2ij

如果将表示链路存在与否的类别标签从{+1,−1}变为{C1,-C2}，式（3）中的代价敏感型风险就可转化为式（2）中的经验风险.一般来讲，代价参数C1、C2的选择标准是使之可以纠正类别分布中的不均匀性所导致的分类偏差.如果n+和n−表示数据中的阳性样本和阴性样本的数量，则C1和C2

Cnn

往往选为1=−.对大型稀疏网络，有−=O(n)，

C2n+n+因此如果设置C1=1，则C2～n−1，进而导致极端惩

罚容易被有限的机器精度污染.为了避免这一情况，需要调整阳性标签和阴性标签的代价，以保持期望

式中，sgn(⋅)为符号函数，如果参数非负则为+1，

第11期 袁芳芳，等：一种改进的代价敏感型链路预测算法 的惩罚比.代价比

C1

的另一意义在于它有助于确定C2

1287

最优代价敏感型决策面.代价敏感型学习时的最优决策面为

f*=argminfEε,A[L(e,a)].

可由贝叶斯决策准则确定为

PAε(a=1e)C1

f*(e)=log.

PAε(a=−1e)C2

因此，对任意代价结构(C1,C2)，代价敏感型最优性与非代价敏感型最优性的区别在于阈值

C

T=log1(假设C1和C2为常数).

C2本文认为，不应该用同一尺度来衡量所有有链路（和无链路）节点对的错分代价.下节给出一种可变代价损失函数，使低节点度有链路节点对在被错分后导致的代价，高于高节点度有链路节点对的错分代价.这一更改有助于链路预测算法在同一社区内预测出更多链路.

式中，γ为自定义参数。当节点度增加时，上式也将增加.现在需要处理阴性示例和阳性示例间的总体偏差.通过选择β和γ的数值使C2⎧1−βkikj如果sgn(f(eij))≠Aij=1⎪

L[f(eij),Aij]=⎨γkikj如果sgn(f(eij))≠Aij=−1 .（4）

⎪

⎩

0

其他

上述损失函数的主要特点在于，它可为不同的节点对分配不同的错分代价.当β=1∑iki

时，

βkikj项表示节点对i和节点对j间的预期链路数量.下节将证明，对该β值，降低可变代价损失函数的关联风险，等价于使模块度指标最大化.这将导致学习算法更倾向于学习同一社区内节点对间的链路，而不是学习不同社区间的链路.

3 模块度

一般而言，同一社区内的链路密度往往高于社区间的链路密度.这表明，链路预测和社区检测间存在紧密联系.网络社区检测的常用方法是使用著名的模块度指标[9].此时，通过比较社区子图中的实际链路密度来检测已知网络中可能存在的社区；如果不管社区结构如何，子图节点始终有链路相连，则密度较大的子图应该存在社区.模块度指标的数学表达式为

Θ=∑[I(Aij>0)−Pij]I(ci=cj)，

ij

2 链路预测可变代价损失函数

现实网络中的节点度分布往往服从幂律分布，高节点度节点的数量较少，低节点度节点数目较多.因此，链路预测有监督学习算法不仅面临着来自大量无链路节点对（阴性类别）造成的偏差，还面临着少量高节点度节点造成的偏差.具体来说，有链路节点对（阳性类别）中的高节点度节点对决定决策面做出的贡献更大.因为希望构建的模型既可以解释观察到的任意节点对间的链路，又不会受到部分高节点度节点所形成的链路的影响.因此，需要设计一种可以去除阳性类别内这种偏差损失函数.

实现这一目标的一种方式就是使用节点度决错分有链路定错分惩罚.设ki节点i的节点度.于是，节点对eij的代价为

C1(eij)=1−βkikj，

式中，β为用户自定义参数，设置该参数以保证代价函数非负.当ki或kj的节点度上升时，C1单调下降，因此使低节点度节点间的链路发生错分时的惩罚度高于高节点度节点间链路被错分时.

类似地，对无链路节点对可做类似推理.相比于高节点度节点对，低节点度节点对对阴性类别的影响更大.为避免阴性示例间的这种偏差，将错分无链路节点对时的代价定义为

C2(eij)=γkikj，

式中，Pij为参考网络中节点i和节点j间的期望链路数量.ci、cj分别为节点i和节点j的社区隶属度.基于模块度的社区检测算法，通过将节点分配给不同的社区，使总体模块度指标Θ最大.于是，根据文献[10]有

kk1

Θ=2∑[I(Aij>0)−ij]I(ci=cj) （5）

nij2m式中，m为网络中的链路数量，m=∑iki/2.假设有一个基于社区的链路预测模型根据节点是否位

于同一社区来预测一个节点对间是否存在一条链路，即

⎧+1如果I(ci=cj)

sgn(fcomm(eij))=⎨ .

−1其他⎩根据如上所述，可以得到如下的定理：

定理1 设有式（4）定义的可变代价损失函数及与基于社区的链路预测模型fcomm(eij)相关联的风险，β=γ=1∑k

i

时使该风险最小化，等价于使

i

式（5）中的模块度函数最大化.

1288辽宁工程技术大学学报（自然科学版） 第34卷

Dij=exp[−(I(Aij>0)−Mij=(I(Aij>0)−

kikj2m

kikj2m

)Fij]；

证明 采用基于社区的链路预测模型时，式（4）定义的可变代价损失函数所关联的经验风险为

ˆ=1[∑I(sgn(fRmodcomm(eij))=−1)(1−βkikj)+

n2ij:Aij=1

ij:Aij=−1

)ft(eij)；

∑

I(sgn(fcomm(eij))=1)(γkikj)]=

sij=sgn(Mij)；WW

+

==

111[(1)(1)(−δ−kk+δkikj)].∑∑ijijij

2m2n2ij:Aij=1mij:Aij=−1

ij∈Mij>0

−

∑

DijMij；DijMij.

替换I(sgn(fcomm(eij))=1)=δij和β=γ=1/2m.δ使经验风险最小化，等价于使下式最大化，

kkkk

ˆ=max1[∑δ(1−ij)−∑δij)]=minRijijmodfδ2mij:Aij=−12mn2ij:Aij=1

max

δij∈Mij<0

∑

1

n2

∑δij

ij

[I(Aij>0)−

kikj2m

在本文中，W+和W−表示正确分类节点对和错误分类节点对的加权和.

可以看出，式（6）中的目标函数受到如下边界约束：

].

∑exp[−(I(Aij>0)−

ij

kikj2m

)(Fij+αtft(eij))]=

因为δij=I(sgn(fcomm(eij))=1)=I(ci=cj)，得证.

∑Dexp(−αs

ijij

tij

Mij)≤∑DijMij(exp(−αtsij)−1)≤

ij

4 链路预测的Boosting方法

本节给出第4节可变代价损失函数的优化方法.式（4）损失函数所关联的风险不可微，因此使用如下可变代价经验风险函数

ˆ=1∑[I(A=1)exp[−(1−βkk)f(e)]+Rmodijijij

n2ij I(Aij=−1)exp[γkikjf(eij)]].

如果设置β=γ，则上述损失函数为 ˆ=1Rmod

n2

(W+exp(−αt)+W−exp(αt)−W+−W−).

利用Jensen不等式和Mij≤1假设可以获得上述不等式.对已知ft，关于αt求其偏导可得 1W+

αt=log−.

2W

11−e

αt表达式从本质上与αt=log(e为弱分

2e

类器的误差率)的AdaBoost算法类似.

∑exp[(I(A

ij

ij

>0−βkikj)f(eij)].

4.2 弱学习器

设X表示n×d维节点属性矩阵.已知节点对间的当前权重矩阵D，弱学习器的目标是估计n×n维链路位势矩阵L(X)，其中Lij=ft(eij)表示节点i和节点j间的链路强度.Lij为正且数值较大，表明节点间链路的位势较大；Lij为负且数值较大，表明节点间形成链路的排斥较大.将L(X)简单看成是节点属性的加权相关性.设L(X)=XWXT.其中，权重矩阵W为d×d维矩阵，通过求解如下目标函数可以估计该矩阵，

λ2

Θ=max∑(DijBij)[XWXT]ij)−W2，

W2ij式中，Bij为模块度指标的系数项或每个节点对关联的代价，Bij=[I(Aij>0)−

kikj2m

].

机器学习领域利用加性建模或Boosting技术[11]对

这种形式损失函数进行深入研究.加性模型的形式为

fα(x)=sgn[∑αtft(x)].

t

为实现提升效果，每个fi对应于弱学习器，且目标是检测出一个常数序列α1,α2,\",αk使弱学习器线性组合的性能优于各个单独学习器. 4.1 估计αt

本文的目标是设计一种可以实现可变代价经

ˆ最小化的Boosting算法.为此，需要验风险函数Rmod

归纳有助于尽量降低风险的一组弱学习器.设

F=∑i=1αif表示第(t−1)步时Boosting算法的解，

i

t−1

ˆf是当前归纳的弱学习器.需要确定可以改进Rmod

t

的合适的αt值.第t步时的优化问题为

minexp[−(I(Aij>0)−t∑

αt,f

ij

目标函数的微分有

∂LT

=−∑DijBij(XipXqj)+λWpq=0； WpqijDijBijXjq.

λijij

设“·”为各元素相乘矩阵乘法，则W可写为

Wpq=

1

T=∑XipDijBijXqj

kikj2m

（6） )(Fij+αtft(eij))].

为突出当前弱学习器的影响，需要将先前弱学

习器的影响从等式中隔离出来.设置为

∑Xλ1

Tpi

第11期 袁芳芳，等：一种改进的代价敏感型链路预测算法

W=

1

12

λXT(B⋅D)X.

因此，已知权重矩阵D时的链路位势函数L(X)=XWX T为

1

L=XXT(B⋅D)XXT.

λ4.3 LinkBoost算法

本节提出一种伸缩性较强的链路预测算法LinkBoost.具体方法是将网络分为多个更小、可能互相重叠的分区，并使用Boosting算法系统地将每个分区构建的弱学习器加以融合.因为链路形成往往是局部现象，网络中有多个小型社区，而且链路多形成于社区内，所以分支定界算法非常适合链路预测问题和Boosting框架.因此，可以根据网络的多个小型分段构建一个局部（弱）学习器，然后按照一定原则对其融合，进而通过Boosting框架形成一个全局模型.有多种策略可以创建大规模网络的子图分区.本文要求：（1）分区之间必须要有明显差异，以保证归纳出一组不同的（不相关）弱学习器；（2）在大型网络上部署时，分区方法的效率要高.在尝试数种分区策略（比如从随机选择的种子节点开始运行随机游走策略）后，发现这些策略均无法满足这两个要求.于是，本文考虑使用域分区策略，该策略特点是部署代价较低，而且可以生成一组不同的分区.

算法1 LinkBoost算法

输入：A：元素为{+1,−1}的n×n维相邻矩阵 X：n×d节点属性矩阵 η：特征分区阈值

输出：F：n×n维链路位势矩阵 初始化：

F=[0]n×n；D(0)=[1]n×n； k：节点度的n×1维列向量 For t=1Tdo

P←GetFeaturePartition(η) For Xp∈Pdo

V←GetSubGraphNodes(Xp)W←GetBaseLearner(Xp,Dv,kv,Av)

本文可伸缩LinkBoost算法总结于算法1中.对每个分区，生成一个包含多个节点的子图，子图中的节点相比于被选择的特征集合必须要有至少一个非零数值.然后，调用GetBaseLearner子程序来构建一个子图局部模型.该子线程的输入参数包括：（1）Av，与特征分区P生成的子图相关联的相邻

（3）Dv，矩阵；（2）Xp，子图中的节点属性子集；

子图中节点对的权重；（4）kv，子图中节点的全局节点度.GetBaseLearner子程序返回的权重用于更新链路位势矩阵估计.该过程在不同特征分区的所有子图上重复T次.

除了部署效率较高、生成的弱学习器具有多样性之外，域分区策略的另一优点是其最终假设具有非线性决策面.可以明显看出，4.2节描述的弱学习器XWX T生成的线性决策面能将有链路节点对和无链路节点对分开.Boosting算法可以对弱学习器进行线性融合，所以它无法显著改变决策面.然而，通过在构建弱学习器时进行域分区，就可以对不同的子图加以利用.只对当前子图V而不是整个网络运用GetBaseLearner函数返回的权重矩阵W.这将在特征空间生成一个非线性决策面.最后，Boosting算法可以对非线性决策面进行融合，生成一个带有非线性决策面的分类器.

5 性能评估

本节主要给出LinkBoost算法的实验结果.因为链路预测从本质上来说是代价敏感型问题，所以基于接收者运行特征曲线（ROC）来评估本文算法和其他基准算法的性能.通过改变节点对间的链路位势估计阈值并计算检测率（true positives）和虚警率（false positives），进而获得ROC曲线. 5.1 实验设置

本节比较LinkBoost算法与目前较为典型的4种算法：优先连接算法(PA)[12]，Katz算法[13]、模块度算法[9]和Adaboost算法[14]等的性能.实验基于两种测试数据集：

（1）用于推断缺失链路的数据集.即使用

首先使Citeseer和Cora数据集[15].在两个数据集中，

网络图为无向图，然后从网络中随机删除30%的链路，并将其作为缺失链路预测的测试集.（2）用于预测未来链路的数据集.即使用DBLP数据集和Wikipedia数据集.其中，DBLP数据集包含1997-2006年间机器学习、数据挖掘和数据库领域28个学术会议的所有计算机科学论文

计算fv=XpWXTp 利用式（17）计算α

F←Fv+αfv

v

Dv=Dvexp(−αAv⋅Lv)End for End for

返回F

1290辽宁工程技术大学学报（自然科学版） 第34卷

面的性能.对Cora和Citeseer数据集，使用真实的社区标签来为每种链路预测算法验证社区内形成的链路比例.对链路位势进行排序，并宣布前K个链路位势为潜在缺失链路或将来链路.图1给出了社区内链路或优质链路比例随着K值的变化情况.

很明显，LinkBoost算法优于模块度和Katz指标算法，证明本文算法可以检测出社区内链路.K值较小时，模块度和Katz算法检测出来的优质链路比例较高，但是当K值较大时，比例迅速下降.

Katz算法 PA优先连接算法 Modularity模块度算法LinkBoost算法 AdaCost算法 （http://dblp.uni-trier.de/）.Wikipedia数据集包括从2008年1月诞生之日起Wikipedia所有页面的编辑历史.此外，本文还考察了用户-用户交互网络（用户交谈网页）.2004年前6个月的用户交互作为训练集，后6个月作为测试集.共有8 178个用户，每个用户有24 1个特征. 5.2 社区内的链路

首先评估LinkBoost算法在社区内链路预测方

0.9优质链路概率 0.70.50.30.10 1 2 3 K×105 4 5 Katz算法 PA优先连接算法 Modularity模块度算法LinkBoost算法 AdaCost算法 0.9优质链路概率 0.70.50.30.10132K×10 5 （a）Cora数据集 （b）Citeseer数据集

图1 社区内链路或优质链路比例随着K值的变化情况 Fig.1 community link or high quality link ratio changes with K value

10.8假阳性 0.60.40.20 0.2 0.6 0.4 真阳性×105 0.8 Katz算法 PA优先连接算法 Modularity模块度算法 LinkBoost算法 FC-Ad算法 1 10.8假阳性 0.60.40.200.20.40.6 真阳性×105 0.8 Katz算法 PA优先连接算法 Modularity模块度算法LinkBoost算法 FC-Ad算法 1 （a）Cora数据集 （b）Citeseer数据集

10.8假阳性 0.60.40.20 0.2 0.6 0.4 真阳性×105 0.8 Katz算法 PA优先连接算法 Modularity模块度算法LinkBoost算法 FC-Ad算法 1 10.8假阳性 0.60.40.200.20.8 0.6 0.45真阳性×10 Katz算法 PA优先连接算法 Modularity模块度算法LinkBoost算法 FC-Ad算法 1 （c）DBLP数据集 （d）WIKI数据集

图2 不同链路预测算法的ROC性能对比

Fig.2 compare performance of different link prediction algorithm by ROC

第11期 袁芳芳，等：一种改进的代价敏感型链路预测算法

1291

5.3 缺失和将来链路

下面评估LinkBoost算法在缺失和将来链路预测方面的性能.图2给出了ROC曲线. LinkBoost算法的AUC始终高于模块度指标.如上文所述，模块度指标只利用了网络链路结构信息，而Boosting算法使用链路和内容信息，因此性能更优.LinkBoost算法的性能也始终优于固定代价Adaboost算法，证明了本文可变代价结构的重要性.

LinkBoost对Cora和Citeseer引用网络的性能均优于Katz指标.Katz对DBLP网络的性能优于固定代价Adaboost算法，但是对Wikipedia网络的性能与LinkBoost相当.然而，该算法对参数非常敏感.本文给出的实验结果使用了与测试集最为匹配的参数设置.

[4] 伍杰华.基于划分社区和差分共邻节点贡献的链路预测[J].计算机应用研究,2013,30(10):2 9-2 957.

Wu Jiehua.Link prediction based on partitioning community and differentiating role of common neighbors[J].Application Research of Computers,2013,30(10):2 9-2 957.

[5] 黄立威,李德毅,马于涛.一种基于元路径的异质信息网络链路预测模 型[J].计算机学报,2014,37(4):848-858.

Huang Liwei,Li Deyi,Ma Yutao.A meta path-based link prediction model for heterogeneous information networks[J].Chinese Journal of Computer,2014,37(4):848-858.

[6] Hasan M A,Chaoji V,Salem S,et al.Link prediction using supervised learning[C]//In Proc.of SDM 06 workshop on Link Analysis, Counterterrorism and Security.Bethesda,MD,USA:IEEE Press,2006: 1-196.

[7] Taskar B,Wong M,Abbeel P,et al.Link prediction in relational data[C]//In Advances in Neural Information Processing Systems.Lake Tahoe, Nevada,USA:IEEE Press,2013:235-242.

[8] Clauset A,Moore C,Newman M.Structural inference of hierarchies in networks [C]//23rd International Conference on Machine Learning.Pittsburgh, Pennsylvania,USA:IEEE Press,2006:332-339.

[9] Vázquez A.Growing network with local rules:Preferential attachment, clustering hierarchy,and degree correlations[J].Physical Review E,2013,67(5):56-104.

[10] Palla G,Derényi I,Farkas I,et al.Uncovering the overlapping community

structure of complex networks in nature and society[J].Nature,2012, 43(7):814-818.

[11] 侯杰,茅耀斌,孙金生.基于指数损失和0-1损失的在线Boosting算法

6 结论

（1）提出一种新的基于节点度的代价函数，并证明使关联风险最小化可实现模块化链路预测，进而预测出社区内的更多链路.该代价函数解决了类别分布和节点度存在的分布不均问题；

（2）本文算法具有较强的伸缩性，且易于部署； （3）本文算法的性能优于当前有监督和无监督算法，还可以有效地预测出低节点度节点的缺失链路.下步工作将研究最优代价参数的估计问题，并改进LinkBoost算法中弱学习器的创建方法. 参考文献:

[1] 王慧,王红飞,牛玉俊.一类节点结构相同的复杂网络脉冲同步[J].辽宁工程技术大学学报:自然科学版,2013,32(1):140-144.

Wang Hui,Wang Hongfei,Niu Yujun.Impulsive synchronization of a kind of complex networks with same nods[J].Journal of Liaoning Technical University:Natural Science,2013,32(1):140-144.

[2] 杨雄.热点话题在交叉社团网络的传播模型[J].辽宁工程技术大学学报:自然科学版,2013,32(2):192-196.

Yang Xiong.Investigation of hot public topic propagation model over multi-social networks[J].Journal of Liaoning Technical University:Natural Science,2013,32(2):192-196.

[3] 吴祖峰,梁棋,刘峤,等.基于AdaBoost的链路预测优化算法[J].通信学报,2014,35(3):116-123.

Wu Zufeng,Liang Qi,Liu Qiao,et al.Modified link prediction algorithm based on AdaBoost[J].Journal on Communications,2014,35(3):116-123.

[J].自动化学报,2014,31(4):1 248-1 256.

Hou Jie,Mao Yaowu,Sun Jinsheng.Online boosting algorithms based onexponential and 0-1 Loss[J].Acta Automatica Sinica,2014,31(4):1 248- 1 256.

[12] Xie Y B,Zhou T,Wang B H.Scale-free networks without growth[J].

Physica A:Statistical Mechanics and its Applications,2008,387(7): 1 683-1 688.

[13] Dhillon I,Savas B,Zhang Y.Social network analysis:Fast and memory

-efficient low-rank approximation of massive graphs[C].Householder Symposium XVIII on Numerical Linear Algebra,Lodge,Tahoe City,CA, IEEE,2011:55-63.

[14] Rubin D B.A Calibrated multiclass extension of AdaBoost[J].Statistical

Applications in Genetics and Molecular Biology,2011,10(1):1-24. [15] P Sen,G M Namata,M Bilgic,et al.Collective classification in network

data[J].AI Magazine,2008,29(3):93-106.