research-article

The multi-walker chain and its application in local community detection

Authors:

Xiang ZhangAuthors Info & Claims

Volume 60, Issue 3

Pages 1663 - 1691

https://doi.org/10.1007/s10115-018-1247-1

Published: 01 September 2019 Publication History

Abstract

Local community detection (or local clustering) is of fundamental importance in large network analysis. Random walk-based methods have been routinely used in this task. Most existing random walk methods are based on the single-walker model. However, without any guidance, a single walker may not be adequate to effectively capture the local cluster. In this paper, we study a multi-walker chain (MWC) model, which allows multiple walkers to explore the network. Each walker is influenced (or pulled back) by all other walkers when deciding the next steps. This helps the walkers to stay as a group and within the cluster. We introduce two measures based on the mean and standard deviation of the visiting probabilities of the walkers. These measures not only can accurately identify the local cluster, but also help detect the cluster center and boundary, which cannot be achieved by the existing single-walker methods. We provide rigorous theoretical foundation for MWC and devise efficient algorithms to compute it. Extensive experimental results on a variety of real-world and synthetic networks demonstrate that MWC outperforms the state-of-the-art local community detection methods by a large margin.

References

[1]

Alamgir M, Von Luxburg U (2010) Multi-agent random walks for local clustering on graphs. In: ICDM

Digital Library

[2]

Alon N, Avin C, Koucky M, Kozma G, Lotker Z, Tuttle MR (2008) Many random walks are faster than one. In: SPPA

[3]

Andersen R, Chung F, Lang K (2006) Local graph partitioning using PageRank vectors. In: FOCS

Digital Library

[4]

Andersen R, Lang KJ (2006) Communities from seed sets. In: WWW

[5]

Barnard K, Duygulu P, Forsyth D, Freitas Nd, Blei DM, Jordan MI (2003) Matching words and pictures. J Mach Learn Res 3:1107–1135

Digital Library

[6]

Brandes U (2001) A faster algorithm for betweenness centrality. J Math Sociol 25(2):163–177

[7]

Cooper C, Frieze A, Radzik T (2009) Multiple random walks and interacting particle systems. In: International colloquium on automata, languages and programming. Springer, New York, pp 399–410

[8]

Guan Z, Wu J, Zhang Q, Singh A, Yan X (2011) Assessing and ranking structural correlations in graphs. In: SIGMOD

Digital Library

[9]

Guillaumin M, Mensink T, Verbeek J, Schmid C (2009) Tagprop: discriminative metric learning in nearest neighbor models for image auto-annotation. In: ICCV

[10]

Hajnal J, Bartlett M (1958) Weak ergodicity in non-homogeneous Markov chains. In: Mathematical proceedings of the Cambridge Philosophical Society

[11]

Haveliwala TH (2002) Topic-sensitive pagerank, WWW

Digital Library

[12]

He K, Shi P, Hopcroft J, Bindel D (2016) Local spectral diffusion for robust community detection. In: SIGKDD twelfth workshop on mining and learning with graphs

[13]

He K, Sun Y, Bindel D, Hopcroft J, Li Y (2015) Detecting overlapping communities from local spectral subspaces. In: ICDM

Digital Library

[14]

Isaacson DL, Madsen RW (1976) Markov chains, theory and applications, vol 4. Wiley, New York

[15]

Jeh G, Widom J (2002) SimRank: a measure of structural-context similarity. In: KDD

Digital Library

[16]

Kloster K, Gleich DF (2014) Heat kernel based community detection. In: KDD

Digital Library

[17]

Kloumann IM, Kleinberg JM (2014) Community membership identification from small seed sets. In: KDD

[18]

Lancichinetti A, Fortunato S, Radicchi F (2008) Benchmark graphs for testing community detection algorithms. Phys Rev E 78(4):046110

[19]

Langville AN, Meyer CD (2004) Deeper inside PageRank. Intern Math 1(3):335–380

[20]

Lee C, Jang W-D, Sim J-Y, Kim C-S (2015) Multiple random walkers and their application to image cosegmentation. In: CVPR

[21]

Lee S-H, Jang W-D, Park B K, Kim C-S (2016) RGB-D image segmentation based on multiple random walkers. In: ICIP

[22]

Li Y, He K, Bindel D, Hopcroft JE (2015) Uncovering the small community structure in large networks: a local spectral approach. In: WWW

[23]

Lu D, Zhang H (1986) Stochastic process and applications. Tsinghua University Press, Beijing

[24]

Pan J-Y, Yang H-J, Faloutsos C, Duygulu P (2004) Automatic multimedia cross-modal correlation discovery. In: KDD

Digital Library

[25]

Sarkar P, Moore A (2007) A tractable approach to finding closest truncated-commute-time neighbors in large graphs. In: UAI

