Title: Hidden Community Detection in Social Networks,
Abstract: We introduce a new paradigm that is important for community detection in the
realm of network analysis. Networks contain a set of strong, dominant
communities, which interfere with the detection of weak, natural community
structure. When most of the members of the weak communities also belong to
stronger communities, they are extremely hard to be uncovered. We call the weak
communities the hidden community structure.
We present a novel approach called HICODE (HIdden COmmunity DEtection) that
identifies the hidden community structure as well as the dominant community
structure. By weakening the strength of the dominant structure, one can uncover
the hidden structure beneath. Likewise, by reducing the strength of the hidden
structure, one can more accurately identify the dominant structure. In this
way, HICODE tackles both tasks simultaneously.
Extensive experiments on real-world networks demonstrate that HICODE
outperforms several state-of-the-art community detection methods in uncovering
both the dominant and the hidden structure. In the Facebook university social
networks, we find multiple non-redundant sets of communities that are strongly
associated with residential hall, year of registration or career position of
the faculties or students, while the state-of-the-art algorithms mainly locate
the dominant ground truth category. In the Due to the difficulty of labeling
all ground truth communities in real-world datasets, HICODE provides a
promising approach to pinpoint the existing latent communities and uncover
communities for which there is no ground truth. Finding this unknown structure
is an extremely important community detection problem.