Searching and Detecting Structurally Similar Communities in Large Heterogeneous Information Networks

Download PDF

Abstract

Heterogeneous information networks (HINs) are prevalent in vari- ous domains, including bibliographic information networks, social media, and knowledge graphs. As a fundamental topic in HIN min- ing, community mining has found various real applications, such as recommendation, biological data analysis, and event organization. Most existing works often rely on meta-paths, relational constraints, spectral partitioning, label propagation, and network representa- tion to define the communities. However, almost all these works do not explicitly consider the structural similarity between vertices, which plays a vital role in modeling communities and also ignore the specific roles of vertices. In this paper, we propose a novel com- munity model, called structurally similar community (SSC), which models the HIN communities by explicitly considering the struc- tural similarity between vertices. In particular, SSC can not only support various structural similarity measures, but also identify different roles of the vertices in the community, such as cores, non- cores, hubs, and outliers. Based on the SSC, we develop fast online and index-based algorithms that support both efficient searching and detecting SSCs in large HINs, where the former one searches an SSC containing a specific query vertex while the latter one detects all the SSCs from the HIN. Extensive experiments on real-world datasets demonstrate the effectiveness of SSC model in revealing meaningful communities and the high efficiency of our proposed algorithms.