Limits...
Label propagation with α-degree neighborhood impact for network community detection.

Sun H, Huang J, Zhong X, Liu K, Zou J, Song Q - Comput Intell Neurosci (2014)

Bottom Line: In this paper, a novel label propagation approach with α-degree neighborhood impact is proposed for efficiently and effectively detecting communities in networks.Firstly, we calculate the neighborhood impact of each node in a network within the scope of its α-degree neighborhood network by using an iterative approach.The α-degree neighborhood impact is also taken as the updating weight value, where the parameter impact scope α can be set to a positive integer.

View Article: PubMed Central - PubMed

Affiliation: School of Electronic and Information Engineering, Xi'an Jiaotong University, Xi'an 710049, China ; State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China.

ABSTRACT
Community detection is an important task for mining the structure and function of complex networks. In this paper, a novel label propagation approach with α-degree neighborhood impact is proposed for efficiently and effectively detecting communities in networks. Firstly, we calculate the neighborhood impact of each node in a network within the scope of its α-degree neighborhood network by using an iterative approach. To mitigate the problems of visiting order correlation and convergence difficulty when updating the node labels asynchronously, our method updates the labels in an ascending order on the α-degree neighborhood impact of all the nodes. The α-degree neighborhood impact is also taken as the updating weight value, where the parameter impact scope α can be set to a positive integer. Experimental results from several real-world and synthetic networks show that our method can reveal the community structure in networks rapidly and accurately. The performance of our method is better than other label propagation based methods.

Show MeSH
The process of label propagation by using algorithm NILP to detect community structure on the sample network.
© Copyright Policy
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4265519&req=5

fig3: The process of label propagation by using algorithm NILP to detect community structure on the sample network.

Mentions: Figure 3 illustrates the process of community detection using algorithm NILP in the above example network when α = 2. In Figure 3(a), in the sample network, each node is marked with a unique label, and the 2-degree neighborhood impact values are labeled beside the nodes. According to the ascending sort order of the impact values, the nodes update order is determined as 5 → 1 → 4 → 2 → 3 → 6 → 7 → 8 → 9 → 10. Node 5 is the first one for label update, using formula (5) to decide the new label, and the result for adjacent neighborhood node 6 has the greatest influence on it, so we change the label of node 5 to the node number of its neighbor, in case 6. Next, we update all the nodes sequentially. Figure 3(b) is the result of the divided community which is updated at the end of the first round of label propagation. After the first round of label update process completed, with the stable ratio of the current node being p1 = 0.3, we are supposed to update labels in accordance with the above order in the next round of node label update process. The algorithm continues to run until the stable ratio no longer rises. Figure 3(c) shows the final results of our algorithm on detecting communities on the sample network.


Label propagation with α-degree neighborhood impact for network community detection.

Sun H, Huang J, Zhong X, Liu K, Zou J, Song Q - Comput Intell Neurosci (2014)

The process of label propagation by using algorithm NILP to detect community structure on the sample network.
© Copyright Policy
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4265519&req=5

fig3: The process of label propagation by using algorithm NILP to detect community structure on the sample network.
Mentions: Figure 3 illustrates the process of community detection using algorithm NILP in the above example network when α = 2. In Figure 3(a), in the sample network, each node is marked with a unique label, and the 2-degree neighborhood impact values are labeled beside the nodes. According to the ascending sort order of the impact values, the nodes update order is determined as 5 → 1 → 4 → 2 → 3 → 6 → 7 → 8 → 9 → 10. Node 5 is the first one for label update, using formula (5) to decide the new label, and the result for adjacent neighborhood node 6 has the greatest influence on it, so we change the label of node 5 to the node number of its neighbor, in case 6. Next, we update all the nodes sequentially. Figure 3(b) is the result of the divided community which is updated at the end of the first round of label propagation. After the first round of label update process completed, with the stable ratio of the current node being p1 = 0.3, we are supposed to update labels in accordance with the above order in the next round of node label update process. The algorithm continues to run until the stable ratio no longer rises. Figure 3(c) shows the final results of our algorithm on detecting communities on the sample network.

Bottom Line: In this paper, a novel label propagation approach with α-degree neighborhood impact is proposed for efficiently and effectively detecting communities in networks.Firstly, we calculate the neighborhood impact of each node in a network within the scope of its α-degree neighborhood network by using an iterative approach.The α-degree neighborhood impact is also taken as the updating weight value, where the parameter impact scope α can be set to a positive integer.

View Article: PubMed Central - PubMed

Affiliation: School of Electronic and Information Engineering, Xi'an Jiaotong University, Xi'an 710049, China ; State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China.

ABSTRACT
Community detection is an important task for mining the structure and function of complex networks. In this paper, a novel label propagation approach with α-degree neighborhood impact is proposed for efficiently and effectively detecting communities in networks. Firstly, we calculate the neighborhood impact of each node in a network within the scope of its α-degree neighborhood network by using an iterative approach. To mitigate the problems of visiting order correlation and convergence difficulty when updating the node labels asynchronously, our method updates the labels in an ascending order on the α-degree neighborhood impact of all the nodes. The α-degree neighborhood impact is also taken as the updating weight value, where the parameter impact scope α can be set to a positive integer. Experimental results from several real-world and synthetic networks show that our method can reveal the community structure in networks rapidly and accurately. The performance of our method is better than other label propagation based methods.

Show MeSH