Comparison of Graph Generation Models focusing on
Accuracy and Variation
Mei Fukuda

Kazuki Nakajima

Kazuyuki Shudo

Tokyo Institute of Technology

Tokyo Institute of Technology

Tokyo Institute of Technology

ABSTRACT
Generation models of graphs have been used to compare
and analyze the properties of graph structures and to produce graphs that resemble real-world networks. When using a generation model to mimic a real-world network, it
is desirable for the error in the properties between the target graph and the generated graph and the variation of theerrors between generated graphs are small. However, since
many existing generation models generate graphs by addingedges at random, the extent of the error and its variation foreach generated graph is unclear.
This paper studies the error and the variation of properties of graphs generated using the dK-series framework,
which has been proposed to analyze the topology of a network based on the degree of nodes. In addition, we propose
a new graph generation model that takes the degree distribution and degree-dependent clustering coeﬃcient as inputs.
We show that the proposed model is able to reduce the error
to a greater extent than other generation models.

KEYWORDS
network analysis, graph generation models, estimation, sampling, social networks
ACM Reference Format:
Mei Fukuda, Kazuki Nakajima, and Kazuyuki Shudo. 2020. Comparison of Graph Generation Models focusing on Accuracy andVariation. In Proceedings of ACM Conference (MLG ’20). ACM,
New York, NY, USA, 7 pages. https://doi.org/10.1145/nnnnnnn.
nnnnnnn1

INTRODUCTION

Graph generation models have historically been used to compare and analyze the properties of graph structures and to
generate graphs that resemble real-world networks. For example, by generating and comparing random graphs withthe same number of nodes and edges as the target graph,
we can observe the properties of the graphs, such as highclustered and small-world properties [33]. Additionally, sufficient real-world graph data are diﬃcult to obtain, though
Permission to make digital or hard copies of all or part of this workfor personal or classroom use is granted without fee provided that
copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first
page. Copyrights for components of this work owned by others thanACM must be honored. Abstracting with credit is permitted. To copy
otherwise, or republish, to post on servers or to redistribute to lists,requires prior specific permission and/or a fee. Request permissions
from permissions@acm.org.
MLG ’20, August, 2020, San Diego, CA
c 2020 Association for Computing Machinery.
⃝
ACM ISBN 978-x-xxxx-xxxx-x/YY/MM. . . $15.00
https://doi.org/10.1145/nnnnnnn.nnnnnnn

researchers want these data, which is a motivation for generating many graphs that resemble real-world networks. Furthermore, while many attempts have been made to use sampling to estimate the overall properties for networks where
the overall topology is unknown, such as large graph structures of user relationships in online social networking services(OSNs) [1, 12, 18, 19], the properties that can be estimatedby sampling are limited to those that can be computed fromlocal information such as the number of nodes, degree distributions, and clustering coeﬃcients. Therefore, graph generation models have been used to generate graphs that mimiceven properties that are diﬃcult to estimate.
Priya et al. proposed a framework for random graph generation models called dK-series, which characterizes the properties of a graph using a series of probability distributions
specifying all the degree correlations within d-sized subgraphsof a given graph [23]. Consider the following scenario. Suppose you want to understand the structure of a real networkby comparing it to a graph generated by fixing a certain
property. In this case, the feature of the generated graphwhen you hierarchically add properties to be fixed is alsoof great interest. Additionally, there is another motivation
for generating graphs with properties that we know or estimate via sampling when a particular property of graphs isavailable or the overall data are not available. The dK-series
provides a systematic description for such various graph generation models we use depending on a purpose. Gjoka et al.
proposed a generation model for a 2.5K graph based on dKseries [15]. The model generates a graph with a fixed joint
degree distribution and degree-dependent clustering coeﬃcients. Moreover, the graphs generated by this model canaccurately mimic real-world networks.
Graphs generated by a generation model based on dKseries can estimate globally defined properties with high accuracy, but due to the random addition of the edges, thenoninput properties are diﬀerent for each generation, even if
the input is the same. Whether the generated graphs vary
greatly from one generation to the next or whether they always fall within a certain range is unclear. If we want to generate a graph that resembles a certain graph, the fact thatthe generated graph is “similar” to the target graph has tobe reliable, so the error in the properties between the target graph and the generated graph, as well as its variation,
should be small. However, so far, the error and variation of
the properties of the generated graphs for the same input
have not been thoroughly studied. Furthermore, while dKseries can mimic almost all properties at 3K graphs, except
those fixed at the input, the generation of 3K graphs entails
enormous computational complexity: 2.5K has been able to16th Int'l Workshop on Mining and Learning with Graphs(MLG 2020), August 2020 (non-archival)

