Physics – Physics and Society
Scientific paper
2011-06-27
Eur. Phys. J. B 81(3), 353-362 (2011)
Physics
Physics and Society
Scientific paper
10.1140/epjb/e2011-10979-2
Label propagation has proven to be an extremely fast method for detecting communities in large complex networks. Furthermore, due to its simplicity, it is also currently one of the most commonly adopted algorithms in the literature. Despite various subsequent advances, an important issue of the algorithm has not yet been properly addressed. Random (node) update orders within the algorithm severely hamper its robustness, and consequently also the stability of the identified community structure. We note that an update order can be seen as increasing propagation preferences from certain nodes, and propose a balanced propagation that counteracts for the introduced randomness by utilizing node balancers. We have evaluated the proposed approach on synthetic networks with planted partition, and on several real-world networks with community structure. The results confirm that balanced propagation is significantly more robust than label propagation, when the performance of community detection is even improved. Thus, balanced propagation retains high scalability and algorithmic simplicity of label propagation, but improves on its stability and performance.
Bajec Marko
Šubelj Lovro
No associations
LandOfFree
Robust network community detection using balanced propagation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Robust network community detection using balanced propagation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Robust network community detection using balanced propagation will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-40529