More Web Proxy on the site http://driver.im/

research-article

On Sampling Nodes in a Network

Authors:

Flavio Chiericetti,

Anirban Dasgupta,

Silvio Lattanzi,

Tamás SarlósAuthors Info & Claims

WWW '16: Proceedings of the 25th International Conference on World Wide Web

Pages 471 - 481

https://doi.org/10.1145/2872427.2883045

Published: 11 April 2016 Publication History

Abstract

Random walk is an important tool in many graph mining applications including estimating graph parameters, sampling portions of the graph, and extracting dense communities. In this paper we consider the problem of sampling nodes from a large graph according to a prescribed distribution by using random walk as the basic primitive. Our goal is to obtain algorithms that make a small number of queries to the graph but output a node that is sampled according to the prescribed distribution. Focusing on the uniform distribution case, we study the query complexity of three algorithms and show a near-tight bound expressed in terms of the parameters of the graph such as average degree and the mixing time. Both theoretically and empirically, we show that some algorithms are preferable in practice than the others. We also extend our study to the problem of sampling nodes according to some polynomial function of their degrees; this has implications for designing efficient algorithms for applications such as triangle counting.

References

[1]

Z. Bar-Yossef, A. C. Berg, S. Chien, J. Fakcharoenphol, and D. Weitz. Approximating aggregate queries about Web pages via random walks. In VLDB, pages 535--544, 2000.

Digital Library

[2]

Z. Bar-Yossef and M. Gurevich. Random sampling from a search engine's index. J. ACM, 55(5), 2008.

Digital Library

[3]

S. Boyd, P. Diaconis, and L. Xiao. Fastest mixing Markov chain on a graph. SIAM Review, 46(4):667--689, 2004.

Digital Library

[4]

J. Cheeger. A lower bound for the smallest eigenvalue of the Laplacian. In R. C. Gunning, editor, Problems in Analysis (Papers dedicated to Salomon Bochner), pages 195--199. Princeton Univ. Press, 1970.

[5]

C. Cooper, T. Radzik, and Y. Siantos. Estimating network parameters using random walks. In CASoN, pages 33--40, 2012.

[6]

A. Dasgupta, R. Kumar, and T. Sarlós. On estimating the average degree. In WWW, pages 795--806, 2014.

Digital Library

[7]

M. Gjoka, M. Kurant, C. Butts, and A. Markopoulou. Walking in Facebook: A case study of unbiased sampling of OSNs. In INFOCOM, pages 1--9, 2010.

Digital Library

[8]

V. Guruswami. Rapidly mixing Markov chains: A comparison of techniques. A Survey, 2000.

[9]

S. J. Hardiman and L. Katzir. Estimating clustering coefficients and size of social networks via random walk. In WWW, pages 539--550, 2013.

Digital Library

[10]

W. K. Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57(1):97--109, 1970.

[11]

M. Hildebrand. Random walks on random simple graphs. Random Structures & Algorithms, 8(4):301--318, 1996.

[12]

M. Jha, C. Seshadhri, and A. Pinar. Path sampling: A fast and provable method for estimating 4-vertex subgraph counts. In WWW, pages 495--505, 2015.

Digital Library

[13]

L. Katzir, E. Liberty, and O. Somekh. Estimating sizes of social networks via biased sampling. In WWW, pages 597--606, 2011.

Digital Library

[14]

L. Katzir, E. Liberty, and O. Somekh. Framework and algorithms for network bucket testing. In WWW, pages 1029--1036, 2012.

Digital Library

[15]

J. Leskovec and C. Faloutsos. Sampling from large graphs. In KDD, pages 631--636, 2006.

Digital Library

[16]

D. Levin, Y. Peres, and E. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, 2009.

[17]

R.-H. Li, J. X. Yu, L. Qin, R. Mao, and T. Jin. On random walk based graph sampling. In ICDE, pages 927--938, 2015.

[18]

L. Lovász and P. Winkler. Efficient stopping rules for Markov chains. In STOC, pages 76--82, 1995.

Digital Library

[19]