MLG ’20, August, 2020, San Diego, CA

reduce the complexity to a practically usable level. However,even at 2.5K, there are concerns about scalability, and thegeneration of large-scale graphs with hundreds of millions ofnodes and edges remains challenging.
In this study, we generate a large number of graphs using generation models based on dK-series for a real network
dataset and compare the errors, variation, and execution
time of each property of the generated graphs. We also propose a new generation model (1K+) that overcomes the scalability of graph generation while maintaining the accuracy.
The structure of the rest of this paper is as follows. Chapter
2 provides the notation and the definitions of the properties
to be discussed. Chapter 3 presents related work. Chapter
4 discusses the errors and the variations of generation models based on dK-series. Chapter 5 proposes the new modeland discusses its accuracy and variation. Finally, Chapter 6
summarizes this paper.

2

NOTATION

We consider an undirected, unweighted and static graph G =(V, E), with |V | = n nodes and |E| = m edges. We call anode v ∈ Vk a “degree k node”, where Vk is the set of allnodes of degree k. Let the set of nodes V = {v1 · · · vn }; thedegree of vi is denoted as di . N (v) ⊂ V is the set of neighbors
of v.

2.1

Properties of Interest

The degree distribution is represented as a probability distribution P (k) = P (di = k) for i ∈ {1, · · · , n}. In this paper,
we use another property of degree, called the joint degree
distribution (JDD) P (k1 , k2 ) = P (di = k1 , dj = k2 ) (i ̸= j),which represents the distribution of a pair of degrees connected as edges.
The clustering coeﬃcient ci of a node vi captures the extent to which the neighbors of a node form triangles andis typically defined as the ratio of the number of edges between neighbors divided by the maximum number of suchedges. Thus, the clustering coeﬃcient ci is represented as
2Ti
ci = di (di−1), where Ti is the number of triangles including vi . The degree-dependent
clustering coeﬃcient c̄(k) is!
defined as c̄(k) = |V1k | vi ∈Vk ci . Additionally, the averageclustering coeﬃcient!c̄, ci averaged over all nodes in G, isdefined as c̄ = n1 vi ci , and c̄(k) determines c̄ because!
c̄ = n1 k |Vk | · c̄(k).
The shortest path distribution is defined as the probability of a distance between arbitrary pairs of nodes, where thedistance between nodes vi and vj , dist(vi , vj ), in unweighted
graphs is denoted as the minimum number of edges of paths
connecting nodes vi and vj . The maximal clique distribution is defined as the frequency of the size of maximal cliques,
where a clique is a complete subgraph and its size is the number of nodes in the subgraph. Furthermore, the cycles distribution is defined as the frequency of the cycle length for aminimal cycle basis, in which a cycle cannot be reconstructedby the union of cycles in the base. The spectrum is the eigenvalues of a graph: we use the distribution of the 20 largest

Mei Fukuda, et al.

eigenvalues. The closeness centralityof a node vi is defined as!
the multiplicative inverse of vj ∈N (vi ) dist(vi , vj ), the sumof distances of the node to all other nodes. The greater thecloseness centrality of a node is, the closer it is to all othernodes.

3

