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
We evaluate the efficiency of
Keywords
Introduction
Complex systems such as social media, biological interactions and internet can be represented as graphs (networks)
Over the last few decades, numerous community detection algorithms have been proposed for identifying disjoint sub-groups (communities) of related nodes within the networks [3]. In recent years, researchers have observed that some community members have significant external connections with the other community members and have proposed new methods for finding overlapping communities [4–6]. Besides these two categories of communities, one form of overlapping community termed as a hidden (or embedded) community may also form due to the variation in the relationship within the community members. Therefore, one can further analyze the detected communities and can build a hierarchical dendrogram based on the neighborhood similarity present within a community. Best of our knowledge, very less attention has been given by the past researches to extract such communities.
During the identification of a community structure, the membership of a node towards the community is measured based on the connectivity or relationship possess by any node at that time. However, in the case of a real-world scenario, the connectivity retains by any node may fluctuate with time. An increase or decrease in connectivity within a community can transform a single community into multiple dense or sparse sub-communities or even leads to the formation of the death community. Contrarily, an increase or decrease in connectivity with other communities leads to the shifting of nodes from one community to others or may create overlapping nodes, which further may lead to the community merging. For a clear understanding of the above situations within a community, let us consider a community of baseball players created by the college students during their graduation. In the beginning, the community members are more close or interactive to each other leads to forming a single and compact community. After a few years, it seems that the interaction among the members of the community deliberately decreases over time, except a few of them, who continue to share similar interests among them. The reasons behind these behavioral changes within the members of the baseball community players depend on several aspects. The community members may either grow interests in other areas than baseball or lack of interest within the members themselves over time. Due to this two probable scenarios (not limited to), the group (including social groups such as Facebook, WhatsApp, etc) may split into sub-groups such as (
It would be more understandable if we consider the formation as well as the transformation of a family community as shown in Fig.1. It is obvious that the male members in the family (brothers, cousin brothers & brothers-in-law) and the female members (wives, sisters & sisters-in-law) both communities are strongly involved in family interest. Communities of their sons and daughters show less involvement in family interests. Similarly, the community of kids and old persons have the least involvement, however, they still get the benefits of being a family member. If we observed the transition within the family communities for a particular period of time, it seems that a highly active community progressively transforms into the least active community. These underlying phenomena present within a community is more crucial and challenging task to uncover. For a similar type of example, we can consider any social media groups like WhatsApp, Facebook groups. In such social groups, a few members are strongly involved and share information in the group. Some of them share or post when they feel it necessary and some of them become inactive all the time, but still getting information from the group. Hence, instead of having a single community of family members or any social community, we can split the whole community into sub-communities based on the role, characteristics or similarity possesses by each community member.

Presence of sub-communities within a community of Family members.
The advantage of revealing sub-communities within a community is to get a better understanding of the underlying properties and to provide better services. Since, the potential members of a community take the reins of almost all imperative activities. Thus, it is essential to impart with the potential members of a community to conceal precise services, rather than providing the services to all the members. Similarly, for the marketing of the commercial products, its’ necessary to target a group of potential users to expose in social networks, rather than targeting all users for optimizing the spread of product consumption. Since, the negative reviews of some people may impair the product value as well as long-term profit.
Uncovering the hidden communities within a community in complex networks come across various challenges. This work focuses on providing insight into the hidden structure and also address the following challenges. Due to frequent manipulation (increase or decrease) of connectivity with in the community leads to the transformation of community structure from one to another. Community objects may join or leave from one sub-group to another due to the alteration of their interests or connectedness.
To address the above issues, we propose a new community detection method
The rest of the paper is organized as follows. In Section 2, the detection of communities within a community is described in detail. The similarity measures for hidden community detection is presented in Section 3. Section 4, report the performance evaluation of the proposed model. Finally, we summarize our work in Section 5.
A sub-graphs with dense intra-community connectivity in comparison to sparse-community connectivity within the network is popularly defined as a community [7].
In community detection problem, each
In the recent past, a few proposals are put forward on identifying hierarchical communities. OSLOM [11] is an optimized fitness function based approach to detect overlapping and hierarchical community structures in diverse types of networks. EAGLE [12] is able to detect both hierarchical and overlapping communities. This algorithm deals with the set of maximal cliques and adopts an agglomerative framework. iLCD [13] is presented by [13] to detect overlapping community structures in dynamic networks. iLCD state that communities are independent of its context and it transforms from one state (origin) to other (current). LCDNN [14], is an NGC (Nodes with Greater Centrality) based local community detection approach. In this approach, a fuzzy relation is adopted to compute the affinity from nodes to their NGC nodes. TSB [15] is a local community detection method based on breadth first search (BFS), transfer similarity and local clustering coefficient. However, this approach ignores the presence of hidden communities within the communities. LGIEM [16] can uncover communities based on global and local influential nodes. First, initial communities are formed based on the most influential nodes. Then, the existing communities are expanded based on an expansion strategy. Finally, overlapping communities are merged to obtain the final communities. However, LGIEM does not report the concept of hidden community structure. Recently, research work like InDEN [17] and InOvIn [18] has proposed an integrated approach to uncover overlapping, non-overlapping and intrinsic communities in growing networks. However, they don’t consider those community structures which don’t have dense connectivity compare to other members yet they retain similar characteristics.
Most of the conventional methods use a mapping function based on certain features (e.g. properties or connectedness), which is remain the same for detecting both communities (from a network) and hierarchical communities (from a community). It fails to uncover hierarchical communities, where members do not retain such particular features. For example, if we need to group family members from a random crowd group (network). We will look into some particular features and identify some members as a family. However, within that family community, the features or connectedness upon which we consider them as a member of this group may not be the same. For example, connectedness between father-son and mother-son has a significant difference. Hence, a particular feature is incompetent to detect hidden or hierarchical community within a community.
Algorithms like InDEN and InOvIn can detect density variation only when there are significant changes (measured by a threshold) in nodes degree within a community. It can not detect communities which do not exhibit significant variations in degree distributions within a particular community. However, it has been observed that members, who do not acquire the essential features (such as connected density, exclusive characteristics, etc.) are also capable of forming communities within the parent community. In our approach, we are not considering only the dense connectivity as a feature. Rather, we are considering all similar kinds of connectivity (both dense and sparse) acquired by each node of the community. Nodes with similar connected density are further group together within a community, what we termed as hidden or embedded communities and it’s detection is our prime objective that has been discussed next.
Uncovering hidden community structures
For every community finding approach, the mapping function used in it assesses the efficiency of the approach. A community with robust similarity measure produces more rigorous community structures. In this work, we have adopted the
We examine the presence of hidden communities by seeking similar kinds of members within a community. In this regard, a few new measures are introduced to find the proximity of one node to another. A brief interpretation of these parameters is discussed below.
Calculating node similarity within a community
We create sub-communities within a community based on the
Next, we discuss how we initiate our hierarchical or hidden community detection approach within a community with the help of neighborhood similarity computation.
To uncovering the hidden communities within a community
Merging communities
Given two sub-communities c
p
and c
q
are merged together only when a significant number of members from both the communities have the
HCNC: The Algorithm
Algorithm 1 represents the stepwise process of our proposed method
We initiate the process by selecting the leader from a community and traverse the neighbors of neighbors (expand the neighbors) of the leader until
Performance evaluation
In this section, we examine the performance of the proposed
Testing data
To evaluate the computational efficiency of the proposed method, we consider four (04) synthetic and eight (08) real-world input networks. Due to unavailability of networks with hidden or embedded communities, we generate four synthetic networks (see Fig. 2) HiNet1 to HiNet4, with significant degree distribution among the nodes. Both network HiNet1 and HiNet4 have four hidden communities. HiNet2 have one hidden communities and network HiNet3 contains two hidden community. All synthetic HiNet networks are available on GitHub 1 for download.
We also use well known real-world networks, which are available at UCI 2 machine repository and SNAP 3 . Table 1 summarized both synthetic and real-world networks used in the experiment.

Original Synthetic
Dataset used in the experiments
– Information not available. Note: All these synthetic and real-world networks used in the experiment are undirected in nature.
Qualitative Assessment of
A series of experiments were performed to quantify the efficiency of
In the case of real-world network karate,

Validity Measures for Karate, Dolphin, Polbook and Les Miserables networks.
To assess the performance of

Validity Measures for ca-CondMat, CaGrQc, ca-HepTh and Facebook networks.
For quality measure, we consider the Normalized Mutual Information (NMI) [23]. In this experiment, we increase the percentage of the incoming edge by

Results generated by five algorithms on Facebook (left) and on Ca-HepTh network (right) with respect to NMI (Y-axis) and Percentage of incoming edge (X-axis).
We initiate the process of uncovering hidden communities after a certain interval of time. Experimentally, we have successfully detected the presence of hidden communities in the real-world datasets namely Karate, Polbooks and Les Miserables. Network Karate contains one hidden communities, whereas Polbooks and Les Miserables contain two and four hidden communities respectively. To the best of our knowledge, no prior research reports the presence of hidden communities in these networks. Figures 6, 7 demonstrate the accuracy of

Sub-communities identified by

Total number of communities including both hidden and disjoint communities identified by various algorithms
– Information not available. Number of nodes are represent by n and m stands for edges.
We introduce an approach ttHCNC for uncovering both disjoint and hidden communities from evolving networks. We introduced a new measure called Node Similarity Index (ttNSI) to calculate the similarity between any two nodes. We test our proposed model against contemporary detectors on both synthetic and real-world networks. Results imply that ttHCNC produce superior results than all other community detectors concerning most of the assessment indices.
In our current work, we assume that networks are evolving in nature, where each incoming node is joining the network in a constant manner. However, in the real-world scenario, nodes may join the network in different time frames with varying velocity. In our future work, we will consider the possible effects that can crop up in detecting communities due to the varying volume and velocity of growing networks.
Footnotes
https://github.com/nathkeshab/HiNet
http://archive.ics.uci.edu/ml/datasets.html
https://snap.stanford.edu/data/#citnets
