Attributed multi-query community search via random walk similarity

Community search aims to provide efficient solutions for searching high-quality communities via given sample nodes from network. Much research effort has devoted to mining a single community based on the assumption of sample nodes are from the same community. Despite their effectiveness, the following two insights are often neglected. First, complex high-order structural relationship and attribute provide auxiliary information to represent nodes and offer meaningful information to compensate the incomplete and missing information of the network, it benefits to optimal results. Second, user usually assumes that sample nodes come from the same community without any prior knowledge. This stringent assumption limits the flexibility of algorithm in many real-world scenarios. To this end, we propose a novel multi-community search method in attributed networks that is capable of effectively searching multi-communities where sample nodes locate. Specifically, we appoint complex structural information as internal attributes which explicitly encode node's interaction and combine it with node attributes. In order to better capture association between nodes and attributes, we construct a node-attribute graph and similarity enhanced random walk is performed based on it. The similarity enhanced random walk is developed to reinforce the walking path of each sample node so that they can better distinguish and capture the community structure for sample nodes. The multi-communities with densely connected and similar attributes can be found by parallel conductance. Extensive experimental results on both synthetic and real-world graphs verify the effectiveness and efficiency of the proposed method, and show its superiority over many state-of-art approaches.