RELATED WORKThe Erdős-Rényi model is a random graph generation model,
also known as the ER model, that was introduced in the late
1950s [11]. There are two types of ER models, the G(n, m)model and the G(n, p) model. The G(n, m) model involves
uniform random selection among a set of graphs with n nodes
and m edges. In contrast, the G(n, p) model independently
constructs an edge for each pair of vertices with probabilityp; "that# is, the expected number of edges in the G(n, p) modelis n2 p. The main motivation for generating random graphswith the ER model is to verify what properties a graph withthe same number of nodes n and edges m generally satisfies,
which is not a suﬃcient model to mimic a real network.
Since the G(n, m) model does not add edges with probability
independent from that of other edges, the G(n, p) model,
which usually considers p as a function of n and considers
the structure in n → ∞, is commonly used.
The model for generating a random graph with a fixed
degree distribution is called the configuration model. The
configuration model has been studied since the 1970s andhas been used in a number of research projects [3–7, 21,
22, 24, 25]. Here, we apply the model using the approach
by Newman, Strogatz, and Watts [9, 10]. Suppose that thedegree sequence di · · · dn is independent and satisfies P (di =k) = |Vnk | . This model takes the number of nodes n andthe degree distribution P (di = k) as inputs and, assumingthat there are di half-edges from node vi , randomly selects
two half-edges to construct a connecting edge. This method
may generate multiple edges and self-loops. An algorithm toavoid multiple edges and self-loops has also been proposed[17].
Priya et al. proposed dK-series [23], a framework for systematically characterizing a graph using a probability distribution P (k1 , k2 , · · · , kd ) that identifies all degree correlations in a connected subgraph consisting of d nodes. The 0K
graph fixes only the average degree k̄ of the graph G; thatis, the G(n, m) model in the Erdős-Rényi model describedabove is equivalent. The 1K graph, given the degree distribution P (k), can be generated by the configuration model described above. The 2K graph is generated by identifying andfixing the joint degree distribution (JDD) P (k1 , k2 ), which
can be accomplished by extending the configuration model[23]. A model for generating 2K graphs that avoids multiple edges and self-loops has been proposed by Isabelle et al.
[29, 30].
The 3K graph fixes the distributions P△ (k1 , k2 , k3 ) andP∧ (k1 , k2 , k3 ) of 3-node subgraphs formed as triangles andwedges. As d increases, the size of the subgraphs increases.
An nK graph defined using the number of nodes n is identicalto graph G of the original network.

16th Int'l Workshop on Mining and Learning with Graphs(MLG 2020), August 2020 (non-archival)

Comparison of Graph Generation Models focusing on
Accuracy and Variation

Priya et al. use a method called dK-randomizing rewiring
to randomly swap edges while preserving the existing formof the dK distribution and compare the result to the properties in the original graph. It has been shown that d = 2
reproduces most of the properties, and d = 3 reproduces
all the properties almost faithfully, while the computational
complexity of the dK graph generation increases rapidly as
d increases [23]. Moreover, generating a graph that satisfies
the input probability distribution is diﬃcult at 3K and above[23].
Gjoka et al. proposed an idea to reproduce properties thatare diﬃcult to estimate by generating a graph with fixed
properties that can be estimated with high accuracy by sampling a large-scale graph structure, such as a social network,where the overall topology is unknown.
Following the dK-series, Gjoka et al. presented a model togenerate 2.25K graphs with a fixed average clustering coefficient c̄ in addition to JDD and 2.5K graphs with a fixed
degree-dependent clustering coeﬃcient c̄(k) and JDD andcompared the results with 2K graphs with respect to accuracy. They also proposed a method to estimate the JDD anddegree-dependent clustering coeﬃcients with high accuracy[15, 31].
A 2.5K graph is generated by two steps: 1) assigning a
number of positions to all nodes in the algorithm to generate
the 2K graph and sorting all pairs of nodes by their distanceto produce a graph with many triangles, and 2) reducing theclustering coeﬃcients by swapping two nodes with the same
degree while still satisfying the JDD.
The 2.5K graph is similar to the target graph for a wide
range of major properties other than the maximal clique
distribution. However, due to its nature as a random graph,diﬀerent graphs are generated for each generation, and there
is no mention of how much variation exists and how reliable
the graphs are once generated.
Orsini et al. studied the randomness of graphs generated
by dK-series models [27]. They showed that many important properties of real networks are closely reproduced by
dk-random graphs whose degree distributions and clustering coeﬃcients are the same as in the corresponding real
network. They considered some, but limited, real networks.
Specifically, social network datasets should also be considered. Additionally, various other properties must be verified,and more graphs must be produced to verify the accuracy.
Furthermore, many studies on graph generation models
that fix degree-dependent clustering coeﬃcients have beenreported. Serrano et al. [28] proposed a model for generating random graphs satisfying the degree-dependent clustering coeﬃcient c̄(k) and degree distribution P (di = k),but this method is not practical for graphs that have large
clustering coeﬃcients. According to Wang [32], graph generation models satisfying a given clustering coeﬃcient has
also been proposed by Bansal et al [2], Newman [26], andGleeson [16]. Bansal et al. proposed a model that satisfies
the average clustering coeﬃcient c̄, and Newman proposed amodel that fixes ci for each node unless one edge is used togenerate multiple triangles. Gleeson proposed an improved

