Large-Scale Community Key-Member Search: An Efficient Approach Based on Random Walks

Given an undirected graph, a specific query, and an cohesiveness parameter, Community Search (CS) aims to identify a cohesive subgraph forming as a community from the undirected graph that includes the query. For users (ordinary or even expert users) with less information of graph structures, setting an suitable cohesiveness parameter is difficult. Even with a large cohesiveness parameter, the resulting size of community size is often too large. Compared with the whole community, key-members are more valuable than others in practice. Therefore, our research focuses on a new problem Community Key-members Search (CKS), shifting our interest to identify key-members from a community, rather than the community as a whole. To address CKS, we first develop an exact method grounded in truss decomposition as a benchmark. Then, we propose four algorithms leveraging random walks to balance efficiency and effectiveness, by using three cohesiveness features for designing an appropriate transition matrix. The key-members are determined based on the stationary distribution. We conduct a theoretical analysis on the rationality of the design of cohesiveness-aware transition matrix, utilizing Bayesian theory, Box-Cox transformation, and Copula function. Furthermore, we design an efficient refinement method to optimize the community key-members with very limited overhead. Then, we adopt it to CKS with multiple query nodes. Experimental studies across real-world datasets demonstrate the superiority of our method, which makes the query algorithm speed up by 512× on average and the highest accuracy reachs 99.3%.