Graph management systems are emerging as an eficient 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 eforts 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.
class citizen in graph management systems [
Real graphs, however, are dynamic [
CEUR Workshop Proceedings (CEUR-WS.org)
snapshots. We achieve this goal by relying on an optimal Given the number of vertices in each graph
snaptransport 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
snapto 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 [
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 breakcedure. 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 ver2. Overview ttihceesg.enFeinraatlelyd, uthpedagtreaspohn− is1.coNmotpeutthedat,btyheapgpelnyeinragtion procedure depicted in this Figure shows a simplified scenario where the number of vertices does not change.
However, if that number changes, a phase consisting of the addition or deletion of vertices should precede the computation of the transportation matrix to assure the following constraint: In this section, we describe the overall generation procedure. Given the characteristics of a series of graph snapshots, our relative generation procedure produces the series of graph snapshots {1, . . . , } whose characteristics approximate the given ones. These graph snapshots are relatively computed by applying a number of graph updates on each snapshot in order to produce its successor snapshot. To clarify, we apply a number of graph updates on a graph snapshot − 1 to produce another graph snapshot whose characteristics approximate the given parameters assigned for the th graph snapshot.
Formally, we define a graph snapshot valid at a time instant as the tuple { , , , } where is the set of vertices, is the set of edges, is a degree distribution and is the density community matrix. For instance, we consider of the form {(1 , 1 , )} as a discrete distribution
), . . . , ( over N where
refers to the degree of a node and refers to the total number of vertices in the graph whose total number of edges is equal to . A density community matrix defines the community structure of the generated graphs, each element of which is equal to the density of edges between the source community and the target community . ∑︁
= ∑︁ , =1 =1
∀1 ≤ ≤
butions and should be equal.
random static graphs with a given degree distribution.
Random graphs were introduced by Erdős and Rényi [23]. The popularity of this model, also known as the model, stems from its simple generation procedure that consists of generating a number of vertices and connecting them by an edge after picking each endpoint with a ifxed 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 suficiently 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 undirected 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 sharing the same degree together in a pool = {| ∈ ∧ = } that we use as a subsidiary generation component. Each vertex in a pool is equally likely to be chosen assuring that the aforementioned linkage probability is not afected for a suficiently large number of vertices. After the degree assignment phase, vertices are distributed throughout the pools having each the following linkage probability: with a mean degree equals to ( − 1) where is the total number of vertices. Hence, it fails to mimic real-world graphs that usually follow a power-law degree distribution. To tackle this limitation, the edge configuration 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 parameter 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 verof 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 verprobability ∝ . 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 diferentiated into within and between edges: • Given a community , an edge is called a within edge if the source vertex ∈ and the target vertex ∈ . • Given two communities and , an edge is called a between edge if the source vertex ∈ and target vertex ∈ or vice versa.
define = = 2 and = . Furthermore, we assign each community with a within edge creation probability , a between edge creation equal to
and a probability of edge creation such that: = + = + 0.5 || ∑︁ (2) 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) , ∈
where is the sum of the degrees of vertices
belonging to community and is the probability of
choosing . The linkage probability of a vertex is the product
of the probability of choosing the community to
In this section, we formulate the SBM model [
In this section, we propose a static graph generation procedure which controls both the community structure and degree distribution. Given a degree distribution and a stochastic community matrix , our proposed model generates a graph which degree distribution is an approximation of and density community matrix is an approximation of . In the following, we provide a description of our generation mechanism that extends the stochastic block model depicted in Section 4.1.
Since the generated graph is undirected, the matrix is symmetric such that = . Having this, we = | |
forward and imposes an exhaustive number of userdefined parameters. Hence, we define an auto-generative procedure that fills the matrix with no exogenous efort. Considering a static graph, we construct a stochastic matrix that reflects a hierarchical community structure with only two given parameters. In a hierarchical community matrix, communities recursively embed subsequent communities in a self-similar fashion such that the community structure is represented by a hierarchical tree where each node represents a community. Each non-leaf node is expanded into other nodes until reaching a desired tree height ℎ (Figure 2). The ending recursion results in = ℎ leaf-nodes referencing the finest scale communities having a linkage probability proportional to the distance between and . The distance between two communities, (, ), is equal to the number of hops traversed in order to reach the least common ancestor of these communities. In order to satisfy the condition stating that within edge linkage probability must be higher than between linkage probability ( > ), we define as follows: = 0.5
+ − 1 ∑︁ =0,̸= where is a tunable parameter which calibration steers the diference between within and between edge densities. The efect of varying is further highlighted in the Section 6. cost:
min ∑︁ ∑︁
=1 =1 where = (, ) is a measure of distance between and . The following constraints must hold for the optimal flow :
≥ 0, 1 ≥ ≥ , 1 ≥ ≥ ∑︁ ≤ , 1 ≥ ≥ , =1 ∑︁ ≤ , 1 ≥ ≥ =1
Once the optimal flow is found, the EMD between and is computed as follows: (, ) = ∑︀ =1 ∑︀ =1 ∑︀ =1 ∑︀ =1
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 desection 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 ver5.1. Earth mover’s distance tices to be added to or removed from the graph based on whether is a positive or negative number, respecThe 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 lfow (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 a breakage probability − defined as extensions of the CL linkage probability (1): + = + , > 0 − = − , < 0
− We collect vertices sharing the same degree variation = ′ − into a linkage pool if > 0 and in a breakage pool if < 0. Consider →′ = {| ∈ ∧ = ′ − } to be the pool containing vertices having a degree that should be transformed into ′. We compute the probability of picking a linkage or breakage pool +→′ and − →′ as follows: +→′ = | →′ | , > 0
+ − →′ = − | →′ | , < 0
− However, breaking an edge might be impossible in situations 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 threshold after a tolerable number of iterations. This statement will be further highlighted in Section 6. − = , ∈ −
A more complex version of the previously described relative graph generation, consists of preserving the graph community structure in the transformation procedure. That is, the input of our community-aware relative graph generator is the graph = {, , , }, the (4) (5) desired degree distribution and the stochastic block matrix . However, the output consists of a graph ′ = { ′, ′, ′ , ′ } where ′ is an approximation of and ′ is an approximation of . Recall that the generation procedure depicted in section 4.2 produces a graph with a given expected degree distribution and stochastic community matrix based on the proposed linkage probability duality presented in Equations (1) and (3).
Indeed, a relative community-aware graph generation is based on an extension of the aforementioned duality by taking into consideration the degree variation of a vertex instead of the its degree. That is, the following linkage and breakage probabilities present a straightforward extension of Equations (4) and (5): + = , ∈
+ Condition 1: For each community ∈ , conditions stating that + = + and − = − must hold, where + and − are the total number of edge insertions and deletions in all communities of , respectively. Incorporating in the previous condition translates to the following equality: || |′| || |′| ∑︁ ∑︁( − ) = (∑︁ ∑︁( − ) ) =0 =0 =0 =0 where and ′ are the source and target degree distributions.
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 when ′ is lower than or equal to or the number of repetitions has already been reached.
By solving the concatenated system of equations obtained from the previous conditions (1, 2, 3) = (1, 2, 3), we find the vector , hence the values of . Pools are created on a local basis in each community such that vertices with the same degree variation = ′ − and belonging to the same community are collected in a single pool → ′ . We compute the probability of picking a linkage or breakage pool +→′ , and − →′ , as follows: +→′ , = | → ′ | , > 0
+ − →′ , = − | → ′ | , < 0 −
Algorithm 1: CRGG Input: = {, , , }, , , ,
_, _
Output: ′ = { ′, ′, ′ , ′ } 1 ← getTransportMatrix(, ) ; 2 X ← getVector(, , , ) ; 3 (+, − ) ← getNumberOfEdges(T) ; 4 ← getCDFComs( ) ; 5 ( +, − ) ← initCDFPools ; 6 ← () 7 for ∈ do 8 ( +, − ) ← getCDFPools(, ) ; +[] ← + ; − [] ← − ; Algorithm CRGG depicts the relative community aware graph generation procedure. The input parameters are 9 the graph snapshot , desired degree distribution , den- 10 sity community matrix , threshold of the EMD distance between and , maximum number of repeti- 11 for ← tions _ and the current number of repetitions 12 (, ) ← _. Whereas, the output is a new graph snapshot 13 ′. Note that, the value of _ is equal to 0 in the ifrst iteration. The transportation matrix is computed 14 using the function getTransportMatrix by taking the 15 for ← degree distributions and as input. The function 16 (, ) ← getVector, computes and based on the Conditions 17 1, 2 and 3 and solves the system of equations defined by = to find the vector . The total number of edges 18 to add (+) and delete (− ) are then computed based on the transporation matrix . The function getCDFComs computes the cumulative distribution function based on the density community matrix . Then, vectors + and − representing the cumulative 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 the probabilities +→′ , and − →′ , . The process return ′ ; 0 + do
chooseComs( ) ; (, ) ← chooseVertices( +[], +[]) ; .addEdge (, ) ;
The first metric measures the inaccuracy of approx- tions or stochastic community matrix and the format of
In order to measure how far the characteristics of the generated graphs are from the ground truth parameters, we define two distance metrics and . imating the degree distributions of the generated graphs with the given sequence of degree distributions. That is, it measures the root mean square of the EMD distances between each degree distribution in the given sequence {1, . . . , } and its corresponding degree distribution in the sequence {1 , . . . } extracted from the generated graphs. Having this, is computed () = ⎸⎷⎯⎸∑︁ ∑︁ | |2
eficiency of our generator RTGEN. We also provide an insight on how changing the input parameters can steer the characteristics of the generated temporal graphs. Note that the source code of RTGEN is publicly available1. Besides the source code, we also provide the instructions describing how to use the tool to generate temporal graphs. For instance, users can pass the input parameters to describe the desired sequence of degree distributhe generated output files to RTGEN using a terminal command. RTGEN proposes two output types: snapshotbased and event-based. The snapshot based type consists a sequence of graph snapshots represented each in a separate file. Whereas, the event-based type, consists of generating the sequence of graph updates (events) that we applied between successive snapshots to transform one snapshot into the next one. 6.0.1. Experimental setup
equipped with Intel(R) Core(TM) i5-8350U CPU 1.70GHz 1.90 GHz, 16 GB memory and 500 GB SSD.
to the optimal transport solver proposed in [25]. The graphs shown in this section are visualized using Gephi tool [26] which ofers network visualization facilities and community detection algorithms [27]. 6.0.2. Preliminaries In the following experiments, we refer to two types of common degree distributions: Gaussian and Zipfian that are defined as follows: () =
− 12 ( − )2 () = ∈ [0, ] We consider a special case where the value of a parameter ∈ N in iteration depends on the its value in the previous iteration − 1 such as = − 1 + such 1https://github.com/MariaMassri/RTGEN
1 √
1 ( + ) graphs where new nodes join the graph and new connections are created as the time elapses. 6.2. Controlling the community structure of the generated graphs that = − 1 + . This is applied on the parameters of the degree distributions , , , , and denoting the total number of vertices. That is, denotes the number of vertices to be added or removed from the graph in the relative generation process. Note that, RTGEN also generates the first snapshot which implies that the parameters of the degree distribution of the first snapshot should be given.
structure with diferent parameters of the stochastic community matrix and the efect of varying parameter of 6.1. Controlling the evolution of the the hierarchical tree. As described in Section 4.3, RTGEN degree distribution is capable of auto-generating the stochastic community matrix representing a hierarchical community structure.
In this experiment, we show the evolution of the degree Consider a stochastic community matrix generated by
setdistribution 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 diferent
degree distributions with diferent 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
distribuof 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
pro2, = 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
nopair of snapshots. This indeed, can model a growth-only ticed that the diference 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
fornections 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 ∈ [
(c) k=8 iterations. By comparing the execution time of 1 iteration and 7 iterations, we can notice that the diference is lower than the execution time of a single iteration. Indeed, the execution time resulting from repeating the generation is lower than the first iteration since the majority of modifications are added in the first iteration and only the remaining vertices whose linkage probability does not satisfy the sum of the linkage probabilities of its neighboring vertices are considered in the next iteration. Note 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 = 60, 0 = 2, = 0, = − 30, = 0}.
We quantify the accuracy of the generated graphs with the given parameters by computing the distance metrics 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 = 2, = 0, = 10, = 0}. Besides, we controlled the community structure by fixing the following parameters of a hierarchical tree: ℎ = 2, = 2, = 4, = 0.
Figures 9, 10 and 11 plot the execution time, value of and in function of the total number of created edges from applying the Gaussian distribution whose parameters are given above. It is clear that the execution time increases with the number of the generated edges. The distance metric, however, decreases implying that RTGEN approximates more accurately the given sequence of degree distribution and community structure as the total number of edges grows.
Synthetic graphs are important for developing benchmarks for assessing the performance of graph-oriented data platforms, when real graphs are not publicly available 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 eficiency 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 [
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 [
We choose to extend this model for its simplicity and In this paper, we addressed the generation of temporal scalability. graphs that represents a critical challenge in the design
Besides, a number of existing graph generators are of benchmarks specific for evaluating temporal graph
community-aware in the sense that they collect vertices management systems. That is, we proposed RTGEN, a
that are more densely connected between each other temporal graph generator that produces a sequence of
than they are with the rest of the graph, in separate or graph snapshots whose community structure and
evoluoverlapping subgraphs called communities [
Despite the extensive work posited on the genera- of degree distributions while minimizing the number of
tion of non-temporal graphs, the generation of tempo- operations needed to transform one snapshot into its
ral graphs has received much less attention. For in- successor. We conducted a number of experiments that
stance, DANCer [31] is capable of generating temporal, validated the eficiency and accuracy of our generation
community-aware property graphs. It separates opera- procedure. In the future, we are planning to include a
tions performed on communities (macro operations) from dynamic community structure to RTGEN. Indeed, the
operations performed on vertices and edges (micro opera- communities found in real-world graphs are subject to
tions). ComAwareNetGrowth [32] is a community-aware splits, merges, shrinks or expansions which should also
graph generator that is capable of creating growth only be modelled in synthetic graphs.
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
netprobability 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 [
Discovery in Databases, Springer, 2016, pp. 41–44. [32] F. Gursoy, B. Badur, A community-aware network growth model for synthetic social network generation, arXiv preprint arXiv:1901.03629 (2019). [33] A. Aghasadeghi, J. Stoyanovich, Generating evolving property graphs with attribute-aware preferential 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: Dsngm, in: 2019 2nd International Conference on Data Intelligence and Security (ICDIS), IEEE, 2019, pp. 167–173.