{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T10:49:24Z","timestamp":1775040564325,"version":"3.50.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,1,29]],"date-time":"2016-01-29T00:00:00Z","timestamp":1454025600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2016,2,3]]},"abstract":"<jats:p>Many online social networks feature restrictive web interfaces that only allow the query of a user\u2019s local neighborhood. To enable analytics over such an online social network through its web interface, many recent efforts use Markov Chain Monte Carlo (MCMC) methods such as random walks to sample users in the social network and thereby support analytics based on the samples. The problem with such an approach, however, is the large amount of queries often required for a random walk to converge to a desired (stationary) sampling distribution. In this article, we consider a novel problem of enabling a faster random walk over online social networks by \u201crewiring\u201d the social network on-the-fly. Specifically, we develop a Modified TOpology Sampling (MTO-Sampling) scheme that, by using only information exposed by the restrictive web interface, constructs a \u201cvirtual\u201d random-walk-friendly overlay topology of the social network while performing a random walk and ensures that the random walk follows the modified overlay topology rather than the original one. We describe in this article instantiations of MTO-Sampling for various types of random walks, such as Simple Random Walk (MTO-SRW), Metropolis-Hastings Random Walk (MTO-MHRW), and General Random Walk (MTO-GRW). We not only rigidly prove that MTO-Sampling improves the efficiency of sampling, but we also demonstrate the significance of such improvement through experiments on real-world online social networks such as Google Plus, Epinion, Facebook, etc.<\/jats:p>","DOI":"10.1145\/2847526","type":"journal-article","created":{"date-parts":[[2016,2,1]],"date-time":"2016-02-01T20:37:54Z","timestamp":1454359074000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["Faster Random Walks by Rewiring Online Social Networks On-the-Fly"],"prefix":"10.1145","volume":"40","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3312-7732","authenticated-orcid":false,"given":"Zhuojie","family":"Zhou","sequence":"first","affiliation":[{"name":"George Washington University, Washington, DC"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nan","family":"Zhang","sequence":"additional","affiliation":[{"name":"George Washington University, Washington, DC"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhiguo","family":"Gong","sequence":"additional","affiliation":[{"name":"University of Macau"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gautam","family":"Das","sequence":"additional","affiliation":[{"name":"University of Texas at Arlington, Arlington, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,1,29]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data.  Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1117454.1117457"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378557"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144503423264"},{"key":"e_1_2_1_6_1","unstructured":"Stephen Boyd A. Ghosh and B. Prabhakar. 2005. Mixing times for random walks on geometric random graphs. SIAM ANALCO (2005).  Stephen Boyd A. Ghosh and B. Prabhakar. 2005. Mixing times for random walks on geometric random graphs. SIAM ANALCO (2005)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2006.07.018"},{"key":"e_1_2_1_8_1","volume-title":"The small world phenomenon in hybrid power law graphs","author":"Chung Fan","unstructured":"Fan Chung and Linyuan Lu. 2004. The small world phenomenon in hybrid power law graphs . In Complex Networks, Eli Ben-Naim, Hans Frauenfelder, and Zoltan Toroczkai (Eds.). Vol. 650 . Springer Berlin Heidelberg , 89--104. Fan Chung and Linyuan Lu. 2004. The small world phenomenon in hybrid power law graphs. In Complex Networks, Eli Ben-Naim, Hans Frauenfelder, and Zoltan Toroczkai (Eds.). Vol. 650. Springer Berlin Heidelberg, 89--104."},{"key":"e_1_2_1_9_1","volume-title":"Paul Erdos is Eighty 2, 157--172","author":"Chung Fan R. K.","year":"1996","unstructured":"Fan R. K. Chung . 1996. Laplacians of graphs and Cheeger's inequalities. Combinatorics , Paul Erdos is Eighty 2, 157--172 ( 1996 ), 13--2. Fan R. K. Chung. 1996. Laplacians of graphs and Cheeger's inequalities. Combinatorics, Paul Erdos is Eighty 2, 157--172 (1996), 13--2."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1214\/09-AOS735"},{"key":"e_1_2_1_11_1","volume-title":"Bayesian Statistics","author":"Geweke John","unstructured":"John Geweke . 1992. Evaluating the accuracy of sampling-based approaches to the calculation of posterior moments . In Bayesian Statistics . University Press , 169--193. John Geweke. 1992. Evaluating the accuracy of sampling-based approaches to the calculation of posterior moments. In Bayesian Statistics. University Press, 169--193."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Charles J. Geyer. 1992. Practical markov chain monte carlo. Statistical Science 473--483.  Charles J. Geyer. 1992. Practical markov chain monte carlo. Statistical Science 473--483.","DOI":"10.1214\/ss\/1177011137"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1833515.1833840"},{"key":"e_1_2_1_14_1","volume-title":"Hammersley and K William Morton","author":"John","year":"1954","unstructured":"John M. Hammersley and K William Morton . 1954 . Poor man\u2019s Monte Carlo. Journal of the Royal Statistical Society . Series B (Methodological) (1954), 23--38. John M. Hammersley and K William Morton. 1954. Poor man\u2019s Monte Carlo. Journal of the Royal Statistical Society. Series B (Methodological) (1954), 23--38."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/57.1.97"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000172.2000178"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963489"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993744.1993773"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254756.2254795"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150479"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"key":"e_1_2_1_22_1","first-page":"1","article-title":"Random walks on graphs: A survey","volume":"2","author":"Lov\u00e1sz L.","year":"1993","unstructured":"L. Lov\u00e1sz . 1993 . Random walks on graphs: A survey . Combinatorics, Paul Erdos Is Eighty 2 , 1 (1993), 1 -- 46 . L. Lov\u00e1sz. 1993. Random walks on graphs: A survey. Combinatorics, Paul Erdos Is Eighty 2, 1 (1993), 1--46.","journal-title":"Combinatorics, Paul Erdos Is Eighty"},{"key":"e_1_2_1_23_1","unstructured":"Julian McAuley and Jure Leskovec. 2012. Learning to discover social circles in ego networks. In NIPS.  Julian McAuley and Jure Leskovec. 2012. Learning to discover social circles in ego networks. In NIPS."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1879141.1879191"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Matthew Richardson Rakesh Agrawal and Pedro Domingos. 2003. Trust management for the semantic web. In ISWC.  Matthew Richardson Rakesh Agrawal and Pedro Domingos. 2003. Trust management for the semantic web. In ISWC.","DOI":"10.1007\/978-3-540-39718-2_23"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1699114"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772778"},{"key":"e_1_2_1_28_1","volume-title":"Moore","author":"Sarkar Purnamrita","year":"2010","unstructured":"Purnamrita Sarkar , Deepayan Chakrabarti , and Andrew W . Moore . 2010 . Theoretical justification of popular link prediction heuristics. In COLT. Purnamrita Sarkar, Deepayan Chakrabarti, and Andrew W. Moore. 2010. Theoretical justification of popular link prediction heuristics. In COLT."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1117454.1117459"},{"key":"e_1_2_1_30_1","unstructured":"Gomez F. Sun Y. and J. Schmidhuber. 2010. Improving asymptotic performance of Markov chain Monte-Carlo by inserting vortices. In NIPS.  Gomez F. Sun Y. and J. Schmidhuber. 2010. Improving asymptotic performance of Markov chain Monte-Carlo by inserting vortices. In NIPS."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544873"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2847526","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2847526","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:43:27Z","timestamp":1750225407000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2847526"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,29]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,2,3]]}},"alternative-id":["10.1145\/2847526"],"URL":"https:\/\/doi.org\/10.1145\/2847526","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1,29]]},"assertion":[{"value":"2013-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-01-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}