=Paper= {{Paper |id=Vol-3135/dataplat_paper2 |storemode=property |title=RTGEN : A Relative Temporal Graph GENerator |pdfUrl=https://ceur-ws.org/Vol-3135/dataplat_paper2.pdf |volume=Vol-3135 |authors=Maria Massri,Zoltan Miklos,Philippe Raipin,Pierre Meye |dblpUrl=https://dblp.org/rec/conf/edbt/Massri0RM22 }} ==RTGEN : A Relative Temporal Graph GENerator== https://ceur-ws.org/Vol-3135/dataplat_paper2.pdf

RTGEN : A Relative Temporal Graph GENerator
Maria Massri1 , Zoltan Miklos2 , Philippe Raipin1 and Pierre Meye1
1
Orange Labs, Cesson-Sévigné, France
2
University of Rennes CNRS IRISA, Rennes, France

Abstract
Graph management systems are emerging as an efficient solution to store and query graph-oriented data. To assess the
performance and compare such systems, practitioners often design benchmarks in which they use large scale graphs. However,
such graphs either do not fit the scale requirements or are not publicly available. This has been the incentive of a number of
graph generators which produce synthetic graphs whose characteristics mimic those of real-world graphs (degree distribution,
community structure, diameter, etc.). Applications, however, require to deal with temporal graphs whose topology is in
constant change. Although generating static graphs has been extensively studied in the literature, generating temporal
graphs has received much less attention. In this work, we propose RTGEN a relative temporal graph generator that allows the
generation of temporal graphs by controlling the evolution of the degree distribution. In particular, we propose to generate
new graphs with a desired degree distribution out of existing ones while minimizing the efforts to transform our source graph
to target. Our proposed relative graph generation method relies on optimal transport methods. We extend our method to also
deal with the community structure of the generated graphs that is prevalent in a number of applications. Our generation
model extends the concepts proposed in the Chung-Lu model with a temporal and community-aware support. We validate
our generation procedure through experiments that prove the reliability of the generated graphs with the ground-truth
parameters.

Keywords
Temporal graphs, Graph generation, Optimal transport

1. Introduction class citizen in graph management systems [13, 14, 15,
16]. Most of these systems rely on real-world temporal
Graphs are the most natural model to describe real world graphs to evaluate their proposed methods. Real-world
interactions and are currently used in a myriad of appli- graphs, however, do not often fit the scale requirements.
cation domains such as citation [1], transportation [? ], Therefore, practitioners must rely on a temporal graph
and sensor networks [2] to cite just a few. These graphs generator that is able to produce large scale graphs whose
are managed by a graph management system whose per- evolution correlates with that of real world temporal
formance is usually evaluated through graph-centered graphs. To tackle this challenge, we proposed RTGEN:
benchmarks that address different performance metrics a relative temporal graph generator that produces large
such as ingestion throughput, space usage and query scale temporal graphs by controlling a number of key
execution time. In this context, practitioners refer to real- features that characterises the evolution of real-world
world and synthetic graphs to use in the benchmarks. graphs. That is, our generation procedure, controls the
Indeed, available graph generation techniques fill the evolution of the degree distribution by extending a very
gap between real and synthetically generated graphs by common generation technique [17] referred to as the
trying to mimic the characteristics of real graphs such as Chung-Lu model with temporal and community-aware
controlling the degree distribution [3, 4, 5, 6, 7, 8]. Besides, support.
a number of existing graph generators are community- We model a temporal graph by a sequence of snapshots
aware in the sense that they group vertices that are more 𝑆 = {𝐺0 , . . . , 𝐺𝑁 } where 𝐺𝑖 is the graph snapshot at
densely connected between each other than they are timestamp 𝑡𝑖 and characterized by a degree distribution
with the rest of the graph, in separate or overlapping that is generated from sampling user-defined temporal
sub-graphs called communities [9, 10, 11]. parameters. Having this, our relative graph generation
Real graphs, however, are dynamic [12] such that their procedure consists of transforming 𝐺𝑖−1 into 𝐺𝑖 by ap-
topology is subject to continuous changes. In this context, plying a stream of atomic graph operations with respect
a new emphasis is being placed to support time as a first to the desired degree distribution at time instants 𝑡𝑖−1
and 𝑡𝑖 . Based on the fact that a strong correlation exists
Published in the Workshop Proceedings of the EDBT/ICDT 2022 Joint between successive snapshots [18, 19, 20], we propose
Conference (March 29-April 1, 2022), Edinburgh, UK
to minimize the number of graph operations that have
" maria.massri@orange.com (M. Massri); zoltan.miklos@irisa.fr
(Z. Miklos); philippe.raipin@orange.com (P. Raipin); to be applied in order to transform a graph snapshot
pierre.meye@orange.com (P. Meye) into its successor. The main idea consists of minimizing
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons Li-
cense Attribution 4.0 International (CC BY 4.0).
the distance between degree distributions of successive
CEUR Workshop Proceedings (CEUR-WS.org)
snapshots. We achieve this goal by relying on an optimal Given the number of vertices in each graph snap-
transport solver which provides a transportation plan ca- shot 𝑘𝑖 ∈ {𝑘1 , . . . , 𝑘𝑛 }, a stochastic community
pable of transforming a "mass" from source distribution matrix 𝑀 and a sequence of degree distributions
to target distribution with a minimum of work. In order {𝜑1 , . . . , 𝜑𝑛 }, we generate a sequence of graph snap-
to apply the obtained transportation plan, we proposed a shots {𝐺1 , . . . , 𝐺𝑛 } such that each snapshot 𝐺𝑖 is
straightforward generalization of the well-known Chung- relatively generated by transforming 𝐺𝑖−1 . This
Lu’s model, also known as the CL model, that was first transformation is based on morphing the 𝜑𝐺𝑖−1 =
discussed in [21] and formalized in [17, 22]. We choose to 𝐺 𝐺 𝐺 𝐺
{(𝑥1 𝑖−1 , 𝜔1 𝑖−1 ), . . . , (𝑥𝑛 𝑖−1 , 𝜔𝑛 𝑖−1 )} into 𝜑𝑖 =
extend this model for the reasons of simplicity and scal- {(𝑥1 , 𝜔1 ), . . . , (𝑥𝑘 , 𝜔𝑘 )} and preserving the community
𝑖 𝑖 𝑖 𝑖

ability. We also extended the CL model to partition the structure that is represented by the stochastic commu-
graph into ground-truth communities that coexist with nity matrix 𝑀 such that 𝑀𝐺𝑖−1 = 𝑀𝐺𝑖 = 𝑀 . Note
the aforementioned time-dependent degree distribution. that each element 𝑚𝑢𝑣 of M is equal to the probability
Our contributions are validated through experimental of edge creation between the source and target commu-
results showing the evolution of the degree distribution nities 𝑐𝑢 and 𝑐𝑣 . Figure 1 illustrates the relative graph
and community structure with respect to ground-truth generation procedure. Each graph snapshot 𝐺𝑖 is rela-
input parameters. tively generated by transforming its ancestor 𝐺𝑖−1 . This
The rest of the paper is organized as follows, Section transformation is based on computing a transportation
2 provides an overview of the generation procedure. Sec- matrix 𝑇 that minimizes the cost of morphing 𝜑𝐺𝑖−1
tion 3 introduces the baseline generation procedure of the into 𝜑𝑖 . The computation of the transportation matrix
CL model. Section 4 describes the proposed community- reduces to an optimal transport problem. Based on the
aware extension of the CL model. Section 5 presents computed transportation matrix, each vertex belonging
a detailed description of the proposed generation pro- to the graph 𝐺𝑖−1 is assigned with a linkage or break-
cedure. Section 6 provides an experimental evaluation age probability to indicate the probability of adding or
of the synthetically generated temporal graphs. Section removing an edge. This phase is followed by creating or
7 describes the related work. Section 8 concludes the removing edges to or from the graph 𝐺𝑖−1 to produce
work. the graph 𝐺𝑖 . These graph updates follows the linkage
or breakage probabilities assigned for each of the ver-
tices. Finally, the graph 𝐺𝑖 is computed by applying
2. Overview the generated updates on 𝐺𝑖−1 . Note that, the genera-
In this section, we describe the overall generation pro- tion procedure depicted in this Figure shows a simplified
cedure. Given the characteristics of a series of graph scenario where the number of vertices does not change.
snapshots, our relative generation procedure produces However, if that number changes, a phase consisting of
the series of graph snapshots {𝐺1 , . . . , 𝐺𝑛 } whose char- the addition or deletion of vertices should precede the
acteristics approximate the given ones. These graph snap- computation of the transportation matrix to assure the
shots are relatively computed by applying a number of following constraint:
graph updates on each snapshot in order to produce its 𝑘 𝑚
successor snapshot. To clarify, we apply a number of
∑︁ ∑︁
𝜔𝑠𝐺𝑖 = 𝜔𝑡𝑖 , ∀1 ≤ 𝑖 ≤ 𝑛
graph updates on a graph snapshot 𝐺𝑖−1 to produce an- 𝑠=1 𝑡=1
other graph snapshot 𝐺𝑖 whose characteristics approx-
imate the given parameters assigned for the 𝑖th graph This constraint implies that the sum of weights of distri-
snapshot. butions 𝜑𝐺𝑖 and 𝜑𝑖 should be equal.
Formally, we define a graph snapshot 𝐺𝑖 valid at a
time instant 𝑡𝑖 as the tuple {𝑉𝐺𝑖 , 𝐸𝐺𝑖 , 𝜑𝐺𝑖 , 𝑀𝐺𝑖 } where 3. Graph generation with given
𝑉𝐺𝑖 is the set of vertices, 𝐸𝐺𝑖 is the set of edges, 𝜑𝐺𝑖
is a degree distribution and 𝑀𝐺𝑖 is the density commu- expected degree distribution
nity matrix. For instance, we consider 𝜑𝐺𝑖 of the form
In this section, we describe the generation procedure of
𝑛 , 𝜔𝑛 )} as a discrete distribution
{(𝑥1𝐺𝑖 , 𝜔1𝐺𝑖 ), . . . , (𝑥𝐺𝑖 𝐺𝑖

over N where 𝑥𝑗 refers to the degree of a node and 𝜔𝑗
𝐺𝑖 𝐺𝑖 random static graphs with a given degree distribution.
refers to the total number of vertices in the graph whose Random graphs were introduced by Erdős and Rényi
total number of edges is equal to 𝑥𝐺 𝑖
. A density commu- [23]. The popularity of this model, also known as the 𝐸𝑅
𝑗
nity matrix 𝑀𝐺𝑖 defines the community structure of the model, stems from its simple generation procedure that
generated graphs, each element 𝑚𝑢𝑣 of which is equal consists of generating a number of vertices and connect-
to the density of edges between the source community ing them by an edge after picking each endpoint with a
𝑐𝑢 and the target community 𝑐𝑣 . fixed probability 𝑝. However, this model produces graphs
whose degree distribution follows a binomial distribution
probability 𝑝𝑣𝑖 in the following Equation:

𝑑𝑣𝑖
𝑝𝑣𝑖 = (1)
𝐷
Subsequently, a linkage phase consists of picking |𝐸| =
𝐷
2
pairs of vertices to connect such that for a sufficiently
large |𝐸| the random variable denoting the degree of
vertex 𝑣𝑖 is Poisson distributed with a mean equals to
𝑑𝑣𝑖 . Iterating the linkage phase |𝐸| times where an edge
is equally likely to be chosen in both directions for undi-
rected graphs, the insertion probability of an edge con-
necting vertex 𝑣𝑖 and vertex 𝑣𝑗 is 𝑝𝑣𝑖 𝑣𝑗 = 2𝑝𝑣𝑖 𝑝𝑣𝑗 𝐷 2
.
The edge insertion probability can be rewritten in the
more convenient form:
𝑑𝑣𝑖 𝑑𝑣𝑗
𝑝𝑣𝑖 𝑣𝑗 =
𝐷
For optimisation sake, we gather all vertices shar-
Figure 1: Relative graph generation procedure. ing the same degree together in a pool 𝛾𝑑 =
{𝑣𝑖 |𝑣𝑖 ∈ 𝑉 ∧ 𝑑𝑣𝑖 = 𝑑} that we use as a subsidiary gen-
eration component. Each vertex in a pool is equally likely
to be chosen assuring that the aforementioned linkage
with a mean degree equals to (𝑁 −1)𝑝 where 𝑁 is the to- probability 𝑝 is not affected for a sufficiently large num-
𝑣𝑖
tal number of vertices. Hence, it fails to mimic real-world ber of vertices. After the degree assignment phase, ver-
graphs that usually follow a power-law degree distribu- tices are distributed throughout the pools having each
tion. To tackle this limitation, the edge configuration the following linkage probability:
model [24] consists of generating a random graph whose
degree distribution matches, approximately, a given de- 𝑑|𝛾𝑑 |
gree distribution. That is, each vertex is assigned with a 𝑝𝛾𝑑 =
𝐷
number of stubs equal to its desired degree that is drawn
independently from the given degree distribution. Hav- Now, instead of picking vertices a pool is first picked
ing this, pairs of stubs are linked randomly forming edges It should be highlighted that self-loops or multi-edges
between their endpoints. Although this technique ap- can be created since each endpoint of an edge is picked
proximately matches any given degree distribution, a independently. The number of these edges, however, is
relaxed version known as the Chung-Lu model was in- independent of the number of vertices and thus can be
troduced in [21]. This model consists of generating a ran- neglected for large scale graphs.
dom graph that approximately matches a given degree
distribution relying on a simple generation procedure 4. Community-aware graph
that can be considered as a variant of the 𝐸𝑅 model. For
simplicity, we will refer to this model as the CL model in generation with given expected
the following description. degree distribution
Consider the degree distribution 𝜑 as the input param-
eter to the CL model and the undirected, unweighted and Although the CL model produces graphs with respect
unlabeled graph 𝐺 = {𝑉, 𝐸, 𝜑𝐺 } as the output where to a given degree distribution, it is not aware of the
𝜑𝐺 denotes the degree distribution of 𝐺, 𝑉 and 𝐸 de- community structure existing in most real-world graphs.
note the set of vertices and edges, respectively. Having Hence, we propose a community-aware extension of the
this, the CL model produces a graph 𝐺 such that 𝜑𝐺 is CL model based on the stochastic block model (SBM).
an approximation of 𝜑. The main idea is to pick each Since a community is not quantitatively well defined,
endpoint of an edge with a certain probability such that, many definitions where provided in literature. Intuitively,
at the end of the generation procedure, the total number one can consider a community as a subgraph which ver-
of incident edges to each vertex is close to its assigned tices are more densely connected between each other
degree. Hence, the starting phase consists of assigning than they are with the rest of the graph. Let’s consider
each vertex 𝑣𝑖 ∈ 𝑉 with a degree 𝑑𝑣𝑖 and a linkage the set of communities 𝐶 = {𝑐𝑖 } and suppose that a ver-
probability 𝑝𝑣𝑖 ∝ 𝑑𝑣𝑖 . Considering that 𝐷 is the sum of tex should belong to one community and edges should
the degrees extracted from 𝜑, we define the CL linkage be differentiated into within and between edges:
• Given a community 𝑐𝑖 , an edge 𝑒 is called a within define 𝜔𝑖𝑗 = 𝜔𝑗𝑖 = 2𝑚𝑖𝑗 and 𝜔𝑖𝑖 = 𝑚𝑖𝑖 . Furthermore,
edge if the source vertex ∈ 𝑐𝑖 and the target vertex we assign each community 𝑐𝑖 with a within edge creation
∈ 𝑐𝑖 . probability 𝑝𝑖𝑛
𝑐𝑖 , a between edge creation equal to 𝑝𝑐𝑖
𝑜𝑢𝑡

• Given two communities 𝑐𝑖 and 𝑐𝑗 , an edge 𝑒 is and a probability of edge creation 𝑝𝑐𝑖 such that:
called a between edge if the source vertex ∈ 𝑐𝑖 |𝐶|
and target vertex ∈ 𝑐𝑗 or vice versa. 𝑝𝑐𝑖 = 𝑝𝑖𝑛 𝑜𝑢𝑡
∑︁
(2)
𝑐𝑖 + 𝑝𝑐𝑖 = 𝜔𝑖𝑖 + 0.5 𝜔𝑖𝑗
To insure that vertices belonging to a community are 𝑗=1,𝑗̸=𝑖

more densely connected to each other than they are with We define the linkage probability 𝑝𝑣𝑖 of choosing a vertex
the rest of the graph, the within and between edge cre- 𝑣𝑖 belonging to community 𝑐𝑚 as follows:
ation probabilities 𝑝𝑖𝑛𝑐𝑖 and 𝑝𝑐𝑖 of 𝑐𝑖 must satisfy the
𝑜𝑢𝑡

condition 𝑝𝑖𝑛 𝑜𝑢𝑡 𝑑 𝑣𝑖
𝑐𝑖 > 𝑝 𝑐𝑖 , ∀𝑐 𝑖 ∈ 𝐶. 𝑝 𝑣𝑖 = 𝑝𝑐 , 𝑣𝑖 ∈ 𝑐𝑚 (3)
𝐷𝑐𝑚 𝑚
4.1. Stochastic block model where 𝐷𝑐𝑚 is the sum of the degrees of vertices belong-
ing to community 𝑐𝑚 and 𝑝𝑐𝑚 is the probability of choos-
In this section, we formulate the SBM model [9] (also ing 𝑐𝑚 . The linkage probability of a vertex is the product
known as the planted partition model) which is com- of the probability 𝑝𝑐𝑚 of choosing the community to
monly used for the generation of random graphs with a 𝑑
which the vertex belongs and the probability 𝐷𝑐𝑣𝑖 of
given community structure. Hence, this generation pro- 𝑚

cedure only considers controlling the community struc- choosing the vertex 𝑣𝑖 in that community. Hence, Equa-
ture of the graph and overlooks the resulting degree dis- tion 3 assures the approximation of the community ma-
𝑑𝑣𝑖
tribution. The input of the generation procedure is a trix. However, 𝑝𝑣𝑖 should be equal to 𝐷 (Equation 1)
stochastic community matrix 𝑀 , each element 𝑚𝑖𝑗 of to assure the approximation of the degree distribution.
which defines the probability of edge creation between Therefore, we define the following condition in order to
the source community 𝑐𝑖 and the target community 𝑐𝑗 . reduce Equation (3) to Equation (1):
The output is a graph 𝐺 = {𝑉, 𝐸, 𝑀𝐺 } where 𝑀𝐺 is 𝐷𝑐𝑚 = 𝐷𝑝𝑐𝑚
the obtained density community matrix, each element
𝐷
𝑚𝐺 𝑖𝑗 of which defines the relative edge density between Now, replacing 𝐷 by 𝐷𝑝𝑐𝑐𝑚 in the original CL linkage
𝑚
the source community 𝑐𝑖 and the target community 𝑐𝑗 . probability (Equation 1) which assures the control of the
The generation procedure starts with the distribution of degree distribution, we obtain Equation 3 which assures
vertices between the planted communities such that each the control of the community structure. Having this, the
vertex belongs to a single community. Now, the linkage duality of the linkage probability given in Equations (1)
probability between a vertex belonging to community 𝑐𝑖 and (3) insures that both requirements are satisfied by
and another vertex belonging to community 𝑐𝑗 is equal to our generation procedure.
𝑚𝑖𝑗 . However, the extracted community density matrix For performance amelioration, we consider the selec-
𝑀𝐺 from the resulting graph 𝐺 is an approximation of tion of pools rather than vertices such that a pool is local
𝑀 . That is, each element 𝑚𝐺 𝑖𝑗 is binomially distributed to one community. That is vertices having the same de-
with mean equals to 𝑚𝑖𝑗 and Poisson distributed with gree variation and belonging to the same community 𝑐𝑚
the same mean for a sufficiently large number of edges. are grouped in a pool 𝛾𝑑𝑐𝑚 = {𝑣𝑖 |𝑣𝑖 ∈ 𝑐𝑚 ∧ 𝑑𝑣 𝑖 = 𝑑}
such that the probability of a pool selection for edge
4.2. Stochastic block model with given insertion is:
𝑑|𝛾𝑑𝑐𝑚 |
degree distribution 𝑝 𝛾 𝑐𝑚 =
𝑑 𝐷
In this section, we propose a static graph generation
procedure which controls both the community structure 4.3. Hierarchical community structure
and degree distribution. Given a degree distribution 𝜑 The specification of the stochastic matrix is not straight-
and a stochastic community matrix 𝑀 , our proposed forward and imposes an exhaustive number of user-
model generates a graph 𝐺 which degree distribution 𝜑𝐺 defined parameters. Hence, we define an auto-generative
is an approximation of 𝜑 and density community matrix procedure that fills the matrix with no exogenous effort.
𝑀𝑔 is an approximation of 𝑀 . In the following, we Considering a static graph, we construct a stochastic ma-
provide a description of our generation mechanism that trix that reflects a hierarchical community structure with
extends the stochastic block model depicted in Section only two given parameters. In a hierarchical community
4.1. matrix, communities recursively embed subsequent com-
Since the generated graph 𝐺 is undirected, the matrix munities in a self-similar fashion such that the commu-
𝑀 is symmetric such that 𝑚𝑖𝑗 = 𝑚𝑗𝑖 . Having this, we nity structure is represented by a hierarchical tree where
each node represents a community. Each non-leaf node cost:
𝑛 ∑︁
𝑚
is expanded into 𝑏 other nodes until reaching a desired ∑︁
min 𝑡𝑖𝑗 𝑑𝑖𝑗
tree height ℎ (Figure 2). The ending recursion results in 𝑇
𝑖=1 𝑗=1
𝑛𝑐 = 𝑏ℎ leaf-nodes referencing the finest scale communi-
ties having a linkage probability 𝜔𝑖𝑗 proportional to the where 𝑑𝑖𝑗 = 𝑑(𝑥𝑖 , 𝑦𝑗 ) is a measure of distance between
distance between 𝑐𝑖 and 𝑐𝑗 . The distance between two 𝑥𝑖 and 𝑦𝑗 . The following constraints must hold for the
communities, 𝑑(𝑐𝑖 , 𝑐𝑗 ), is equal to the number of hops optimal flow 𝑇 :
traversed in order to reach the least common ancestor of
these communities. In order to satisfy the condition stat- 𝑡𝑖𝑗 ≥ 0, 1 ≥ 𝑖 ≥ 𝑛, 1 ≥ 𝑗 ≥ 𝑚
ing that within edge linkage probability must be higher 𝑚 𝑛
than between linkage probability (𝑝𝑖𝑛𝑐𝑖 > 𝑝𝑐𝑖 ), we define
𝑜𝑢𝑡
∑︁ ∑︁
𝑡𝑖𝑗 ≤ 𝑝𝑖 , 1 ≥ 𝑖 ≥ 𝑛, 𝑡𝑖𝑗 ≤ 𝑞𝑗 , 1 ≥ 𝑗 ≥ 𝑚
𝜔𝑖𝑖 as follows: 𝑗=1 𝑖=1

𝑐 −1
𝑛∑︁ Once the optimal flow 𝑇 is found, the EMD between
𝜔𝑖𝑖 = 0.5 𝜔𝑖𝑗 + 𝑘 𝑃 and 𝑄 is computed as follows:
𝑗=0,𝑗̸=𝑖 ∑︀𝑛 ∑︀𝑚
𝑖=1 𝑗=1 𝑡𝑖𝑗 𝑑𝑖𝑗
where 𝑘 is a tunable parameter which calibration steers 𝐸𝑀 𝐷(𝑃, 𝑄) = ∑︀𝑛 ∑︀𝑚
𝑗=1 𝑡𝑖𝑗
the difference between within and between edge densi- 𝑖=1

ties. The effect of varying 𝑘 is further highlighted in the The EMD is fundamental in our generation procedure
Section 6. since it is used to compute the distance between two
degree distributions as described in the following Section.

5.2. Baseline relative graph generation
In this section, we provide the baseline procedure of
transforming a graph 𝐺 with degree distribution 𝜑 into
𝐺′ with degree distribution 𝜑′ which we refer to as the
Baseline relative graph generation. Note that, we use this
technique for generating temporal graphs such that 𝐺
Figure 2: Hierarchical community tree with height ℎ and and 𝐺′ corresponds to successive graph snapshots. For
branching factor 𝑏. generalisation purposes, however, we remove the notion
of time in this section. This transformation is enabled by a
set of atomic graph operations including the addition and
deletion of a vertex or an edge. Following the assumption
that temporal graphs gradually evolve, this number of
5. Relative graph generation graph operations between successive snapshots should
be minimized which is assured in our model by applying
In order to control the evolution of the degree distribu- an optimal transport method.
tion of the generated temporal graphs, we propose in this Consider the input graph 𝐺 = {𝑉, 𝐸, 𝜑} and de-
section an extension of the CL model that is based on the gree distribution 𝜑′ , the generated output graph 𝐺′ =
optimal transport to compute the minimal distance be- {𝑉 ′ , 𝐸 ′ , 𝜑𝐺′ } such that 𝜑𝐺′ is an approximation of 𝜑′ .
tween the degree distributions of each pair of successive We define the distance between two degree distributions
graph snapshots. 𝜑 and 𝜑′ as the earth mover’s distance 𝐸𝑀 𝐷(𝜑, 𝜑′ ).
Consider 𝛿𝑛 = |𝑉 ′ | − |𝑉 | as the total number of ver-
tices to be added to or removed from the graph based
5.1. Earth mover’s distance
on whether 𝛿𝑛 is a positive or negative number, respec-
The Earth mover’s distance can be defined as a mea- tively. When adding a new vertex, this vertex is assigned
sure of distance over a domain 𝐷 between two dis- with a degree equals to 0 and deleting a vertex consists
tributions of the form {(𝑥1 , 𝜔1 ), ..., (𝑥𝑛 , 𝜔𝑛 )} where of removing the vertex with its corresponding incident
𝑥𝑖 ∈ 𝐷 and 𝜔𝑖 is the density of 𝑥𝑖 . Having this, edges. This transformation phase assures that 𝐺 and 𝐺′
the problem reduces to the computation of an optimal share the same number of vertices, hence, enables the
flow (transportation matrix) 𝑇 = [𝑡𝑖𝑗 ] between two transformation of 𝜑 into 𝜑′ . In order to morph 𝜑 into
distributions 𝑃 = {(𝑥1 , 𝑝1 ), ..., (𝑥𝑛 , 𝑝𝑛 )} and 𝑄 = 𝜑′ , a transportation matrix 𝑇 is computed, where each
{(𝑦1 , 𝑞1 ), ..., (𝑦𝑛 , 𝑞𝑛 )} such that 𝑡𝑖𝑗 is the mass trans- row corresponds to a degree 𝑑 in the set of degrees in the
ported between 𝑝𝑖 and 𝑞𝑗 which minimizes the overall source distribution 𝜑 and each column corresponds to a
degree 𝑑′ in the set of degrees in the target distribution 𝜑′ .
Now, each cell consists of the portion of vertices having
a degree 𝑑 for which links are to be inserted or removed
in order to be assigned a total number of edges equals to
degree 𝑑′ . That is, a vertex 𝑣𝑖 , with a degree 𝑑𝑣𝑖 = 𝑑, will
be assigned a degree variation of 𝛿𝑑𝑣𝑖 = 𝑑′ − 𝑑 resulting
in a total number of edge insertions and deletions defined
as 𝐷+ and 𝐷− , respectively.
We assign, for each vertex 𝑣𝑖 , a linkage probability 𝑝+ 𝑣𝑖 or Figure 3: Graph representing the case of a non-possible edge
a breakage probability 𝑝− 𝑣𝑖 defined as extensions of the
breakage.
CL linkage probability (1):
𝛿𝑑𝑣𝑖 desired degree distribution 𝜑 and the stochastic block
𝑝+
𝑣𝑖 = , 𝛿𝑑𝑣𝑖 > 0 (4)
𝐷+ matrix 𝑀 . However, the output consists of a graph
−𝛿𝑑𝑣𝑖 𝐺′ = {𝑉 ′ , 𝐸 ′ , 𝜑𝐺′ , 𝑀𝐺′ } where 𝜑𝐺′ is an approxima-
𝑝−
𝑣𝑖 = , 𝛿𝑑𝑣𝑖 < 0 (5) tion of 𝜑 and 𝑀𝐺′ is an approximation of 𝑀 . Recall that
𝐷−
We collect vertices sharing the same degree variation the generation procedure depicted in section 4.2 produces
𝛿𝑑 = 𝑑′ − 𝑑 into a linkage pool if 𝛿𝑑 > 0 and in a a graph with a given expected degree distribution and
breakage pool if 𝛿𝑑 < 0. Consider 𝛾𝑑→𝑑′ = {𝑣𝑖 |𝑣𝑖 ∈ stochastic community matrix based on the proposed link-
𝑉 ∧ 𝛿𝑣𝑖 = 𝑑′ − 𝑑} to be the pool containing vertices age probability duality presented in Equations (1) and (3).
having a degree 𝑑 that should be transformed into 𝑑′ . We Indeed, a relative community-aware graph generation is
compute the probability of picking a linkage or breakage based on an extension of the aforementioned duality by
pool 𝑝+ taking into consideration the degree variation of a vertex
𝛾𝑑→𝑑′ and 𝑝𝛾𝑑→𝑑′ as follows:
−
instead of the its degree. That is, the following linkage
𝛿𝑑|𝛾𝑑→𝑑′ | and breakage probabilities present a straightforward ex-
𝑝+
𝛾𝑑→𝑑′ = , 𝛿𝑑 > 0 tension of Equations (4) and (5):
𝐷+
𝛿𝑑𝑣𝑖
−𝛿𝑑|𝛾𝑑→𝑑′ | 𝑝+
𝑣𝑖 = 𝑝𝑐𝑚 , 𝑣𝑖 ∈ 𝑐𝑚
𝑝−
𝛾𝑑→𝑑′ = , 𝛿𝑑 < 0 𝐷𝑐+𝑚
𝐷−
However, breaking an edge might be impossible in situ- 𝛿𝑑𝑣𝑖
𝑝−
𝑣𝑖 = 𝑝𝑐𝑚 , 𝑣𝑖 ∈ 𝑐𝑚
ations where the source degree variation 𝛿𝑑 is negative 𝐷𝑐−𝑚
and the sum of the negative degree variations of its neigh- Where 𝐷𝑐+𝑚 and 𝐷𝑐−𝑚 are the total number of edge
bors is higher than 𝛿𝑑. For the sake of illustration, we insertions and deletions in 𝑐𝑚 , respectively. From the
present in Figure 3 a graph in which the number of edges transportation matrix defined in section 5.2, we find
to remove from a node is higher than the sum of the 𝑛𝑖𝑗 as the portion of vertices with degree variation
number of edges to remove from its neighboring vertices. 𝛿𝑑 = 𝑑𝑗 − 𝑑𝑖 . However, finding the portion 𝑛𝑐𝑖𝑗𝑚 of
That is, the transformation of this graph implies remov- vertices in community 𝑐𝑚 should satisfy three conditions
ing 2 edges from vertex 𝑣1 since 𝛿𝑣1 = −2. However, detailed bellow. Each condition 𝑖 results in a system of
the number of the edges that have to be removed from linear equations of the form 𝐴𝑖 𝑋 = 𝐵𝑖 where 𝑋 is a
the neighboring vertices of 𝑣1 is equal to 𝛿𝑣2 = −1 since 𝑐
vector composed of 𝑛𝑐𝑖𝑗𝑚 such that 𝑋 = {𝑛𝑖𝑗𝑘 | ∀1 ≤ 𝑖 ≤
𝛿𝑣3 = 0 and 𝛿𝑣4 = 1. To overcome this, we repeat the |𝜑𝐺 | ∧ ∀1 ≤ 𝑗 ≤ |𝜑| ∧ 0 ≤ 𝑘 ≤ |𝐶|} where 𝑛𝑐 is the
morphing procedure until EMD(𝜑, 𝜑′ ) reaches a desired total number of communities.
threshold. Our simulations have proved that the value
of EMD(𝜑, 𝜑′ ) converges rapidly towards the minimum Condition 1: For each community 𝑐𝑚 ∈ 𝐶, conditions
threshold after a tolerable number of iterations. This stating that 𝐷𝑐+𝑚 = 𝐷+ 𝑝𝑐𝑚 and 𝐷𝑐−𝑚 = 𝐷− 𝑝𝑐𝑚
statement will be further highlighted in Section 6. must hold, where 𝐷+ and 𝐷− are the total number
of edge insertions and deletions in all communities
5.3. Relative community-aware graph of 𝐶, respectively. Incorporating 𝑛𝑐𝑖𝑗𝑚 in the previous
generation condition translates to the following equality:
′ ′
|𝜑𝐺 | |𝜑 | |𝜑𝐺 | |𝜑 |
A more complex version of the previously described ∑︁ ∑︁ 𝑐𝑚
∑︁ ∑︁
(𝑑 𝑗 − 𝑑𝑖 )𝑛𝑖𝑗 = ( (𝑑𝑗 − 𝑑𝑖 )𝑛𝑖𝑗 )𝑝𝑐𝑚
relative graph generation, consists of preserving the
𝑖=0 𝑗=0 𝑖=0 𝑗=0
graph community structure in the transformation proce-
dure. That is, the input of our community-aware relative where 𝜑𝐺 and 𝜑′ are the source and target degree distri-
graph generator is the graph 𝐺 = {𝑉, 𝐸, 𝜑𝐺 , 𝑀𝐺 }, the butions.
Condition 2: This condition states that the sum of of adding and removing edges is repeated 𝐷+ and 𝐷−
all portions of vertices with degree variation 𝑑𝑗 − 𝑑𝑖 times, respectively. In each iteration, communities 𝑐𝑛 and
∀𝑑𝑗 ∈ 𝜑𝑡 in 𝑐𝑚 should be equal to the portion 𝑛𝑐𝑖 𝑚 of 𝑐𝑚 are picked based on 𝑐𝑑𝑓 𝐶𝑜𝑚𝑠 and vertices 𝑛𝑖 and
vertices in 𝑐𝑚 having a degree 𝑑𝑖 resulting in the follow- 𝑛𝑗 are picked using 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠+ [𝑛] and 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠− [𝑚].
ing equality: Now, an addition or deletion graph update between the
𝑚
∑︁ chosen vertices is added to the list of logs using functions
𝑛𝑐𝑖𝑗𝑚 = 𝑛𝑐𝑖 𝑚 addEdge and removeEdge whether the vertices where
𝑗=0
chosen from the linkage or breakage pools. However,
breaking an edge might be impossible in some situations
Condition 3: This condition states that the por- as shown in Figure 3. In such a use case, no graph update
tion 𝑛𝑖𝑗 of vertices with degree variation 𝑑𝑗 − 𝑑𝑖 in is added to the list of logs 𝐿. Finally, the EMD distance
the graph must be equal to the sum of all portions 𝑛𝑐𝑖𝑗𝑚 𝜖 ′is computed between the obtained degree distribution
∀𝑐𝑚 ∈ 𝐶. 𝜑 𝐺 and the desired one 𝜑. If 𝜖 ′
is higher than 𝜖 and
𝑛𝑐
∑︁ the number of repetitions 𝑐𝑢𝑟_𝑖𝑡𝑒𝑟 has not yet reached
𝑛𝑐𝑖𝑗𝑚 = 𝑛𝑖𝑗 𝑚𝑎𝑥_𝑖𝑡𝑒𝑟, the same algorithm is repeated on the newly
𝑐𝑚 =0 computed graph snapshot 𝐺′ . The computation stops
By solving the concatenated system of equations obtained when 𝜖′ is lower than or equal to 𝜖 or the number of
from the previous conditions 𝑐𝑜𝑛𝑐𝑎𝑡(𝐴1 , 𝐴2 , 𝐴3 )𝑋 = repetitions has already been reached.
𝑐𝑜𝑛𝑐𝑎𝑡(𝐵1 , 𝐵2 , 𝐵3 ), we find the vector 𝑋, hence the Algorithm 1: CRGG
values of 𝑛𝑐𝑖𝑗𝑚 . Pools are created on a local basis in each
Input: 𝐺 = {𝑉, 𝐸, 𝜑𝐺 , 𝑀𝐺 }, 𝜑, 𝑀 , 𝜖,
community such that vertices with the same degree vari-
𝑚𝑎𝑥_𝑖𝑡𝑒𝑟, 𝑐𝑢𝑟_𝑖𝑡𝑒𝑟
ation 𝛿𝑑 = 𝑑 − 𝑑 and belonging to the same community
′
Output: 𝐺′ = {𝑉 ′ , 𝐸 ′ , 𝜑𝐺′ , 𝑀𝐺′ }
𝑐𝑚 are collected in a single pool 𝛾𝑑→𝑑′ . We compute
𝑐𝑚
1 𝑇 ← getTransportMatrix(𝜑𝐺 , 𝜑) ;
the probability of picking a linkage or breakage pool
2 X ← getVector(𝜑𝐺 , 𝜑, 𝑇 , 𝑀 ) ;
𝑝𝛾𝑑→𝑑′ ,𝑐𝑚 and 𝑝𝛾𝑑→𝑑′ ,𝑐𝑚 as follows:
+ −
3 (𝐷 , 𝐷 ) ← getNumberOfEdges(T) ;
+ −

𝑐𝑚 4 𝑐𝑑𝑓 𝐶𝑜𝑚 ← getCDFComs(𝑀 ) ;
𝛿𝑑|𝛾𝑑→𝑑 ′|
𝑝+
𝛾𝑑→𝑑′ ,𝑐𝑚 = +
, 𝛿𝑑 > 0 5 (𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠+ , 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠− ) ← initCDFPools ;
𝐷
6 𝐿 ← 𝑖𝑛𝑖𝑡𝐿𝑜𝑔𝑠()
𝑐𝑚
−𝛿𝑑|𝛾𝑑→𝑑 ′| 7 for 𝑐𝑚 ∈ 𝐶 do
𝑝−
𝛾𝑑→𝑑′ ,𝑐𝑚 = , 𝛿𝑑 < 0 −
𝐷− 8 (𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠+𝑐𝑚 , 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠𝑐𝑚 ) ←
Algorithm CRGG depicts the relative community aware getCDFPools(𝑋, 𝑐𝑚 ) ;
graph generation procedure. The input parameters are 9 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠+ [𝑚] ← 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠+ 𝑐𝑚 ;
the graph snapshot 𝐺, desired degree distribution 𝜑, den- 10 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠− [𝑚] ← 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠− 𝑐𝑚 ;
sity community matrix 𝑀 , threshold of the EMD dis- +
11 for 𝑖 ← 0 𝑡𝑜 𝐷 do
tance between 𝜑𝐺 and 𝜑, maximum number of repeti-
12 (𝑐𝑛 , 𝑐𝑚 ) ← chooseComs(𝑐𝑑𝑓 𝐶𝑜𝑚) ;
tions 𝑚𝑎𝑥_𝑖𝑡𝑒𝑟 and the current number of repetitions
13 (𝑛𝑖 , 𝑛𝑗 ) ← chooseVertices(𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠+ [𝑛],
𝑐𝑢𝑟_𝑖𝑡𝑒𝑟. Whereas, the output is a new graph snapshot
𝐺′ . Note that, the value of 𝑐𝑢𝑟_𝑖𝑡𝑒𝑟 is equal to 0 in the 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠+ [𝑚]) ;
first iteration. The transportation matrix 𝑇 is computed 14 𝐿.addEdge (𝑛𝑖 , 𝑛𝑗 ) ;
using the function getTransportMatrix by taking the 15 for 𝑖 ← 0 𝑡𝑜 𝐷− do
degree distributions 𝜑𝐺 and 𝜑 as input. The function 16 (𝑐𝑛 , 𝑐𝑚 ) ← chooseComs(𝑐𝑑𝑓 𝐶𝑜𝑚) ;
getVector, computes 𝐴 and 𝐵 based on the Conditions 17 (𝑛𝑖 , 𝑛𝑗 ) ← chooseVertices(𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠− [𝑛],
1, 2 and 3 and solves the system of equations defined by 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠− [𝑚]) ;
𝐴𝑋 = 𝐵 to find the vector 𝑋. The total number of edges 18 𝐿.removeEdge (𝑛𝑖 , 𝑛𝑗 ) ;
to add (𝐷+ ) and delete (𝐷− ) are then computed based on
19 𝐺 ← applyLogs(𝐺, 𝐿) ;
′
the transporation matrix 𝑇 . The function getCDFComs
20 𝜖 ← getEMD(𝜑, 𝜑𝐺 ) ;
′ ′
computes the cumulative distribution function 𝑐𝑑𝑓 𝐶𝑜𝑚 ′
21 if 𝜖 ≥ 𝜖 ∧ 𝑐𝑢𝑟_𝑖𝑡𝑒𝑟 < 𝑚𝑎𝑥_𝑖𝑡𝑒𝑟 then
based on the density community matrix 𝑀 . Then, vectors
22 𝑐𝑢𝑟_𝑖𝑡𝑒𝑟 ← 𝑐𝑢𝑟_𝑖𝑡𝑒𝑟 + 1 ;
𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠+ and 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠− representing the cumulative
23 𝐺′ ←
density functions of the linkage and breakage pools and a
𝐶𝑅𝐺𝐺(𝐺′ , 𝜑, 𝑀, 𝑐𝑢𝑟_𝑖𝑡𝑒𝑟, 𝑚𝑎𝑥_𝑖𝑡𝑒𝑟) ;
list of logs (graph updates) 𝐿 are initialized. The function
getCDFPools is used to compute the cumulative distri- 24 else
bution functions 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠+ and 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠− based on 25 return 𝐺′ ;
the probabilities 𝑝𝛾𝑑→𝑑′ ,𝑐𝑚 and 𝑝𝛾𝑑→𝑑′ ,𝑐𝑚 . The process
+ −
×10 4 ×10 4
15000 10 6
Number of occurrences

Number of occurrences

Number of occurrences
8 5

10000 4
6
3
4
5000 2
2 1

0 0 0
20 20 0
40 10 40 10 10
8 8 20 8
60 6 60 6 6
Deg 4 Deg 4 Deg 40 4
ree 80 ree 80 ree
2
st amp 2
st amp 2
st amp
100 0 Time 100 0 Time 60 0 Time

Figure 4: Gaussian degree distribution Figure 5: Gaussian degree distribution Figure 6: Zipfian degree distribution
of a growth only graph of a graph with edge deletions of a growth only graph

5.4. Accuracy of the generation characteristics of the generated temporal graphs. Note
procedure that the source code of RTGEN is publicly available1 .
Besides the source code, we also provide the instruc-
In order to measure how far the characteristics of the tions describing how to use the tool to generate temporal
generated graphs are from the ground truth parameters, graphs. For instance, users can pass the input parame-
we define two distance metrics 𝜀𝑑 and 𝜀𝑐 . ters to describe the desired sequence of degree distribu-
The first metric 𝜀𝑑 measures the inaccuracy of approx- tions or stochastic community matrix and the format of
imating the degree distributions of the generated graphs the generated output files to RTGEN using a terminal
with the given sequence of degree distributions. That command. RTGEN proposes two output types: snapshot-
is, it measures the root mean square of the EMD dis- based and event-based. The snapshot based type consists
tances between each degree distribution 𝜑𝑖 in the given a sequence of graph snapshots represented each in a sep-
sequence {𝜑1 , . . . , 𝜑𝑛 } and its corresponding degree dis- arate file. Whereas, the event-based type, consists of
tribution 𝜑𝐺𝑖 in the sequence {𝜑𝐺1 , . . . 𝜑𝐺𝑛 } extracted generating the sequence of graph updates (events) that
from the generated graphs. Having this, 𝜀𝑑 is computed we applied between successive snapshots to transform
as follows: one snapshot into the next one.
√︀∑︀𝑛
2
𝑖=1 (𝐸𝑀 𝐷(𝜑𝑖 , 𝜑𝐺𝑖 ))
𝜀𝑑 = 6.0.1. Experimental setup
𝑛
Whereas, the second metric 𝜀𝑐 measures the inaccuracy The experiments were conducted on a single machine
of approximating the community density matrix of the equipped with Intel(R) Core(TM) i5-8350U CPU @
generated graphs with a given stochastic matrix. That 1.70GHz 1.90 GHz, 16 GB memory and 500 GB SSD.
is, it measure the root mean square of the difference be- We used Go 1.17.5 and Python 3.8.0. Besides, we referred
tween the Frobenius norms of the given stochastic matrix to the optimal transport solver proposed in [25]. The
𝑀 and the stochastic matrix 𝑀𝐺𝑖 extracted from every graphs shown in this section are visualized using Gephi
generated graph snapshot. Having this, 𝜀𝑐 is computed tool [26] which offers network visualization facilities and
as follows: community detection algorithms [27].
√︀∑︀𝑛
𝑖=1 (𝐹 (𝑀 ) − 𝐹 (𝑀𝐺𝑖 ))
2
𝜀𝑐 = 6.0.2. Preliminaries
𝑛
In the following experiments, we refer to two types of
where 𝐹 (𝑀 ) is the Frobenius norm of the stochastic
common degree distributions: Gaussian 𝑓𝐺 and Zipfian
community matrix 𝑀 . We recall that the Frobenius norm
𝑓𝑍 that are defined as follows:
of a matrix 𝐴 of dimensions (𝑛,𝑚) is defined as follows:
1 1 𝑥−𝜇 2
𝑓𝐺 (𝑥) = √ 𝑒− 2 ( 𝜎 )
⎯
⎸ 𝑛 ∑︁ 𝑚
⎸∑︁
𝜎 𝜋
𝐹 (𝐴) = ⎷ |𝑎𝑖𝑗 |2
𝑖=1 𝑗=1 1
𝑓𝑍 (𝑥) = 𝑥 ∈ [0, 𝑑𝑚𝑎𝑥 ]
(𝑥 + 𝑣)𝑠
6. Experimental evaluation We consider a special case where the value of a parameter
𝑥 ∈ N in iteration 𝑖 depends on the its value in the
We conducted a number of experiments to validate the previous iteration 𝑖 − 1 such as 𝑥𝑖 = 𝑥𝑖−1 + 𝛿𝑥 such
efficiency of our generator RTGEN. We also provide an in-
sight on how changing the input parameters can steer the 1
https://github.com/MariaMassri/RTGEN
that 𝜇𝑖 = 𝜇𝑖−1 +𝛿𝜇. This is applied on the parameters of graphs where new nodes join the graph and new connec-
the degree distributions 𝜇, 𝜎, 𝑑𝑚𝑎𝑥 , 𝑠, 𝑣 and 𝑛 denoting tions are created as the time elapses.
the total number of vertices. That is, 𝛿𝑛 denotes the
number of vertices to be added or removed from the graph 6.2. Controlling the community structure
in the relative generation process. Note that, RTGEN
also generates the first snapshot which implies that the
of the generated graphs
parameters of the degree distribution of the first snapshot In this experiment, we show the generated community
should be given. structure with different parameters of the stochastic com-
munity matrix and the effect of varying parameter 𝑘 of
6.1. Controlling the evolution of the the hierarchical tree. As described in Section 4.3, RTGEN
is capable of auto-generating the stochastic community
degree distribution
matrix representing a hierarchical community structure.
In this experiment, we show the evolution of the degree Consider a stochastic community matrix generated by set-
distribution of a sequence of graph snapshots generated ting 𝑏 = 4 and ℎ = 2. As depicted in Equation 2, one can
with the relative generation procedure given a set of input tune the parameter 𝑘 in order to control the within and
parameters. Hence, we consider Gaussian and Zipfian between edge densities. Hence, we select three different
degree distributions with different parameters and plot- values of 𝑘 in {2, 4, 8}. Furthermore consider, 𝑛 = 1000
ted the obtained degree distributions in Figures 4, 5 and to be the total number of vertices and parameters 𝜇 = 30
6. Figure 4 shows the evolution of the degree distribution and 𝜎 = 2 to be the parameters of a Gaussian distribu-
of a generated sequence of 10 graph snapshots given the tion. Note that, in this experiment, we generate a single
following parameters: {𝑛0 = 10𝐾, 𝜇0 = 30, 𝜎 0 = graph snapshot relying on the generation procedure pro-
2, 𝛿𝑛 = 10𝑘, 𝛿𝜇 = 5, 𝛿𝜎 = 0.1}. By setting 𝛿𝜇 posed in Section 4.2. The generated graphs are shown in
to 5, we increase the average degree by 5 between each Figures 7a, 7b and 7c using the Gephi tool. It can be no-
pair of snapshots. This indeed, can model a growth-only ticed that the difference between the within and between
graph where the average edge degree tend to regularly edge densities is proportional to 𝑘 since 𝑘 ∝ 𝑝𝑖𝑛 𝑜𝑢𝑡
𝑐𝑖 − 𝑝𝑐𝑖
increase as the time elapses. where 𝑝𝑐𝑖 and 𝑝𝑐𝑖 are the within and between linkage
𝑖𝑛 𝑜𝑢𝑡

However, some real-world graphs are not growth-only probabilities of a community 𝑐𝑖 . Furthermore, Figure 8
in the sense that they are subject to edge deletions. This presents the modularity in function of parameter 𝑘 which
is indeed the case of human-proximity or transportation we vary from 0 to 32. The modularity is a measure to
graphs where an important number of short-term con- quantify the goodness of community structure. Its for-
nections is only valid during peak hours. To model this mula compares, for all the communities, the fraction of
characteristic, RTGEN also supports edge deletions. The edges that falls within the given community with the
evolution of the degree distribution with edge deletions expected fraction if edges were distributed at random.
is presented in Figure 5. Let the following parameters It is clear from the results that the modularity increases
define the evolution of degree distribution for 𝑖 ∈ [0, 4]: with the increase of 𝑘. This is justified by the fact that
{𝑛0 = 1𝑀, 𝜇0 = 60, 𝜎 0 = 4, 𝛿𝑛 = 0, 𝛿𝜇 = 𝑘 is proportional to the difference between within and
5, 𝛿𝜎 = 0} Whereas the following parameters de- between edge linkage probabilities 𝑝𝑖𝑛 𝑐𝑖 − 𝑝𝑐𝑖 .
𝑜𝑢𝑡

fine its evolution for 𝑖 ∈ [5, 9]: {𝑛0 = 10𝐾, 𝜇0 =
80, 𝜎 0 = 2, 𝛿𝑛 = 0, 𝛿𝜇 = −5, 𝛿𝜎 = 0}. In- 6.3. Generating graphs with deletions
deed, setting 𝛿𝜇 to −5 indicates that the average degree
decreases by a value of 5 between each pair of successive
between snapshots
graph snapshots. As mentioned in Section 5, the relative graph genera-
Since real-world temporal graphs usually exhibit a power tion procedure may incur a number of edge deletions.
law degree distribution, we also generated graphs with This can be cumbersome when the number of edges to
an evolutionary Zipfian degree distribution composed delete for a given vertex is higher than the total sum of
of 10 graph snapshots as shown in Figure 6. For this edges to delete from its neighboring vertices. We solve
generated temporal graph, we set the following param- this problem by repeating the generation process until
eters {𝑛0 = 50𝑘, 𝑠0 = 2.5, 𝑣 0 = 10, 𝑑0𝑚𝑎𝑥 = reaching an acceptable error threshold that is defined by
10, 𝛿𝑛 = 50𝑘, 𝑠 = 0, 𝛿𝑣 = 0, 𝛿𝑑𝑚𝑎𝑥 = 5}. the EMD between the obtained and desired degree dis-
By setting parameter 𝛿𝑑𝑚𝑎𝑥 to 5, we consider that the tributions. Figure 12 shows the variation of the number
maximum degree of nodes increases by a value of 5 be- of iterations and the execution time of the generation
tween each pair of successive snapshots. Whereas, the process in function of the threshold error defined by the
value of 𝛿𝑛 indicates that 50𝑘 new nodes join the graph EMD. The obtained results show that our generation pro-
between successive snapshots. These parameters reflect cedure converges rapidly to a tolerable threshold. That
the growth of a large number of real-world temporal is, a threshold equals to 0.001 can be reached with only 7
(a) k=2 (b) k=4 (c) k=8

Figure 7: A visualization of the generated graphs with a hierarchical Figure 8: Modularity value in function
community structure with parameters: 𝑏 = 4, ℎ = 2, 𝑐 = 4 and a varying 𝑘. of parameter 𝑘 ranging from 0 to 32.

Figure 9: Execution time in Figure 10: 𝜀𝑑 in function of the Figure 11: 𝜀𝑐 in function of the
function of the number of edges. number of edges. number of edges.

6.4. Accuracy of the generation
procedure
We quantify the accuracy of the generated graphs with
the given parameters by computing the distance met-
rics 𝜀𝑑 and 𝜀𝑐 defined in Section 5.4. We generated
a sequence of 𝑛 = 5 snapshots with the following
parameters of Gaussian degree distribution: {𝑛0 ∈
{10𝑘, 100𝑘, 500𝑘, 1𝑀 }, 𝜇0 = 30, 𝜎0 =
Figure 12: The variation of the number of iterations and 2, 𝛿𝑛 = 0, 𝛿𝜇 = 10, 𝛿𝜎 = 0}. Besides, we con-
execution time in function of the EMD. trolled the community structure by fixing the following
parameters of a hierarchical tree: ℎ = 2, 𝑏 = 2, 𝑐 =
4, 𝑘 = 0.
iterations. By comparing the execution time of 1 iteration Figures 9, 10 and 11 plot the execution time, value of
and 7 iterations, we can notice that the difference is lower 𝜀𝑑 and 𝜀𝑐 in function of the total number of created edges
than the execution time of a single iteration. Indeed, the from applying the Gaussian distribution whose parame-
execution time resulting from repeating the generation ters are given above. It is clear that the execution time
is lower than the first iteration since the majority of mod- increases with the number of the generated edges. The
ifications are added in the first iteration and only the distance metric, however, decreases implying that RT-
remaining vertices whose linkage probability does not GEN approximates more accurately the given sequence
satisfy the sum of the linkage probabilities of its neigh- of degree distribution and community structure as the
boring vertices are considered in the next iteration. Note total number of edges grows.
that these results are obtained from the generation of two
successive snapshots with the following input parameters
of a Gaussian degree distribution: {𝑛0 = 500𝑘, 𝜇0 =
7. Related work
60, 𝜎0 = 2, 𝛿𝑛 = 0, 𝛿𝑚𝑢 = −30, 𝛿𝜎 = 0}. Synthetic graphs are important for developing bench-
marks for assessing the performance of graph-oriented
data platforms, when real graphs are not publicly avail-
able or expensive to obtain. This has been the incentive updates. DSNG-M (dynamic social network generator
to design models and generators, which are very use- based on modularity) [35] is a graph generator that is
ful for evaluating the efficiency of graph management capable of generating temporal graphs by flipping the
techniques as storage, query evaluation, indexing, parti- direction of edges of a given graph in order to satisfy a
tioning, etc. randomly chosen modularity value assigned to a single
An extensive work has been posited for the genera- graph snapshot.
tion of static graphs. For instance, a special emphasis Some of the aforementioned graph generators produce
has been placed to control the degree distribution of the temporal graphs with properties on nodes or vertices,
generated graphs. In this context, many graph genera- which we do not address in this paper. None of them,
tors were designed such as RTG [3], RMAT [4] and its however, allows the control of the evolution of the degree
generalisation Kronecker [5] producing only Power-Law distribution given ground truth parameters that describe
distributions. Since real-world graphs are not limited this evolution. This challenge lead to the elaboration of
to power-law distributions, BTER [6] and its extension the RTGEN tool that allows the approximation of any
Darwini [7] and GMark [8] produce graphs with any user given sequence of degree distributions that describes the
defined distribution. evolution of the graph. We firmly believe, that the degree
Another graph generation model producing a given distribution is a key feature that characterizes graphs,
degree distribution is the CL model, forming the basis hence, it should not be disregarded in graph generation
of the RTGEN tool. This model can be regarded as a tools.
successor of the Erdos-Rényi model [23] that is designed
for the generation of random graphs and a variant of
the edge configuration model of Newman et al. [24]. 8. Conclusion
It was extensively discussed and reused [17, 28, 29, 30].
In this paper, we addressed the generation of temporal
We choose to extend this model for its simplicity and
graphs that represents a critical challenge in the design
scalability.
of benchmarks specific for evaluating temporal graph
Besides, a number of existing graph generators are
management systems. That is, we proposed RTGEN, a
community-aware in the sense that they collect vertices
temporal graph generator that produces a sequence of
that are more densely connected between each other
graph snapshots whose community structure and evolu-
than they are with the rest of the graph, in separate or
tion of the degree distribution results from approximating
overlapping subgraphs called communities [9, 10, 11].
user defined parameters. This generation procedure con-
Although these generators preserve a given community
sists of relatively generating a graph snapshot from a
structure, they fail to produce a graph with respect to a
previous one by applying a number of atomic graph op-
given degree distribution. In this paper, we overcome this
erations. Our generation technique relies on an Optimal
limitation by allowing not only the generation of a given
transport solver to approximate a user-defined sequence
community structure but also a given degree distribution.
of degree distributions while minimizing the number of
Despite the extensive work posited on the genera-
operations needed to transform one snapshot into its
tion of non-temporal graphs, the generation of tempo-
successor. We conducted a number of experiments that
ral graphs has received much less attention. For in-
validated the efficiency and accuracy of our generation
stance, DANCer [31] is capable of generating temporal,
procedure. In the future, we are planning to include a
community-aware property graphs. It separates opera-
dynamic community structure to RTGEN. Indeed, the
tions performed on communities (macro operations) from
communities found in real-world graphs are subject to
operations performed on vertices and edges (micro opera-
splits, merges, shrinks or expansions which should also
tions). ComAwareNetGrowth [32] is a community-aware
be modelled in synthetic graphs.
graph generator that is capable of creating growth only
graphs. APA (Attribute-Aware Preferential Attachment)
[33] is a graph generator capable of creating growth-only References
property graphs based on a non-conventional triangle
closing. Instead of closing a triangle based on a uniform [1] J. R. Clough, T. S. Evans, Time and citation net-
probability given as an input parameter, their proposed works, arXiv preprint arXiv:1507.01388 (2015).
model consists of closing a triangle based on the simi- [2] M. D. Mueller, D. Hasenfratz, O. Saukh, M. Fierz,
larity between the candidate edge’s endpoints. While C. Hueglin, Statistical modelling of particle number
GMark [8] generates static graphs, EGG (Evolving Graph concentration in zurich at high spatio-temporal res-
Generator) [34] proposes an extension including evolv- olution utilizing data from a mobile sensor network,
ing properties attached to each vertex. EGG, however, Atmospheric Environment 126 (2016) 171–181.
disregard the topological changes to the network and [3] L. Akoglu, C. Faloutsos, Rtg: a recursive realistic
narrow the temporal evolution of the graph to property graph generator using random typing, in: Joint
European Conference on Machine Learning and 15882.
Knowledge Discovery in Databases, Springer, 2009, [18] A. G. Labouseur, J. Birnbaum, P. W. Olsen, S. R.
pp. 13–28. Spillane, J. Vijayan, J.-H. Hwang, W.-S. Han, The
[4] D. Chakrabarti, Y. Zhan, C. Faloutsos, R-mat: A g* graph database: efficiently managing large dis-
recursive model for graph mining, in: Proceedings tributed dynamic graphs, Distributed and Parallel
of the 2004 SIAM International Conference on Data Databases 33 (2015) 479–514.
Mining, SIAM, 2004, pp. 442–446. [19] M. Then, T. Kersten, S. Günnemann, A. Kemper,
[5] J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Falout- T. Neumann, Automatic algorithm transformation
sos, Z. Ghahramani, Kronecker graphs: An ap- for efficient multi-snapshot analytics on temporal
proach to modeling networks, Journal of Machine graphs, Proceedings of the VLDB Endowment 10
Learning Research 11 (2010) 985–1042. (2017) 877–888.
[6] T. G. Kolda, A. Pinar, T. Plantenga, C. Seshadhri, A [20] C. Ren, E. Lo, B. Kao, X. Zhu, R. Cheng, On querying
scalable generative graph model with community historical evolving graph sequences, Proceedings
structure, SIAM Journal on Scientific Computing of the VLDB Endowment 4 (2011) 726–737.
36 (2014) C424–C452. [21] W. Aiello, F. Chung, L. Lu, A random graph model
[7] S. Edunov, D. Logothetis, C. Wang, A. Ching, M. Ka- for power law graphs, Experimental Mathematics
biljo, Darwini: Generating realistic large-scale so- 10 (2001) 53–66.
cial graphs, arXiv preprint arXiv:1610.00664 (2016). [22] F. Chung, L. Lu, Connected components in ran-
[8] G. Bagan, A. Bonifati, R. Ciucanu, G. H. Fletcher, dom graphs with given expected degree sequences,
A. Lemay, N. Advokaat, gmark: Schema-driven Annals of combinatorics 6 (2002) 125–145.
generation of graphs and queries, IEEE Transac- [23] P. Erdos, A. rényi on random graphs i, Publ. Math.
tions on Knowledge and Data Engineering 29 (2016) Debrecen 6 (1959) 290–297.
856–869. [24] M. E. Newman, D. J. Watts, S. H. Strogatz, Random
[9] P. W. Holland, K. B. Laskey, S. Leinhardt, Stochastic graph models of social networks, Proceedings of the
blockmodels: First steps, Social networks 5 (1983) national academy of sciences 99 (2002) 2566–2572.
109–137. [25] R. Flamary, N. Courty, A. Gramfort, M. Z. Alaya,
[10] B. Karrer, M. E. Newman, Stochastic blockmodels A. Boisbunon, S. Chambon, L. Chapel, A. Corenflos,
and community structure in networks, Physical K. Fatras, N. Fournier, L. Gautheron, N. T. Gayraud,
review E 83 (2011) 016107. H. Janati, A. Rakotomamonjy, I. Redko, A. Rolet,
[11] B. Kamiński, P. Prałat, F. Théberge, Artificial bench- A. Schutz, V. Seguy, D. J. Sutherland, R. Tavenard,
mark for community detection (abcd): Fast ran- A. Tong, T. Vayer, Pot: Python optimal transport,
dom graph model with community structure, arXiv Journal of Machine Learning Research 22 (2021)
preprint arXiv:2002.00843 (2020). 1–8. URL: http://jmlr.org/papers/v22/20-451.html.
[12] P. Holme, Modern temporal network theory: a [26] M. Bastian, S. Heymann, M. Jacomy, Gephi: an open
colloquium, The European Physical Journal B 88 source software for exploring and manipulating
(2015) 234. networks, in: Third international AAAI conference
[13] E. Pitoura, Historical graphs: models, storage, pro- on weblogs and social media, 2009.
cessing, in: European Business Intelligence and Big [27] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, E. Lefeb-
Data Summer School, Springer, 2017, pp. 84–111. vre, Fast unfolding of communities in large net-
[14] Y. Miao, W. Han, K. Li, M. Wu, F. Yang, L. Zhou, works, Journal of statistical mechanics: theory and
V. Prabhakaran, E. Chen, W. Chen, Immortal- experiment 2008 (2008) P10008.
graph: A system for storage and analysis of tempo- [28] F. Chung, F. R. Chung, F. C. Graham, L. Lu, K. F.
ral graphs, ACM Transactions on Storage (TOS) 11 Chung, et al., Complex graphs and networks, 107,
(2015) 1–34. American Mathematical Soc., 2006.
[15] U. Khurana, A. Deshpande, Storing and analyz- [29] A. Pinar, C. Seshadhri, T. G. Kolda, The similarity
ing historical graph data at scale, arXiv preprint between stochastic kronecker and chung-lu graph
arXiv:1509.08960 (2015). models, in: Proceedings of the 2012 SIAM Interna-
[16] M. Haeusler, T. Trojer, J. Kessler, M. Farwick, tional Conference on Data Mining, SIAM, 2012, pp.
E. Nowakowski, R. Breu, Chronograph: A ver- 1071–1082.
sioned tinkerpop graph database, in: International [30] M. Winlaw, H. DeSterck, G. Sanders, An in-depth
Conference on Data Management Technologies and analysis of the chung-lu model, Technical Report,
Applications, Springer, 2017, pp. 237–260. Lawrence Livermore National Lab.(LLNL), Liver-
[17] F. Chung, L. Lu, The average distances in random more, CA (United States), 2015.
graphs with given expected degrees, Proceedings of [31] O. Benyahia, C. Largeron, B. Jeudy, O. R. Zaïane,
the National Academy of Sciences 99 (2002) 15879– Dancer: Dynamic attributed network with com-
munity structure generator, in: Joint European
Conference on Machine Learning and Knowledge
Discovery in Databases, Springer, 2016, pp. 41–44.
[32] F. Gursoy, B. Badur, A community-aware network
growth model for synthetic social network genera-
tion, arXiv preprint arXiv:1901.03629 (2019).
[33] A. Aghasadeghi, J. Stoyanovich, Generating evolv-
ing property graphs with attribute-aware preferen-
tial attachment, in: Proceedings of the Workshop
on Testing Database Systems, 2018, pp. 1–6.
[34] K. Alami, R. Ciucanu, E. M. Nguifo, Synthetic graph
generation from finely-tuned temporal constraints.,
in: TD-LSG@ PKDD/ECML, 2017, pp. 44–47.
[35] B. Duan, W. Luo, H. Jiang, L. Ni, Dynamic social
networks generator based on modularity: Dsng-
m, in: 2019 2nd International Conference on Data
Intelligence and Security (ICDIS), IEEE, 2019, pp.
167–173.