A. Nazi, Z. Zhou, S. Thirumuruganathan, N. Zhang, and G. Das. Walk, not wait: Faster sampling over online social networks. PVLDB, 8(6):678--689, 2015.

Digital Library

[20]

B. Ribeiro and D. Towsley. Estimating and sampling graphs with multidimensional random walks. In IMC, pages 390--403, 2010.

Digital Library

[21]

C. Seshadhri, A. Pinar, and T. G. Kolda. Wedge sampling for computing clustering coefficients and triangle counts on large graphs. Statistical Analysis and Data Mining, 7(4):294--307, 2014.

Digital Library

[22]

A. Sinclair. Improved bounds for mixing rates of Markov chains and multicommodity flow. Combinatorics, Probability, & Computing 1, pages 351--370, 1992.

[23]

D. Stutzbach, R. Rejaie, N. G. Duffield, S. Sen, and W. Willinger. On unbiased sampling for unstructured peer-to-peer networks. IEEE/ACM Trans. Netw., 17(2):377--390, 2009.

Digital Library

[24]

S. Ye and F. Wu. Estimating the size of online social networks. In SocialCom, pages 169--176, 2010.

Digital Library

[25]

Z. Zhou, N. Zhang, Z. Gong, and G. Das. Faster random walks by rewiring online social networks on-the-fly. In ICDE, pages 769--780, 2013.

Digital Library

Cited By

Basu SKōshima NEden TBen-Eliezer OSeshadhri CNejdl WAuer SKarras OCha MMoens MNajork M(2025)A Sublinear Algorithm for Approximate Shortest Paths in Large NetworksProceedings of the Eighteenth ACM International Conference on Web Search and Data Mining10.1145/3701551.3703512(20-29)Online publication date: 10-Mar-2025
https://dl.acm.org/doi/10.1145/3701551.3703512
Kim HMoon HBu FKo JShin K(2025)Estimating simplet counts via samplingThe VLDB Journal10.1007/s00778-024-00890-934:2Online publication date: 18-Jan-2025
https://doi.org/10.1007/s00778-024-00890-9
Hasegawa THironaka SShudo K(2024)Estimation of Graph Features Based on Random Walks Using Neighbors’ PropertiesWeb Information Systems Engineering – WISE 202410.1007/978-981-96-0567-5_32(456-466)Online publication date: 3-Dec-2024
https://doi.org/10.1007/978-981-96-0567-5_32
Show More Cited By

Index Terms

On Sampling Nodes in a Network
1. Human-centered computing
  1. Collaborative and social computing
    1. Collaborative and social computing design and evaluation methods
      1. Social network analysis
2. Theory of computation
  1. Design and analysis of algorithms
    1. Streaming, sublinear and near linear time algorithms
      1. Sketching and sampling
  2. Randomness, geometry and discrete structures
    1. Random walks and Markov chains

Recommendations

Estimating and sampling graphs with multidimensional random walks
IMC '10: Proceedings of the 10th ACM SIGCOMM conference on Internet measurement

Estimating characteristics of large graphs via sampling is a vital part of the study of complex networks. Current sampling methods such as (independent) random vertex and random walks are useful but have drawbacks. Random vertex sampling may require too ...
Expander properties and the cover time of random intersection graphs

We investigate important combinatorial and algorithmic properties of G"n","m","p random intersection graphs. In particular, we prove that with high probability (a) random intersection graphs are expanders, (b) random walks on such graphs are ''rapidly ...
Unbiased Sampling of Bipartite Graph
CYBERC '11: Proceedings of the 2011 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery

Increasing size of online social networks (OSNs) has given rise to sampling method studies that provide a relatively small but representative sample of large-scale OSNs so that the measurement and analysis burden can be affordable. So far, a number of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

WWW '16: Proceedings of the 25th International Conference on World Wide Web

April 2016

1482 pages

ISBN:9781450341431

General Chairs:
Jacqueline Bourdeau
Tele-university (TELUQ), Montreal, QC, Canada
,
Jim A. Hendler
Rensselaer Polytechnic Institute, Troy, NY, USA
,
Roger Nkambou Nkambou
Université du Québec à Montréal, Montreal, QC, Canada
,
Program Chairs:
Ian Horrocks
University of Oxford, UK
,
Ben Y. Zhao
University of California at Santa Barbara, CA, USA

