An adaptive granulation algorithm for community detection based on improved label propagation

摘要: Abstract Community detection is a hot research in complex network analysis. Detecting community structure networks crucial for insight into the internal connections within networks. A variety of algorithms have previously been proposed, while few them can efficiently apply to large-scale due unacceptable running time and intractable parameter tuning. To tackle above issues, this paper proposes an adaptive granulation algorithm based on improved label propagation (Gr-ILP), which granulates hierarchically with strategy. For given network, first, strategy (ILP) adopted gather similar nodes non-overlapping collections consist high similarity. Second, each collection detected first step granulated super node, edges between two are edge. After processing, super-network that coarser smaller than original one formed. Then, steps repeated iteratively until it stops forming new step. Due adoption strategy, proposed Gr-ILP certain layer saves much when processing Finally, assigns unallocated isolated appropriate community. The requires neither any priori information communities nor adjustment parameters still obtained satisfactory adaptively. tends preserve small-scale by limiting growth node collections. Moreover, because sharp decline size process, consumes less suitable Experimental results eight real-world datasets different types sizes demonstrate effectiveness efficiency our algorithm, compared several other baseline algorithms.