CHARO DEL GENIO
  • Home
  • Publications
  • Computer codes
    • Graphical sequence generator
    • Graph sampling
    • Directed graph sampling
    • Graphical directed sequence generator
    • Community detection
    • Sampling graphs with given correlations
    • TomoDock
  • Media coverage
  • Alumni
  • Contact
Exact sampling of graphs with prescribed degree correlations

K. E. Bassler, C. I. Del Genio, P. Erdős, I. Miklós and Z. Toroczkai
New Journal of Physics 17, 083052 (2015)
Picture

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. 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 efficient and 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 O(NM) where N is the number of nodes and M is the number of edges.




Download

Link to the journal
Direct link to the preprint
Link to the arXiv
Link to a code implementing the algorithm

Powered by Create your own unique website with customizable templates.
  • Home
  • Publications
  • Computer codes
    • Graphical sequence generator
    • Graph sampling
    • Directed graph sampling
    • Graphical directed sequence generator
    • Community detection
    • Sampling graphs with given correlations
    • TomoDock
  • Media coverage
  • Alumni
  • Contact