Detecting Overlapping Communities in Two-mode Data Networks using Formal Concept Analysis
Abstract
Social networks frequently feature complex structures such as two-
mode data expressed by bipartite graphs. Most research work on community de-
tection in bipartite graphs focus on either finding non-overlapping communities
or identifying overlapping ones by first projecting two-mode (bi-dimensional)
data into two one-mode tables which are further analyzed. However, this often
leads to a loss of information and produces inaccurate communities. Therefore,
efficiently detecting communities in such two-mode data networks often remains
a key challenge in social network analysis. In this paper, we introduce a novel
three-step strategy to detect overlapping as well as hierarchically nested com-
munities in bipartite graphs. First, we extract the formal concepts that represent
potential groups in the social network. Then, we rank and filter the obtained
groups to keep only core ones that have a high mean of stability and separation.
Finally, we detect communities by refining the core groups using a Silhouette
Analysis. Our experiments on real-world social networks show that our method
can accurately identify overlapping communities.