Measuring preferential attachment in growing networks with missing-timelines using Markov chain Monte Carlo

Paul Sheridan, Yuichi Yagahara and Hidetoshi Shimodaira

Physica A: Statistical Mechanics and its Applications, 2012, vol. 391, issue 20, 5031-5040

Abstract: Preferential attachment is widely recognised as the principal driving force behind the evolution of many growing networks, and measuring the extent to which it occurs during the growth of a network is important for explaining its overall structure. Conventional methods require that the timeline of a growing network is known, that is, the order in which the nodes of the network appeared in time is available. But growing network datasets are commonly accompanied by missing-timelines, in which instance the order of the nodes in time cannot be readily ascertained from the data. To address this shortcoming, we propose a Markov chain Monte Carlo algorithm for measuring preferential attachment in growing networks with missing-timelines. Key to our approach is that any growing network model gives rise to a probability distribution over the space of networks. This enables a growing network model to be fitted to a growing network dataset with missing-timeline, allowing not only for the prevalence of preferential attachment to be estimated as a model parameter, but the timeline also. Parameter estimation is achieved by implementing a novel Metropolis–Hastings sampling scheme for updating both the preferential attachment parameter and timeline. A simulation study demonstrates that our method accurately measures the occurrence of preferential attachment in networks generated according to the underlying model. What is more, our approach is illustrated on a small sub-network of the United States patent citation network. Since the timeline for this example is in fact known, we are able to validate our approach against the conventional methods, showing that they give mutually consistent estimates.

Keywords: Growing network; Markov chain Monte Carlo; Metropolis–Hastings; Missing-timeline; Preferential attachment; Scale-free network (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437112004128
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

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:eee:phsmap:v:391:y:2012:i:20:p:5031-5040

DOI: 10.1016/j.physa.2012.05.041

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().