Affordable Access

Access to the full text

Memory-based random walk for multi-query local community detection

Authors
  • Bian, Yuchen1
  • Luo, Dongsheng1
  • Yan, Yaowei1
  • Cheng, Wei2
  • Wang, Wei3
  • Zhang, Xiang1
  • 1 The Pennsylvania State University, University Park, PA, 16802, USA , University Park (United States)
  • 2 NEC Laboratories America, Princeton, USA , Princeton (United States)
  • 3 University of California, Los Angeles, USA , Los Angeles (United States)
Type
Published Article
Journal
Knowledge and Information Systems
Publisher
Springer-Verlag
Publication Date
Sep 09, 2019
Volume
62
Issue
5
Pages
2067–2101
Identifiers
DOI: 10.1007/s10115-019-01398-3
Source
Springer Nature
Keywords
License
Yellow

Abstract

Local community detection, which aims to find a target community containing a set of query nodes, has recently drawn intense research interest. The existing local community detection methods usually assume all query nodes are from the same community and only find a single target community. This is a strict requirement and does not allow much flexibility. In many real-world applications, however, we may not have any prior knowledge about the community memberships of the query nodes, and different query nodes may be from different communities. To address this limitation of the existing methods, we propose a novel memory-based random walk method, MRW, that can simultaneously identify multiple target local communities to which the query nodes belong. In MRW, each query node is associated with a random walker. Different from commonly used memoryless random walk models, MRW records the entire visiting history of each walker. The visiting histories of walkers can help unravel whether they are from the same community or not. Intuitively, walkers with similar visiting histories are more likely to be in the same community. Moreover, MRW allows walkers with similar visiting histories to reinforce each other so that they can better capture the community structure instead of being biased to the query nodes. We provide rigorous theoretical foundations for the proposed method and develop efficient algorithms to identify multiple target local communities simultaneously. Comprehensive experimental evaluations on a variety of real-world datasets demonstrate the effectiveness and efficiency of the proposed method.

Report this publication

Statistics

Seen <100 times