Label propagation algorithm: a semi-synchronous approach
by Gennaro Cordasco; Luisa Gargano
International Journal of Social Network Mining (IJSNM), Vol. 1, No. 1, 2012

Abstract: A recently introduced novel community detection strategy is based on a label propagation (LP) algorithm which uses the diffusion of information in the network to identify communities. Studies of LP algorithms showed that the strategy is effective in finding a good community structure. Label propagation step can be performed in parallel on all nodes (synchronous model) or sequentially (asynchronous model); both models present some drawback, e.g., algorithm termination is not granted in the first case, performances can be worst in the second case. In this paper, we present a semi-synchronous version of LP algorithms which aims to combine the advantages of both synchronous and asynchronous models. We prove that our models always converge to a stable labelling. Moreover, we experimentally investigate the effectiveness of the proposed strategy comparing its performance with the asynchronous model both in terms of quality, efficiency and stability. Tests show that the proposed protocol does not harm the quality of the partitioning. Moreover, it is quite efficient; each propagation step is extremely parallelisable and it is more stable than the asynchronous model, thanks to the fact that only a small amount of randomisation is used by our proposal.

Online publication date: Thu, 21-Aug-2014

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Social Network Mining (IJSNM):
Login with your Inderscience username and password:

    Username:        Password:         

Forgotten your password?


Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com