面向动态性分析的社会网络链路预测方法研究

作     者：纪鹏佳 

作者单位：国防科学技术大学 

学位级别：硕士

导师姓名：唐九阳

授予年度：2013年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：社会网络 链路预测 移动社会网络 科学家合作网络 子图演化 

摘      要：网络中的链路预测作为数据挖掘领域的研究方向之一获得了研究者的广泛关注,它通过已知的网络节点、网络结构等信息,预测网络中由于信息丢失而未被探测的链路以及节点之间未来的链路,以达到挖掘网络中隐藏关系、分析网络结构演化等目的。现有的链路预测方法主要是利用当前网络的结构信息来对下一时刻的节点链路作预测,而由于社会网络具有较强的动态性,如内部个体不断相互作用,个体之间的关系和属性不断改变等,现有依靠网络结构静态信息的链路预测方法都无法体现社会网络的动态性。本文面向社会网络的动态性,分析总结了移动社会网络(Mobile Social Network)以及科学家合作网络(Scientific Collaboration Network)这两种典型社会网络的主要特征,综合考虑网络节点的历史连接信息、网络时间以及网络结构等因素,通过引入基于局部信息的相似性指标和子图演化理论,相应提出了移动社会网络中基于行为分析(Human Behavioral Rhythms Analysis,HBRA)的链路预测方法以及科学家合作网络中基于子图演化(Sub-graph Evolution,SE)的链路预测方法,寻求预测精度和效率之间的平衡,为高可靠的链路预测应用奠定基础。移动社会网络中节点间下一时刻是否存在连接主要是节点对之间互相影响的结果,而这种相互影响往往与它们在前一段时间内的行为规律紧密相关。基于将网络历史结构信息与现有结构信息相结合的思想,本文根据移动社会网络中特有节点行为的移动性和时间相关性,建立了移动社会网络链路预测模型,通过定义节点间的最短路径,提取网络拓扑结构;在此基础上引入节点间的连接引力值指标,将移动社会网络链路预测问题转化为动态网络中连接引力值的计算问题,通过将两个节点从初始时刻到当前时刻不同时间段内的所有链接贡献的引力值求和来度量链接的可能性。然后利用实际数据进行了实验分析,实验结果表明,本文提出的HBRA链路预测方法大大提高了链路预测的精度,而且在不降低精度的情况下提高了命中率。科学家之间的合作往往以二人以上的多人团队合作的形式出现,此外,两个科学家间的合作关系容易受到别的科学家的影响,因此对科学家合作网络进行链路预测必须考虑网络结构对节点关系演化的影响。由于三个科学家组成的一个三角形关系是体现这种影响关系最简单的形式,而且在网络中三个节点组成的平凡子图对网络结构变化十分敏感,基于上述原理,本文提出一种基于子图演化的链路预测方法。首先通过科学家合作的行为分析过滤部分不相关节点,得到聚类系数较高的局部网络,然后通过计算子图的状态转移概率矩阵来判断目标节点对间链接的可能性。由于在划分子图时减少了不必要的计算,基于子图演化的科学家合作网络链路预测方法在确保预测精度的同时提高了效率。相应实验表明,SE链路预测方法还能够有效克服预测精度随网络动态变化波动的问题,提高了预测算法的鲁棒性。