Linked Life Data

20386694

Source:http://linkedlifedata.com/resource/pubmed/id/20386694

Statements in which the resource exists as a subject.
PredicateObject
rdf:type
lifeskim:mentions
pubmed:issue
4
pubmed:dateCreated
2010-4-13
pubmed:abstractText
Uniform sampling from graphical realizations of a given degree sequence is a fundamental component in simulation-based measurements of network observables, with applications ranging from epidemics, through social networks to Internet modeling. Existing graph sampling methods are either link-swap based (Markov-Chain Monte Carlo algorithms) or stub-matching based (the Configuration Model). Both types are ill-controlled, with typically unknown mixing times for link-swap methods and uncontrolled rejections for the Configuration Model. Here we propose an efficient, polynomial time algorithm that generates statistically independent graph samples with a given, arbitrary, degree sequence. The algorithm provides a weight associated with each sample, allowing the observable to be measured either uniformly over the graph ensemble, or, alternatively, with a desired distribution. Unlike other algorithms, this method always produces a sample, without back-tracking or rejections. Using a central limit theorem-based reasoning, we argue, that for large , and for degree sequences admitting many realizations, the sample weights are expected to have a lognormal distribution. As examples, we apply our algorithm to generate networks with degree sequences drawn from power-law distributions and from binomial distributions.
pubmed:commentsCorrections
pubmed:language
eng
pubmed:journal
pubmed:citationSubset
IM
pubmed:status
MEDLINE
pubmed:issn
1932-6203
pubmed:author
pubmed:issnType
Electronic
pubmed:volume
5
pubmed:owner
NLM
pubmed:authorsComplete
Y
pubmed:pagination
e10012
pubmed:meshHeading
pubmed:year
2010
pubmed:articleTitle
Efficient and exact sampling of simple graphs with given arbitrary degree sequence.
pubmed:affiliation
Department of Physics, University of Houston, Houston, Texas, United States of America.
pubmed:publicationType
Journal Article, Research Support, U.S. Gov't, Non-P.H.S., Research Support, Non-U.S. Gov't