Robust Local Community Search over Large Heterogeneous Information Networks

Given a heterogeneous information network (HIN) \(G\) and a query node \(q\) , community search (CS) over HINs aims to find a group of nodes containing the query node. However, we discover existing methodologies, such as \((k, \mathcal {P})\) -core and \((k, \mathcal {P})\) -truss, where \(\mathcal {P}\) represents the meta-path, only require the nodes within the communities are \(\mathcal {P}\) -connected to q, without considering the distance between these nodes and the query node. As a result, the communities may include distant and irrelevant nodes, leading to the free-rider effect. To tackle these challenges, we propose a query densest \(\mathcal {P}\) -connected community (QDPC) model. In QDPC, we develop a query density goodness metric, which utilizes the node and edge weighting schemes to reduce the free rider effect. In particular, each target type node is weighted based on its proximity to the query node. Larger distance will cause higher node weight. The QDPC will shift to the neighborhood of the query node and demonstrate stronger edge weights, i.e., \(\mathcal {P}\) -connectivity. We further propose the expanding-and-shrinking algorithm to locally find QDPC. Extensive experiments on four real datasets underscore QDPC effectively alleviates the free ride effect and the proposed methods are efficient.