Ascalable an‎d efficient distributed method for community detection in large graphs

1/1/1900 12:00:00 AM

In today’s world, networks play a fundamental role in many fields such as social networks, communications, recommendation systems, an‎d biology. One of the most important tasks in network analysis is community detection, which has widespread applications in the analysis of network data. However, due to the complex structure of graphs an‎d the nature of community detection algorithms, many of these algorithms operate sequentially, which is inefficient for large graphs. The ever-increasing volume of data an‎d complexity of networks highlights the need for scalable an‎d distributed algorithms. This challenge has motivated the development of new approaches to enhance scalability an‎d efficiency in processing large graphs. In this study, a scalable approach for executing community detection algorithms is presented, based on graph partitioning an‎d creating overlap among subgraphs. This approach, by creating independent an‎d local processes, enables parallel an‎d distributed processing. The main goal of this method is to provide a model with high scalability, an‎d its results are designed to be as close as possible to the output of the algorithm in its sequential form. This model is designed to work independently of the type of community detection algorithm an‎d can be applied to a wide range of algorithms. The performance eva‎luation of the proposed method on the DBLP an‎d Amazon datasets shows that by using a 2 Hop overlap strategy, subgraphs equivalent to one-seventh an‎d one-twentieth of the original graph size were generated for these two datasets. These subgraphs were processed using the FOX algorithm an‎d 64 independent local processes in parallel. Parallel execution of the processes resulted in a threefold speedup for the DBLP dataset an‎d a sixfold speedup for the Amazon dataset. After merging the results of the local processes, the model’s performance was eva‎luated using the results of the original algorithm in its sequential form as the ground truth. The F1-Score metric for the DBLP an‎d Amazon datasets reached 98% an‎d 97%, respectively. Additionally, the percentage of identical community detection was reported to be 93% for DBLP an‎d 90% for Amazon. These results highlight the high efficiency of the proposed method in reducing computational complexity while maintaining accuracy an‎d performance quality compared to the sequential form.

گراف , تشخيص انجمن , مقياس پذيري , پردازش موازي , پردازش توزيع شده

Graph , Community detection , Scalability , Parallel Processing , Distributed Processing

mohamad hadi dadizadeh

Dr mohammad reza kangavari