MLG ’20, August, 2020, San Diego, CA

Table 1: Dataset: Each number is of the largest connected component of each graph.
DatasetCaltech [14]Rice [14]wiki-Vote [20]

|V |
769
4 087
7 115

|E|
16 656
184 828
100 762c̄d¯
21.65 0.409
45.22 0.294
14.16 0.141

Table 2: Environment.
OS
Processor
MemoryLanguage

macOS Mojave 10.14.5
TM
R Corei7
2.7 GHz Intel⃝
16 GB 2133 MHz LPDDR3
Python 2.7.10 (for 2K & 2.5K graphs)
Python 3.6.3 (for others)

model that focuses on the constraints of Newman’s generation model. Except for Bansal et al.’s generation model,
these approaches cannot satisfy the degree distribution at
the same time. Therefore, limited graph generation models
are available for fixing degree-dependent clustering coeﬃcients and degree distributions.

4

ERROR AND ITS VARIATION FOR
GENERATED GRAPHS

We generate a number of random graphs with generation
models based on dK-series using properties computed fromreal network datasets as input and compare the various properties of the generated graphs with the real values in thedatasets.

4.1

Preparation

In this experiment, we use three datasets with the various
topologies shown in Table 1. The entire dataset is treated as
an undirected graph, and its largest connected component(LCC) is used in the experiment.
The 0K graphs are generated with gnm random graph [8]in NetworkX, a Python library for network graph analysis.
The 1K graphs are generated with the configuration model,
and 2K graphs and 2.5K graphs are generated withconstruct simple 2K, construct triangles 2K andmcmc improved 2 5 K of the software published by Gjoka etal. [13], respectively.
We measure the diﬀerence between two discrete distributions using the normalized mean absolute error (NMAE)
defined below.
!
(|x$i − xi |)$, ⃗x) =!
NMAE(⃗xxi$ and ⃗x are vectors that correspond to the real and estimated⃗x
discrete distributions.
Additionally, this experiment is conducted under the environment described in Table 2.

16th Int'l Workshop on Mining and Learning with Graphs(MLG 2020), August 2020 (non-archival)

MLG ’20, August, 2020, San Diego, CA

Mei Fukuda, et al.

Table 3: Graph generation time in seconds.
DatasetCaltech [14]Rice [14]wiki-Vote [20]4.2

0K
0.0658
0.629
0.382

1K
1.17
64.0
47.2

1K+
1.13
53.1
42.5

2K
0.532
5.09
3.29

2.5K
11.3
84.7
62.7

Measurement

For each dataset, 1) we calculate the number of nodes, number of edges, degree distribution, JDD, and degree-dependent
clustering coeﬃcients, 2) generate 100 graphs with each random graph generation model using the corresponding properties, and 3) for their generated graphs, calculate the NMAE
of the following graph properties.
• Shortest path distribution• Maximal clique distribution• Cycles distribution• Spectrum (20 largest eigenvalues)• Closeness centrality
4.2.1 Property Analysis. The distributions of the above fiveproperties for the Caltech dataset and its generated graphs
are shown in Figure 1.
The red line in each figure plots the distribution of thetarget graphs, while the other plots the distribution of thegenerated graphs. As d of dK increases, some properties become closer to the distribution of the red line.
4.2.2 Error Distribution. For each of the graphs generated
from the three datasets Caltech, Rice, and wiki-Vote, theerror distributions of the above five properties are shown in
Figure 2.
For all properties, the error variation is small regardlessof the generation model: 0K is very small for all properties.
For each dK, the variation of the shortest path distribution, spectrum, and closeness centrality is stably small, andthe error tends to decrease as d increases.
The errors and their variations of the maximum clique andcycle distributions are larger than those of the other properties, and the distributions vary depending on the topologyof the data set.
4.2.3 Performance. The execution time to generate one graphfor each generation model is shown in Table 3. Ten graphs
were generated, and the average is shown. The 0K and 1Kgraphs were run with Python 3.6.3, and 2K and 2.5K were
run with Python 2.7.10.
The 0K graphs can be generated the fastest, and the generation of 2.5K graphs is the most time consuming.

