Finding overlapping communities based on Markov chain and link clustering

详细信息    查看全文

• 作者：Xiaoheng Deng ; Genghao Li ; Mianxiong Dong…
• 关键词：Community detection ; Random walk ; Link community ; Overlapping community
• 刊名：Peer-to-Peer Networking and Applications
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：10
• 期：2
• 页码：411-420
• 全文大小：
• 刊物类别：Engineering
• 刊物主题：Communications Engineering, Networks; Information Systems and Communication Service; Computer Communication Networks; Signal,Image and Speech Processing;
• 出版者：Springer US
• ISSN：1936-6450
• 卷排序：10

文摘

Since community structure is an important feature of complex network, the study of community detection has attracted more and more attention in recent years. Despite most researchers focus on identifying disjoint communities, communities in many real networks often overlap. In this paper, we proposed a novel MCLC algorithm to discover overlapping communities, which using random walk on the line graph and attraction intensity. Unlike traditional random walk starting from a node, our random walk starts from a link. First we transform an undirected network graph to a weighted line graph, and then random walks on this line graph can be associated with a Markov chain. By calculating the transition probability of the Markov chain, we obtain the similarity between link pairs. Next the links can be clustered into “link communities” by a linkage method, and these nodes between link communities can be overlapping nodes. When converting the “link communities” into the “node communities”, we make a definition of attraction intensity to control the overlapping size. Finally the detected communities are permitted overlapped. Experiments on synthetic networks and some real world networks validate the effectiveness and efficiency of the proposed algorithm. Comparing overlapping modularity Q_ov with other related algorithms, the results of this algorithm are satisfactory.