基于符号网络的边值预测方法研究

佘宏俊，胡梦缘

(1.东北财经大学 数学与数量经济学院, 辽宁 大连 116025；2.中南财经政法大学 工商管理学院，湖北 武汉 430073)



基于符号网络的边值预测方法研究

佘宏俊1，胡梦缘2

(1.东北财经大学 数学与数量经济学院, 辽宁 大连 116025；2.中南财经政法大学 工商管理学院，湖北 武汉 430073)

针对社会网络中存在的正负二元边值关系，基于共同邻居指标法在识别社会网络符号边值问题中的优势，提出了一种符号网络下的边值预测方法(ICN-Predict)。该符号网络边值预测方法有效结合了节点符号密度属性和网络拓扑结构特征，避免了共同邻居法预测选值敏感性问题。通过实验仿真发现，ICN-Predict预测方法扩大了符号网络边值预测的适用面，提高了边值预测精度，同时表明进一步提高预测精度的关键在于提高负值边的预测准确率。

符号网络；共同邻居；边值预测

近年来，网络图分析在诸多领域有着广泛的应用，例如化学领域中物质的分子结构、互联网范畴的虚拟社区关系及生物信息学等，这些领域中的大量数据都可以抽象建模为图结构并用于进一步研究，基于网络图的链接关系预测已成为数据挖掘领域新的研究热点。

应用马尔科夫链进行网络链接预测[1]、采用回归模型[2]及蚁群算法[3]对网络进行分析是计算机领域对社会网络进行研究的一类重要方法。针对网络中的拓扑结构，文献[4]提出了相似性的相关定义，分析了社会网络中许多主要指标链路预测的效果。基于网络结构的极大似然估计则是另一类进行链路预测的方法，其中由CLAUSET等[5]提出的一种基于网络层次结构的极大似然链路预测方法在小规模层次结构分明的网络中效率较高。同时，上述这些链接预测方法在不同领域、学科都有着广泛的实际应用。在生物学中，蛋白质相互作用的网络结构和新陈代谢网络相关预测在文献[6]中有所介绍，指出约有80%的蛋白质关系尚未被发现，利用网络边值预测可以解决该问题。而在社会关系网络研究中往往会遇到数据缺失的情形，链接预测亦可用于准确预测缺失的社会关系。该方法可用于虚拟社交网络方面[7]，即通过已知部分节点类型的社区网络结构信息去预测未知标签节点的类型，好友推荐模式是社会网络预测理论的典型应用。

国内学者徐恪等[8]从测量的角度总结了在线社会网络的拓扑结构、用户行为和网络演化方面，对常见的测量方法和典型的网络拓扑参数进行了综述。王刚等[9]提出了社会网络中交易节点的选取及其信任关系计算方法，通过设计一个竞标服务策略来调动节点提供资源服务的积极性。张昱等[10]针对社会网络中有权图的链接预测问题，提出了一个基于时间信息的链接预测方法，通过博客数据集验证了该方法相对于传统方法效果更好。

符号网络是社会网络中边值为正负两种关系的二元复杂网络。目前对该网络边值预测问题的研究较少，其预测重点在于边值的符号关系，传统边值符号预测多基于节点自身的属性特征或网络拓扑结构。但是，对于互联网上的社交网络数据，很多用户信息都是虚假的或是保密的，导致节点信息有误，网络结构分离，难以获得节点属性及拓扑结构的真实情况。同时，判断各种信息中哪些是对当前社会网络预测有用的，哪些信息是无用的也是一个重要问题。因此，单独采用网络拓扑结构或节点属性相似度对符号网络进行边值预测都存在一定的偏误。笔者基于已有研究成果，提出一种基于共同邻居的符号网络改进边值预测方法(improved common neighbor-predict，ICN-Predict)。该方法较好地结合了节点属性的相似性指标和网络结构的相似性指标，综合两个属性特征对符号网络边值进行预测。实验证明，与已有边值预测算法相比，ICN-Predict方法有较高的预测精度。

1 基本理论

符号社会网络中的边值预测(link sign prediction)是指通过符号社会网络内已知的节点和网络拓扑结构关系等信息去预测尚未产生连接的两个节点之间的正负关系。这种预测是对网络中边的未知符号关系进行预测。符号社会网络的边值预测方法的主要思想来源于社会平衡理论和相似性度量算法。

1.1 社会平衡理论

所讨论符号网络的模型是采用CARTWRIGHT和HARARY在1956年提出的社会学结构平衡理论。在社会平衡理论中，对于一个给定的三方关系u，v，w如图1所示，从人际交往的直观意义上解释上述符号网络：