Copyright © 2016 Copyright is held by the International World Wide Web Conference Committee (IW3C2).

Sponsors

IW3C2: International World Wide Web Conference Committee

In-Cooperation

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

International World Wide Web Conferences Steering Committee

Republic and Canton of Geneva, Switzerland

Publication History

Published: 11 April 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

SIR Grant
Google Focused Research Award
ERC Starting Grant DMAP
Google Faculty Research Award

Conference

WWW '16

Sponsor:

IW3C2

WWW '16: 25th International World Wide Web Conference

April 11 - 15, 2016

Québec, Montréal, Canada

Acceptance Rates

WWW '16 Paper Acceptance Rate 115 of 727 submissions, 16%;

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
736
Total Downloads

Downloads (Last 12 months)41
Downloads (Last 6 weeks)7

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Basu SKōshima NEden TBen-Eliezer OSeshadhri CNejdl WAuer SKarras OCha MMoens MNajork M(2025)A Sublinear Algorithm for Approximate Shortest Paths in Large NetworksProceedings of the Eighteenth ACM International Conference on Web Search and Data Mining10.1145/3701551.3703512(20-29)Online publication date: 10-Mar-2025
https://dl.acm.org/doi/10.1145/3701551.3703512
Kim HMoon HBu FKo JShin K(2025)Estimating simplet counts via samplingThe VLDB Journal10.1007/s00778-024-00890-934:2Online publication date: 18-Jan-2025
https://doi.org/10.1007/s00778-024-00890-9
Hasegawa THironaka SShudo K(2024)Estimation of Graph Features Based on Random Walks Using Neighbors’ PropertiesWeb Information Systems Engineering – WISE 202410.1007/978-981-96-0567-5_32(456-466)Online publication date: 3-Dec-2024
https://doi.org/10.1007/978-981-96-0567-5_32
Preti GDe Francisci Morales GRiondato M(2023)MaNIACS: Approximate Mining of Frequent Subgraph Patterns through SamplingACM Transactions on Intelligent Systems and Technology10.1145/358725414:3(1-29)Online publication date: 13-Apr-2023
https://dl.acm.org/doi/10.1145/3587254
Cousins CWohlgemuth CRiondato M(2023) Bavarian: Betweenness Centrality Approximation with Variance-aware Rademacher AveragesACM Transactions on Knowledge Discovery from Data10.1145/357702117:6(1-47)Online publication date: 6-Mar-2023
https://dl.acm.org/doi/10.1145/3577021
Nakajima KShudo K(2023)Random Walk Sampling in Social Networks Involving Private NodesACM Transactions on Knowledge Discovery from Data10.1145/356138817:4(1-28)Online publication date: 24-Feb-2023
https://dl.acm.org/doi/10.1145/3561388
Zhang LZhang ZWang GYuan Y(2023)Efficiently Sampling and Estimating Hypergraphs By Hybrid Random Walk2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00102(1273-1285)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00102
Tětek JThorup MLeonardi SGupta A(2022)Edge sampling and graph parameter estimation via vertex neighborhood accessesProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520059(1116-1129)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520059
Ben-Eliezer OEden TOren JFotakis DSelcuk Candan KLiu HAkoglu LLuna Dong XTang J(2022)Sampling Multiple Nodes in Large NetworksProceedings of the Fifteenth ACM International Conference on Web Search and Data Mining10.1145/3488560.3498383(37-47)Online publication date: 11-Feb-2022
https://dl.acm.org/doi/10.1145/3488560.3498383
Ponciano JLinhares CRocha LFaria ETravençolo BHong JBures MPark JCerny T(2022)Combining clutter reduction methods for temporal network visualizationProceedings of the 37th ACM/SIGAPP Symposium on Applied Computing10.1145/3477314.3507018(1748-1755)Online publication date: 25-Apr-2022
https://dl.acm.org/doi/10.1145/3477314.3507018
Show More Cited By

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten