论文部分内容阅读
现实世界中存在着大量的复杂网络,例如朋友网络、社会网络、技术网络、生物学网络、网络中页面之间相互链接而形成的网络、论文合著网络、文献引用网络等等。许多研究表明,复杂网络除了拥有无标度和小世界特性,还具有社区结构特性。近年来,复杂网络中社区结构发现在学术界得到了深入的研究和探索,社区结构发现算法的设计已成为复杂网络研究的热点。在现实生活中,社区间是有可能重叠的,如,在科研合作网络中,一个学者可能同时在多个领域与人合作;在社会网络中,一个兴趣广泛的人可能参与多个不同的社区活动,这样,就可能有某些节点同时属于多个社区,为多个社区所共享。揭示复杂网络中的重叠社区结构可以帮助我们更好的理解网络的拓扑结构,对重叠部分的研究有助于我们开启新的思路去解决网络拥塞、舆论的传播、计算机病毒和流行病毒传播等问题。 针对现有社区发现算法大多假定社区是不重叠的问题,本文将模糊合作博弈应用于重叠社区发现,设计了基于模糊合作博弈的重叠社区发现算法,通过隶属函数来确定节点属于社区的程度,通过收益函数来确定节点加入社区后社区的收益,隶属函数和收益函数共同决定节点是否加入社区。本文的主要工作包括: (1)根据重叠社区发现中重叠节点所代表的实际意义,本文将模糊合作博弈应用于重叠社区的发现,给出了算法的思路,并且对隶属函数和收益函数的计算给出了详细的过程,网络中的节点以一定的隶属度属于社区,同时节点加入社区后社区会获得相应的收益,通过隶属度和收益共同决定节点加入相应的社区。 (2)设计了一种改进的基于模糊合作博弈的重叠社区发现算法,该算法以非重叠社区发现算法的社区划分结果作为初始的社区,也就是社区结构是已知的,通过计算社区的邻接点的隶属度以及邻接点加入到社区后社区的收益,确定社区的重叠点,该算法的效率依赖于初始算法的选取,本文选取BGLL算法作为初始的算法,该算法是目前比较优秀的非重叠社区发现算法。该方法很大程度上提高了发现重叠社区的效率。 (3)对本文中所提出的两种算法在三种真实数据集上进行仿真实验,并对其进行性能评价与算法分析。通过实验结果表明,本文算法(1)在准确率上比较好,本文的算法(2)在时间效率和准确率效果均比较好。因此本文算法的研究结果具有一定的现实意义。