5graphs, as shown in Figure 1, we focus on cliques and generate graphs by two steps: 1) generating cliques according
to the number of triangles for degree k, and 2) matching
the degree of each node using the conventional configuration
model. We call the graph generated by this generation modela 1K+ graph.
In the proposed generation model, for each degree, we
generate cliques that can form the closest number of triangles
to the target number of triangles among nodes with the same
degree.
Algorithm 1 illustrates the implementation of 1K+. Let
the input be ntri[k], which is the sum of the number of triangles joined by the degree k nodes, computed from the degree
distribution P (di = k) and the degree-dependent clustering
coeﬃcient c̄(k).
The graphs generated by this 1K+ algorithm can ensurethat the degree-dependent clustering coeﬃcients are closer tothe target graph than the graphs generated by the 0K, 1K,
and 2K graph generation models. Figure 3 shows the distribution of degree-dependent clustering coeﬃcients of thegenerated graphs. The red dots in the figure plot the distribution of the target graphs, and the others are the distribution of the 100 generated graphs. The distribution of thedegree-dependent clustering coeﬃcients of the 1K+ graphs
overlaps well with the red dots compared to the graphs generated by the 0K, 1K, and 2K approaches.
The experiment discussed in Chapter 4 is repeated forthe 1K+ generation model. Using the degree distribution
and the distribution of the degree-dependent clustering coeﬃcient as inputs, we generate 100 graphs with the 1K+
model in Python 3.6.3, as described in Algorithm 1.
The distribution of properties for the Caltech dataset isshown in Figure 1. As shown in Figure 2, the graphs generated by the proposed 1K+ algorithm have smaller errors
than the 2K graphs; for example, with respect to the shortest
path distribution, 1K+ has the smallest error in the Caltech
graph and the second smallest error, after 2.5K, in the Ricegraph. Additionally, the errors of the maximal clique andcycle distributions in the 1K+ graph are the smallest, on
average, in the Wiki-Vote graph, with some improvementfrom 1K in Caltech and Rice. Furthermore, as can be seenfrom Table 3, although the 1K+ graph requires more inputs
than the 1K graph, it can be generated in a shorter time.

1K+ GRAPH GENERATION MODEL

We propose a generation model that fixes the degree distribution and makes the degree-dependent clustering coeﬃcients closer to the input than that of the 1K graph. In thisgeneration model, because graphs generated by conventionalmodels tend not to have large size cliques compared to real

16th Int'l Workshop on Mining and Learning with Graphs(MLG 2020), August 2020 (non-archival)

Comparison of Graph Generation Models focusing on
Accuracy and Variation

Shortest path

MLG ’20, August, 2020, San Diego, CA

Maximal clique

Cycle

Spectrum

Closeness centrality

0K

1K

1K+

2K

2.5K

Figure 1: Distribution of properties (Caltech).

(a) Caltech(b) Rice

Figure 2: Error distribution.

16th Int'l Workshop on Mining and Learning with Graphs(MLG 2020), August 2020 (non-archival)(c) wiki-VoteMLG ’20, August, 2020, San Diego, CA

Mei Fukuda, et al.

