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
Average node impact in the sample network (α = 1, 2, 3).
© Copyright Policy
Related In: Results  -  Collection

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

fig2: Average node impact in the sample network (α = 1, 2, 3).

Mentions: The weights of the edges of the sample undirected network given in Figure 1 are considered as 1. As shown in Figure 2, the α-degree neighborhood impact of each node is calculated by formulas (1) and (2) in the sample network shown in Figure 1 with parameter α = 1, 2, and 3. For example, for node 7, the 1-degree neighborhood impact is 1/4, the 2-degree impact is 5/16, and the 3-degree impact is 271/960. We take VI7(3) below as an example, illustrating the calculation procedure of 3-degree neighborhood impact. Consider(3)VI7(3)=VI6(2)+VI8(2)+VI9(2)+VI10(2)4=VI11+VI41+VI51+VI714+VI71+VI91+VI1013  +VI71+VI81+VI1013+VI71+VI81+VI913 ×14=14VI11+14VI41+14VI51+54VI71+23VI81 +23VI91+23VI10(1)=271960.


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)

Average node impact in the sample network (α = 1, 2, 3).
© Copyright Policy
Related In: Results  -  Collection

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

fig2: Average node impact in the sample network (α = 1, 2, 3).
Mentions: The weights of the edges of the sample undirected network given in Figure 1 are considered as 1. As shown in Figure 2, the α-degree neighborhood impact of each node is calculated by formulas (1) and (2) in the sample network shown in Figure 1 with parameter α = 1, 2, and 3. For example, for node 7, the 1-degree neighborhood impact is 1/4, the 2-degree impact is 5/16, and the 3-degree impact is 271/960. We take VI7(3) below as an example, illustrating the calculation procedure of 3-degree neighborhood impact. Consider(3)VI7(3)=VI6(2)+VI8(2)+VI9(2)+VI10(2)4=VI11+VI41+VI51+VI714+VI71+VI91+VI1013  +VI71+VI81+VI1013+VI71+VI81+VI913 ×14=14VI11+14VI41+14VI51+54VI71+23VI81 +23VI91+23VI10(1)=271960.

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