Abstract
Community detection is an important task for identifying the structure and function of complex networks. The task is challenging as communities often show overlapping and hierarchical behavior, i.e., a node can belong to multiple communities, and multiple smaller communities can be embedded within a larger community. Moreover, real-world networks often contain communities of arbitrary size and shape, along with outliers. This paper presents a novel density-based overlapping community detection method, OCMiner, to identify overlapping community structures in social networks. Unlike other density-based community detection methods, OCMiner does not require the neighborhood threshold parameter (ε) to be set by the users. Determining an optimal value for ε is a longstanding and challenging task for density-based clustering methods. Instead, OCMiner automatically determines the neighborhood threshold parameter for each node locally from the underlying network. It also uses a novel distance function which utilizes the weights of the edges in weighted networks, besides being able to find communities in un-weighted networks. The efficacy of the proposed method has been established through experiments on various real-world and synthetic networks. In comparison to the existing state-of-the-art community detection methods, OCMiner is computationally faster, scalable to large-scale networks, and able to find significant community structures in social networks.