Algorithm 1 Generate 1K+ graph.
Require: d1 · · · dn : degree sequencentri[k]: the sum of the number of triangles joined by nodev ∈ VkEnsure: 1K+ graphV ′ ← {1, · · · n}
E ′ ← empty set
Vk′ ← degree k node vi
for all degree k do
if |Vk′ | < k + 1 thenif ntri[k] < the number of triangles can be generated
by the size |Vk′ | clique thengenerate clique with nodes v ∈ Vk′ whose size cangenerate the nearest number of triangles to ntri[k]update E ′else
generate size |Vk′ | clique with nodes v ∈ Vk′
update E ′end ifelse
if |Vk′ | ≥ the number of triangles can be generated by
the size k clique thengenerate size k + 1 clique with nodes v ∈ Vk′
update E ′else
generate clique with nodes v ∈ Vk′ whose size cangenerate the nearest number of triangles to ntri[k]update E ′end ifend ifend formatch the degree with configuration modelG′ ← (V ′ , E ′ )return G′

6

CONCLUSION AND FUTURE WORKIn this study, we examined the variation of properties ofgraphs generated by the graph generation model based on
dK-series. We also considered the distribution of errors: theerror variation is small for properties not given as inputs in
the generation models.
Furthermore, we proposed a model for generating a 1K+
graph that focuses on cliques and constructs triangles using
degree-dependent clustering coeﬃcients as input. We showedthat this model is faster than 1K and 2.5K graph generation
and, depending on the topology, can reduce the error of theproperties compared to those of the 2K graph.
The future task is to improve the 1K+ model by making
its degree-dependent clustering coeﬃcients closer to the inputs and to stably reduce the errors in the properties, suchas the maximum clique distribution.

(a) 0K(b) 1K(c) 2K(d) 1K+

Figure 3: Distribution of degree-dependent clustering coeﬃcient (Caltech).

ACKNOWLEDGMENTS
This work was supported by New Energy and Industrial
Technology Development Organization (NEDO).

REFERENCES[1] Yong-Yeol Ahn, Seungyeop Han, Haewoon Kwak, Sue Moon, andHawoong Jeong. 2007. Analysis of topological characteristics ofhuge online social networking services. In Proceedings of the 16th
international conference on World Wide Web. 835–844.
[2] Shweta Bansal, Shashank Khandelwal, and Lauren Ancel Meyers. 2009. Exploring biological network structure with clustered
random networks. BMC Bioinformatics 10, 1 (2009), 405.
[3] Edward A. Bender and E. Rodney Canfield. 1978. The Asymptotic Number of Labeled Graphs with Given Degree Sequences.
Journal of Combinatorial Theory, Series A 24, 3 (1978), 296–
307.
[4] Béla Bollobás. 1980. A Probabilistic Proof of an Asymptotic
Formula for the Number of Labelled Regular Graphs. European
Journal of Combinatorics 1, 4 (1980), 311–316.
[5] Nicholas C. Wormald. 1981. The asymptotic connectivity of labelled regular graphs. Journal of Combinatorial Theory, Series
B 31, 2 (1981), 156–167.
[6] Fan Chung and Linyuan Lu. 2002. Connected Components in
Random Graphs with Given Expected Degree Sequences. Annalsof Combinatorics 6, 2 (2002), 125–145.
[7] Fan Chung and Linyuan Lu. 2004. The Average Distance in a
Random Graph with Given Expected Degree. Internet Mathematics 1, 1 (2004), 91–113.
[8] NetworkX 1.10 documentation. 2015.
gnm random graph.
Retrieved February 12, 2020 from https://networkx.github.io/
documentation/networkx-1.10/reference/generated/networkx.
generators.random graphs.gnm random graph.html[9] Rick Durrett. 2006. Random Graph Dynamics.
[10] Mark E.J. Newman, Steven H. Strogatz, and Duncan J Watts.
2001. Random Graphs with Arbitrary Degree Distributions andtheir Applications. Physical review. E 64, 2 (2001), 026118.
[11] P. Erdős and A. Rényi. 1959. On Random Graphs I. Publicationes Mathematicae Debrecen 6 (1959), 290.
[12] Emilio Ferrara. 2014. Measurement and Analysis of Online Social Networks Systems. 891–893.
[13] Minas Gjoka. 2013. 2.5K-Graphs Software. Retrieved February
12, 2020 from http://www.minasgjoka.com/2.5K/instructions/

16th Int'l Workshop on Mining and Learning with Graphs(MLG 2020), August 2020 (non-archival)

