论文部分内容阅读
在现实生活中存在着各式各样的社会网络,如路由自治网络,科学家合作网,Twitter用户关系网等。对于社会网络的研究早在1969年之前就已经开始,研究发现社会网络具有小世界性质,度的幂分布性,社区结构等内在特性。由于社会网络巨大的实用价值,这一领域吸引了生物学家,社会学家,计算机科学工作者等的深入研究。社区结构因其巨大的实用价值如恐怖分子追踪,个性化推荐,舆论控制等,成为了研究者关注的重点。随着研究者的不断探索与创新,一系列社区划分方法被提出,在社区结构方面取得了一定的成就。然而,随着科学与技术的发展,社会网络的规模迅速扩大,如一些社交类社会网络其用户数大多都是数以亿计的,这使得目前的大多数社区划分算法难以胜任。较高的时间开销是许多算法无法在大规模社会网络上进行社区划分的主要原因,针对这种情况,本文提出基于相似度投票的社区划分算法Community Division Algorithm Base on Similarity Voting(CDBSV算法)来满足这一迫切需求。CDBSV算法利用邻居节点间的局部相似度结合投票机制快速完成社区的初步划分,使得大规模社会网络的规模得以快速缩减,然后在较小规模的社会网络上利用模块度增量准则迭代地进行社区划分,直到获得具有最大模块度的社区划分。因为CDBSV算法使用计算简单的局部相似度并结合投票的机制,所以算法第一阶段在保证模块度的同时能够实现网络的快速缩减。在减小网络规模后,就可以使用准确度较高,但计算略显复杂的模块度增量准则来进行进一步的划分以获得最大的模块度,从而完成大规模社会网络的社区划分。在探究社会网络的社区结构的过程中,研究者注意到随着时间的缓慢推移,社会网络是在不断变化的。节点间的关系不是一成不变的,社会网络会有节点的新增和消失。虽然,社会网络在缓慢变化,但是其社区结构往往在较短时间内却是稳定不变的,或者变动不大。因此,通过详细研究社区结构与节点的关系,以及节点变动对社区结构的影响,本文提出了一种增量式的动态划分算法来完成社会网络的快速划分。基于信息传递的动态划分算法Dynamic Partitioning Algorithm Base on Information Transmission(DPBIT算法)利用网络增量对社区划分进行修正来完成新社区的划分。通过分析节点变动对邻接社区模块度的影响,来确定其邻居节点可能被划分到的社区,从而将节点变动的信息传递给其邻居节点,而不是直接测试邻居节点所有可能的社区,以此加速算法。最后,在真实的社会网络上验证了CDBSV算法与DPBIT算法的有效性,实验结果表明CDBSV算法适用于大规模的社会网络的社区划分任务,算法准确率较高,且时间效率要高于现有算法;而DPBIT算法相对其他动态算法可以更为高效地完成动态社会网络的社区划分且模块度较高,在时间效率上也远胜于传统静态社区划分算法。