G Voisin

I Cognard

P C C Freire

N Wex

L Guillemot

G Desvignes

M Kramer

G Theureau

M Saillenfest

One pulsar, two white dwarfs, and a planet confirming the strong equivalence principle

The strong equivalence principle is a cornerstone of general relativity, tested with exquisite accuracy in the Solar system. However, tests in the strong-field regime require a compact object. Currently, PSR J0337+1715 is the unique millisecond pulsar found in a triple stellar system, orbiting two white dwarfs within an area comparable to the orbit of the Earth. This configuration offers the opportunity for a dramatic improvement over previous tests, provided that accurate and regular timing of the pulsar can be achieved. This also requires the development of a new timing model solving numerically the relativistic three-body problem with great accuracy. We report on the analysis of the high-quality dataset gathered on PSR J0337+1715 by the Nançay radiotelescope over the past 8 years. In particular, I will show how we could obtain the most stringent limit to-date on a potential violation of the strong equivalent principle in the strong field regime. I will also introduce preliminary resuts showing that the presence of a small planet in the system may explain a tiny residual signal so far unaccounted for, which if confirmed would make this system exceptionally rich.

Introduction

Tests of the universality of free fall with strongly self-gravitating bodies have strongly benefited from the discovery of the millisecond pulsar PSR J0337+1715 1 . Up until that discovery, strongequivalence-principle (SEP) tests consisted mainly in the Damour-Shafer test 2 whereby one looks for a systematic orbital polarisation of pulsar-white dwarf binaries by the local gravitational potential of the galaxy. This is a kind of three-body test: two test masses, a neutron star and a white dwarf, fall in the gravitational potential of a third one, the Galaxy. If such test suffers primarily from the weakness of the galactic gravitational attraction, it can be partly compensated by the possibility of using a sample of binaries instead of a single system 3 . PSR J0337+1715 offers a unique opportunity: the system is a hierarchical triple stellar system with two white dwarfs. The innermost white dwarf orbits the pulsar in 1.6 days, while the outermost white dwarf orbits the inner binary in approximately 327 days. Schematically, this configuration allows for a test of the universality of free fall between the two components of the inner binary in the gravitational field of the outer star which is much stronger than the galactic field. In addition, mutual interactions allow for a complete characterisation of the system parameters. For all these reasons, PSR J0337+1715 has permitted a leap forward in the accuracy of SEP tests involving a neutron star 4,5 .

The principle of the experiment is thus not very different from, for example, Lunar Laser ranging in the Solar system, where Earth and Moon fall in the potential of the Sun. What is massively different is the amount of gravitational energy carried by the neutron star which represents about ∼ -0.15 of its total mass-energy, against ∼ -10 -10 for the Earth. This allows the test to be sensitive to effects which may occur only in this regime, such as the effect of spontaneous scalarization in the Damour-Esposito Farese scalar-tensor theory 6,7 .

In this contribution, we will present the results obtained from the timing of PSR J0337+1715 at the radiotelescope of Nançay 5 (V20 in the following), as well as preliminary results showing hints of the presence of a small planet in the system.

2 Testing SEP with PSR J0337+1715

Timing model

Pulsar timing consists in accurately measuring the times of arrival of pulses from the neutron star. For an isolated star, these are only affected by the spin frequency decay due to the conversion of spin energy into electromagnetic energy and particles, as well as by occasional glitches. When in a binary, the motion of the pulsar on its orbit changes the geometrical path to the observer in a periodic manner. This allows one to extract orbital parameters from the timing data. But since times of arrival are mostly sensitive to the projection of the orbital motion along the line of sight, there remains degeneracies. The first one is between the semi-major axis and the inclination of the orbital plane. The reason is that a Newtonian binary orbit is an ellipse, and the projection of an ellipse remains an ellipse. As a result, one cannot disentangle between all the orbits which share the same projection. The second one results from the fact that a Newtonian binary can be cast into an equivalent single body attracted by a reduced mass which is a function of the two actual masses. In pulsar timing, this is usually shown in terms of the so-called mass function (which is related to, albeit not equal to the reduced mass) which is the observable. Without additional knowledge, masses thus remain degenerate.

