SLPA-based parallel overlapping community detection approach in large complex social networks
- PDF / 3,896,075 Bytes
- 32 Pages / 439.642 x 666.49 pts Page_size
- 118 Downloads / 179 Views
SLPA-based parallel overlapping community detection approach in large complex social networks Aminollah Mahabadi1,2 · Mohammad Hosseini1 Received: 18 March 2020 / Revised: 19 August 2020 / Accepted: 29 September 2020 / © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Performance improvement of community detection is an N P 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). 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◦ )
1 Introduction Many natural entities from micro agents such as proteins to macro agents such as humans interact with each other to condense agents by static chemical relations in biological systems to intelligent support of dynamic relations in social and information networks [24]. When Aminollah Mahabadi
[email protected]; [email protected] 1
Computer Engineering Department, Shahed University, Tehran, Iran
2
Acoustic Research Center, Shahed University, Tehran, Iran
Multimedia Tools and Applications
the interactions among agents of a complex system map to network graph by nodes and links, these groups of agents form tightly connected modules in biological systems to social in social networks that are only weakly connected to another [30]. The strong relationship of the dependent agents in a social graph, forms stable and robust overlapped communities in the large social networks of a wide range of applications such as Facebook, MySpace, Twitter, and LinkedIn [17]. Network analysis is an essential field of sociology and anthropology which is c
Data Loading...
