The Library
Exact sampling of graphs with prescribed degree correlations
Tools
Tools
Tools
Bassler, Kevin E., Del Genio, Charo I., Erdős, Péter L., Miklós, István and Toroczkai, Zoltán (2015) Exact sampling of graphs with prescribed degree correlations. New Journal of Physics, 17 (8). 083052. doi:10.1088/1367-2630/17/8/083052
![[img]](http://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
WRAP_bassler_-_exact_sampling_of_graphs.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial. Download (1541Kb) |
Official URL: http://dx.doi.org/10.1088/1367-2630/17/8/083052
Abstract
Many real-world networks exhibit correlations between the node degrees. For instance, in social networks nodes tend to connect to nodes of similar degree and conversely, in biological and technological networks, high-degree nodes tend to be linked with low-degree nodes. Degree correlations also affect the dynamics of processes supported by a network structure, such as the spread of opinions or epidemics. The proper modelling of these systems, i.e., without uncontrolled biases, requires the sampling of networks with a specified set of constraints. We present a solution to the sampling problem when the constraints imposed are the degree correlations. In particular, we develop an exact method to construct and sample graphs with a specified joint-degree matrix, which is a matrix providing the number of edges between all the sets of nodes of a given degree, for all degrees, thus completely specifying all pairwise degree correlations, and additionally, the degree sequence itself. Our algorithm always produces independent samples without backtracking. The complexity of the graph construction algorithm is ${\mathcal{O}}({NM})$ where N is the number of nodes and M is the number of edges.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics T Technology > TK Electrical engineering. Electronics Nuclear engineering |
||||||||
| Divisions: | Faculty of Science > Centre for Complexity Science Faculty of Science > Life Sciences (2010- ) Faculty of Science > Mathematics Faculty of Medicine > Warwick Medical School |
||||||||
| Library of Congress Subject Headings (LCSH): | Computer networks, Graph algorithms, Markov processes, Monte Carlo method | ||||||||
| Journal or Publication Title: | New Journal of Physics | ||||||||
| Publisher: | IOP Publishing | ||||||||
| ISSN: | 1367-2630 | ||||||||
| Official Date: | 26 August 2015 | ||||||||
| Dates: |
|
||||||||
| Volume: | 17 | ||||||||
| Number: | 8 | ||||||||
| Article Number: | 083052 | ||||||||
| DOI: | 10.1088/1367-2630/17/8/083052 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Open Access | ||||||||
| Funder: | United States. Air Force. Office of Scientific Research (AFOSR), United States. Defense Advanced Research Projects Agency (DARPA), National Science Foundation (U.S.) (NSF), Seventh Framework Programme (European Commission) (FP7), United States. Defense Threat Reduction Agency (DTRA) | ||||||||
| Grant number: | FA9550-12-1-0405 (AFOSR/DARPA), DMR-1206839 (NSF), 288021 (FP7), HDTRA-1-09-1-0039 (DTRA) |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
