《计算机应用研究》|Application Research of Computers

基于群体智能的自组织重叠社团结构分析算法

Self-organizing overlapping community structure analysis algorithm based on swarm intelligence

免费全文下载 (已被下载 次)  
获取PDF全文
作者 孙韩林,马素刚,王忠民
机构 西安邮电大学 a.计算机学院;b.陕西省网络数据智能处理重点实验室,西安 710121
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2019)05-018-1363-08
DOI 10.19734/j.issn.1001-3695.2017.11.0733
摘要 社团结构分析是复杂网络研究的一项重要内容,基于群体智能思想提出了一种自组织的重叠社团结构分析算法SO2CSA2。把网络视为一个群体,网络节点是其中的一个个具有简单智能的个体,每个个体依据定义的社团连接分数自主决定要加入的社团(可同时加入多个社团)。在网络中寻找一组K-派系作为初始社团结构,所有个体迭代地选择其社团归属,最终整个网络的社团结构将逐渐生长出来。最后对获得的社团结构进行后处理,即调整少量节点的社团归属,以提高其质量。在一组合成网络和现实世界网络上的实验表明,SO2CSA2发现的社团结构的质量比两种对比算法(SLPA和OSLOM)更好,尤其是在网络中重叠节点较多或节点重叠度较大的情况下,社团结构质量的提升更为明显。
关键词 重叠社团结构; 社团检测; 社团结构分析; 复杂网络; 群体智能
基金项目 陕西省科技统筹创新工程计划资助项目(2016KTZDGY04-01)
陕西省自然科学基础研究计划资助项目(2016JM6048)
陕西省自然科学与技术研究计划资助项目(2016GY-092)
陕西省教育厅专项科学研究项目(16JK1687)
本文URL http://www.arocmag.com/article/01-2019-05-018.html
英文标题 Self-organizing overlapping community structure analysis algorithm based on swarm intelligence
作者英文名 Sun Hanlin, Ma Sugang, Wang Zhongmin
机构英文名 a.School of Computer Science & Technology,b.Shaanxi Key Laboratory of Network Data Intelligent Processing,Xi'an University of Posts & Telecommunications,Xi'an 710121,China
英文摘要 Community structure analysis is a critical task in examining a complex network. This paper presented a self-organizing overlapping community structure analysis algorithm(SO2CSA2) based on the swarm intelligence theory. The basic idea behind the algorithm was that it treats an analyzed network as a swarm intelligence system, of which each node was an individual with simple intelligence. Each individual independently decides to which community it joined based on a defined metric named connection score. An individual could join to multiple communities simultaneously. At first, the algorithm found a set of K-cliques from the analyzed network as the initial community structure. Then, each individual in the system acted iteratively to join into or leave from communities, and an optimal community structure of the whole network could develop and eventually emerge from the initial community structure. Finally, to improve the quality of the obtained community structure, a post process adjusted community assignments of a small number of individuals. Experimental evaluation on a number of synthesized networks and real-world networks indicates that the quality of community structures discovered by SO2CSA2 is better than those of two compared algorithms, SLPA and OSLOM, especially on networks with a large number of overlapping nodes or on networks with overlapping nodes of which overlapping degrees are high.
英文关键词 overlapping community structure; community detection; community structure analysis; complex network; swarm intelligence
参考文献 查看稿件参考文献
 
收稿日期 2017/11/1
修回日期 2017/12/28
页码 1363-1370
中图分类号 TP301.6
文献标志码 A