Efficient Cross-layer Community Search in Large Multilayer Graphs

Community search is a query-dependent graph task to find communities containing a given set of query vertices, which is useful for personalized search and recommendation. Recently, community search over multilayer networks has gained attention thanks to its strong ability to capture cross-layer relationships among diverse entities from multiple domains. This brings significant advantages against the classical studies of community search over only single-layer graphs. However, most existing multilayer community models suffer from two major limitations: 1) failure to identify informative communities with the most layers when a multilayer graph is associated with a large number of layers; 2) missing to distinguish the degree of connections in internal layers and cross-layers. To tackle the above limitations, this paper proposes a novel multilayer subgraph model called$(k, d)$-core. A$(k,d)$-core based community requires that every two layers have enough$k$internal layer connections and$d$cross-layer connections for each vertex in this community. We formulate the problem of multilayer community search (MCS-problem), which finds a$(k,d)$-core connected subgraph$H$containing query vertices to achieve the largest number of cross-layers. For cross-layer connectivity, we consider two-fold definitions of full-layer and path-layer connectivities. First, we consider a strong definition of full-layer connectivity, which constrains that every two layers are connected in$H$. We show that the MCS-problem under full-layer connectivity is NP-hard. We propose two methods of exact exploration and heuristic search for finding M CS answers. Second, to improve the efficiency of community search, we further study a relaxation of path-layer connectivity, allowing two layers to be connected via a path of immediate layers. Then, we develop a fast search algorithm to identify path-layer-based communities and then refine them to full-layer answers. Furthermore, we develop a novel$(k,d){-}$core index that effectively captures essential$(k,d)$-core structure, including the neighborhood information, the layer connectivities, and the internal/cross-layer corenesses. Extensive experiments on nine real-world multilayer graphs demonstrate the effectiveness and efficiency of our M CS model and algorithms.