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 commu- nity 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 MCS 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 MCS model and algorithms.