论文部分内容阅读
摘 要：链路预测是社交网络中一项具有挑战性的任务，移动社交网络中的链路预测是指通过已知的网络节点以及社会网络结构等信息预测移动社交网络中尚未产生连边的两个节点之间产生链接的可能性。本文主要比较了4种常用的链路预测方法。最终，我们使用米兰大学数据集进行仿真实验，结果显示基于共同邻居的相似性指标能够使移动社交网络中链路预测有更好的效果。
关键词：移动社交网络；链路预测；相似性；共同邻居
中图分类号：TP393.09
由于人们使用的各种个人无线设备的（如手机，GPS设备）迅速和广泛普及，导致移动社交网络（MSNs）变得越来越有重要。可以把MSNs看作图，其中节点对应于一个人或实体，边对应与人们之间的某种关联。在移动社交网络中，联系和实体往往随着时间出现，这就导致了高度的动态性和复杂的系统。此外，圈内好友也经常改变，当人们通过社会联系建立友谊，或当它们在一种社会关系的兴趣结束，链接会被移除[1]。对于移动社交网络，我们本文中研究讨论的是预测未来两个节点之间相关联的可能性。Liben-Nowel[2]提出了链路预测问题：在t时刻记录社交网络，我们精确预测在t到给定的未来时间t’时间间隔内添加到网络中的边。
在本文中，我们主要关注网络的局部信息，并利用相似性指数来表征未来互动的可能性。本文的其余部分安排如下。第2节介绍一些相关工作。第3节提出了移动社交网络预测的方法。结果和实验都在第4节讨论，第5节总结全文。
1 相关工作
链路预测的现有方法可以分为三类。第一种基于机器学习的方法[3]。Hasan等人[4]指出监督式学习和预测，在社交网络中的两个潜在连接的节点是否是一个正的或负的示例。他们尝试了七个不同的分类算法，并使用不同的性能度量比较这些分类的性能。然而，他们的工作并没有赶上复杂网络研究目前的进展，特别是他们缺乏认真考虑网络的结构特点。
第二种方法基于最大似然估计。Clauset，Moore和Newman[5]提出了一种方法，从网络数据的分层结构推断，并进一步将其应用到在部分已知的网络中去预测丢失的链接，如草地物种食物网和恐怖分子关联网络。然而，该算法的一个很大的缺点是运行速度非常慢。另一个值得注意的要点是，这种模式可能会对这些没有明确的层次结构的网络有较差的预测结果。
第三类基于节点邻居的测量方法。拥有更多的共同邻居数的节点未来连边的可能性越大。Liben-Nowell and Kleinberg[2]将一些基于结构的节点相似性指标与随机预测方法在五种合著网络中进行比较，发现的确有包含在单独的网络拓扑结构中的有用信息。这种方法对待所有的共同邻居结果都一样，它没有区分不同邻居的预测出不同的效果。
在本文中，我们将主要介绍最后一个方法。节点的相似性可以通过使用节点的本质属性来定义，即当两个节点具有更多共同的特征时，两个节点更相似。
2 移动社交网络预测方法
我们将4个经典的基于局部信息的相似性指标进行比较：共同邻居CN（common neighbors），Jaccard指数（JC），Adamic–Adar指数（AA）和Leicht–Holme–Newman指数（LHN-I）。下面对每个方法进行说明：
CN方法[6]就是说两个节点如果有更多的共同邻居，则它们更倾向于连边。确切地讲，该方法被定义为：
其中，Γ（x）为网络中节点x的邻居节点集合，x的邻居节点定义为与节点x直接相连的节点。节点x与节点y的相似度就是它们共同拥有邻居节点的个数。
JC方法[7]确保那些共享较高比例的共同邻居数的节点对享有较高的预测值。 （2）
AA指标思想是度小的共同邻居节点的贡献大于度大的共同邻居节点[8]，因此根据共同邻居节点的度为每个节点赋予一个权重值，该权重等于该节点的度的对数分之一，即1/lgk。其定义如下：
LHN-I指标给部分节点分配较高的相似性，这些节点有很多共同邻居数不是因为潜在最大值的存在而是这些邻居预期的数量[9]。分母被定义为kx×ky，正比于节点x和y的共同邻居的预期数目[10]。
3 实验结果与分析
本文采用的衡量链路预测算法精度的指标是AUC[11]，AUC从整体上衡量算法的精度。定义为： 。
每次随机从测试集中选取一条边与随机选择的不存在的边进行比较，如果测试集中的边的分数值大于不存在边的分数值，就加1分；如果两个分数值相等，就加0.5分。n表示独立比较的次数。n表示测试集中的分数值大于不存在边的分数值的次数，表示两分数值相等的次数。
我们使用的数据集是由米兰大学（UniMi）掌上移动跟踪记录设备收集的。该数据集包含米兰大学44个移动设备的移动轨迹。该数据收集的是2008年11月的19天。
本文实验采取对比的方式进行，将所取得的数据集分别用上述4种方法进行实现并得到不同的结果。仿真工具是MATLAB。我们使用真正的跟踪数据，确保了预测方法的准确性。米兰大学（UniMi）数据集是一个很小的移动社交网络，它的节点之间进行频繁的互动。因此，如示于图1中，我们可以看到，链路数目随着时间的推移，显示出周期性的变化。因此，我们选择400000s到800000s的数据进行实验。
我们的研究结果是基于100次的独立实验。可以看出，CN指标比其他指标测量结果更好。从表4中可以看出，基于共同邻居的方法（CN）的AUC值要高于要优于其他算法。结果表明，CN预测效果和预测精度要更好，能更好地预测节点之间下一时刻的连边。
4 结束语
本文对移动社交网络的一些特点进行了研究，对多种链路预测的方法进行研究分析，而且通过AUC指标将4种预测方法进行了对比分析。证明采用共同邻居的算法能在移动社交网络中取得更好的链路预测效果。本文主要考虑了共同和邻居对预测结果的影响，下一步的研究中可以通过加入时间相关的局部结构变化.建立概率模型等方法来进行更好的链路预测。 参考文献：
[1]Schall D.Link prediction in directed social networks[J].Social Network Analysis and Mining，2014（01）：1-14.
[2]Liben-Nowell D，Kleinberg J.The link-prediction problem for social networks[J].Journal of the American Society for Information Science and Technology，2007（58）：1019-1031.
[3]Wang C.，Satuluri V.and Parthasarathy S.，Local Probabilistic Models for Link Prediction，in Proceedings of the 2007 seventh IEEE International Conference on Data Mining（IEEE Press，Washington DC），2007：322-331.
[4]M.A.Hasan，V.Chaoji，S.Salem，M.Zaki，Link Prediction Using Supervised Learning，in Proc.of SDM 06 workshop on Link Analysis[J].Counterterrorism and Security，2006.
[5]A.Clauset，C.Moore，M.E.J.Newman，Hierarchical structure and the prediction of missing links in networks[J].Nature，2008（98）.
[6]Newman，M.E.J.Clustering and preferential attachment in growing networks[J].Physical Review E，2001（64）.
[7]JACCARD P.Etude comparative de la distribution florale dans une portion des Alpes et des Jura[J].Bulletin de la Société Vaudoise des Science Naturelles，1901（37）：547-579.
[8]Adamic，L.A.，&Adar，E.Friends and neighbors on the web[J].Social Networks，2003（25）：211-230.
[9]E.A.Leicht，P.Holme，M.E.J.Newman，Vertex similarity in networks[J].Phys.Rev.E，2006.
[10]M.Molloy，B.Reed，A critical point for random graphs with a given degree sequence，Random Structures Algorithms，1995（06）：161.
[11]HANELY J A，MCNEIL B J.The meaning and use of the area under a receiver operating characteristic（ROC） curve[J].Radiology，1982（143）：29-36.
作者简介：郑巍（1982.09-），男，江西萍乡人，讲师，博士，研究方向：无线传感器网络、网络优化、最优化算法。
作者单位：南昌航空大学 软件学院，南昌 330063
基金项目：江西省青年科学基金（项目编号：20142BAB217017）：基于节点运动特征的机会传感网络局部拓扑预测。
关键词：移动社交网络；链路预测；相似性；共同邻居
中图分类号：TP393.09
由于人们使用的各种个人无线设备的（如手机，GPS设备）迅速和广泛普及，导致移动社交网络（MSNs）变得越来越有重要。可以把MSNs看作图，其中节点对应于一个人或实体，边对应与人们之间的某种关联。在移动社交网络中，联系和实体往往随着时间出现，这就导致了高度的动态性和复杂的系统。此外，圈内好友也经常改变，当人们通过社会联系建立友谊，或当它们在一种社会关系的兴趣结束，链接会被移除[1]。对于移动社交网络，我们本文中研究讨论的是预测未来两个节点之间相关联的可能性。Liben-Nowel[2]提出了链路预测问题：在t时刻记录社交网络，我们精确预测在t到给定的未来时间t’时间间隔内添加到网络中的边。
在本文中，我们主要关注网络的局部信息，并利用相似性指数来表征未来互动的可能性。本文的其余部分安排如下。第2节介绍一些相关工作。第3节提出了移动社交网络预测的方法。结果和实验都在第4节讨论，第5节总结全文。
1 相关工作
链路预测的现有方法可以分为三类。第一种基于机器学习的方法[3]。Hasan等人[4]指出监督式学习和预测，在社交网络中的两个潜在连接的节点是否是一个正的或负的示例。他们尝试了七个不同的分类算法，并使用不同的性能度量比较这些分类的性能。然而，他们的工作并没有赶上复杂网络研究目前的进展，特别是他们缺乏认真考虑网络的结构特点。
第二种方法基于最大似然估计。Clauset，Moore和Newman[5]提出了一种方法，从网络数据的分层结构推断，并进一步将其应用到在部分已知的网络中去预测丢失的链接，如草地物种食物网和恐怖分子关联网络。然而，该算法的一个很大的缺点是运行速度非常慢。另一个值得注意的要点是，这种模式可能会对这些没有明确的层次结构的网络有较差的预测结果。
第三类基于节点邻居的测量方法。拥有更多的共同邻居数的节点未来连边的可能性越大。Liben-Nowell and Kleinberg[2]将一些基于结构的节点相似性指标与随机预测方法在五种合著网络中进行比较，发现的确有包含在单独的网络拓扑结构中的有用信息。这种方法对待所有的共同邻居结果都一样，它没有区分不同邻居的预测出不同的效果。
在本文中，我们将主要介绍最后一个方法。节点的相似性可以通过使用节点的本质属性来定义，即当两个节点具有更多共同的特征时，两个节点更相似。
2 移动社交网络预测方法
我们将4个经典的基于局部信息的相似性指标进行比较：共同邻居CN（common neighbors），Jaccard指数（JC），Adamic–Adar指数（AA）和Leicht–Holme–Newman指数（LHN-I）。下面对每个方法进行说明：
CN方法[6]就是说两个节点如果有更多的共同邻居，则它们更倾向于连边。确切地讲，该方法被定义为：
其中，Γ（x）为网络中节点x的邻居节点集合，x的邻居节点定义为与节点x直接相连的节点。节点x与节点y的相似度就是它们共同拥有邻居节点的个数。
JC方法[7]确保那些共享较高比例的共同邻居数的节点对享有较高的预测值。 （2）
AA指标思想是度小的共同邻居节点的贡献大于度大的共同邻居节点[8]，因此根据共同邻居节点的度为每个节点赋予一个权重值，该权重等于该节点的度的对数分之一，即1/lgk。其定义如下：
LHN-I指标给部分节点分配较高的相似性，这些节点有很多共同邻居数不是因为潜在最大值的存在而是这些邻居预期的数量[9]。分母被定义为kx×ky，正比于节点x和y的共同邻居的预期数目[10]。
3 实验结果与分析
本文采用的衡量链路预测算法精度的指标是AUC[11]，AUC从整体上衡量算法的精度。定义为： 。
每次随机从测试集中选取一条边与随机选择的不存在的边进行比较，如果测试集中的边的分数值大于不存在边的分数值，就加1分；如果两个分数值相等，就加0.5分。n表示独立比较的次数。n表示测试集中的分数值大于不存在边的分数值的次数，表示两分数值相等的次数。
我们使用的数据集是由米兰大学（UniMi）掌上移动跟踪记录设备收集的。该数据集包含米兰大学44个移动设备的移动轨迹。该数据收集的是2008年11月的19天。
本文实验采取对比的方式进行，将所取得的数据集分别用上述4种方法进行实现并得到不同的结果。仿真工具是MATLAB。我们使用真正的跟踪数据，确保了预测方法的准确性。米兰大学（UniMi）数据集是一个很小的移动社交网络，它的节点之间进行频繁的互动。因此，如示于图1中，我们可以看到，链路数目随着时间的推移，显示出周期性的变化。因此，我们选择400000s到800000s的数据进行实验。
我们的研究结果是基于100次的独立实验。可以看出，CN指标比其他指标测量结果更好。从表4中可以看出，基于共同邻居的方法（CN）的AUC值要高于要优于其他算法。结果表明，CN预测效果和预测精度要更好，能更好地预测节点之间下一时刻的连边。
4 结束语
本文对移动社交网络的一些特点进行了研究，对多种链路预测的方法进行研究分析，而且通过AUC指标将4种预测方法进行了对比分析。证明采用共同邻居的算法能在移动社交网络中取得更好的链路预测效果。本文主要考虑了共同和邻居对预测结果的影响，下一步的研究中可以通过加入时间相关的局部结构变化.建立概率模型等方法来进行更好的链路预测。 参考文献：
[1]Schall D.Link prediction in directed social networks[J].Social Network Analysis and Mining，2014（01）：1-14.
[2]Liben-Nowell D，Kleinberg J.The link-prediction problem for social networks[J].Journal of the American Society for Information Science and Technology，2007（58）：1019-1031.
[3]Wang C.，Satuluri V.and Parthasarathy S.，Local Probabilistic Models for Link Prediction，in Proceedings of the 2007 seventh IEEE International Conference on Data Mining（IEEE Press，Washington DC），2007：322-331.
[4]M.A.Hasan，V.Chaoji，S.Salem，M.Zaki，Link Prediction Using Supervised Learning，in Proc.of SDM 06 workshop on Link Analysis[J].Counterterrorism and Security，2006.
[5]A.Clauset，C.Moore，M.E.J.Newman，Hierarchical structure and the prediction of missing links in networks[J].Nature，2008（98）.
[6]Newman，M.E.J.Clustering and preferential attachment in growing networks[J].Physical Review E，2001（64）.
[7]JACCARD P.Etude comparative de la distribution florale dans une portion des Alpes et des Jura[J].Bulletin de la Société Vaudoise des Science Naturelles，1901（37）：547-579.
[8]Adamic，L.A.，&Adar，E.Friends and neighbors on the web[J].Social Networks，2003（25）：211-230.
[9]E.A.Leicht，P.Holme，M.E.J.Newman，Vertex similarity in networks[J].Phys.Rev.E，2006.
[10]M.Molloy，B.Reed，A critical point for random graphs with a given degree sequence，Random Structures Algorithms，1995（06）：161.
[11]HANELY J A，MCNEIL B J.The meaning and use of the area under a receiver operating characteristic（ROC） curve[J].Radiology，1982（143）：29-36.
作者简介：郑巍（1982.09-），男，江西萍乡人，讲师，博士，研究方向：无线传感器网络、网络优化、最优化算法。
作者单位：南昌航空大学 软件学院，南昌 330063
基金项目：江西省青年科学基金（项目编号：20142BAB217017）：基于节点运动特征的机会传感网络局部拓扑预测。