@inproceedings{Dasgupta2014AverageDegree,
abstract = {Networks are characterized by nodes and edges. While there has been a spate of recent work on estimating the number of nodes in a network, the edge-estimation question appears to be largely unaddressed. In this work we consider the problem of estimating the average degree of a large network using efficient random sampling, where the number of nodes is not known to the algorithm. We propose a new estimator for this problem that relies on access to node samples under a prescribed distribution. Next, we show how to effi- ciently realize this ideal estimator in a random walk setting. Our estimator has a natural and simple implementation using random walks; we bound its performance in terms of the mixing time of the underlying graph. We then show that our estimators are both provably and practically better than many natural estimators for the problem. Our work contrasts with existing theoretical work on estimating average degree, which assume that a uniform random sample of nodes is available and the number of nodes is known.},
address = {Seoul},
author = {Dasgupta, Anirban and Kumar, Ravi and Sarlos, Tamas},
booktitle = {Proc. 23rd Int. Conf. World Wide Web (WWW)},
file = {:home/ecem/Dropbox/mendeley\_sampling\_references/Dasgupta, Kumar, Sarlos/2014\_Dasgupta, Kumar, Sarlos\_On Estimating the Average Degree.pdf:pdf},
keywords = {Average degree,Graph sampling,Random walks,average degree,estimation,random walk},
mendeley-tags = {average degree,estimation,random walk},
pages = {795--806},
title = {{On Estimating the Average Degree}},
year = {2014}
}

{"_id":{"_str":"53b9a5457cc42ee75e000dc4"},"__v":0,"authorIDs":[],"author_short":["Dasgupta, A.","Kumar, R.","Sarlos, T."],"bibbaseid":"dasgupta-kumar-sarlos-onestimatingtheaveragedegree-2014","bibdata":{"bibtype":"inproceedings","type":"inproceedings","abstract":"Networks are characterized by nodes and edges. While there has been a spate of recent work on estimating the number of nodes in a network, the edge-estimation question appears to be largely unaddressed. In this work we consider the problem of estimating the average degree of a large network using efficient random sampling, where the number of nodes is not known to the algorithm. We propose a new estimator for this problem that relies on access to node samples under a prescribed distribution. Next, we show how to effi- ciently realize this ideal estimator in a random walk setting. Our estimator has a natural and simple implementation using random walks; we bound its performance in terms of the mixing time of the underlying graph. We then show that our estimators are both provably and practically better than many natural estimators for the problem. Our work contrasts with existing theoretical work on estimating average degree, which assume that a uniform random sample of nodes is available and the number of nodes is known.","address":"Seoul","author":[{"propositions":[],"lastnames":["Dasgupta"],"firstnames":["Anirban"],"suffixes":[]},{"propositions":[],"lastnames":["Kumar"],"firstnames":["Ravi"],"suffixes":[]},{"propositions":[],"lastnames":["Sarlos"],"firstnames":["Tamas"],"suffixes":[]}],"booktitle":"Proc. 23rd Int. Conf. World Wide Web (WWW)","file":":home/ecem/Dropbox/mendeley_sampling_references/Dasgupta, Kumar, Sarlos/2014_Dasgupta, Kumar, Sarlos_On Estimating the Average Degree.pdf:pdf","keywords":"Average degree,Graph sampling,Random walks,average degree,estimation,random walk","mendeley-tags":"average degree,estimation,random walk","pages":"795–806","title":"On Estimating the Average Degree","year":"2014","bibtex":"@inproceedings{Dasgupta2014AverageDegree,\nabstract = {Networks are characterized by nodes and edges. While there has been a spate of recent work on estimating the number of nodes in a network, the edge-estimation question appears to be largely unaddressed. In this work we consider the problem of estimating the average degree of a large network using efficient random sampling, where the number of nodes is not known to the algorithm. We propose a new estimator for this problem that relies on access to node samples under a prescribed distribution. Next, we show how to effi- ciently realize this ideal estimator in a random walk setting. Our estimator has a natural and simple implementation using random walks; we bound its performance in terms of the mixing time of the underlying graph. We then show that our estimators are both provably and practically better than many natural estimators for the problem. Our work contrasts with existing theoretical work on estimating average degree, which assume that a uniform random sample of nodes is available and the number of nodes is known.},\naddress = {Seoul},\nauthor = {Dasgupta, Anirban and Kumar, Ravi and Sarlos, Tamas},\nbooktitle = {Proc. 23rd Int. Conf. World Wide Web (WWW)},\nfile = {:home/ecem/Dropbox/mendeley\\_sampling\\_references/Dasgupta, Kumar, Sarlos/2014\\_Dasgupta, Kumar, Sarlos\\_On Estimating the Average Degree.pdf:pdf},\nkeywords = {Average degree,Graph sampling,Random walks,average degree,estimation,random walk},\nmendeley-tags = {average degree,estimation,random walk},\npages = {795--806},\ntitle = {{On Estimating the Average Degree}},\nyear = {2014}\n}\n","author_short":["Dasgupta, A.","Kumar, R.","Sarlos, T."],"key":"Dasgupta2014AverageDegree","id":"Dasgupta2014AverageDegree","bibbaseid":"dasgupta-kumar-sarlos-onestimatingtheaveragedegree-2014","role":"author","urls":{},"keyword":["Average degree","Graph sampling","Random walks","average degree","estimation","random walk"],"downloads":0},"bibtype":"inproceedings","biburl":"http://www.utdallas.edu/~emrah.cem/Sampling.bib","creationDate":"2014-07-06T19:36:37.520Z","downloads":0,"keywords":["average degree","graph sampling","random walks","average degree","estimation","random walk"],"search_terms":["estimating","average","degree","dasgupta","kumar","sarlos"],"title":"On Estimating the Average Degree","year":2014,"dataSources":["NzvQMDNRQxZEm47er"]}