(1)如果w是u的朋友，v是w的朋友，则v也是u的朋友。

(2)如果w是u的朋友，v是w的敌人，则v也是u的敌人。

(3)如果w是u的敌人，v是w的朋友，则v是u的敌人。

(4)如果w是u的敌人，v是w的敌人，则v是u的朋友。

图1 符号网络三方平衡关系

而图1(b)中4种关系不符合社会学人际关系实际意义，暂时不做讨论。

根据上述社会平衡理论，若已知其中任意两点之间的边值关系，则可对其第三方节点边值之间的关系进行预测，当已知u，w节点之间的边值s(u,w)和v，w节点之间的边值s(v,w)，则可给出一个预测第三方节点关系边值s(u,v)的定义，如式(1)所示：

s(u,v)=s(u,w)s(v,w)

(1)

由于在计算s(u,v)边值符号过程中并没有加入网络图的有向性标识，因此基于社会平衡理论的边值预测仅适用于包含无向关系的符号网络。

1.2 相似性度量指标

符号网络边值预测拟采用基于共同划分的相似性指标作为预测评价的依据。目前学术界已提出很多相似性度量指标，包括CN(common neighbor)指标法，Jaccard指标法，Adamic/Adar指标法和Preferential Attachment指标法等，在上述诸多方法中，CN指标法是其中预测过程简单且预测精度较高的一种。CN指标法[11]将Score(x,y)定义为节点x，y之间共同邻居的个数，即：Score(x,y)=|Γ(x)∩Γ(y)|。该定义表明两个节点之间拥有的共同邻居节点越多，则这两个节点间的关联可能性越大。并且CN指标法能够与社会平衡理论较好地结合，因此选择该指标作为相似度的度量标准。

2 基于共同邻居的符号网络预测方法

2.1 基于共同邻居(CN-Predict)的预测方法

如上所述，CN指标法是通过Score(x,y)相似度计算，建立节点之间的相似关系网。定义Score(x,y)为相似性指标，Γ(x)为节点x的邻居节点集合，s(x,y)为节点x与y之间的边值符号。如果要预测节点u对v的边值符号关系，则首先要找出u的邻居节点集合Γ(u)及v的邻居节点集合Γ(v)，然后根据Γ(u)∩Γ(v)中的节点集合与u，v的边值符号情况，预估u对v的符号关系。

若两个节点x,y之间共有的邻居节点C，定义基于平衡理论的相似度BScore(x,y)为：

(2)

其中，Balance(xi,yi,ci)表示根据社会平衡关系理论预测出的xi，yi,ci三方正关系，即Balance(xi,yi,ci)=s(xi,ci)s(yi,ci)。设定相似度的阈值为λ，当BScore(x,y)≥λ时，认为节点x，y之间为正关系，即s(x,y)=1；当BScore(x,y)<λ时，认为节点x，y之间为负关系，即s(x,y)=-1。

在预测符号网络边值时，若只考虑邻居节点的结构特征，则会在某些情况下不能得到一个合理的预测值，有必要保留部分节点属性信息来进行预测，用于提高预测的准确性。

2.2 改进的边值预测方法

为了完善CN预测方法中没有共同邻居及某些情况下预测的合理性，采用基于节点度数的预测方法进行改进。节点x的度数和Deg(x)=d+(x)+d-(x)代表了该节点的人际关系情况，在比较两个节点之间连接边的可能性时，可以用节点之间对集合T中节点的节点度数和相似性度量来表示它们之间的差异性。将这个差异定义为节点之间的相似性差异，那么基于节点度数的相似度可以定义为：

(3)

式(3)表明，|Deg(x)+Deg(y)|越小，则表示x与y之间的节点类型差异越大。

为避免由于DScore(x,y)对BScore(x,y)的值产生较大影响，而导致最终结果的误差比较大，可通过适当的方式加入DScore(x,y)的影响因素。现考虑以下3种情形，其中T=Γ(x)∩Γ(y)表示x与y节点之间的共同邻居集合，TScore表示综合相似度评分。

(1)当Γ(x)∩Γ(y)=∅时，此时节点x和y没有共同邻居，可以认为节点x与y之间没有任何相关性，即BScore=0，TScore=DScore。

(2)当DScore(x,y)=0，Γ(x)∩Γ(y)≠∅时，表示两个节点x和y分别属于不同的类型，共同邻居关系决定两节点之间的相关关系, 即TScore=BScore。

(3)当DScore(x,y)≠0，Γ(x)∩Γ(y)≠∅时，该情况下节点x和y的共同邻居，以及它们自身的节点属性值共同决定TScore的值。

综上所述，基于CN的改进预测方法为：

