{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:30:06Z","timestamp":1750221006186,"version":"3.41.0"},"reference-count":76,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,3,26]],"date-time":"2019-03-26T00:00:00Z","timestamp":1553558400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1423151","CNS-1824518"],"award-info":[{"award-number":["CNS-1423151","CNS-1824518"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2019,3,26]]},"abstract":"<jats:p>Markov Chain Monte Carlo (MCMC) has been the de facto technique for sampling and inference of large graphs such as online social networks. At the heart of MCMC lies the ability to construct an ergodic Markov chain that attains any given stationary distribution $\\boldsymbol\u03c0 $, often in the form of random walks or crawling agents on the graph. Most of the works around MCMC, however, presume that the graph is undirected or has reciprocal edges, and become inapplicable when the graph is directed and non-reciprocal. Here we develop a similar framework for directed graphs, which we call Non-Markovian Monte Carlo (NMMC), by establishing a mapping to convert $\\boldsymbol\u03c0 into the quasi-stationary distribution of a carefully constructed transient Markov chain on an extended state space. As applications, we demonstrate how to achieve any given distribution $\\boldsymbol\u03c0 $ on a directed graph and estimate the eigenvector centrality using a set of non-Markovian, history-dependent random walks on the same graph in a distributed manner. We also provide numerical results on various real-world directed graphs to confirm our theoretical findings, and present several practical enhancements to make our NMMC method ready for practical use in most directed graphs. To the best of our knowledge, the proposed NMMC framework for directed graphs is the first of its kind, unlocking all the limitations set by the standard MCMC methods for undirected graphs.<\/jats:p>","DOI":"10.1145\/3322205.3311086","type":"journal-article","created":{"date-parts":[[2020,3,26]],"date-time":"2020-03-26T13:12:37Z","timestamp":1585228357000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Non-Markovian Monte Carlo on Directed Graphs"],"prefix":"10.1145","volume":"3","author":[{"given":"Chul-Ho","family":"Lee","sequence":"first","affiliation":[{"name":"Florida Institute of Technology, Melbourne, FL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Min","family":"Kang","sequence":"additional","affiliation":[{"name":"North Carolina State University, Raleigh, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Do Young","family":"Eun","sequence":"additional","affiliation":[{"name":"North Carolina State University, Raleigh, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,3,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1017\/S026996480000084X"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0219199707002551"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1239\/jap\/1308662630"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1186\/s40649-018-0051-0"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2896377.2901477"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/645926.671873"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411514"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1071\/PH650119"},{"key":"e_1_2_1_9_1","article-title":"Vertex-reinforced random walks and a conjecture of Pemantle","volume":"25","author":"Bena\u00efm Michel","year":"1997","journal-title":"Annals of Probability"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v20-3956"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1214\/17-AAP1360"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-015-9598-x"},{"key":"e_1_2_1_13_1","volume-title":"Advances in Applied Probability","volume":"48","author":"Blanchet J.","year":"2016"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144503423264"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"P. Br\u00e9maud. 1999. Markov chains: Gibbs fields Monte Carlo simulation and queues.  P. Br\u00e9maud. 1999. Markov chains: Gibbs fields Monte Carlo simulation and queues.","DOI":"10.1007\/978-1-4757-3124-8"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_2_1_17_1","volume-title":"Localization of the Maximal Entropy Random Walk. Physical Review Letters","volume":"102","author":"Burda Z.","year":"2009"},{"volume-title":"Canright and Kenth Eng\u00f8-Monsen","year":"2006","author":"Geoffrey","key":"e_1_2_1_18_1"},{"volume-title":"Eigenvector Centrality in Highly Partitioned Mobile Networks: Principles and Applications","author":"Carreras Iacopo","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1284680.1284681"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2903148"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301315"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.spl.2013.05.002"},{"key":"e_1_2_1_24_1","first-page":"3","article-title":"Analysis of a nonreversible Markov chain sampler","volume":"10","author":"Diaconis Persi","year":"2000","journal-title":"Annals of Applied Probability"},{"key":"e_1_2_1_25_1","first-page":"573","article-title":"On the spectral analysis of second-order Markov chains. Annales de la Facult\u00e9 des sciences de Toulouse","volume":"22","author":"Diaconis Persi","year":"2013","journal-title":"Math\u00e9matiques"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1576"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1214\/07-AAP470"},{"volume-title":"Networks, Crowds, and Markets: Reasoning About a Highly Connected World","author":"Easley David","key":"e_1_2_1_28_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511761942"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cpc.2010.11.017"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2619239.2631452"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2005.1498374"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2011.111011"},{"volume-title":"Hydrodynamic limit for a Fleming-Viot type system. Stochastic Processes and their Applications","year":"2004","author":"Grigorescu Ilie","key":"e_1_2_1_33_1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-011-0347-6"},{"key":"e_1_2_1_35_1","first-page":"497","article-title":"Markov processes with redistribution","volume":"19","author":"Grigorescu Ilie","year":"2013","journal-title":"Markov Process and Related Fields"},{"key":"e_1_2_1_36_1","first-page":"521","article-title":"Simulation of Quasi-Stationary Distributions on Countable Spaces","volume":"19","author":"Groisman Pablo","year":"2013","journal-title":"Markov Processes and Related Fields"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488436"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/57.1.97"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(00)00055-4"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.88.020101"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-017-1805-z"},{"volume-title":"Meyer","year":"2006","author":"Langville Amy N.","key":"e_1_2_1_43_1"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254756.2254795"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2017.8057071"},{"key":"e_1_2_1_46_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\/."},{"volume-title":"Monte Carlo Strategies in Scientific Computing","author":"Liu Jun S.","key":"e_1_2_1_47_1"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2016.06.007"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1214\/11-PS191"},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","unstructured":"Carl D. Meyer. 2000. Matrix Analysis and Applied Linear Algebra .SIAM.   Carl D. Meyer. 2000. Matrix Analysis and Applied Linear Algebra .SIAM.","DOI":"10.1137\/1.9780898719512"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450342480"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1214\/07-PS094"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/60.3.607"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-016-1565-1"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1879141.1879192"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2012.6195540"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.4169\/000298910x485923"},{"volume-title":"Proceedings of AAAI Fall Symposium on Using Uncertainty Within Computation. 121--128","author":"Rusmevichientong Paat","key":"e_1_2_1_61_1"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.93.043318"},{"volume-title":"Barkema","year":"2015","author":"Schram Raoul D.","key":"e_1_2_1_63_1"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.83.030103"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2008.2001730"},{"volume-title":"Gomez","year":"2010","author":"Sun Yi","key":"e_1_2_1_66_1"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.118.078301"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physd.2010.10.003"},{"key":"e_1_2_1_69_1","unstructured":"Twitter. {n. d.}. Rate Limiting . https:\/\/dev.twitter.com\/rest\/public\/rate-limiting.  Twitter. {n. d.}. Rate Limiting . https:\/\/dev.twitter.com\/rest\/public\/rate-limiting."},{"key":"e_1_2_1_70_1","first-page":"191","article-title":"Quasi-stationary distributions for reducible absorbing Markov chains in discrete time","volume":"15","author":"van Doorn Erik A.","year":"2009","journal-title":"Markov Process and Related Fields"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2013.01.032"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2008.925623"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983703"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1119\/1.4961596"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/1851182.1851231"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2014.6848229"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2017.8057169"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794373"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/2847526"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3322205.3311086","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3322205.3311086","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3322205.3311086","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:25:55Z","timestamp":1750206355000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3322205.3311086"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,26]]},"references-count":76,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,3,26]]}},"alternative-id":["10.1145\/3322205.3311086"],"URL":"https:\/\/doi.org\/10.1145\/3322205.3311086","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2019,3,26]]},"assertion":[{"value":"2019-03-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}