论文部分内容阅读
社区由网络中联系密切的节点组成,其作为复杂网络重要特征之一,引起了国内外大量学者的关注,同时,社区还被应用于搜索引擎、广告推荐、蛋白质功能预测等不同方面,具有重大的理论研究意义和应用价值。社区发现的目的在于挖掘社区(部分)与整个网络(整体)的联系,对网络未知功能进行预测,发现其隐藏的规律,并把握网络未来的演化倾向。目前,社区发现算法众多,其中标签传播算法因其速度快、效率高被广泛应用于社区发现领域。标签传播算法在标签初始化阶段,一视同仁对待所有节点,忽略了节点的差异性的问题,在传播更新阶段,当邻居节点标签个数相同时,随机选择一个。由于算法在这两个阶段中未考虑节点特性以及采用随机选择策略,造成了相关标签传播的社区发现算法稳定性差、准确度低。基于此,本文利用节点在网络中的重要性不同区分对待节点,确定初始化序列,减小算法的随机性,分别提出了两种不同的改进算法,本文的主要工作如下:(1)对社区发现算法进行了归类总结,列出了每一类中代表性的算法,并对标签传播算法进行了详细的介绍。(2)提出了基于社区中心点的标签传播社区发现算法(CN_LPA算法)。首先,从局部角度出发,利用节点度与聚集系数局部中心性给出了社区中心节点的概念,将社区中心点作为初始节点分配唯一标签,并给予邻居节点与其相同的标签。接着,进行标签的异步更新,重复迭代,直到算法结束。实验结果显示该算法大大降低了社区划分结果的随机性和不稳定性。(3)提出了综合节点中心性和相互作用的标签传播社区发现算法(NCEW_LPA算法)。鉴于CN_LPA算法只考虑了节点的局部信息,忽略了节点之间的影响,后续结合网络节点中心性和相互作用给出了NCEW_LPA算法。算法首先基于优化的LeaderRank方法计算全部节点的中心性大小,根据节点与邻居节点相互作用不同,用相似度度量方法得到节点间的相互作用力大小。接着,融合中心性和相互作用计算出所有节点的重要性大小,根据均值和互不相邻策略确定前k个重要度最大的序列K,在标签传播更新时以这些节点为中心,以重要度大小为传播方向,进行一层一层展开传播,直到算法结束。最后,实验对比分析显示该算法能有效找出重要节点并进行社区划分。