A Markov chain-based overlapping community detection algorithm for complex networks

被引：3

作者：

Xing R. ^{[1
]}

Fan Y. ^{[1
]}

Liu W. ^{[2
]}

机构：

[1] School of Intelligent Science and Information Engineering, Xi'an Peihua University, Xi'an

[2] Xi 'an Aerospace General Hospital, Xi'an

来源：

Ingenierie des Systemes d'Information | 2019年 / 24卷 / 06期

关键词：

Complex networks; Markov chain; Overlapping community detection; Random walk;

D O I：

10.18280/isi.240603

中图分类号：

学科分类号：

摘要：

Most community detection algorithms for complex networks are focused on nonoverlapping communities. However, there are many overlapping communities in real-world complex networks. To solve the contradiction, this paper develops a novel overlapping community detection algorithm based on Markov chain. First, the input adjacency matrix was expanded to guide the information flow. Then, the inflation operation was implemented to enhance the weakening boundary of communities. After that, an adaptive threshold was introduced to reconstruct the matrix. The network corresponding to the reconstructed matrix displays the overlapping communities in the original network. The proposed algorithm was compared with several popular community detection algorithms on artificial and real-world networks. The results show that our algorithm achieved higher recognition accuracy and faster convergence than the contrastive algorithms. © 2019 International Information and Engineering Technology Association. All rights reserved.

引用

页码：577 / 582

页数：5

共 27 条

[1]

Rozum J.C., Albert R., Identifying (un)controllable dynamical behavior in complex networks, Plos Computational Biology, 14, 12, (2018)

[2]

Gupta P., Jindal R., Sharma A., Community trolling: An active learning approach for topic based community detection in big data, Journal of Grid Computing, 16, 4, pp. 553-567, (2018)

[3]

Nascimento M.C.V., Pitsoulis L., Community detection by modularity maximization using GRASP with path relinking, Computers & Operations Research, 40, 12, pp. 3121-3131, (2013)

[4]

Shi C., Cai Y., Fu D., Dong Y.X., Wu B., A link clustering based overlapping community detection algorithm, Data & Knowledge Engineering, 87, pp. 394-404, (2013)

[5]

Borkar V., Meyn S.P., Oja’s algorithm for graph clustering, Markov spectral decomposition, and risk sensitive control, Automatica, 48, 10, pp. 2512-2519, (2012)

[6]

Chen D.B., Feng Z., Lu R.Q., Lei Y., Li Z., Wang J.T., Multi-objective optimization of community detection using discrete teaching–learning-based optimization with decomposition, Information Sciences, 369, 3, pp. 402-418, (2016)

[7]

Newman M.E.J., Girvan M., Finding and evaluating community structure in networks, Physical Review E, 69, 2, (2004)

[8]

Newman M.E.J., Fast algorithm for detecting community structure in networks, Physical Review E, 69, 6, (2004)

[9]

Ashrafi Payaman N., Kangavari M., GSSC: Graph summarization based on both structure and concepts, International Journal of Information and Communication Technology Research, 9, 1, pp. 33-44, (2017)

[10]

Jarukasemratana S., Murata T., Liu X., Community detection algorithm based on centrality and node closeness in scale-free networks, Transactions of the Japanese Society for Artificial Intelligence, 29, 2, pp. 234-244, (2014)

← 1 2 3 →