Comparison of Graph Generation Models focusing on
Accuracy and Variation[14] Minas Gjoka. 2018. Index of /2.5K/graphs. Retrieved February
12, 2020 from http://www.minasgjoka.com/2.5K/graphs/[15] Minas Gjoka, Maciej Kurant, and Athina Markopoulou. 2013.
2.5 k-graphs: from sampling to generation. In 2013 Proceedings
IEEE INFOCOM. 1968–1976.
[16] James P. Gleeson. 2009. Bond percolation on a class of clustered
random networks. Physical review. E 80, 3 (2009), 036107.
[17] Charo I Del Genio, Hyunju Kim, Zoltan Toroczkai, and Kevin
Bassler. 2010. Eﬃcient and Exact Sampling of Simple Graphswith Given Arbitrary Degree Sequence. PloS one 5, 4 (2010),
e10012.
[18] Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue B. Moon.
2010. What is Twitter, a social network or a news media?. In Proceedings of the 19th international conference on World Wide
Web. 591–600.
[19] Jure Leskovec and Christos Faloutsos. 2006. Sampling from large
graphs. In Proceedings of the 12th ACM SIGKDD international
conference on Knowledge discovery and data mining. 631–636.
[20] Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.
edu/data.
[21] T. Luczak. 1989. Sparse random graphs with a given degree
sequence. In Proceedings of the Symposium on Random Graphs,
Poznan. 165–182.
[22] Junling Ma, P. van den Driessche, and Frederick H. Willeboordse.
2013. Eﬀective degree household network disease model. Journalof Mathematical Biology 66, 1 (2013), 75–94.
[23] Priya Mahadevan, Dmitri Krioukov, Kevin Fall, and Amin Vahdat. 2006. Systematic topology analysis and generation using
degree correlations. ACM SIGCOMM Computer Communication Review 36, 4 (2006), 135–146.
[24] Michael Molloy and Bruce A. Reed. 1995. A Critical Point for
Random Graphs with a Given Degree Sequence. Random structures & algorithms 6, 2-3 (1995), 161–180.

MLG ’20, August, 2020, San Diego, CA[25] Michael Molloy and Bruce A. Reed. 1998. The Size of the GiantComponent of a Random Graph with a Given Degree Sequence.
Combinatorics, Probability & Computing 7, 3 (1998), 295–305.
[26] Mark EJ Newman. 2009. Random Graphs with Clustering. Physical review letters 103 (2009), 058701.
[27] Chiara Orsini, Marija Mitrović Dankulov, Pol Colomer de Simon, Almerima Jamakovic, Priya Mahadevan, Amin Vahdat,
Kevin E. Bassler, Zoltán Toroczkai, Marián Boguñá, Guido Caldarelli, Santo Fortunato, and Dmitri V. Krioukov. 2015. Quantifying randomness in real networks. Nature communications 6,
1 (2015), 1–10.
[28] M Angeles Serrano and Marián Boguná. 2005. Tuning clusteringin random networks with arbitrary degree distributions. Physicalreview. E 72 (2005), 036133.
[29] Isabelle Stanton and Ali Pinar. 2011. Sampling Graphs with a
Prescribed Joint Degree Distribution Using Markov Chains. In
Proceedings of the 13th Workshop on Algorithm Engineeringand Experiments. 151–163.
[30] Isabelle Stanton and Ali Pinar. 2012. Constructing and Sampling
Graphs with a Prescribed Joint Degree Distribution. Journal of
Experimental Algorithmics 17 (2012), 3–1.
[31] Bálint Tillman, Athina Markopoulou, Minas Gjoka, and Carter T
Buttsc. 2019. 2K+ Graph Construction Framework: Targeting
Joint Degree Matrix and Beyond. IEEE/ACM Transactions on
Networking 27, 2 (2019), 591–606.
[32] Cheng Wang, Omar Lizardo, and David Hachen. 2014. Algorithms for generating large-scale clustered random graphs. Network Science 2, 3 (2014), 403–415.
[33] Duncan J. Watts and Steven H. Strogatz. 1998. Collective dynamics of ’small-world’ networks. Nature 393, 6684 (1998), 440–
442.

16th Int'l Workshop on Mining and Learning with Graphs(MLG 2020), August 2020 (non-archival)