COMMUNITY DTECTION USING FIRE PROPAGATION AND BOUNDARY VERTICES ALGORITHMS

Abstract

Community detection in complex networks deal with grouping related nodes together and plays a vital role to understand the functioning of the system in real-life situations. Community detection is classified as an NP-hard problem. Various algorithms are currently available for it but the problem with these existing algorithms is either they have high in time complexity or they have not able to partition the network perfectly. In this paper, we propose a novel community detection algorithm that works in two phases. In the first phase, we apply fire propagation technique in which choosing an arbitrary vertex as the core vertex and connecting an adjacent vertex to it and shapes a community this is similar to how fire spreads in real-life situations. In the second phase,we use the result of the first phase of an overlapped community and detect all boundary vertices which are belongings to more than one communities and assign them to the single community based on the weight that each core vertex assign to that particular boundary vertex using Dijkstra distance and the count of the adjacent vertex that belong that community. The proposed algorithm performs well as compared to label propagation and walk-trap algorithm in terms of modularity score using various synthetic and real-world datasets.