Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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] 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

Request Changes to record.

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:
DateEvent
26 August 2015Published
17 July 2015Accepted
20 March 2015Submitted
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 View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us