[26]

Schaeffer SE (2007) Graph clustering. Comput Sci Rev 1(1):27–164

Digital Library

[27]

Spielman DA, Teng S-H (2013) A local clustering algorithm for massive graphs and its application to nearly-linear time graph partitioning. SIAM J Comput 42(1):1–26

Digital Library

[28]

Tong H, Faloutsos C, Pan J-Y (2006) Fast random walk with restart and its applications. In: ICDM

Digital Library

[29]

Whang JJ, Gleich DF, Dhillon IS (2013) Overlapping community detection using seed set expansion. In: CIKM

[30]

Wolfowitz J (1963) Products of indecomposable, aperiodic, stochastic matrices. Linear Algebra Appl 14(5):733–737

[31]

Wu CW (2005) On bounds of extremal eigenvalues of irreducible and m-reducible matrices. Linear Algebra Appl 402:29–45

[32]

Wu X-M, Li Z, So AM, Wright J, Chang S-F (2012) Learning with partially absorbing random walks. NIPS

[33]

Wu Y, Jin R, Li J, Zhang X (2015) Robust local community detection: on free rider effect and its elimination. In: VLDB

[34]

Yang J, Leskovec J (2012) Defining and evaluating network communities based on ground-truth. In: ICDM

[35]

Yin H, Benson AR, Leskovec J, Gleich DF (2017) Local higher-order graph clustering. In: KDD

Digital Library

[36]

Yu W, Lin X, Zhang W, Chang L, Pei J (2013) More is simpler: effectively and efficiently assessing node-pair similarities based on hyperlinks. In: VLDB

[37]

Zhang J, Tang J, Ma C, Tong H, Jing Y, Li J ( 2015) Panther: fast top-k similarity search on large networks. In: KDD

[38]

Zhou D, Zhang S, Yildirim MY, Alcorn S, Tong H, Davulcu H, He J (2017) A local algorithm for structure-preserving graph cut. In: KDD

Digital Library

[39]

Zhu X, Goldberg AB (2009) Introduction to semi-supervised learning. Synth Lect Artif Intell Mach Learn 3(1):1–130

Cited By

Luo DBian YYan YYu XHuan JLiu XZhang X(2023)Random Walk on Multiple NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.322166835:8(8417-8430)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TKDE.2022.3221668
Luo DBian YYan YLiu XHuan JZhang XGupta RLiu YShah MRajan STang JPrakash B(2020)Local Community Detection in Multiple NetworksProceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3394486.3403069(266-274)Online publication date: 23-Aug-2020
https://dl.acm.org/doi/10.1145/3394486.3403069
Bian YLuo DYan YCheng WWang WZhang X(2019)Memory-based random walk for multi-query local community detectionKnowledge and Information Systems10.1007/s10115-019-01398-362:5(2067-2101)Online publication date: 9-Sep-2019
https://dl.acm.org/doi/10.1007/s10115-019-01398-3

Index Terms

The multi-walker chain and its application in local community detection

Index terms have been assigned to the content through auto-classification.

Recommendations

Memory-based random walk for multi-query local community detection
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 ...
Multi-agent Random Walks for Local Clustering on Graphs
ICDM '10: Proceedings of the 2010 IEEE International Conference on Data Mining

We consider the problem of local graph clustering where the aim is to discover the local cluster corresponding to a point of interest. The most popular algorithms to solve this problem start a random walk at the point of interest and let it run until ...
Local community detection algorithm based on local modularity density
Abstract
Compared to global community detection, local community detection aims to find communities that contain a given node. Therefore, it can be regarded as a specific and personalized community detection task. Local community detection algorithms based ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Knowledge and Information Systems

Knowledge and Information Systems Volume 60, Issue 3

Sep 2019

581 pages

ISSN:0219-1377

Issue’s Table of Contents

Copyright © 2019 Springer-Verlag London Ltd., part of Springer Nature.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 September 2019

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Luo DBian YYan YYu XHuan JLiu XZhang X(2023)Random Walk on Multiple NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.322166835:8(8417-8430)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TKDE.2022.3221668
Luo DBian YYan YLiu XHuan JZhang XGupta RLiu YShah MRajan STang JPrakash B(2020)Local Community Detection in Multiple NetworksProceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3394486.3403069(266-274)Online publication date: 23-Aug-2020
https://dl.acm.org/doi/10.1145/3394486.3403069
Bian YLuo DYan YCheng WWang WZhang X(2019)Memory-based random walk for multi-query local community detectionKnowledge and Information Systems10.1007/s10115-019-01398-362:5(2067-2101)Online publication date: 9-Sep-2019
https://dl.acm.org/doi/10.1007/s10115-019-01398-3

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents