{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T19:01:22Z","timestamp":1780426882833,"version":"3.54.1"},"reference-count":56,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2023,2,20]],"date-time":"2023-02-20T00:00:00Z","timestamp":1676851200000},"content-version":"vor","delay-in-days":1639,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011102","name":"seventh framework programme","doi-asserted-by":"publisher","award":["FP7\/2007\u20132013"],"award-info":[{"award-number":["FP7\/2007\u20132013"]}],"id":[{"id":"10.13039\/100011102","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["617071"],"award-info":[{"award-number":["617071"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-15-1-0074"],"award-info":[{"award-number":["FA9550-15-1-0074"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,11,1]]},"abstract":"<jats:title>Summary<\/jats:title><jats:p>We introduce a class of generative network models that insert edges by connecting the starting and terminal vertices of a random walk on the network graph. Within the taxonomy of statistical network models, this class is distinguished by permitting the location of a new edge to depend explicitly on the structure of the graph, but being nonetheless statistically and computationally tractable. In the limit of infinite walk length, the model converges to an extension of the preferential attachment model\u2014in this sense, it can be motivated alternatively by asking what preferential attachment is an approximation to. Theoretical properties, including the limiting degree sequence, are studied analytically. If the entire history of the graph is observed, parameters can be estimated by maximum likelihood. If only the final graph is available, its history can be imputed by using Markov chain Monte Carlo methods. We develop a class of sequential Monte Carlo algorithms that are more generally applicable to sequential network models and may be of interest in their own right. The model parameters can be recovered from a single graph generated by the model. Applications to data clarify the role of the random-walk length as a length scale of interactions within the graph.<\/jats:p>","DOI":"10.1111\/rssb.12289","type":"journal-article","created":{"date-parts":[[2018,8,28]],"date-time":"2018-08-28T05:38:12Z","timestamp":1535434692000},"page":"871-898","source":"Crossref","is-referenced-by-count":15,"title":["Random-Walk Models of Network Formation and Sequential Monte Carlo Methods for Graphs"],"prefix":"10.1093","volume":"80","author":[{"given":"Benjamin","family":"Bloem-Reddy","sequence":"first","affiliation":[{"name":"University of Oxford \u00a0 UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Orbanz","sequence":"additional","affiliation":[{"name":"Columbia University , New York , USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2018,8,26]]},"reference":[{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/978-1-4615-0005-6_4","volume-title":"In Handbook of Massive Data Sets","author":"Aiello","year":"2002"},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1111\/j.1467-9868.2011.01009.x","article-title":"New consistent and asymptotically normal parameter estimates for random-graph mixture models","volume":"74","author":"Ambroise","year":"2012","journal-title":"J. R. Statist. Soc."},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1111\/j.1467-9868.2009.00736.x","article-title":"Particle Markov chain Monte Carlo methods (with discussion)","volume":"72","author":"Andrieu","year":"2010","journal-title":"J. R. Statist. Soc."},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of scaling in random networks","volume":"186","author":"Barab\u00e1si","year":"1999","journal-title":"Science"},{"key":"2023022101111313200_","volume-title":"Pajek datasets","author":"Batagelj","year":"2006"},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"2280","DOI":"10.1214\/11-AOS904","article-title":"The method of moments and degree distributions for network models","volume":"39","author":"Bickel","year":"2011","journal-title":"Ann. Statist."},{"key":"2023022101111313200_","volume-title":"In Proc. Int. Conf. Uncertainty in Artificial Intelligence","author":"Bloem-Reddy","year":"2018"},{"key":"2023022101111313200_","volume-title":"Preferential attachment and vertex arrival times","author":"Bloem-Reddy","year":"2017"},{"key":"2023022101111313200_","volume-title":"An Lp theory of sparse graph convergence I: limits, sparse random graph models and power law distributions","author":"Borgs","year":"2014"},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"1801","DOI":"10.1016\/j.aim.2008.07.008","article-title":"Convergent sequences of dense graphs: I","volume":"219","author":"Borgs","year":"2008","journal-title":"Adv. Math."},{"key":"2023022101111313200_","first-page":"383","article-title":"Sampling and Bayes\u2019 inference in scientific modelling and robustness","volume":"143","author":"Box","year":"1980","journal-title":"J. R. Statist. Soc."},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1109\/TNSE.2015.2397592","article-title":"On the influence of the seed graph in the preferential attachment model","volume":"2","author":"Bubeck","year":"2015","journal-title":"IEEE Trans. Netwrk Sci. Engng"},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1038\/nature03239","article-title":"Interaction network containing conserved and essential protein complexes in Escherichia coli","volume":"433","author":"Butland","year":"2005","journal-title":"Nature"},{"key":"2023022101111313200_","first-page":"4249","volume-title":"In Advances in Neural Information Processing Systems 29","author":"Cai","year":"2016"},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"1295","DOI":"10.1111\/rssb.12233","article-title":"Sparse graphs using exchangeable random measures (with discussion)","volume":"79","author":"Caron","year":"2017","journal-title":"J. R. Statist. Soc."},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1006\/jcta.2000.3094","article-title":"Discrete Green\u2019s functions","volume":"91","author":"Chung","year":"2000","journal-title":"J. Combin. Theory"},{"key":"2023022101111313200_","article-title":"Edge exchangeable models for interaction networks","author":"Crane","year":"2017","journal-title":"J. Am. Statist. Ass."},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"969","DOI":"10.1137\/15M1011214","article-title":"Sequential Monte Carlo with highly informative observations","volume":"3","author":"Del Moral","year":"2015","journal-title":"SIAM J. Uncertnty Quantficn"},{"key":"2023022101111313200_","first-page":"656","volume-title":"In Oxford Handbook of Nonlinear Filtering","author":"Doucet","year":"2011"},{"key":"2023022101111313200_","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546594","volume-title":"Random Graph Dynamics","author":"Durrett","year":"2006"},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"887","DOI":"10.1111\/1467-9868.00421","article-title":"On-line inference for hidden Markov models via particle filters","volume":"65","author":"Fearnhead","year":"2003","journal-title":"J. R. Statist. Soc."},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"2624","DOI":"10.1214\/15-AOS1354","article-title":"Rate-optimal graphon estimation","volume":"43","author":"Gao","year":"2015","journal-title":"Ann. Statist."},{"key":"2023022101111313200_","first-page":"733","article-title":"Posterior predictive assessment of model fitness via realized discrepancies","volume":"6","author":"Gelman","year":"1996","journal-title":"Statist. Sin."},{"key":"2023022101111313200_","first-page":"2265","article-title":"Euclidean embedding of co-occurrence data","volume":"8","author":"Globerson","year":"2007","journal-title":"J. Mach. Learn. Res."},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1561\/2200000005","article-title":"A survey of statistical network models","volume":"2","author":"Goldenberg","year":"2010","journal-title":"Found. Trends Mach. Learn."},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1006\/tpbi.1994.1023","article-title":"Simulating probability distributions in the coalescent","volume":"46","author":"Griffiths","year":"1994","journal-title":"Theoret. Popln Biol."},{"key":"2023022101111313200_","first-page":"657","volume-title":"In Advances in Neural Information Processing Systems 20","author":"Hoff","year":"2008"},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"1090","DOI":"10.1198\/016214502388618906","article-title":"Latent space approaches to social network analysis","volume":"97","author":"Hoff","year":"2002","journal-title":"J. Am. Statist. Ass."},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1198\/016214507000000446","article-title":"Goodness of fit of social network models","volume":"103","author":"Hunter","year":"2008","journal-title":"J. Am. Statist. Ass."},{"key":"2023022101111313200_","volume-title":"Generalized Mittag-Leffler distributions arising as limits in preferential attachment models","author":"James","year":"2015"},{"key":"2023022101111313200_","article-title":"On edge exchangeable random graphs","author":"Janson","year":"2017","journal-title":"J. Statist. Phys."},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"1025","DOI":"10.1089\/cmb.2015.0072","article-title":"Bayesian inference for duplication\u2013mutation with complementarity network models","volume":"22","author":"Jasra","year":"2015","journal-title":"J. Computnl Biol."},{"key":"2023022101111313200_","first-page":"381","volume-title":"In Proc. American Association for Artifical Intelligence Conf.","author":"Kemp","year":"2006"},{"key":"2023022101111313200_","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-88146-1","volume-title":"Statistical Analysis of Network Data","author":"Kolaczyk","year":"2009"},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"3930","DOI":"10.1016\/j.jspi.2007.04.011","article-title":"Bayesian inference for dynamic social network data","volume":"137","author":"Koskinen","year":"2007","journal-title":"J. Statist. Planng Inf."},{"key":"2023022101111313200_","first-page":"129","article-title":"Diffusion kernels on statistical manifolds","volume":"6","author":"Lafferty","year":"2005","journal-title":"J. Mach. Learn. Res."},{"key":"2023022101111313200_","doi-asserted-by":"crossref","DOI":"10.1007\/b138374","volume-title":"Interacting Particle Systems","author":"Liggett","year":"2005"},{"key":"2023022101111313200_","volume-title":"Turrialba: Social Systems and the Introduction of Change","author":"Loomis","year":"1953"},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1177\/0022343316630783","article-title":"A new approach to analyzing coevolving longitudinal networks in international relations","volume":"53","author":"Minhas","year":"2016","journal-title":"J. Peace Res."},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1017\/S0963548304006133","article-title":"The maximum degree of the Barab\u00e1si\u2013Alb\u00e9rt random tree","volume":"14","author":"M\u00f3ri","year":"2005","journal-title":"Comb. Probab. Comput."},{"issue":"no. 4","key":"2023022101111313200_","article-title":"Network archaeology: uncovering ancient networks from present-day interactions","volume":"7","author":"Navlakha","year":"2011","journal-title":"PLOS Computnl Biol."},{"key":"2023022101111313200_","volume-title":"Networks: an Introduction","author":"Newman","year":"2009"},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1109\/TPAMI.2014.2334607","article-title":"Bayesian models of graphs, arrays and other exchangeable random structures","volume":"37","author":"Orbanz","year":"2015","journal-title":"IEEE Trans. Pattn Anal. Mach. Intell."},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1017\/apr.2017.5","article-title":"Joint degree distributions of preferential attachment random graphs","volume":"49","author":"Pek\u00f6z","year":"2017","journal-title":"Adv. Appl. Probab."},{"key":"2023022101111313200_","volume-title":"Combinatorial Stochastic Processes","author":"Pitman","year":"2006"},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"191","DOI":"10.7155\/jgaa.00124","article-title":"Computing communities in large networks using random walks","volume":"10","author":"Pons","year":"2006","journal-title":"J. Graph Algrthms Appl."},{"key":"2023022101111313200_","volume-title":"In Proc. A. Conf. Computational Learning Theory","author":"Smola","year":"2003"},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"2653","DOI":"10.1098\/rsif.2012.0220","article-title":"Graph spectral analysis of protein interaction network evolution","volume":"9","author":"Thorne","year":"2012","journal-title":"J. R. Soc. Interfc."},{"key":"2023022101111313200_","article-title":"The role of endogenous and exogenous mechanisms in the formation of R&D networks","volume":"4","author":"Tomasello","year":"2014","journal-title":"Scient. Rep."},{"key":"2023022101111313200_","first-page":"1201","article-title":"Graph kernels","volume":"11","author":"Vishwanathan","year":"2010","journal-title":"J. Mach. Learn. Res."},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1089\/cmb.2013.0082","article-title":"Computational methods for a class of network models","volume":"21","author":"Wang","year":"2014","journal-title":"J. Computnl Biol.,"},{"key":"2023022101111313200_","first-page":"1","article-title":"Nonparametric network models for link prediction","volume":"17","author":"Williamson","year":"2016","journal-title":"J. Mach. Learn. Res."},{"key":"2023022101111313200_","doi-asserted-by":"crossref","first-page":"7566","DOI":"10.1073\/pnas.0600061103","article-title":"A likelihood approach to analysis of network data","volume":"103","author":"Wiuf","year":"2006","journal-title":"Proc. Natn. Acad. Sci. USA"},{"key":"2023022101111313200_","volume-title":"Nonparametric graphon estimation","author":"Wolfe","year":"2013"},{"key":"2023022101111313200_","volume-title":"Network archaeology: phase transition in the recoverability of network history","author":"Young","year":"2018"},{"key":"2023022101111313200_","first-page":"1135","volume-title":"In Proc. 18th Int. Conf. Artificial Intelligence and Statistics","author":"Zhou","year":"2015"}],"container-title":["Journal of the Royal Statistical Society Series B: Statistical Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1111%2Frssb.12289","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1111\/rssb.12289","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1111\/rssb.12289","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/am-pdf\/10.1111\/rssb.12289","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/jrsssb\/article-pdf\/80\/5\/871\/49270525\/jrsssb_80_5_871.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/jrsssb\/article-pdf\/80\/5\/871\/49270525\/jrsssb_80_5_871.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,4]],"date-time":"2023-09-04T16:31:59Z","timestamp":1693845119000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/jrsssb\/article\/80\/5\/871\/7048386"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,26]]},"references-count":56,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2018,8,26]]},"published-print":{"date-parts":[[2018,11,1]]}},"URL":"https:\/\/doi.org\/10.1111\/rssb.12289","relation":{},"ISSN":["1369-7412","1467-9868"],"issn-type":[{"value":"1369-7412","type":"print"},{"value":"1467-9868","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2018,11]]},"published":{"date-parts":[[2018,8,26]]}}}