算法：ICN-Predict(srcnode, dstnode, truesign)

输入：srcnode：待测边的源节点 dstnode：待测边的目标节点 truesign：待测边的实际符号值

输出：true/false ：预测真值

foreachvi∈N(srcnode),vi∈N(dstnode) do

computeDeg(srcnode) andDeg(dstnode); //计算节点度数和

end foreach

if abs(Deg(srcnode))+abs(Deg(dstnode))≠0

computeDScore(srcnode, dstnode);//计算DScore

GetCmnNbh( srcnode, dstnode, CNbhV);//获得共同邻居集合CNbhV

foreachvi∈CNbhV do

S1=GetEdgeSign(srcnode,vi); //获得边值符号

S2=GetEdgeSign(vi, dstnode);

if(S1×S2=1) then

Balance++;

end foreach

BScore=Balance/CNbhV.Len; //计算BScore

if(CNbhV.Len=0 orBScore<α)then

do predict onDScore; //基于节点度数的预测

else

do predict onBScore;//基于共同邻居的预测

令符号网络中节点的个数为n，边的个数为m，ICN-Predict算法中计算扫描符号网络中的所有节点对产生的结果，因此含有n个节点，m条边的符号网络对于邻接表存储形式而言，其总的时间复杂度为O(n+m)。

2.3 预测精度标准

预测精度即预测模型拟合的好坏程度，笔者采用AUC指标作为预测精度的标准，每次随机从测试集中选取一条边与随机选择的并不存在的边进行比较，独立地进行比较n次，令n′表示测试过程中正值边类型预测正确的个数且权重为1，n″表示测试过程中负值边类型预测正确的个数且权重为0.5，将最终统计的预测正确率作为模型评价标准，则将AUC定义为：

(4)

3 实验测试

3.1 实验过程

符号网络的边值预测实验以随机生成的符号网络数据集G(30,700,0)(30个节点，700条边，随机符号网络图)，Gama数据集和Sam_aff数据集作为实验数据来源，实验仿真系统在Windows环境下开发，采用C++语言，使用的是VS 2010开发工具。分别采用上述4种方法对Gama数据集和Sam_aff数据集分别进行预测分析统计。Gama数据集包含了16个Gahuku-Gama种族之间的社会网络关系，其中正边和负边分别代表种族之间的同盟和敌对关系。Sam_aff数据集记录了Sampson修道院中18个僧侣之间的人际关系情况，其边值取值范围在-3和3之间，分别代表不同的人际关系程度。为了简化讨论，将Sam_aff数据集中的边值元素统一处理为<+1,-1>的二值，公共数据集统计参数如表1所示。

表1 公共数据集统计参数

该实验从实验数据集的边集中依次选择待预测边并删除该边，然后对该缺失边使用上述4种预测方法对未知的边值符号进行预测，并将预测边值结果与真实边值进行比较，记录在结果集中，最后对符号网络数据集中的所有边值预测结果进行统计分析得到实验最终结果。

3.2 实验结果分析

实验结果如表2、表3和表4所示。第1列代表4种预测方法；第2列至第5列分别表示真实边值和预测边值符号的实验结果统计，例如“+/+”代表真实边值为正，预测边值结果也为正的实验结果统计；最后一列表示AUC值的计算结果。

表2 RandomGraph(30,700)预测实验结果

表3 Gama(16，116)预测实验结果

表2为随机符号网络数据集的预测统计结果，从表2中可以看出基于节点度数的预测(Deg-Predict)，基于共同邻居的预测(CN-Predict)及改进的基于共同邻居预测方法(ICN-Predict)与随机预测(Rnd-Predict)的预测精度52.7%相比分别下降了1.0%，10.3%，4.0%，证明这4种方法无法对随机符号网络进行预测分析。随机符号网络是由随机函数产生的网络图，其结构本身没有任何社会关系基础，随机产生的符号边也没有预测规律可循，因而均无法对随机生成符号网络的边值进行预测。

表4 Sam_aff(18，158)预测实验结果

Gama数据下的实验预测结果如表3所示，可以发现，对Gama数据集中116个边值符号进行预测后，ICN-Predict方法的预测精度最高，达到了86.2%，Rnd-Predict的预测精度最低，仅为50.0%，其他两种方法中Deg-Predict的预测精度为62.9%，CN-Predict方法的预测精度为81.0%。Gama数据来源于社会人际关系的实地调查，实验结果表明，基于社会平衡理论的预测方法都能表现出良好的预测效果，其中ICN-Predict方法预测效果最佳。

