Random‐walk models of network formation and sequential Monte Carlo methods for graphs

Benjamin Bloem‐Reddy and Peter Orbanz

Journal of the Royal Statistical Society Series B, 2018, vol. 80, issue 5, 871-898

Abstract: 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—in 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.

Date: 2018
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1111/rssb.12289

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bla:jorssb:v:80:y:2018:i:5:p:871-898

Ordering information: This journal article can be ordered from
http://ordering.onli ... 1111/(ISSN)1467-9868

Access Statistics for this article

Journal of the Royal Statistical Society Series B is currently edited by P. Fryzlewicz and I. Van Keilegom

More articles in Journal of the Royal Statistical Society Series B from Royal Statistical Society Contact information at EDIRC.
Bibliographic data for series maintained by Wiley Content Delivery ().