{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:27:32Z","timestamp":1787333252584,"version":"build-2736575974"},"reference-count":56,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>We address the problem of obtaining by local computation a sample of a graph such that the vertices are sampled uniformly. The presented solution uses a Markov chain to combine a rapidly mixing random walk that does not reach a uniform distribution with a slow-mixing walk that does. The resulting chain mixes at a notably faster rate than the standard uniform random walk and can be simulated exactly using only local information.<\/jats:p>","DOI":"10.1137\/080716086","type":"journal-article","created":{"date-parts":[[2010,9,30]],"date-time":"2010-09-30T18:48:34Z","timestamp":1285872514000},"page":"2937-2963","source":"Crossref","is-referenced-by-count":2,"title":["Scalable Uniform Graph Sampling by Local Computation"],"prefix":"10.1137","volume":"32","author":[{"given":"Satu Elisa","family":"Schaeffer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,9,29]]},"reference":[{"key":"R1","unstructured":"A.C. Achilles,\n                      The Collection of Computer Science Bibliographies\n                      , http:\/\/liinwww.ira.uka. de\/bibliography\/ (2002)."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"D. Achlioptas, A. Clauset, D. Kempe, and C. Moore,\n                      On the bias of traceroute sampling, or: Power-law degree distributions in regular graphs)\n                      , in Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing (STOC), H. N. Gabow and R. Fagin, eds., ACM Press, New York, 2005, pp. 694\u2013703.","DOI":"10.1145\/1060590.1060693"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"P. Baldi, P. Frasconi, and P. Smyth,\n                      Modeling the Internet and the Web: Probabilistic Methods and Algorithms\n                      , John Wiley & Sons, Chichester, UK, 2003.","DOI":"10.1002\/047086799X"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Z. Bar-Yossef, S. R. Kumar, and D. Sivakumar,\n                      Sampling algorithms: Lower bounds and applications\n                      , in Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing (STOC), ACM Press, New York, 2001, pp. 266\u2013275.","DOI":"10.1145\/380752.380810"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-4371(01)00369-7"},{"key":"R6","unstructured":"E. Behrends,\n                      Introduction to Markov Chains, with Special Emphasis on Rapid Mixing\n                      , Vieweg & Sohn, Braunschweig\/Wiesbaden, Germany, 2000."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144503423264"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(00)00083-9"},{"key":"R9","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1080\/10618600.1997.10474741","volume":"6","author":"Brooks S. P.","year":"1997","journal-title":"J. Comput. Graph. Statist.","ISSN":"https:\/\/id.crossref.org\/issn\/1061-8600","issn-type":"print"},{"key":"R10","unstructured":"D. Chakrabarti, Y. Zhan, D. Blandford, C. Faloutsos, and G. Blelloch,\n                      Netmine: New mining tools for large graphs\n                      , presented at the 4th SIAM International Conference on Data Mining, Workshop on Link Analysis, Counterterrorism, and Privacy, Buena Vista, FL, 2004. Available online at http:\/\/www-users.cs.umn.edu\/~aleks\/sdm04~\/talks.htm."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9574.2005.00277.x"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson,\n                      Further applications of random sampling to computational geometry\n                      , in Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (STOC), ACM Press, New York, 1986, pp. 414\u2013423.","DOI":"10.1145\/12130.12173"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson,\n                      Applications of random sampling in computational geometry\n                      , II, in Proceedings of the Fourth Annual Symposium on Computational Geometry, ACM Press, New York, 1998, pp. 1\u201311.","DOI":"10.1145\/73393.73394"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.94.018701"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2006.08.027"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.12.009"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"S. Datta and H. Kargupta,\n                      Uniform data sampling from a peer-to-peer network\n                      , in Proceedings of the Twenty-Seventh International Conference on Distributed Computing Systems, IEEE Computer Society, Washington, DC, 2007, p. 50.","DOI":"10.1109\/ICDCS.2007.6238553"},{"key":"R18","first-page":"65","volume":"149","author":"Deo N.","year":"2001","journal-title":"Congr. Numer.","ISSN":"https:\/\/id.crossref.org\/issn\/0384-9864","issn-type":"print"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.65.066122"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1080\/00018730110112519"},{"key":"R21","unstructured":"J. W. Eaton et al.\n                      GNU Octave\u2014A High-Level Language for Numerical Computations\n                      , http:\/\/www.gnu.org\/software\/octave\/ (2010)."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00081"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"M. Faloutsos, P. Faloutsos, and C. Faloutsos,\n                      On power-law relationships of the Internet topology\n                      , in Proceedings of the ACM SIGCOMM'99 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, ACM Press, New York, 1999, pp. 251\u2013262.","DOI":"10.1145\/316188.316229"},{"key":"R24","unstructured":"N. G. Feamster,\n                      Proactive Techniques for Correct and Predictable Internet Routing\n                      , Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA, 2006."},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1145\/774763.774767"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"B. G\u00e4rtner and E. Welzl,\n                      Random sampling in geometric optimization: New insights and applications\n                      , in Proceedings of the Sixteenth Annual Symposium on Computational Geometry, ACM Press, New York, 2000, pp. 91\u201399.","DOI":"10.1145\/336154.336186"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"D. Gillman,\n                      A Chernoff bound for random walks on expander graphs\n                      , in Proceedings of the Thirty-Fourth Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Washington, DC, 1993, pp. 680\u2013691.","DOI":"10.1109\/SFCS.1993.366819"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"G. R. Grimmett and D. R. Stirzaker,\n                      Probability and Random Processes\n                      , 3rd ed., Oxford University Press, Oxford, UK, 2001.","DOI":"10.1093\/oso\/9780198572237.001.0001"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"I. Gutman,\n                      The energy of a graph: Old and new results\n                      , in Algebraic Combinatorics and Applications, A. Betten, A. Kohnert, R. Laue, and A. Wassermann, eds., Springer-Verlag, Berlin, 2001, pp. 196\u2013211.","DOI":"10.1007\/978-3-642-59448-9_13"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2005.09.008"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth131"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199712)11:4<299::AID-RSA2>3.0.CO;2-U"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"D. R. Karger,\n                      Random sampling in cut, flow, and network design problems\n                      , in Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing (STOC), ACM Press, New York, 1994, pp. 648\u2013657.","DOI":"10.1145\/195058.195422"},{"key":"R35","unstructured":"D. R. Karger,\n                      Random Sampling in Graph Optimization Problems\n                      , Ph.D. thesis, Stanford University, Stanford, CA, 1995."},{"key":"R36","doi-asserted-by":"crossref","unstructured":"J. M. Kleinberg, S. R. Kumar, P. Raghavan, S. Rajagopalan, and A. S. Tomkins,\n                      The Web as a graph: Measurements, models, and methods\n                      , in Proceedings of the Fifth Annual International Conference on Computing and Combinatorics, T. Asano, H. Imai, D. Lee, S. Nakano, and T. Tokuyama, eds., Lecture Notes in Comput. Sci. 1627, Springer, Berlin, 1999, pp. 1\u201317.","DOI":"10.1007\/3-540-48686-0_1"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1145\/1273445.1273450"},{"key":"R38","unstructured":"V. Krishnamurty, J. Sun, M. Faloutsos, and S. Tauro,\n                      Sampling Internet topologies: How small can we go?\n                      , in Proceedings of the International Conference on Internet Computing (Las Vegas, NV, 2003,) H. R. Arabnia and Y. Mun, eds., CSREA Press, Athens, GA, pp. 577\u2013580."},{"key":"R39","unstructured":"R. Lehoucq, K. Maschhoff, D. Sorensen, and C. Yang, Arpack\n                      \u2014Arnoldi Package\n                      , http:\/\/www.caam.rice.edu\/software\/ARPACK\/ (2008)."},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2006.10129122"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.98.2.404"},{"key":"R42","unstructured":"M. E. J. Newman,\n                      A Measure of Betweenness Centrality Based on Random Walks\n                      , preprint, http:\/\/arxiv.org\/abs\/cond-mat\/0309045 (2003)."},{"key":"R43","unstructured":"P. Orponen and S. E. Schaeffer,\n                      Efficient Algorithms for Sampling and Clustering of Large Nonuniform Networks\n                      , preprint, http:\/\/arxiv.org\/cond-mat\/0406048 (2004)."},{"key":"R44","unstructured":"P. Orponen, S. E. Schaeffer, and V. A. Gayt\u00e1n,\n                      Locally Computable Approximations for Spectral Clustering and Absorption Times of Random Walks\n                      , preprint, http:\/\/arxiv.org\/abs\/0810.4061 (2008)."},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1145\/1163593.1163602"},{"key":"R46","doi-asserted-by":"crossref","unstructured":"V. Paxson and S. Floyd,\n                      Why we don't know how to simulate the Internet\n                      , in Proceedings of the 1997 Winter Simulation Conference, ACM Press, New York, 1997, pp. 1037\u20131044.","DOI":"10.1145\/268437.268737"},{"key":"R47","unstructured":"S. E. Schaeffer,\n                      Algorithms for Nonuniform Networks\n                      , Research Report A102, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, 2006."},{"key":"R48","doi-asserted-by":"crossref","unstructured":"B. Selman, H. A. Kautz, and B. Cohen,\n                      Local search strategies for satisfiability testing\n                      , in Cliques, Coloring and Satisfiability: Second DIMACS Implementation Challenge, D. S. Johnson and M. A. Trick, eds., DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 26, AMS, Providence, RI, 1996, pp. 521\u2013532.","DOI":"10.1090\/dimacs\/026\/25"},{"key":"R49","doi-asserted-by":"crossref","unstructured":"A. Sinclair,\n                      Improved bounds for mixing rates of marked chains and multicommodity flow\n                      , in Proceedings of the First Latin American Symposium on Theoretical Informatics, Lecture Notes in Comput. Sci. 583, Springer-Verlag, London, 1992, pp. 474\u2013487.","DOI":"10.1007\/BFb0023849"},{"key":"R50","doi-asserted-by":"crossref","unstructured":"A. Sinclair,\n                      Algorithms for Random Generation & Counting: A Markov Chain Approach\n                      , Birkh\u00e4user Boston, Boston, MA, 1993.","DOI":"10.1007\/978-1-4612-0323-0"},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/18.suppl_1.S136"},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176325750"},{"key":"R53","unstructured":"S. E. Virtanen,\n                      Properties of Nonuniform Random Graph Models\n                      , Research Report A77, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, 2003."},{"key":"R54","doi-asserted-by":"crossref","unstructured":"D. Vukadinovi\u0107, P. Huang, and T. Erlebach,\n                      On the spectrum and structure of Internet topology graphs\n                      , in Proceedings of the Second International Workshop on Innovative Internet Computing Systems, H. Unger, T. B\u00f6hme, and A. R. Mikler, eds., Lecture Notes in Comput. Sci. 2346, Springer-Verlag GmbH, Berlin\/Heidelberg, 2002, pp. 83\u201395.","DOI":"10.1007\/3-540-48080-3_8"},{"key":"R55","unstructured":"W. Wei, J. Erenrich, and B. Selman,\n                      Towards efficient sampling: Exploiting random walk strategies\n                      , in Proceedings of the Nineteenth National Conference on Artificial Intelligence and Sixteenth Conference on Innovative Applications of Artificial Intelligence, D. L. McGuinness and G. Ferguson, eds., AAAI Press\/The MIT Press, Menlo Park, CA\/Cambridge, MA, 2004, pp. 670\u2013676."},{"key":"R56","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/18.4.536"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080716086","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:45:08Z","timestamp":1787330708000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080716086"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":56,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/080716086"],"URL":"https:\/\/doi.org\/10.1137\/080716086","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}