计算机工程与应用 ›› 2017, Vol. 53 ›› Issue (15): 164-169.DOI: 10.3778/j.issn.1002-8331.1611-0487

• 模式识别与人工智能 • 上一篇    下一篇

一种基于中心极大团扩展的社区挖掘算法

赵卫绩1,2,张凤斌2,刘井莲1,金  昊1   

  1. 1.绥化学院 信息工程学院,黑龙江 绥化 152061
    2.哈尔滨理工大学 计算机科学与技术学院,哈尔滨 150080
  • 出版日期:2017-08-01 发布日期:2017-08-14

Community mining algorithm based on central maximal-clique expansion

ZHAO Weiji1,2, ZHANG Fengbin2, LIU Jinglian1, JIN Hao1   

  1. 1.School of Information Engineering, Suihua University, Suihua, Heilongjiang 152061, China
    2.School of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China
  • Online:2017-08-01 Published:2017-08-14

摘要:

社区挖掘是复杂网络分析中的一项重要工作,目前已提出多种社区挖掘算法,但多数算法是通过节点间的连接关系来发现内聚的社区结构。结合真实网络中的节点具有不同的行为和影响力,在充分考虑网络中节点的连接关系的基础上,提出一种基于中心极大团扩展的社区挖掘两阶段算法。第一阶段发现初始社区:首先找到网络中所有的内聚子团,然后找出[k]个分散、内聚且有影响力的中心极大团作为初始社区;第二阶段形成最终社区划分:对初始社区外节点,充分考虑不同邻居节点对其潜在的影响力,采用局部模块度扩展的方法将节点扩展到与其连接紧密的社区内。实验结果表明,该方法能够快速揭示出网络中的社区结构,相比FN算法,具有较高的准确度和模块度,相比GN算法,不需要预先知道社区个数。

关键词: 社区结构, 中心极大团, 局部模块度

Abstract:

Community mining is an important work in complex network analysis, and many algorithms have been proposed. However, most of them are based on the links to find the cohesive community structure. Taking the nodes that have different behaviors and influences in real-world networks into consideration, together with links between nodes, a two?stage community mining algorithm based on central maximal-clique expansion is proposed. In the first stage, initial communities are found: Firstly, all the cohesive cliques are found out in the network, and then [k] separate cohesive and influential central maximal-cliques are chosen to form initial communities. In the second stage, the final community division is detected: For the nodes outside the initial communities, taking potential impacts of neighbor nodes into consideration, the neighbor nodes are expanded to the corresponding connected closely community by adopting the local modularity. Experimental results show that the method can quickly reveal cohesive community structure in network, compared with the FN algorithm it has a relatively higher accuracy and modularity, compared with the GN algorithm, it do not need to know the prior number of communities.

Key words: community structure, central maximal-clique, local modularity