基于节点重要性与相似性的重叠社区发现算法
2018-09-11孟凡荣
计算机工程 2018年9期
付 饶,孟凡荣,邢 艳
(中国矿业大学 计算机科学与技术学院,江苏 徐州 221116)
0 概述
现实生活中诸如万维网、社交网络和蛋白质相互作用网络等都能够抽象成复杂网络,其中,节点表示客观实体,边代表节点间的联系[1]。在社交网络中,人们因兴趣爱好相投或者志同道合而形成密集交流的圈子;在蛋白质相互作用网络中,若干蛋白质会频繁交互协作完成某项功能。这些交互频繁的节点就是复杂网络中广泛存在的一种结构,它由内部联系紧密而外部联系稀疏的若干节点构成,被称为社区[2]。而社区发现就是探索复杂网络中存在的社区结构,在社交网络舆情传播分析、蛋白质的相互作用研究[3]和商业广告精准投放[4]等方面得到实际应用,因而得到广泛关注和深入研究。
Newman快速算法[5]基于凝聚的思想,不断合并模块度增益最大的节点,而用以衡量社区划分质量的模块度极大地促进了社区发现的发展。随后基于模块度优化的算法被相继提出,如Louvain算法[6]和LPAMP算法[7]。CPM算法[8]通过寻找网络中的极大完全子图来发现重叠社区,但处理较大规模网络时难以在有限时间内得到结果且无法判定极大完全子图外的节点。文献[9]结合FCM算法[10]和谱聚类进行重叠社区发现,但其对初始值敏感,对邻接矩阵进行特征提取,忽略了不直接相连节点间存在的相似关系。LFM算法[11]的主要思想是随机选择种子节点,不断吸纳适应度增益最大的节点来构建局部社区,尽管LFM算法能够发现重叠社区和社区间的层次关系,但存在结果不稳定、社区漂移等问题。……
登录APP查看全文