Sam_aff数据集的预测结果如表4所示，由于Sam_aff数据集在数据分析之前进行了归一化预处理，因此相对于Gama数据集而言，其整体预测效果有所下降。其中，Rnd-Predict方法依然维持在50%左右的准确率，而Deg-Predict方法和CN-Predict方法的预测精度分别为64.6%和74.1%，ICN-Predict方法仍然保持了最优的预测精度，达到79.7%。该结果表明ICN-Predict方法在不同数据集下都能保持较优的预测精度，具有一定的稳健性。

基于Gama和Sam_aff数据集预测实验结果显示，4种基于社会平衡理论的共同邻居预测方法能够对社会中普遍存在的符号网络人际关系进行较好的预测，而改进后的共同邻居预测方法(ICN-Predict)能够在一定程度上提高对不同数据集的预测精度。同时从表3和表4的预测结果还可以发现，基于共同邻居的预测方法对正值边的预测准确度远远高于负值边的预测准确度。

4 结论

基于社会网络的链接预测已成为当今热门和前沿的研究领域，针对符号网络的边值预测，提出了一种基于共同邻居的改进预测方法(ICN-Predict)。改进后的预测方法进一步考虑了无邻居和某些不合理的预测条件，在网络拓扑结构预测方法的基础上，补充加入了基于节点符号密度的预测方法，从而提高了符号网络边值预测方法的适应性。通过模拟实验比较验证了4种基于社会平衡理论的共同邻居预测方法，实验结果表明，ICN-Predict方法能有效地提高符号网络边值的预测精度，同时表明了进一步提高预测精度的关键在于提高负值边的预测准确率。但是该方法尚不能较好地对负值边存在缺失的情况进行预测分析，有必要寻找其他的相关理论支持。如何对动态变化的社会网络进行实时有效的结构分析，也是今后的一项重要研究工作。

[1] SARUKKAI R R. Link prediction and path analysis using markov chains[J]. Computer Networks, 2000,33(1):377-386.

[2] POPESCUL A, UNGAR L H. Statistical relational learning for link prediction[C]∥IJCAI Workshop on Learning Statistical Models from Relational Data.[S.l.]:[s.n.],2003:101-103.

[3] SHERKAT E, RAHGOZAR M, ASADPOUR M. Structural link prediction based on ant colony approach in social networks[J]. Physica A: Statistical Mechanics and its Applications, 2015(419):80-94.

[4] LIBEN N D, KLEINBERG J. The link-prediction problem for social networks[J]. Journal of the American Society for Information Science and Technology, 2007,58(7):1019-1031.

[5] CLAUSET A, MOORE C, NEWMAN M E J. Hierarchical structure and the prediction of missing links in networks[J]. Nature, 2008,453(7191):98-101.

[6] YU H, BRAUN P, YILDIRIM M A, et al. High-quality binary protein interaction map of the yeast interactome network[J]. Science, 2008,322(5898):104-110.

[7] GALLAGHER B, TONG H, ELIASSI-RAD T, et al. Using ghost edges for classification in sparsely labeled networks[C]∥Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.[S.l.]:ACM, 2008:256-264.

[8] 徐恪,张赛,陈昊,等.在线社会网络的测量与分析[J].计算机学报,2014,37(1):164-188.

[9] 王刚,桂小林.社会网络中交易节点的选取及其信任关系计算方法[J].计算机学报,2013,36(2):368-383.

[10] 张昱,张恩德,李封,等.基于时间信息的社会网络链接预测研究[J].计算机与数字工程,2012,40(11):50-51.

[11] NEWMAN M E J. Clustering and preferential attachment in growing networks[J]. Physical Review E, 2001,64(2):25102-25109.

SHE Hongjun:Doctorial Candidate; School of Mathematics, Dongbei University of Finance and Economics, Dalian 116025, China.

[编辑：王志全]

Link Prediction Based on Signed Network

SHEHongjun,HUMengyuan

The social network contains positive and negative edge relations. Based on the common neighbor index method in the recognition of social network signed edge, a kind of signed network link prediction method (ICN-Predict) was proposed. This method combines the signed density property of the node and the network topology characteristic effectively in order to avoid the problem of selecting sensitivity values in common neighbor method. From the experimental results, ICN-Predict method expands the application of the signed network prediction and improves the prediction accuracy. Meanwhile, it shows that the key point of high accuracy is the predictive ability of negative edge sign.

signed network; common neighbor; link prediction

2015-02-21.

佘宏俊(1985-)，男，湖北武汉人，东北财经大学数学与数量经济学院博士研究生.

国家自然科学基金资助项目(71171035).

2095-3852(2015)05-0602-05

A

TP393

10.3963/j.issn.2095-3852.2015.05.017