Node Embedding With a <inline-formula> <tex-math notation="LaTeX">$CN$ </tex-math></inline-formula>-Based Random Walk for Community Search

Abstract

Community search is a query request-oriented community detection problem. Given a query node $v$ in network $G$ , the goal of community search is to discover a community in $G$ that contains node $v$ . Traditional algorithms rely on carefully engineered features to measure local neighborhood structures. Designing these features is a time-consuming process that limits their practical application. Motivated by node embedding using deep learning method to learn distributed representations for nodes in networks, we propose a two-stage community search algorithm based on node embedding. To address the drawbacks of existing node embedding methods, we propose a node embedding model with a $CN$ -based random walk (NECNW) based on a skip-gram model in the first stage. Via NECNW, we learn a low-dimensional representation of nodes in networks. In the second stage, we propose a community quality metric $closeness{-}isolation$ ( $CI$ ) based on the learned vectors. Then, we expand the target community by greedy addition of a shell node that has maximum similarity with the current community. We evaluate the proposed algorithm on both real-world and synthetic networks with related community search and node embedding algorithms. The experimental results show that the proposed algorithm is more effective and efficient for community search than other algorithms.

Keywords

• Community search
• node embedding
• local community detection
• community structure
• random walk