Uncovering hidden community structures in evolving networks based on neighborhood similarity

Abstract

Detection of densely interconnected nodes also called modules or communities in static or dynamic networks has become a key approach to comprehend the topology, functions and organizations of the networks. Over the years, numerous methods have been proposed to detect the accurate community structure in the networks. State-of-the-art approaches only focus on finding non-overlapping and overlapping communities in a network. However, many networks are known to possess a hidden or embedded structure, where communities are recursively grouped into a hierarchical structure. Here, we reinvent such sub-communities within a community, which can be redefined based on nodes similarity. We term those derived communities as hidden or hierarchical communities. In this work, we present a method called Hidden Community based on Neighborhood Similarity Computation (HCNC) to uncover undetected groups of communities that embedded within a community. HCNC can detect hidden communities irrespective of density variation within the community. We define a new similarity measure based on the degree of a node and it’s adjacent nodes degree.

We evaluate the efficiency of HCNC by comparing it with several well-known community detectors through various real-world and synthetic networks. Results show that HCNC has better performance in comparison to the candidate community detectors concerning various statistical measures. The most intriguing findings of HCNC is that it became the first research work to report the presence of hidden communities in Les Miserables, Karate and Polbooks networks.