An improved label propagation algorithm based on node importance and random walk for community detection
| Autor: | Tianren Ma, Zhengyou Xia |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Computer science
Node (networking) Stability (learning theory) Community structure Statistical and Nonlinear Physics Complex network Condensed Matter Physics Random walk 01 natural sciences 010305 fluids & plasmas Similarity (network science) 0103 physical sciences Metric (mathematics) 010306 general physics Time complexity Algorithm |
| Zdroj: | Modern Physics Letters B. 31:1750162 |
| ISSN: | 1793-6640 0217-9849 |
| Popis: | Currently, with the rapid development of information technology, the electronic media for social communication is becoming more and more popular. Discovery of communities is a very effective way to understand the properties of complex networks. However, traditional community detection algorithms consider the structural characteristics of a social organization only, with more information about nodes and edges wasted. In the meanwhile, these algorithms do not consider each node on its merits.Label propagation algorithm (LPA) is a near linear time algorithm which aims to find the community in the network. It attracts many scholars owing to its high efficiency. In recent years, there are more improved algorithms that were put forward based on LPA. In this paper, an improved LPA based on random walk and node importance (NILPA) is proposed. Firstly, a list of node importance is obtained through calculation. The nodes in the network are sorted in descending order of importance. On the basis of random walk, a matrix is constructed to measure the similarity of nodes and it avoids the random choice in the LPA. Secondly, a new metric IAS (importance and similarity) is calculated by node importance and similarity matrix, which we can use to avoid the random selection in the original LPA and improve the algorithm stability.Finally, a test in real-world and synthetic networks is given. The result shows that this algorithm has better performance than existing methods in finding community structure. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|