基于多标签传播的重叠社区发现优化算法*

2018-04-13 07:26:57杜长江王志晓邢贞明
数据采集与处理 2018年2期
关键词:实验

杜长江 王志晓 邢贞明

(中国矿业大学计算机科学与技术学院,徐州,221116)

引  言

随着社交网络的兴起,社会网络引起了研究人员的重视。社区结构不仅反映了网络的拓扑结构,同时也被认为是能体现真实社会网络功能的一个重要属性[1-2],因此社区发现算法的研究有很重要的理论价值和现实意义[1,3-4]。比如针对互联网用户进行社区划分,可根据用户所在社区提供特定服务,有很大的商业价值。

近年来,研究人员提出了很多富有成效的社区发现算法。经典的基于图划分的KL (Kernighan-Lin)算法[5]和谱平分算法[6],前者基于贪婪原理[5,7],后者则利用拉普拉斯矩阵[6,8]的特征向量,都可将网络划分成两个社区。但是这两种方法有很大的局限性,适用于社区数目已知的网络。基于层次聚类的GN(Girvan-Newman)算法[9],Newman和Girvanc采用分裂思想,构造出分层树,可将网络划分为多个社区,一定程度上克服了KL算法[5]和谱平分算法[6]的缺陷,但是该算法复杂度较高[10],而且社区数量不确定,依赖于在分层树上选取的划分位置[1]。2014年,Jiang等人[7]提出了基于优化的贪心算法的社区发现算法(Algorithm based on greedy surprise optimization, AGSO)及其改进版本FAGSO(Fast-AGSO)算法,该算法在实验中展现出了比社区发现的几种重要算法更好的效果,包括BGLL(Blondel-Guillaume-Lambiotte-Lefebvre)[11]、CNM (Clauset-Newman-Moore)[12]、OSLOM(Order statistics local optimization method)[13]等。不同于传统的算法,Raghavan等人[14]首次将标签传播思想引入到社区发现领域,提出标签传播算法(Label propagation algorithm,LPA),综合考虑了网络结构和网络本身的传播特性,且具有较高的效率,适用于大规模网络的社区发现[15]。

然而上述算法均是针对非重叠社区,即网络中的一个节点只能属于一个社区[1]。……

登录APP查看全文

猜你喜欢
实验
记住“三个字”,写好小实验
记一次有趣的实验
有趣的实验
小主人报(2022年4期)2022-08-09 08:52:06
做个怪怪长实验
NO与NO2相互转化实验的改进
实践十号上的19项实验
太空探索(2016年5期)2016-07-12 15:17:55
《实验流体力学》征稿简则
我实验,我快乐
学与玩(2004年7期)2004-04-29 00:00:00