Shahed University

SLPA-based parallel overlapping community detection approach in large complex social networks

Mohammad Hosseini
URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=137940
Date :  2020/10/26
Publish in :    Multimedia Tools and Applications
DOI :  https://doi.org/10.1007/s11042-020-09993-1
Link :  https://doi.org/10.1007/s11042-020-09993-1
Keywords :Overlapping community detection, Large and complex social networks, Parallel processing, Speaker-listener push-pull propagation approach (SL3PA), Speaker-listener propagation approach (SLPA) , Speaker-listener push-pull propagation algorithm (SL3PA?) ,Speaker-listener propagation algorithm (SLPA?)

Abstract :
Performance improvement of community detection is an NP problem in large social networks analysis where by integrating the overlapped communities’ information and modularity maximization increases the time complexity and memory usage. This paper presents an online parallel overlapping community detection approach based on a speaker-listener propagation algorithm by proposing a novel parallel algorithm and applying three new metrics. This approach is presented to improve modularity and expand scalability for getting a significantly speedup in low time-consuming and usage memory through an agent-based parallel implementation in a multi-core architecture. The key ideas of our approach are increasing the communities’ conductance score, limiting the speaking-listening stages and executing a strategic updating order to develop a speaker-listeners label propagation algorithm for getting better speedup and semi-deterministic results without using prior training or requiring particular predefined features. Experimental results of used large datasets compared with state-of-the-art algorithms show that the proposed method is extremely convergence and achieves an average 820 speedup in the label propagation algorithm, and significantly improves the modularity that are effective in finding better overlapping communities in a linear time complexity O(m) and lower usage memory O(n).