Estimating and Sampling Graphs with Multidimensional Random Walks. Ribeiro, B. & Towsley, D. In Proc. 10th ACM SIGCOMM Conf. Internet Measurement (IMC '10), pages 390–403, Melbourne, 2010. abstract bibtex 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 many resources (time, bandwidth, or money). Random walks, which normally require fewer resources per sample, can suffer from large estimation errors in the presence of disconnected or loosely connected graphs. In this work we propose a new m-dimensional random walk that uses m dependent random walkers. We show that the proposed sampling method, which we call Frontier sampling, exhibits all of the nice sampling properties of a regular random walk. At the same time, our simulations over large real world graphs show that, in the presence of disconnected or loosely connected components, Frontier sampling exhibits lower estimation errors than regular random walks. We also show that Frontier sampling is more suitable than random vertex sampling to sample the tail of the degree distribution of the graph.
@inproceedings{Ribeiro2010,
abstract = {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 many resources (time, bandwidth, or money). Random walks, which normally require fewer resources per sample, can suffer from large estimation errors in the presence of disconnected or loosely connected graphs. In this work we propose a new m-dimensional random walk that uses m dependent random walkers. We show that the proposed sampling method, which we call Frontier sampling, exhibits all of the nice sampling properties of a regular random walk. At the same time, our simulations over large real world graphs show that, in the presence of disconnected or loosely connected components, Frontier sampling exhibits lower estimation errors than regular random walks. We also show that Frontier sampling is more suitable than random vertex sampling to sample the tail of the degree distribution of the graph.},
address = {Melbourne},
author = {Ribeiro, Bruno and Towsley, Don},
booktitle = {Proc. 10th ACM SIGCOMM Conf. Internet Measurement (IMC '10)},
file = {:home/ecem/Dropbox/mendeley\_sampling\_references/Ribeiro, Towsley/2010\_Ribeiro, Towsley\_Estimating and sampling graphs with multidimensional random walks.pdf:pdf},
keywords = {Estimating and Sampling Graphs with Multidimension,degree distribution,frontier sampling,graph sampling,random walk},
mendeley-tags = {degree distribution,frontier sampling,graph sampling,random walk},
pages = {390--403},
title = {{Estimating and Sampling Graphs with Multidimensional Random Walks}},
year = {2010}
}
Downloads: 0
{"_id":{"_str":"53b9a5457cc42ee75e000dc6"},"__v":0,"authorIDs":[],"author_short":["Ribeiro, B.","Towsley, D."],"bibbaseid":"ribeiro-towsley-estimatingandsamplinggraphswithmultidimensionalrandomwalks-2010","bibdata":{"bibtype":"inproceedings","type":"inproceedings","abstract":"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 many resources (time, bandwidth, or money). Random walks, which normally require fewer resources per sample, can suffer from large estimation errors in the presence of disconnected or loosely connected graphs. In this work we propose a new m-dimensional random walk that uses m dependent random walkers. We show that the proposed sampling method, which we call Frontier sampling, exhibits all of the nice sampling properties of a regular random walk. At the same time, our simulations over large real world graphs show that, in the presence of disconnected or loosely connected components, Frontier sampling exhibits lower estimation errors than regular random walks. We also show that Frontier sampling is more suitable than random vertex sampling to sample the tail of the degree distribution of the graph.","address":"Melbourne","author":[{"propositions":[],"lastnames":["Ribeiro"],"firstnames":["Bruno"],"suffixes":[]},{"propositions":[],"lastnames":["Towsley"],"firstnames":["Don"],"suffixes":[]}],"booktitle":"Proc. 10th ACM SIGCOMM Conf. Internet Measurement (IMC '10)","file":":home/ecem/Dropbox/mendeley_sampling_references/Ribeiro, Towsley/2010_Ribeiro, Towsley_Estimating and sampling graphs with multidimensional random walks.pdf:pdf","keywords":"Estimating and Sampling Graphs with Multidimension,degree distribution,frontier sampling,graph sampling,random walk","mendeley-tags":"degree distribution,frontier sampling,graph sampling,random walk","pages":"390–403","title":"Estimating and Sampling Graphs with Multidimensional Random Walks","year":"2010","bibtex":"@inproceedings{Ribeiro2010,\nabstract = {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 many resources (time, bandwidth, or money). Random walks, which normally require fewer resources per sample, can suffer from large estimation errors in the presence of disconnected or loosely connected graphs. In this work we propose a new m-dimensional random walk that uses m dependent random walkers. We show that the proposed sampling method, which we call Frontier sampling, exhibits all of the nice sampling properties of a regular random walk. At the same time, our simulations over large real world graphs show that, in the presence of disconnected or loosely connected components, Frontier sampling exhibits lower estimation errors than regular random walks. We also show that Frontier sampling is more suitable than random vertex sampling to sample the tail of the degree distribution of the graph.},\naddress = {Melbourne},\nauthor = {Ribeiro, Bruno and Towsley, Don},\nbooktitle = {Proc. 10th ACM SIGCOMM Conf. Internet Measurement (IMC '10)},\nfile = {:home/ecem/Dropbox/mendeley\\_sampling\\_references/Ribeiro, Towsley/2010\\_Ribeiro, Towsley\\_Estimating and sampling graphs with multidimensional random walks.pdf:pdf},\nkeywords = {Estimating and Sampling Graphs with Multidimension,degree distribution,frontier sampling,graph sampling,random walk},\nmendeley-tags = {degree distribution,frontier sampling,graph sampling,random walk},\npages = {390--403},\ntitle = {{Estimating and Sampling Graphs with Multidimensional Random Walks}},\nyear = {2010}\n}\n","author_short":["Ribeiro, B.","Towsley, D."],"key":"Ribeiro2010","id":"Ribeiro2010","bibbaseid":"ribeiro-towsley-estimatingandsamplinggraphswithmultidimensionalrandomwalks-2010","role":"author","urls":{},"keyword":["Estimating and Sampling Graphs with Multidimension","degree distribution","frontier sampling","graph sampling","random walk"],"downloads":0},"bibtype":"inproceedings","biburl":"http://www.utdallas.edu/~emrah.cem/Sampling.bib","creationDate":"2014-07-06T19:36:37.529Z","downloads":0,"keywords":["estimating and sampling graphs with multidimension","degree distribution","frontier sampling","graph sampling","random walk"],"search_terms":["estimating","sampling","graphs","multidimensional","random","walks","ribeiro","towsley"],"title":"Estimating and Sampling Graphs with Multidimensional Random Walks","year":2010,"dataSources":["NzvQMDNRQxZEm47er"]}