Community search finds query-dependent communities over graphs, which has been investigated broadly. In this work, we focus on the task of returning only a single connected community containing all user input query vertices. Most existing studies in the literature only propose a single and static model based on a particular subgraph (e.g., k -core, k -truss, quasi-clique, and learning-based component). These fixed models are hard to find exact community answers on all datasets and fit with different underlying desires of users and queries. This implies that the community search task needs human-in-loop interactions , which allows users to give feedback and dynamically advise community refinement. To tackle the above issues, we formulate and study the problem of interactive community search , which allows users to add/delete vertices for improving community answers in a few rounds of interactions. We first summarize dozens of existing community models and develop an integrated notation system M( G, M, O, P ) to describe them all. Then, we propose a flexible approach to interactive community search over graphs called GICS-framework. The successful principle of GICS-framework lies on three key components: personalized adding/deleting recommendation, parameter auto-tuning , and fast partial refinement. We develop efficient algorithms and successfully deploy three community models on our GICS-framework. We further analyze algorithm complexity of GICS-framework by illustrating one instance model in detail. Extensive experiments on ground-truth communities demonstrate that our interaction of GICS-framework improves F1-score accuracy by 22% against state-of-the-art competitors, and gives users real-time responses within one second.

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.

The COVID-19 pandemic has caused the society lockdowns and a large number of deaths in many countries. Potential transmission cluster discovery is to find all suspected users with infections, which is greatly needed to fast discover virus transmission chains so as to prevent an outbreak of COVID-19 as early as possible. In this article, we study the problem of potential transmission cluster discovery based on the spatio-temporal logs. Given a query of patient user q and a timestamp of confirmed infection t q , the problem is to find all potential infected users who have close social contacts to user q before time t q . We motivate and formulate the potential transmission cluster model, equipped with a detailed analysis of transmission cluster property and particular model usability. To identify potential clusters, one straightforward method is to compute all close contacts on-the-fly, which is simple but inefficient caused by scanning spatio-temporal logs many times. To accelerate the efficiency, we propose two indexing algorithms by constructing a multigraph index and an advanced BCG-index. Leveraging two well-designed techniques of spatio-temporal compression and graph partition on bipartite contact graphs, our BCG-index approach achieves a good balance of index construction and online query processing to fast discover potential transmission cluster. We theoretically analyze and compare the algorithm complexity of three proposed approaches. Extensive experiments on real-world check-in datasets and COVID-19 confirmed cases in the United States validate the effectiveness and efficiency of our potential transmission cluster model and algorithms.