LabelRankT: Incremental Community Detection in Dynamic Networks via Label Propagation

Abstract

An increasingly important challenge in network analysis is efficient detection and tracking of communities in dynamic networks for which changes arrive as a stream. There is a need for algorithms that can incrementally update and monitor communities whose evolution generates huge realtime data streams, such as the Internet or on-line social networks. In this paper, we propose LabelRankT, an online distributed algorithm for detection of communities in large-scale dynamic networks through stabilized label propagation. Results of tests on real-world networks demonstrate that LabelRankT has much lower computational costs than other algorithms. It also improves the quality of the detected communities compared to dynamic detection methods and matches the quality achieved by static detection approaches. Unlike most of other algorithms which apply only to binary networks, LabelRankT works on weighted and directed networks, which provides a flexible and promising solution for real-world applications.

DyNetMM 2013, New York, USA (conjunction with SIGMOD/PODS 2013)

References in corpus (5)

• Near linear time algorithm to detect community structures in large-scale networks
• Quantifying social group evolution
• Community Detection Using A Neighborhood Strength Driven Label Propagation Algorithm
• Towards Linear Time Overlapping Community Detection in Social Networks
• LabelRank: A Stabilized Label Propagation Algorithm for Community Detection in Networks

Cited by in corpus (6)

• OLCPM: An Online Framework for Detecting Overlapping Communities in Dynamic Social Networks
• Parallel Toolkit for Measuring the Quality of Network Community Structure
• On Efficiently Detecting Overlapping Communities over Distributed Dynamic Graphs
• On the visualization of the detected communities in dynamic networks: A case study of Twitter's network
• Ensemble-Based Discovery of Disjoint, Overlapping and Fuzzy Community Structures in Networks
• Approximate Closest Community Search in Networks