Efficient estimation of tail probabilities of the typical distance in preferential attachment models

Grant, Morgan R. and Kroese, Dirk P. (2017). Efficient estimation of tail probabilities of the typical distance in preferential attachment models. In: Proceedings - Winter Simulation Conference. 2016 Winter Simulation Conference, WSC 2016, Arlington, VA, United States, (338-346). 11 - 14 December 2016. doi:10.1109/WSC.2016.7822101


Author Grant, Morgan R.
Kroese, Dirk P.
Title of paper Efficient estimation of tail probabilities of the typical distance in preferential attachment models
Conference name 2016 Winter Simulation Conference, WSC 2016
Conference location Arlington, VA, United States
Conference dates 11 - 14 December 2016
Convener IEEE
Proceedings title Proceedings - Winter Simulation Conference   Check publisher's open access policy
Journal name Proceedings - Winter Simulation Conference   Check publisher's open access policy
Place of Publication Piscataway, NJ, United States
Publisher Institute of Electrical and Electronics Engineers
Publication Year 2017
Sub-type Fully published paper
DOI 10.1109/WSC.2016.7822101
Open Access Status Not yet assessed
ISBN 9781509044863
ISSN 0891-7736
Start page 338
End page 346
Total pages 9
Language eng
Abstract/Summary The properties of random graphs provide insight into the behavior of real-world complex networks. One such property is the Typical Distance, which characterizes the time required to traverse the network. For example, the Typical Distance measures how fast a virus spreads through a population. The probability that the Typical Distance is large is difficult to estimate via crude Monte Carlo. We propose a new sequential importance sampling estimator that can find the probability of a large Typical Distance in preferential attachment models, with a computational complexity that is quadratic in the number of nodes. Numerical experiments indicate that the estimator is significantly more efficient than crude Monte Carlo.
Q-Index Code E1
Q-Index Status Provisional Code
Institutional Status UQ

Document type: Conference Paper
Collections: School of Mathematics and Physics
HERDC Pre-Audit
 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in Thomson Reuters Web of Science Article
Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Tue, 21 Mar 2017, 00:25:23 EST by Web Cron on behalf of Learning and Research Services (UQ Library)