These two symmetries are broken when additional effects are taken into account, in particular the so-called Shapiro and Einstein delays which result from companion-induced time dilation along the path of light and at the source, respectively. Orbital motion can also be affected by relativistic effects such as periastron precession or gravitational-wave emission. With two of these effects, degeneracies can be lifted, and with additional effects general relativity can be put to a consistency test (see P.C.C Freire's contribution on the double pulsar 8 ).

In the case of PSR J0337+1715, these effects are not very strong but detectable except for gravitational wave emissions. Nonetheless, mutual interactions between the three bodies at Newtonian level is in itself sufficient to break the above two symmetries. This comes at the cost of a computationally much more expensive evaluation of the orbital motion. Indeed, contrary to binary pulsars a numerical integration has to be performed with an accuracy of a few meters on the position of the pulsar. This is why we specifically developed a Numerical Timing Model (Nutimo, V20), which solves the equations of motion at first post-Newtonian order and compute the associated delays. A Markov Chain Monte Carlo (MCMC) estimation of the posterior probability density of each parameter of the problem is then performed.

Limits on SEP violations

At Newtonian level, a violation of SEP can be formalised by introducing different gravitational constants for different pairs of interacting bodies. In the case of the triple system, one can show that any measurable violation in the interaction between the two white dwarfs would be larger than limits from Solar system experiments. Thus, we consider that the pulsar interacts with each white dwarf through a constant G(1 + ∆) while they interact with each other through the gravitational constant G. Thus, ∆ is the SEP violation parameter which is fitted for along with the other parameters of the system. A posterior distribution function is obtained which indicates that |∆| ≤ 2 × 10 -6 at 95% confidence level (V20).

To go further, this results needs to be interpreted in the frame of a specific alternative theory of gravity. The parametrised post-Newtonian framework cannot be used because it is not generally valid in the strong field regime, and a Nordvedt parameter cannot be rigorously defined for the same reason 9 . As an example, we may however cast our result into the frame of the Damour-Esposito Farèse scalar-tensor theory of gravity. This theory depends on two parameters α 0 , β 0 and tends to general relativity when they tend to zero. PSR J0337+1715 is the most constraining observation for a large part of the parameter space (see figure 12 in V20 or 14 in Kramer et al. 8 ), only surpassed by the double pulsar 8 (see P.C.C. Freire's contribution) and pulsar-white dwarf binaries in the low beta region of the plot.

3 A small planet perturbing the system ?

Hint: a low frequency signal in the fit residuals

The fit residuals of V20 exhibited low-frequency noise which we initially associated with red noise, a phenomenon quite common in pulsar timing (see e.g. A. Chalumeau's contribution 10 ). Red noise can have either intrinsic causes, presumably due to variations in the emission region of the pulsar magnetosphere, or be caused by propagation effects. The latter results from variations of the column density of free electrons along the line of sight, the so-called dispersion measure, and is a chromatic effect, contrary to the former. In the present case, no sign of chromaticity is present, and it can be ruled out.

On the other hand, the small amplitude of noise, about 1µs, and its timescale of a few thousand days are compatible with a small planet orbiting the stellar triple system at a sufficiently large distance such that its orbit may remain stable. Although rare, planets have been found around pulsars (see e.g. Nit ¸u et al. 11 and references therein). We therefore implemented a fourth body in Nutimo in order to test that hypothesis.

Preliminary results

The planet model is able to absorb all the low-frequency components down to the point where residuals show a flat periodogram compatible with white noise, Fig. 1. The planet has a mass of a few 10 -8 M , comparable to the mass of the moon and an orbital period of ∼ 3000 days. When compared to V20, the best fit has a significantly better χ 2 even when a penalty against additional parameters is applied using the Akaike Information Criterion (AIC) or the Bayesian information criterion (BIC), as shown in table 1.

In V20, the low-frequency signal was accounted for by rescaling uncertainties on times of arrival such that the reduced χ 2 would be unity. Although the frequency of a SEP violation would be much higher 4 , and therefore is not expected to be biased by such low-frequency components, this procedure allowed us to produce a conservative estimate of the uncertainty on the SEP violation parameter ∆ (as well as on every other parameter). Conversely, the presence of the planet does not affect directly the SEP test, but the rescaling of error bars is more limited, which translates into a narrower uncertainty on every parameter, including ∆.

Conclusion

We have shown that the timing of PSR J0337+1715, although complex to model and computationally challenging, provides one of the most constraining tests of the strong equivalence principle to date. Preliminary results show that the addition of a small planet to the model allows for a significantly better fit to the data which leads to an improved limit on a putative violation of the equivalence principle. If confirmed, this would also make the formation channel of this system particularly intriguing.

Figure 1 -

 1 Figure 1 -Lomb-Scargle periodogram of fit residuals of the planet model. The three grey horizontal lines represent the mean and the upper and lower limit of the 99% region obtained by bootstrapping white noise. These lines have been smoothed by a sliding mean over 40 frequency bins to improve clarity. fI , fO, fE are the inner binary, outer white dwarf and Earth orbital frequencies respectively. 2fI -fO is the frequency of the signal produced by SEP violation.

Table 1 :

 1 Comparison between the planet model and the results of V20. Npar is the number of parameters of the model and N dof = 9303 -Npar is the number of degrees of freedom.

	Model N par	χ 2	χ 2 /N dof ∆AIC ∆BIC
	V20	25	16066 1.7316	0	0
	Planet	32	13185 1.4220	-2869 -2827


Patrice Berthod

Elodie Conrath

come

Microstructure evolution and oxidation behavior at high temperature of cobalt-based superalloys strengthened by hafnium carbides

patrice.berthod@univ-lorraine.fr, elodie.conrath@univ-lorraine.fr

Cobalt-based superalloys elaborated by foundry are often reinforced by carbides [START_REF] Donachie | Superalloys: A Technical Guide[END_REF] , which are generally of different types. The most common among them are chromium carbides and tantalum carbides. Unfortunately the presence of the formers generally induces for the alloy a decrease in solidus temperature while the later tend to become fragmented during high temperature exposures [START_REF] Berthod | Experimental and thermodynamic study of the microstructure evolution in cobalt-base superalloys at high temperature[END_REF] , with consequently a loss of mechanical resistance at high temperature. Other types of carbides can be considered to strengthen such superalloys, for example hafnium carbides [START_REF] Berthod | High temperature properties of several chromium-containing Co-based alloys reinforced by different types of MC carbides (M=Ta, Nb, Hf and/or Zr)[END_REF] .

In this work three HfC-reinforced chromium-rich cobalt-based alloys, Co(bal.)-25Cr-xC-yHf with (x; y)=(0.25; 3.72), (0.50; 3.72) and (0.50; 7.44) (weight contents chosen for having 1/1 and 2/1 atomic ratios between C and Hf), were elaborated by foundry and exposed at 1200°C for 50 hours to characterize their behaviours in terms of microstructure stability and of high temperature oxidation. In these fields they were compared with two Hf-free Co-25Cr-0.25&0.50C alloys subjected to the same tests.

Two of the three HfC-strengthened Co-based alloys studied in this work were thus successfully obtained with a dendritic matrix and an interdendritic carbides network of script eutectic HfC, thanks to an atomic ratio Hf/C equal to 1. The obtained HfC carbides were obviously slower fragmented than what it was generally observed for TaC when they are present in such quantities in other cobalt-based alloys. These observations let think that such alloys may owning high mechanical properties at high temperature and notably efficient resistance against creep-deformation. In contrast their high temperature oxidation behaviour was not so good since no of them showed a chromia-forming behaviour despite their 25wt.%Cr and severe oxide spallation. Fortunately this may be improved by modifying their bulk chemical composition (e.g. increase in Cr, rare earth additions), the one of their sub-surface (e.g. by enriching it in Cr by pack-cementation) or by depositing a protective coating.

Faculté des Sciences et Technologies

Aged bulk microstructures

Thermogravimetry runs and post-mortem examinations:

Parabolic but fast mass gain by comparison with the Hf-free alloys* Kp of about 800 ×10 -12 g 2 cm -4 s -1 (against 30 to 50 ×10 -12 g 2 cm -4 s -1 for *) Very thick multiconstituted ext. oxides (no Cr2O3-forming behaviour)

Severe oxide spallation despite slow cooling (-5°C min -1 ) ↑ 0.25C containing alloys ↑ → 0.50C containing alloys

  (only HfC) 7.44Hf after 50h at 1200 C (only HfC) 3.72Hf (HfC, but Cr carbides also exists: 0.63+/-0.13 surf .%) 3.72Hf after 50h at 1200 C (only HfC) Beyond Nickel-Based Superalloys -Bad Berneck (Bavaria), Germany -May 13-17, 2013 MICROSTRUCTURE EVOLUTION AND OXIDATION BEHAVIOUR AT HIGH TEMPERATURE OF COBALT-BASED SUPERALLOYS STRENGTHENED BY HAFNIUM CARBIDES Patrice BERTHOD, Elodie CONRATH -Institut Jean Lamour, University of Lorraine BP 70239, Bd des Aiguillettes, 54506 Vandoeuvre-lès-Nancy, France

  Fusion and solidification under 300mbars Ar in a High Frequency induction furnace (pure elements → ingots of 40g) SEM examinations, X-ray maps and XRD runs: Dendritic matrix (fcc & hcp at room temperature) Hafnium carbides: compact pro-eutectic and script eutectic (mainly interdendritic) Rare chromium carbides in the 0.50C-3.72Hf alloy (for which at.%Hf = ½ at.%C) aft er 50h at 1200 C 3.7 2Hf aft er 50h at 1200 C Hf -free alloys aft er 50h at 1 200 C 7.4 4Hf (as-cast ) 3.7 2Hf (as-cast ) Hf -free a llo ys (as-cast)HfC surface fractions and hardness (aged compared to as-cast)


Maria Massri
email: maria.massri@orange.com

Zoltan Miklos
email: zoltan.miklos@irisa.fr

Philippe Raipin
email: philippe.raipin@orange.com

Pierre Meye
email: pierre.meye@orange.com

Rtgen

RTGEN : A Relative Temporal Graph GENerator

Keywords: Temporal graphs, Graph generation, Optimal transport

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Graphs are the most natural model to describe real world interactions and are currently used in a myriad of application domains such as citation [START_REF] Clough | Time and citation networks[END_REF], transportation [? ], and sensor networks [START_REF] Mueller | Statistical modelling of particle number concentration in zurich at high spatio-temporal resolution utilizing data from a mobile sensor network[END_REF] to cite just a few. These graphs are managed by a graph management system whose performance is usually evaluated through graph-centered benchmarks that address different performance metrics such as ingestion throughput, space usage and query execution time. In this context, practitioners refer to realworld and synthetic graphs to use in the benchmarks. Indeed, available graph generation techniques fill the gap between real and synthetically generated graphs by trying to mimic the characteristics of real graphs such as controlling the degree distribution [START_REF] Akoglu | Rtg: a recursive realistic graph generator using random typing[END_REF][START_REF] Chakrabarti | R-mat: A recursive model for graph mining[END_REF][START_REF] Leskovec | Kronecker graphs: An approach to modeling networks[END_REF][START_REF] Kolda | A scalable generative graph model with community structure[END_REF][START_REF] Edunov | Darwini: Generating realistic large-scale social graphs[END_REF][START_REF] Bagan | gmark: Schema-driven generation of graphs and queries[END_REF]. Besides, a number of existing graph generators are communityaware in the sense that they group vertices that are more densely connected between each other than they are with the rest of the graph, in separate or overlapping sub-graphs called communities [START_REF] Holland | Stochastic blockmodels: First steps[END_REF][START_REF] Karrer | Stochastic blockmodels and community structure in networks[END_REF][START_REF] Kamiński | Artificial benchmark for community detection (abcd): Fast random graph model with community structure[END_REF].

Real graphs, however, are dynamic [START_REF] Holme | Modern temporal network theory: a colloquium[END_REF] such that their topology is subject to continuous changes. In this context, a new emphasis is being placed to support time as a first class citizen in graph management systems [START_REF] Pitoura | Historical graphs: models, storage, processing[END_REF][START_REF] Miao | Immortalgraph: A system for storage and analysis of temporal graphs[END_REF][START_REF] Khurana | Storing and analyzing historical graph data at scale[END_REF][START_REF] Haeusler | Chronograph: A versioned tinkerpop graph database[END_REF]. Most of these systems rely on real-world temporal graphs to evaluate their proposed methods. Real-world graphs, however, do not often fit the scale requirements. Therefore, practitioners must rely on a temporal graph generator that is able to produce large scale graphs whose evolution correlates with that of real world temporal graphs. To tackle this challenge, we proposed RTGEN: a relative temporal graph generator that produces large scale temporal graphs by controlling a number of key features that characterises the evolution of real-world graphs. That is, our generation procedure, controls the evolution of the degree distribution by extending a very common generation technique [START_REF] Chung | The average distances in random graphs with given expected degrees[END_REF] referred to as the Chung-Lu model with temporal and community-aware support.

We model a temporal graph by a sequence of snapshots 𝑆 = {𝐺0, . . . , 𝐺𝑁 } where 𝐺𝑖 is the graph snapshot at timestamp 𝑡𝑖 and characterized by a degree distribution that is generated from sampling user-defined temporal parameters. Having this, our relative graph generation procedure consists of transforming 𝐺𝑖-1 into 𝐺𝑖 by applying a stream of atomic graph operations with respect to the desired degree distribution at time instants 𝑡𝑖-1 and 𝑡𝑖. Based on the fact that a strong correlation exists between successive snapshots [START_REF] Labouseur | The g* graph database: efficiently managing large distributed dynamic graphs[END_REF][START_REF] Then | Automatic algorithm transformation for efficient multi-snapshot analytics on temporal graphs[END_REF][START_REF] Ren | On querying historical evolving graph sequences[END_REF], we propose to minimize the number of graph operations that have to be applied in order to transform a graph snapshot into its successor. The main idea consists of minimizing the distance between degree distributions of successive snapshots. We achieve this goal by relying on an optimal transport solver which provides a transportation plan capable of transforming a "mass" from source distribution to target distribution with a minimum of work. In order to apply the obtained transportation plan, we proposed a straightforward generalization of the well-known Chung-Lu's model, also known as the CL model, that was first discussed in [START_REF] Aiello | A random graph model for power law graphs[END_REF] and formalized in [START_REF] Chung | The average distances in random graphs with given expected degrees[END_REF][START_REF] Chung | Connected components in random graphs with given expected degree sequences[END_REF]. We choose to extend this model for the reasons of simplicity and scalability. We also extended the CL model to partition the graph into ground-truth communities that coexist with the aforementioned time-dependent degree distribution. Our contributions are validated through experimental results showing the evolution of the degree distribution and community structure with respect to ground-truth input parameters.

The rest of the paper is organized as follows, Section 2 provides an overview of the generation procedure. Section 3 introduces the baseline generation procedure of the CL model. Section 4 describes the proposed communityaware extension of the CL model. Section 5 presents a detailed description of the proposed generation procedure. Section 6 provides an experimental evaluation of the synthetically generated temporal graphs. Section 7 describes the related work. Section 8 concludes the work.

Overview

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 𝑐𝑣.

Given the number of vertices in each graph snapshot 𝑘𝑖 ∈ {𝑘1, . . . , 𝑘𝑛}, a stochastic community matrix 𝑀 and a sequence of degree distributions {𝜑1, . . . , 𝜑𝑛}, we generate a sequence of graph snapshots {𝐺1, . . . , 𝐺𝑛} such that each snapshot 𝐺𝑖 is relatively generated by transforming 𝐺𝑖-1. This transformation is based on morphing the 𝜑𝐺𝑖-1 = {(𝑥

𝐺 𝑖-1 1 , 𝜔 𝐺 𝑖-1 1
), . . . , (𝑥

𝐺 𝑖-1 𝑛 , 𝜔 𝐺 𝑖-1 𝑛 )} into 𝜑𝑖 = {(𝑥 𝑖
1 , 𝜔 𝑖 1 ), . . . , (𝑥 𝑖 𝑘 , 𝜔 𝑖 𝑘 )} and preserving the community structure that is represented by the stochastic community matrix 𝑀 such that 𝑀𝐺 𝑖-1 = 𝑀𝐺 𝑖 = 𝑀 . Note that each element 𝑚𝑢𝑣 of M is equal to the probability of edge creation between the source and target communities 𝑐𝑢 and 𝑐𝑣. Figure 1 illustrates the relative graph generation procedure. Each graph snapshot 𝐺𝑖 is relatively generated by transforming its ancestor 𝐺𝑖-1. This transformation is based on computing a transportation matrix 𝑇 that minimizes the cost of morphing 𝜑𝐺 𝑖-1 into 𝜑𝑖. The computation of the transportation matrix reduces to an optimal transport problem. Based on the computed transportation matrix, each vertex belonging to the graph 𝐺𝑖-1 is assigned with a linkage or breakage probability to indicate the probability of adding or removing an edge. This phase is followed by creating or removing edges to or from the graph 𝐺𝑖-1 to produce the graph 𝐺𝑖. These graph updates follows the linkage or breakage probabilities assigned for each of the vertices. Finally, the graph 𝐺𝑖 is computed by applying the generated updates on 𝐺𝑖-1. Note that, the generation 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:

𝑘 ∑ 𝑠=1 𝜔 𝐺 𝑖 𝑠 = 𝑚 ∑ 𝑡=1 𝜔 𝑖 𝑡 , ∀1 ≤ 𝑖 ≤ 𝑛
This constraint implies that the sum of weights of distributions 𝜑𝐺 𝑖 and 𝜑𝑖 should be equal.

Graph generation with given expected degree distribution

In this section, we describe the generation procedure of random static graphs with a given degree distribution. Random graphs were introduced by Erdős and Rényi [START_REF] Erdos | rényi on random graphs i[END_REF]. 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 fixed probability 𝑝. However, this model produces graphs whose degree distribution follows a binomial distribution 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 [START_REF] Newman | Random graph models of social networks[END_REF] consists of generating a random graph whose degree distribution matches, approximately, a given degree 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. Having this, pairs of stubs are linked randomly forming edges between their endpoints. Although this technique approximately matches any given degree distribution, a relaxed version known as the Chung-Lu model was introduced in [START_REF] Aiello | A random graph model for power law graphs[END_REF]. This model consists of generating a random graph that approximately matches a given degree distribution relying on a simple generation procedure that can be considered as a variant of the 𝐸𝑅 model. For simplicity, we will refer to this model as the CL model in the following description.

Consider the degree distribution 𝜑 as the input parameter to the CL model and the undirected, unweighted and unlabeled graph 𝐺 = {𝑉, 𝐸, 𝜑𝐺} as the output where 𝜑𝐺 denotes the degree distribution of 𝐺, 𝑉 and 𝐸 denote the set of vertices and edges, respectively. Having this, the CL model produces a graph 𝐺 such that 𝜑𝐺 is an approximation of 𝜑. The main idea is to pick each endpoint of an edge with a certain probability such that, at the end of the generation procedure, the total number of incident edges to each vertex is close to its assigned degree. Hence, the starting phase consists of assigning each vertex 𝑣𝑖 ∈ 𝑉 with a degree 𝑑𝑣 𝑖 and a linkage probability 𝑝𝑣 𝑖 ∝ 𝑑𝑣 𝑖 . Considering that 𝐷 is the sum of the degrees extracted from 𝜑, we define the CL linkage 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 undirected graphs, the insertion probability of an edge connecting 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 affected for a sufficiently large number of vertices. After the degree assignment phase, vertices are distributed throughout the pools having each the following linkage probability:

𝑝𝛾 𝑑 = 𝑑|𝛾 𝑑 | 𝐷
Now, instead of picking vertices a pool is first picked It should be highlighted that self-loops or multi-edges can be created since each endpoint of an edge is picked independently. The number of these edges, however, is independent of the number of vertices and thus can be neglected for large scale graphs.

Community-aware graph generation with given expected degree distribution

Although the CL model produces graphs with respect to a given degree distribution, it is not aware of the community structure existing in most real-world graphs. Hence, we propose a community-aware extension of the CL model based on the stochastic block model (SBM). Since a community is not quantitatively well defined, many definitions where provided in literature. Intuitively, one can consider a community as a subgraph which vertices are more densely connected between each other than they are with the rest of the graph. Let's consider the set of communities 𝐶 = {𝑐𝑖} and suppose that a vertex should belong to one community and edges should be differentiated 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.

To insure that vertices belonging to a community are more densely connected to each other than they are with the rest of the graph, the within and between edge creation probabilities 𝑝 𝑖𝑛 𝑐 𝑖 and 𝑝 𝑜𝑢𝑡 𝑐 𝑖 of 𝑐𝑖 must satisfy the condition 𝑝 𝑖𝑛 𝑐 𝑖 > 𝑝 𝑜𝑢𝑡 𝑐 𝑖 , ∀𝑐𝑖 ∈ 𝐶.

Stochastic block model

In this section, we formulate the SBM model [START_REF] Holland | Stochastic blockmodels: First steps[END_REF] (also known as the planted partition model) which is commonly used for the generation of random graphs with a given community structure. Hence, this generation procedure only considers controlling the community structure of the graph and overlooks the resulting degree distribution. The input of the generation procedure is a stochastic community matrix 𝑀 , each element 𝑚𝑖𝑗 of which defines the probability of edge creation between the source community 𝑐𝑖 and the target community 𝑐𝑗.

The output is a graph 𝐺 = {𝑉, 𝐸, 𝑀𝐺} where 𝑀𝐺 is the obtained density community matrix, each element 𝑚 𝐺 𝑖𝑗 of which defines the relative edge density between the source community 𝑐𝑖 and the target community 𝑐𝑗. The generation procedure starts with the distribution of vertices between the planted communities such that each vertex belongs to a single community. Now, the linkage probability between a vertex belonging to community 𝑐𝑖 and another vertex belonging to community 𝑐𝑗 is equal to 𝑚𝑖𝑗. However, the extracted community density matrix 𝑀𝐺 from the resulting graph 𝐺 is an approximation of 𝑀 . That is, each element 𝑚 𝐺 𝑖𝑗 is binomially distributed with mean equals to 𝑚𝑖𝑗 and Poisson distributed with the same mean for a sufficiently large number of edges.

Stochastic block model with given degree distribution

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 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 |𝐶| ∑ 𝑗=1,𝑗̸ =𝑖 𝜔𝑖𝑗 (2)
We define the linkage probability 𝑝𝑣 𝑖 of choosing a vertex 𝑣𝑖 belonging to community 𝑐𝑚 as follows:

𝑝𝑣 𝑖 = 𝑑𝑣 𝑖 𝐷𝑐 𝑚 𝑝𝑐 𝑚 , 𝑣𝑖 ∈ 𝑐𝑚 (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 which the vertex belongs and the probability 𝑑𝑣 𝑖 𝐷𝑐 𝑚 of choosing the vertex 𝑣𝑖 in that community. Hence, Equation 3 assures the approximation of the community matrix. However, 𝑝𝑣 𝑖 should be equal to 1) to assure the approximation of the degree distribution. Therefore, we define the following condition in order to reduce Equation (3) to Equation (1):

𝑑𝑣 𝑖 𝐷 (Equation
𝐷𝑐 𝑚 = 𝐷𝑝𝑐 𝑚 Now, replacing 𝐷 by 𝐷𝑐 𝑚 𝐷𝑝𝑐 𝑚
in the original CL linkage probability (Equation 1) which assures the control of the degree distribution, we obtain Equation 3 which assures the control of the community structure. Having this, the duality of the linkage probability given in Equations ( 1) and (3) insures that both requirements are satisfied by our generation procedure.

For performance amelioration, we consider the selection of pools rather than vertices such that a pool is local to one community. That is vertices having the same degree variation and belonging to the same community 𝑐𝑚 are grouped in a pool 𝛾 𝑐𝑚 𝑑 = {𝑣𝑖|𝑣𝑖 ∈ 𝑐𝑚 ∧ 𝑑𝑣𝑖 = 𝑑} such that the probability of a pool selection for edge insertion is:

𝑝 𝛾 𝑐𝑚 𝑑 = 𝑑|𝛾 𝑐𝑚 𝑑 | 𝐷

Hierarchical community structure

The specification of the stochastic matrix is not straightforward and imposes an exhaustive number of userdefined parameters. Hence, we define an auto-generative procedure that fills the matrix with no exogenous effort. 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 difference between within and between edge densities. The effect of varying 𝑘 is further highlighted in the Section 6.

Relative graph generation

In order to control the evolution of the degree distribution of the generated temporal graphs, we propose in this section an extension of the CL model that is based on the optimal transport to compute the minimal distance between the degree distributions of each pair of successive graph snapshots.

Earth mover's distance

The Earth mover's distance can be defined as a measure of distance over a domain 𝐷 between two distributions of the form {(𝑥1, 𝜔1), ..., (𝑥𝑛, 𝜔𝑛)} where 𝑥𝑖 ∈ 𝐷 and 𝜔𝑖 is the density of 𝑥𝑖. Having this, the problem reduces to the computation of an optimal flow (transportation matrix) 𝑇 = [𝑡𝑖𝑗] between two distributions 𝑃 = {(𝑥1, 𝑝1), ..., (𝑥𝑛, 𝑝𝑛)} and 𝑄 = {(𝑦1, 𝑞1), ..., (𝑦𝑛, 𝑞𝑛)} such that 𝑡𝑖𝑗 is the mass transported between 𝑝𝑖 and 𝑞𝑗 which minimizes the overall 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 𝑡𝑖𝑗
The EMD is fundamental in our generation procedure since it is used to compute the distance between two degree distributions as described in the following Section.

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 𝐺 and 𝐺 ′ corresponds to successive graph snapshots. For 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 graph operations between successive snapshots should be minimized which is assured in our model by applying an optimal transport method.

Consider the input graph 𝐺 = {𝑉, 𝐸, 𝜑} and degree distribution 𝜑 ′ , the generated output graph 𝐺 ′ = {𝑉 ′ , 𝐸 ′ , 𝜑 𝐺 ′ } such that 𝜑 𝐺 ′ is an approximation of 𝜑 ′ . We define the distance between two degree distributions 𝜑 and 𝜑 ′ as the earth mover's distance 𝐸𝑀 𝐷(𝜑, 𝜑 ′ ).

Consider 𝛿𝑛 = |𝑉 ′ | -|𝑉 | as the total number of vertices to be added to or removed from the graph based on whether 𝛿𝑛 is a positive or negative number, respectively. When adding a new vertex, this vertex is assigned with a degree equals to 0 and deleting a vertex consists of removing the vertex with its corresponding incident edges. This transformation phase assures that 𝐺 and 𝐺 ′ share the same number of vertices, hence, enables the transformation of 𝜑 into 𝜑 ′ . In order to morph 𝜑 into 𝜑 ′ , a transportation matrix 𝑇 is computed, where each row corresponds to a degree 𝑑 in the set of degrees in the 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 (4) 𝑝 - 𝑣 𝑖 = -𝛿𝑑𝑣 𝑖 𝐷 -, 𝛿𝑑𝑣 𝑖 < 0 (5)
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 neighbors is higher than 𝛿𝑑. For the sake of illustration, we present in Figure 3 a graph in which the number of edges to remove from a node is higher than the sum of the number of edges to remove from its neighboring vertices. That is, the transformation of this graph implies removing 2 edges from vertex 𝑣1 since 𝛿𝑣1 = -2. However, the number of the edges that have to be removed from the neighboring vertices of 𝑣1 is equal to 𝛿𝑣 2 = -1 since 𝛿𝑣 3 = 0 and 𝛿𝑣 4 = 1. To overcome this, we repeat the morphing procedure until EMD(𝜑, 𝜑 ′ ) reaches a desired 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.

Relative community-aware graph generation

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 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):

𝑝 + 𝑣 𝑖 = 𝛿𝑑𝑣 𝑖 𝐷 + 𝑐𝑚 𝑝𝑐 𝑚 , 𝑣𝑖 ∈ 𝑐𝑚 𝑝 - 𝑣 𝑖 = 𝛿𝑑𝑣 𝑖 𝐷 - 𝑐𝑚 𝑝𝑐 𝑚 , 𝑣𝑖 ∈ 𝑐𝑚
Where 𝐷 + 𝑐𝑚 and 𝐷 - 𝑐𝑚 are the total number of edge insertions and deletions in 𝑐𝑚, respectively. From the transportation matrix defined in section 5.2, we find 𝑛𝑖𝑗 as the portion of vertices with degree variation 𝛿𝑑 = 𝑑𝑗 -𝑑𝑖. However, finding the portion 𝑛 𝑐𝑚 𝑖𝑗 of vertices in community 𝑐𝑚 should satisfy three conditions detailed bellow. Each condition 𝑖 results in a system of linear equations of the form 𝐴𝑖𝑋 = 𝐵𝑖 where 𝑋 is a vector composed of 𝑛 𝑐𝑚 𝑖𝑗 such that 𝑋 = {𝑛

𝑐 𝑘 𝑖𝑗 | ∀1 ≤ 𝑖 ≤ |𝜑𝐺| ∧ ∀1 ≤ 𝑗 ≤ |𝜑| ∧ 0 ≤ 𝑘 ≤ |𝐶|}
where 𝑛𝑐 is the total number of communities.

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 all portions of vertices with degree variation 𝑑𝑗 -𝑑𝑖 ∀𝑑𝑗 ∈ 𝜑𝑡 in 𝑐𝑚 should be equal to the portion 𝑛 𝑐𝑚 𝑖 of vertices in 𝑐𝑚 having a degree 𝑑𝑖 resulting in the following equality: 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: 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 chosen from the linkage or breakage pools. However, breaking an edge might be impossible in some situations as shown in Figure 3. In such a use case, no graph update is added to the list of logs 𝐿. Finally, the EMD distance 𝜖 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 computed graph snapshot 𝐺 ′ . The computation stops when 𝜖 ′ is lower than or equal to 𝜖 or the number of repetitions has already been reached.

𝑝 + 𝛾 𝑑→𝑑 ′ ,𝑐𝑚 = 𝛿𝑑|𝛾 𝑐𝑚 𝑑→𝑑 ′ | 𝐷 + , 𝛿𝑑 > 0 𝑝 - 𝛾 𝑑→𝑑 ′ ,𝑐𝑚 = -𝛿𝑑|𝛾 𝑐𝑚 𝑑→𝑑 ′ | 𝐷 - ,

Algorithm 1: CRGG

Input: 𝐺 = {𝑉, 𝐸, 𝜑𝐺, 𝑀𝐺}, 𝜑, 𝑀 , 𝜖, 𝑚𝑎𝑥_𝑖𝑡𝑒𝑟, 𝑐𝑢𝑟_𝑖𝑡𝑒𝑟 Output:

𝐺 ′ = {𝑉 ′ , 𝐸 ′ , 𝜑 𝐺 ′ , 𝑀 𝐺 ′ } 1 𝑇 ← getTransportMatrix(𝜑𝐺, 𝜑) ; 2 X ←

Accuracy of the generation procedure

In order to measure how far the characteristics of the generated graphs are from the ground truth parameters, we define two distance metrics 𝜀 𝑑 and 𝜀𝑐.

The first metric 𝜀 𝑑 measures the inaccuracy of approximating 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 as follows:

𝜀 𝑑 = √∑ 𝑛 𝑖=1 (𝐸𝑀 𝐷(𝜑𝑖, 𝜑𝐺 𝑖 )) 2 𝑛
Whereas, the second metric 𝜀𝑐 measures the inaccuracy of approximating the community density matrix of the generated graphs with a given stochastic matrix. That is, it measure the root mean square of the difference between the Frobenius norms of the given stochastic matrix 𝑀 and the stochastic matrix 𝑀𝐺 𝑖 extracted from every generated graph snapshot. Having this, 𝜀𝑐 is computed as follows:

𝜀𝑐 = √∑ 𝑛 𝑖=1 (𝐹 (𝑀 ) -𝐹 (𝑀𝐺 𝑖 )) 2 𝑛
where 𝐹 (𝑀 ) is the Frobenius norm of the stochastic community matrix 𝑀 . We recall that the Frobenius norm of a matrix 𝐴 of dimensions (𝑛,𝑚) is defined as follows:

𝐹 (𝐴) = ⎯ ⎸ ⎸ ⎷ 𝑛 ∑ 𝑖=1 𝑚 ∑ 𝑗=1 |𝑎𝑖𝑗| 2

Experimental evaluation

We conducted a number of experiments to validate the efficiency 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 available 1 .

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 distributions or stochastic community matrix and the format of the 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.

Experimental setup

The experiments were conducted on a single machine equipped with Intel(R) Core(TM) i5-8350U CPU @ 1.70GHz 1.90 GHz, 16 GB memory and 500 GB SSD. We used Go 1.17.5 and Python 3.8.0. Besides, we referred to the optimal transport solver proposed in [START_REF] Flamary | Pot: Python optimal transport[END_REF]. The graphs shown in this section are visualized using Gephi tool [START_REF] Bastian | Gephi: an open source software for exploring and manipulating networks[END_REF] which offers network visualization facilities and community detection algorithms [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF].

Preliminaries

In the following experiments, we refer to two types of common degree distributions: Gaussian 𝑓𝐺 and Zipfian 𝑓𝑍 that are defined as follows:

𝑓𝐺(𝑥) = 1 𝜎 √ 𝜋 𝑒 -1 2 ( 𝑥-𝜇 𝜎 ) 2 𝑓𝑍 (𝑥) = 1 (𝑥 + 𝑣) 𝑠 𝑥 ∈ [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 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.

Controlling the evolution of the degree distribution

In this experiment, we show the evolution of the degree distribution of a sequence of graph snapshots generated with the relative generation procedure given a set of input parameters. Hence, we consider Gaussian and Zipfian degree distributions with different parameters and plotted the obtained degree distributions in Figures 4, 5 and 6. Figure 4 shows the evolution of the degree distribution of a generated sequence of 10 graph snapshots given the following parameters: {𝑛 0 = 10𝐾, 𝜇 0 = 30, 𝜎 0 = 2, 𝛿𝑛 = 10𝑘, 𝛿𝜇 = 5, 𝛿𝜎 = 0.1}. By setting 𝛿𝜇 to 5, we increase the average degree by 5 between each pair of snapshots. This indeed, can model a growth-only graph where the average edge degree tend to regularly increase as the time elapses. However, some real-world graphs are not growth-only in the sense that they are subject to edge deletions. This is indeed the case of human-proximity or transportation graphs where an important number of short-term connections is only valid during peak hours. To model this characteristic, RTGEN also supports edge deletions. The evolution of the degree distribution with edge deletions is presented in Figure 5. Let the following parameters define the evolution of degree distribution for 𝑖 ∈ [0, 4]: {𝑛 0 = 1𝑀, 𝜇 0 = 60, 𝜎 0 = 4, 𝛿𝑛 = 0, 𝛿𝜇 = 5, 𝛿𝜎 = 0} Whereas the following parameters define its evolution for 𝑖 ∈ [START_REF] Leskovec | Kronecker graphs: An approach to modeling networks[END_REF][START_REF] Holland | Stochastic blockmodels: First steps[END_REF]: {𝑛 0 = 10𝐾, 𝜇 0 = 80, 𝜎 0 = 2, 𝛿𝑛 = 0, 𝛿𝜇 = -5, 𝛿𝜎 = 0}. Indeed, setting 𝛿𝜇 to -5 indicates that the average degree decreases by a value of 5 between each pair of successive graph snapshots. Since real-world temporal graphs usually exhibit a power law degree distribution, we also generated graphs with an evolutionary Zipfian degree distribution composed of 10 graph snapshots as shown in Figure 6. For this generated temporal graph, we set the following parameters {𝑛 0 = 50𝑘, 𝑠 0 = 2.5, 𝑣 0 = 10, 𝑑 0 𝑚𝑎𝑥 = 10, 𝛿𝑛 = 50𝑘, 𝑠 = 0, 𝛿𝑣 = 0, 𝛿𝑑𝑚𝑎𝑥 = 5}. By setting parameter 𝛿𝑑𝑚𝑎𝑥 to 5, we consider that the maximum degree of nodes increases by a value of 5 between each pair of successive snapshots. Whereas, the value of 𝛿𝑛 indicates that 50𝑘 new nodes join the graph between successive snapshots. These parameters reflect the growth of a large number of real-world temporal graphs where new nodes join the graph and new connections are created as the time elapses.

Controlling the community structure of the generated graphs

In this experiment, we show the generated community structure with different parameters of the stochastic community matrix and the effect of varying parameter 𝑘 of the hierarchical tree. As described in Section 4. where 𝑝 𝑖𝑛 𝑐 𝑖 and 𝑝 𝑜𝑢𝑡 𝑐𝑖 are the within and between linkage probabilities of a community 𝑐𝑖. Furthermore, Figure 8 presents the modularity in function of parameter 𝑘 which we vary from 0 to 32. The modularity is a measure to quantify the goodness of community structure. Its formula compares, for all the communities, the fraction of edges that falls within the given community with the expected fraction if edges were distributed at random. It is clear from the results that the modularity increases with the increase of 𝑘. This is justified by the fact that 𝑘 is proportional to the difference between within and between edge linkage probabilities 𝑝 𝑖𝑛 𝑐 𝑖 -𝑝 𝑜𝑢𝑡 𝑐𝑖 .

Generating graphs with deletions between snapshots

As mentioned in Section 5, the relative graph generation procedure may incur a number of edge deletions. This can be cumbersome when the number of edges to delete for a given vertex is higher than the total sum of edges to delete from its neighboring vertices. We solve this problem by repeating the generation process until reaching an acceptable error threshold that is defined by the EMD between the obtained and desired degree distributions. Figure 12 shows the variation of the number of iterations and the execution time of the generation process in function of the threshold error defined by the EMD. The obtained results show that our generation procedure converges rapidly to a tolerable threshold. That is, a threshold equals to 0.001 can be reached with only 7 iterations. By comparing the execution time of 1 iteration and 7 iterations, we can notice that the difference 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}.

Accuracy of the generation procedure

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 RT-GEN approximates more accurately the given sequence of degree distribution and community structure as the total number of edges grows.

Related work

Synthetic graphs are important for developing benchmarks 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 to design models and generators, which are very useful for evaluating the efficiency of graph management techniques as storage, query evaluation, indexing, partitioning, etc.

An extensive work has been posited for the generation of static graphs. For instance, a special emphasis has been placed to control the degree distribution of the generated graphs. In this context, many graph generators were designed such as RTG [START_REF] Akoglu | Rtg: a recursive realistic graph generator using random typing[END_REF], RMAT [START_REF] Chakrabarti | R-mat: A recursive model for graph mining[END_REF] and its generalisation Kronecker [START_REF] Leskovec | Kronecker graphs: An approach to modeling networks[END_REF] producing only Power-Law distributions. Since real-world graphs are not limited to power-law distributions, BTER [START_REF] Kolda | A scalable generative graph model with community structure[END_REF] and its extension Darwini [START_REF] Edunov | Darwini: Generating realistic large-scale social graphs[END_REF] and GMark [START_REF] Bagan | gmark: Schema-driven generation of graphs and queries[END_REF] produce graphs with any user defined distribution.

Another graph generation model producing a given degree distribution is the CL model, forming the basis of the RTGEN tool. This model can be regarded as a successor of the Erdos-Rényi model [START_REF] Erdos | rényi on random graphs i[END_REF] that is designed for the generation of random graphs and a variant of the edge configuration model of Newman et al. [START_REF] Newman | Random graph models of social networks[END_REF]. It was extensively discussed and reused [START_REF] Chung | The average distances in random graphs with given expected degrees[END_REF][START_REF] Chung | Complex graphs and networks[END_REF][START_REF] Pinar | The similarity between stochastic kronecker and chung-lu graph models[END_REF][START_REF] Winlaw | An in-depth analysis of the chung-lu model[END_REF]. We choose to extend this model for its simplicity and scalability.

Besides, a number of existing graph generators are community-aware in the sense that they collect vertices that are more densely connected between each other than they are with the rest of the graph, in separate or overlapping subgraphs called communities [START_REF] Holland | Stochastic blockmodels: First steps[END_REF][START_REF] Karrer | Stochastic blockmodels and community structure in networks[END_REF][START_REF] Kamiński | Artificial benchmark for community detection (abcd): Fast random graph model with community structure[END_REF]. Although these generators preserve a given community structure, they fail to produce a graph with respect to a given degree distribution. In this paper, we overcome this limitation by allowing not only the generation of a given community structure but also a given degree distribution.

Despite the extensive work posited on the generation of non-temporal graphs, the generation of temporal graphs has received much less attention. For instance, DANCer [START_REF] Benyahia | Dancer: Dynamic attributed network with com-munity structure generator[END_REF] is capable of generating temporal, community-aware property graphs. It separates operations performed on communities (macro operations) from operations performed on vertices and edges (micro operations). ComAwareNetGrowth [START_REF] Gursoy | A community-aware network growth model for synthetic social network generation[END_REF] is a community-aware graph generator that is capable of creating growth only graphs. APA (Attribute-Aware Preferential Attachment) [START_REF] Aghasadeghi | Generating evolving property graphs with attribute-aware preferential attachment[END_REF] is a graph generator capable of creating growth-only property graphs based on a non-conventional triangle closing. Instead of closing a triangle based on a uniform probability given as an input parameter, their proposed model consists of closing a triangle based on the similarity between the candidate edge's endpoints. While GMark [START_REF] Bagan | gmark: Schema-driven generation of graphs and queries[END_REF] generates static graphs, EGG (Evolving Graph Generator) [START_REF] Alami | Synthetic graph generation from finely-tuned temporal constraints[END_REF] proposes an extension including evolving properties attached to each vertex. EGG, however, disregard the topological changes to the network and narrow the temporal evolution of the graph to property updates. DSNG-M (dynamic social network generator based on modularity) [START_REF] Duan | Dynamic social networks generator based on modularity: Dsngm[END_REF] is a graph generator that is capable of generating temporal graphs by flipping the direction of edges of a given graph in order to satisfy a randomly chosen modularity value assigned to a single graph snapshot. Some of the aforementioned graph generators produce temporal graphs with properties on nodes or vertices, which we do not address in this paper. None of them, however, allows the control of the evolution of the degree distribution given ground truth parameters that describe this evolution. This challenge lead to the elaboration of the RTGEN tool that allows the approximation of any given sequence of degree distributions that describes the evolution of the graph. We firmly believe, that the degree distribution is a key feature that characterizes graphs, hence, it should not be disregarded in graph generation tools.

Conclusion

In this paper, we addressed the generation of temporal graphs that represents a critical challenge in the design of benchmarks specific for evaluating temporal graph management systems. That is, we proposed RTGEN, a temporal graph generator that produces a sequence of graph snapshots whose community structure and evolution of the degree distribution results from approximating user defined parameters. This generation procedure consists of relatively generating a graph snapshot from a previous one by applying a number of atomic graph operations. Our generation technique relies on an Optimal transport solver to approximate a user-defined sequence of degree distributions while minimizing the number of operations needed to transform one snapshot into its successor. We conducted a number of experiments that validated the efficiency and accuracy of our generation procedure. In the future, we are planning to include a dynamic community structure to RTGEN. Indeed, the communities found in real-world graphs are subject to splits, merges, shrinks or expansions which should also be modelled in synthetic graphs.

Figure 1 :

 1 Figure 1: Relative graph generation procedure.

Figure 2 :

 2 Figure 2: Hierarchical community tree with height ℎ and branching factor 𝑏.

Figure 3 :

 3 Figure 3: Graph representing the case of a non-possible edge breakage.

Condition 3 :

 3 This condition states that the portion 𝑛𝑖𝑗 of vertices with degree variation 𝑑𝑗 -𝑑𝑖 in the graph must be equal to the sum of all portions 𝑛 𝑐𝑚 𝑖𝑗 ∀𝑐𝑚 ∈ 𝐶.

Figure 4 : 8 Ti

 48 Figure 4: Gaussian degree distribution of a growth only graph

Figure 5 : 8 Ti

 58 Figure 5: Gaussian degree distribution of a graph with edge deletions

Figure 6 :

 6 Figure 6: Zipfian degree distribution of a growth only graph

Figure 7 :

 7 Figure 7: A visualization of the generated graphs with a hierarchical community structure with parameters: 𝑏 = 4, ℎ = 2, 𝑐 = 4 and a varying 𝑘.

Figure 8 :

 8 Figure 8: Modularity value in function of parameter 𝑘 ranging from 0 to 32.

Figure 9 :

 9 Figure 9: Execution time in function of the number of edges.

Figure 10 :

 10 Figure 10: 𝜀 𝑑 in function of the number of edges.

Figure 11 :

 11 Figure 11: 𝜀𝑐 in function of the number of edges.

Figure 12 :

 12 Figure 12: The variation of the number of iterations and execution time in function of the EMD.

  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 using the function getTransportMatrix by taking the degree distributions 𝜑𝐺 and 𝜑 as input. The function getVector, computes 𝐴 and 𝐵 based on the Conditions 1, 2 and 3 and solves the system of equations defined by 𝐴𝑋 = 𝐵 to find the vector 𝑋. The total number of edges 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 distribution functions 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠 + and 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠 -based on the probabilities 𝑝 + 𝛾 𝑑→𝑑 ′ ,𝑐𝑚 and 𝑝 - 𝛾 𝑑→𝑑 ′ ,𝑐𝑚 . The process of adding and removing edges is repeated 𝐷 + and 𝐷 - times, respectively. In each iteration, communities 𝑐𝑛 and 𝑐𝑚 are picked based on 𝑐𝑑𝑓 𝐶𝑜𝑚𝑠 and vertices 𝑛𝑖 and 𝑛𝑗 are picked using 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠 + [𝑛] and 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠 -[𝑚].

𝛿𝑑 < 0

Algorithm CRGG depicts the relative community aware graph generation procedure. The input parameters are the graph snapshot 𝐺, desired degree distribution 𝜑, density community matrix 𝑀 , threshold of the EMD distance between 𝜑𝐺 and 𝜑, maximum number of repetitions 𝑚𝑎𝑥_𝑖𝑡𝑒𝑟 and the current number of repetitions 𝑐𝑢𝑟_𝑖𝑡𝑒𝑟.

  getVector(𝜑𝐺, 𝜑, 𝑇 , 𝑀 ) ;

	10
	8
	Ti me st am p
	23	𝐺 ′ ←
		𝐶𝑅𝐺𝐺(𝐺 ′ , 𝜑, 𝑀, 𝑐𝑢𝑟_𝑖𝑡𝑒𝑟, 𝑚𝑎𝑥_𝑖𝑡𝑒𝑟) ;
	24 else
	25	return 𝐺 ′ ;

3 (𝐷 + , 𝐷 -) ← getNumberOfEdges(T) ; 4 𝑐𝑑𝑓 𝐶𝑜𝑚 ← getCDFComs(𝑀 ) ; 5 (𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠 + , 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠 -) ← initCDFPools ; 6 𝐿 ← 𝑖𝑛𝑖𝑡𝐿𝑜𝑔𝑠() 7 for 𝑐𝑚 ∈ 𝐶 do 8 (𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠 + 𝑐𝑚 , 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠 - 𝑐𝑚 ) ← getCDFPools(𝑋, 𝑐𝑚) ; 9 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠 + [𝑚] ← 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠 + 𝑐𝑚 ; 10 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠 -[𝑚] ← 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠 - 𝑐𝑚 ; 11 for 𝑖 ← 0 𝑡𝑜 𝐷 + do 12 (𝑐𝑛, 𝑐𝑚) ← chooseComs(𝑐𝑑𝑓 𝐶𝑜𝑚) ; 13 (𝑛𝑖, 𝑛𝑗) ← chooseVertices(𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠 + [𝑛], 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠 + [𝑚]) ; 14 𝐿.addEdge (𝑛𝑖, 𝑛𝑗) ; 15 for 𝑖 ← 0 𝑡𝑜 𝐷 -do 16 (𝑐𝑛, 𝑐𝑚) ← chooseComs(𝑐𝑑𝑓 𝐶𝑜𝑚) ; 17 (𝑛𝑖, 𝑛𝑗) ← chooseVertices(𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠 -[𝑛], 𝑐𝑑𝑓 𝑃 𝑜𝑜𝑙𝑠 -[𝑚]) ; 18 𝐿.removeEdge (𝑛𝑖, 𝑛𝑗) ; 19 𝐺 ′ ← applyLogs(𝐺, 𝐿) ; 20 𝜖 ′ ← getEMD(𝜑, 𝜑 ′ 𝐺 ) ; 21 if 𝜖 ′ ≥ 𝜖 ∧ 𝑐𝑢𝑟_𝑖𝑡𝑒𝑟 < 𝑚𝑎𝑥_𝑖𝑡𝑒𝑟 then 22 𝑐𝑢𝑟_𝑖𝑡𝑒𝑟 ← 𝑐𝑢𝑟_𝑖𝑡𝑒𝑟 + 1 ;

  [START_REF] Akoglu | Rtg: a recursive realistic graph generator using random typing[END_REF], RTGEN is capable of auto-generating the stochastic community matrix representing a hierarchical community structure. Consider a stochastic community matrix generated by setting 𝑏 = 4 and ℎ = 2. As depicted in Equation2, one can tune the parameter 𝑘 in order to control the within and between edge densities. Hence, we select three different values of 𝑘 in {2, 4, 8}. Furthermore consider, 𝑛 = 1000 to be the total number of vertices and parameters 𝜇 = 30 and 𝜎 = 2 to be the parameters of a Gaussian distribution. Note that, in this experiment, we generate a single graph snapshot relying on the generation procedure proposed in Section 4.2. The generated graphs are shown in Figures7a, 7band 7c using the Gephi tool. It can be noticed that the difference between the within and between edge densities is proportional to 𝑘 since 𝑘 ∝ 𝑝 𝑖𝑛 𝑐 𝑖 -𝑝 𝑜𝑢𝑡 𝑐𝑖

https://github.com/MariaMassri/RTGEN