论文部分内容阅读
近年来,复杂网络的研究已成为各个领域的热点课题,对计算机科学、经济学和社会学等众多领域的发展都产生了深远的影响。检测社团结构是复杂网络研究中一项基础而又重要的工作,在分析网络拓扑结构、挖掘网络潜在功能以及预测网络行为中扮演了重要的角色。由于网络中的节点通常属于多个社团,导致社团之间相互重叠,因此现实世界的真实网络往往存在重叠的社团结构,研究重叠社团结构可以更全面地认识和分析真实网络。基于此,本文对复杂网络的重叠社团检测问题进行了研究,提出了一种基于单步添加团的重叠社团检测算法,同时在此研究基础上对在线社交网络朋友推荐算法进行了研究,提出了一种基于单步添加团的社交网络推荐算法。本文的主要研究工作如下:(1)本文提出了一种基于单步添加团的重叠社团检测算法。局部社团扩充是当前检测复杂网络重叠社团结构的主流解决方法之一,其主要思想是从单个节点出发,通过不断添加一个新的节点来获得最终的社团划分。现有的采用基于单个节点逐步加入社团的扩充算法没有充分考虑到新添加节点的局部信息,从而在一定程度上影响了社团检测的准确性。团作为网络中的一个完全连通子图,该子图中所有节点两两之间相互连接,由于这种强连接关系,在社团检测中,团中的节点属于同一社团的可能性更大。基于此,在局部社团扩充的基础上,本文提出基于单步添加团的重叠社团检测算法,该算法在局部扩充社团时采用单步添加团的策略,在扩充过程中,若判断出某节点应加入到当前社团,则把该节点所在的团加入到当前社团中。在计算机生成网络和真实网络数据集上的实验结果表明,与现有重叠社团检测算法相比,基于单步添加团的重叠社团检测算法可以更准确地检测出网络中的重叠社团结构,特别是在网络社团结构不明显时本算法仍然可以取得较高的精度值。同时,相比较于多数传统重叠社团检测算法,本文算法也具有较低的时间复杂度。(2)本文提出了一种基于单步添加团的社交网络推荐算法。朋友推荐作为一种经典的信息推荐问题,对其研究可以帮助在线社交网络里的用户整理并分类他们的朋友圈,给他们推荐潜在感兴趣的信息资源。在朋友推荐算法中,能否实现对朋友进行比较准确的自动分组决定了推荐算法的性能。基于单步添加团的重叠社团检测算法,本文提出了一种新的社交网络朋友推荐算法。该算法将朋友分组和朋友推荐结合起来,首先利用单步添加团的重叠社团算法对社交网络进行社团结构检测,从而实现社交网络中的用户自动分组,然后根据得到的朋友分组结果,利用相似度函数为用户搜索最佳的朋友,给用户提供既高效又准确的朋友推荐。在现实世界社交网络上的实验结果表明,与其他常用的推荐算法相比,本文提出的基于单步添加团的社交网络推荐算法不仅可以准确地对社交网络进行分组,同时可以给用户推荐最佳的需求信息,实现更有效的朋友推荐。