A Study on the Impact of Partitioning on Community Detection in Graph Networks
摘要
The rapid growth of electronic data generation, processing and storage necessitates large-scale data processing in numerous domains like road networks, car ad hoc networks, bitcoin, pictures, brain networks, and citation networks. In these applications, Graph is a natural and potent tool for describing and capturing dependence relationships between items and it is important to detect the communities within these networks for meaningful interpretation, aiding in tasks such as identifying anomalies in road traffic systems or uncovering deceptive activities on social media. This paper delves into the exploration of graph partitioning approaches, employed to segment large graphs into subgraphs and subsequently identify communities within these partitioned graph networks. The investigation focuses on modularity-based algorithms, particularly the Louvain algorithm, and examines the effectiveness of pyMetis and Deep Learning-based methods in enhancing the efficiency of graph partitioning to yield reliable community detection. The experiments showed that pyMetis outperformed the GCN Method in case of graph partitioning and also showed that the computation cost is reduced while doing graph partition and then proceeding with community detection as compared to usual community detection. Also, the non-distributed and distributed methods of community detection are evaluated and the distributed approach using Ray Framework produced better results than non-distributed community detection.