Thibaud Trolliet

Nathann Cohen

Frédéric Giroire

Luc Hogie

Stéphane Pérennes

Interest Clustering Coefficient: a New Metric for Directed Networks like Twitter *

Keywords: Complex networks, Clustering Coefficient, Directed networks, Social networks, Twitter

We study here the clustering of directed social graphs. The clustering coefficient has been introduced to capture the social phenomena that a friend of a friend tends to be my friend. This metric has been widely studied and has shown to be of great interest to describe the characteristics of a social graph. In fact, the clustering coefficient is adapted for a graph in which the links are undirected, such as friendship links (Facebook) or professional links (LinkedIn). For a graph in which links are directed from a source of information to a consumer of information, it is no longer adequate. We show that former studies have missed much of the information contained in the directed part of such graphs. We thus introduce a new metric to measure the clustering of a directed social graph with interest links, namely the interest clustering coefficient. We compute it (exactly and using sampling methods) on a very large social graph, a Twitter snapshot with 505 million users and 23 billion links. We additionally provide the values of the formerly introduced directed and undirected metrics, a first on such a large snapshot. We exhibit that the interest clustering coefficient is larger than classic directed clustering coefficients introduced in the literature. This shows the relevancy of the metric to capture the informational aspects of directed graphs.

Introduction

Networks appear in a large number of complex systems, whether they are social, biological, economical or technological. Examples include neuronal networks, the Internet, financial transactions, online social networks, ... Most "real-world" networks exhibit some properties that are not due to chance and that are really different from random networks or regular lattices. In this paper, we focus on the study of the clustering coefficient of social networks. Nodes in a network tend to form highly connected neighborhoods. This tendency can be measured by the clustering coefficient. It is classically defined for undirected networks as three times the number of triangles divided by the number of open triangles (formed by two incident edges). This clustering coefficient had been computed in many social networks and had been observed as much higher than what randomness would give. Triangles thus are of crucial interest to understand "real-world" networks. However, a large quantity of those networks are in fact directed (e.g. the web, online social networks like Instagram, financial transactions). It is for instance the case of Twitter, one of the largest and most influential social networks with 126 million daily active users [14]. In Twitter, a person can follow someone she is interested in; the resulting graph, where there is a link u → v if the account associated to the node u followed the account associated to the node v, is thus directed. In this study, we used as main dataset the snapshot of Twitter (TS in short) extracted by Gabielkov et al. as explained in [START_REF] Gabielkov | Studying social networks at scale: macroscopic anatomy of the twitter social graph[END_REF] and made available by the authors. The TS has around 505 million nodes and 23 billion arcs, making it one of the biggest snapshots of a social network available today. The classic definition of the clustering coefficient cannot be directly applied on directed graphs. This is why most of the studies computed it on the so-called mutual graph, as defined by Myers & al. in [START_REF] Myers | Information network or social network?: the structure of the twitter follow graph[END_REF], i.e., on the subgraph built with only the bidirectional links. We call mutual clustering coefficient (mcc for short) the clustering coefficient associated with this graph. We computed this coefficient in the TS, using both exact and approximated methods. We find a value for the mcc of 10,7%. This is a high value, of the same order as those found in other web social networks. However, this classical way to operate leaves out 2/3 of the graph! Indeed, we computed that the bidirectional edges only represents 35% of the edges of the TS. A way to avoid it is to consider all links as undirected and to compute the clustering coefficient of the obtained undirected graph. We refer to the corresponding computed clustering coefficient as the undirected clustering coefficient (ucc for short). Such a computation in the TS gives a value of ucc of only 0.11%. This is way lower than what was found in most undirected social networks. It is thus a necessity to introduce specific clustering coefficients for the directed graphs. More generally, when analyzing any directed datasets, it is of crucial importance to take into account the information contained in its directed part in the most adequate way. A first way to do that is to look at the different ways to form triangles with directed edges. Fagiolo computed the expected values of clustering coefficients considering directed triangles for random graphs in [START_REF] Fagiolo | Clustering in complex directed networks[END_REF] and illustrated his method on empirical data on world-trade flows. There are two possible orientations of triangles: transitive and cyclic triangles, see Figures 1b and1c. Each type of triangles corresponds to a directed clustering coefficient:

the transitive clustering coefficient (tcc in short), defined as:

tcc = # transitive triangles # open transitive triangles ,
the cyclic clustering coefficient (ccc in short), defined as:

ccc = 3 • # cyclic triangles # open transitive triangles .
We computed both coefficients for the snapshot, obtaining tcc = 1.9% and ccc = 1.7%. However, note that a large part of the transitive and cyclic triangles comes from bidirectional triangles. When removing them, we arrive to values of tcc = 0.51% and ccc = 0.24%. We believe those metrics miss an essential aspect of the Twitter graph: while the clustering coefficient was defined to represent the social cliques between people, it is not adequate to capture the information aspect of Twitter, known to be both a social and information media [START_REF] Kwak | What is twitter, a social network or a news media?[END_REF][START_REF] Myers | Information network or social network?: the structure of the twitter follow graph[END_REF]. In this work, we go one step further in the way directed relationships are modeled. We argue that in directed networks, the best way to define a relation or similarity between two individuals (Bob and Alice) is not always by a direct link, but by a common interest, that is, two links towards the same node (e.g., Bob → Carol and Alice → Carol). Indeed, when discussing interests, consider two nodes having similar interests. Apart from being friends, these two nodes do not have any reason to be directly connected. However, they would tend to be connected to the same out-neighbors.

We exploit this to study a new notion of connections in directed networks and the new naturally associated clustering coefficient, which we name interest clustering coefficient, or icc in short, and define as follows:

icc = 4 • # K22s # open K22s ,
where a K22 is defined as a set of four nodes in which two of them follow the two others, and an open K22 is a K22 with a missing link, see Figure 1d. We computed the icc on the Twitter snapshot, obtaining icc = 3.6% (3.1% when removing the bidirectional structures). This value, an order of magnitude higher than the previous clustering coefficients computed on the non bidirectional directed graph, confirms the interest of this metric. If the clustering coefficient of triangles are good metrics to capture the social aspect of a graph, the interest clustering coefficient is a good metric to capture the informational aspect. In summary, our contributions are the following:

-We define a new clustering coefficient for graphs with interest links.

-We succeeded in computing it, both exactly and using sampling methods, for a snapshot of Twitter with 505 million nodes and 23 billion edges. -We additionally provide the values of the directed and undirected clustering coefficients previously defined in the literature. We believe this is the first time that such coefficients are computed exactly for a large directed online social network.

The paper is organized as follows. We first discuss related work in Section 2. In Section 3, we present the algorithms we used to compute the values of the interest clustering coefficient, both exactly and by sampling. We discuss the results on the clustering coefficients of Twitter in Section 4 .

Related Work

Clustering coefficient. The clustering coefficient shows that, when two people know each other, there is a high probability that those people have common friends. The clustering coefficient has numerous important applications, such as spam detection [START_REF] Boykin | Leveraging social networks to fight spam[END_REF], link recommendation [START_REF] Nitai | A graph-based friend recommendation system using genetic algorithm[END_REF], information spread [START_REF] Mark | The strength of weak ties[END_REF], etc. There are different definitions of the clustering coefficient. The global clustering coefficient, sometimes also called transitivity, was first introduced by Barrat and Weigt in [START_REF] Barrat | On the properties of small-world network models[END_REF]. It is defined as 3 times the number of triangles in the graph, divided by the number of connected triplets of vertices in the graph. Another definition was given by Watts and Strogatz [START_REF] Duncan | Collective dynamics of 'smallworld'networks[END_REF] and is called the local clustering coefficient.

It is defined as the mean over all nodes of the graph of the local clustering of each node, that is the probability that two random neighbors of the node are also connected together. We use the global clustering coefficient in this paper.

The clustering coefficient has also been defined for weighted graphs [START_REF] Saramäki | Generalizations of the clustering coefficient to weighted complex networks[END_REF].

Computations for social graphs. The undirected clustering coefficient of some social networks has been provided in the literature. It has been computed on very large snapshots for Facebook [START_REF] Ugander | The anatomy of the facebook social graph[END_REF], Flickr, and YouTube [START_REF] Mislove | Measurement and analysis of online social networks[END_REF]. The local clustering coefficient has also been studied in the undirected mutual graph of Twitter [START_REF] Myers | Information network or social network?: the structure of the twitter follow graph[END_REF]. The undirected clustering coefficient is usually much higher in social networks than in random models.

Directed graphs. All these studies only consider the undirected clustering coefficient, even for directed graphs like Twitter. Fagiolo introduced definitions of directed clustering coefficients, that we named tcc and ccc [START_REF] Fagiolo | Clustering in complex directed networks[END_REF], but those definitions had never been computed and discussed on large datasets to our knowledge, as we do in this paper. Moreover, we believe that these metrics are not the most relevant ones for directed graphs with interest links.

Computing substructures. Researchers studied methods to efficiently compute the number of triangles in a graph, as naive methods are computationally very expensive on large graphs. Two families of methods have been proposed: triangle exact counting or enumeration and estimations. In the first family, the fastest algorithm is due to Alon, Yuster, and Zwick [START_REF] Alon | Finding and counting given length cycles[END_REF] and runs in O(m 1.41 ), with m the number of edges. However, methods using matrix multiplication cannot be used for large graphs because of their memory requirements. In practice, enumeration methods are often used, see e.g., [START_REF] Latapy | Main-memory triangle computations for very large (sparse (power-law)) graphs[END_REF]. Methods to count rectangles and butterfly structures in undirected bipartite networks were also proposed in [START_REF] Wang | Rectangle counting in large bipartite graphs[END_REF] and in [START_REF] Sanei-Mehri | Butterfly counting in bipartite networks[END_REF]. In this paper, we propose an efficient enumeration algorithm to count the number of K22s and open K22s in a very large graph. We focused on the case in which only one adjacency can be stored, as this was our case for the TS. To the best of our knowledge, we are the first to consider this setting.

Computing Clustering Coefficients in Twitter

To compute the interest clustering coefficient and the triangle clustering coefficients of very large networks, we used two different methods presented here: an exact count and an estimation using sampling techniques, either with a Monte Carlo algorithm or with a sampling of the graph. As a typical example of a massive directed social network with interest links, we carried out the computations for a Twitter snapshot (TS in short) with 505 million nodes and 23 billion links, described in Report [START_REF] Trolliet | Interest clustering coefficient: a new metric for directed networks like twitter[END_REF].

Exact Count

We computed the exact numbers of K22s and open K22s in the Twitter Snapshot.

Recall that we are discussing a dataset with hundreds of million nodes and billions of arcs. Results are reported in Table 1 and discussed in section 4. We first present in this section the algorithms we use, and discuss their complexity.

In the rest of this paper, we call top vertices (resp. bottom vertices) of a K22 the vertices which are destinations (resp. sources) of the K22 edges. We call a fork a set of two edges of a K22 connected to the same vertex. We say that a fork has top (or bottom) vertex x if both edges are connected to x and x is a top (resp. bottom) vertex of the K22. The same terminology applies to open K22s.

Trivial algorithm. The trivial algorithm would consider all quadruplets of vertices with 2 upper vertices. Then, for each quadruplet, it would check the existence of a K22 and of open K22s. There are 4 2 n 4 such quadruplets. It thus gives a complexity of O(n 4 ). This method can thus not be considered for the TS as it would perform 6.4 × 10 33 iterations.

Improved algorithm. The practical complexity can be greatly improved by only considering connected quadruplets, and by mutualizing the computations of the common neighbors of the in-neighbors of a vertex, as explained below. The pseudo-code is given in Algorithm 1. The algorithm's main loop iterates on the vertices of the graph. For each vertex x, we consider its in-neighborhood N -(x). We then compute how many times a vertex w (with w < x to avoid counting a K22 twice) appears in the outneighborhoods of the vertices of N -(x). We denote it #occ(w). We use a table to store the value of #occ(w) in order to be able to do a single pass on each out-neighbor. For a vertex w, any pair of its #occ(w) in-neighbors common with x forms a K22 with x and w as top vertices. There are hence #occ(w) 2 K22s with x and w as top vertices. The number of K22s with x as a top vertex is then

#K22(x) = w|#occ(w)≥2 #occ(w)
2 .

The number of open K22s with x as the top vertex is computed by noticing that, for any pair of vertices u and v of N -(x), we have

d + (u) -1 + d + (v) -1 - 1 v∈N + (u) -1 u∈N + (v)
open K22s containing this fork (ux, vx). We can count the number of open K22s with x as a top vertex, u as the bottom vertex of out-degree at least 2 (and thus another vertex v as the bottom vertex of out-degree at least 1).

A vertex u ∈ N -(x) is thus in (d + (u) -1 v∈N -(x)\{u} 1 v∈N + (u) )(d -(x) -1)
such open K22s. The only subtlety is that we count the number of arcs, which are between two vertices of N -(x), during the loop on the out-neighborhoods of the vertices of N -(x). We note this number #internalArcs. We then have:

#openK22(x) =   u∈N -(x) (d + (u) -1)(d -(x) -1)   -#internalArcs.
Lastly, the global number of K22s (resp. open K22s) in the digraph is just the sum of the number of K22s (resp. open K22s) with a vertex x as a top vertex, as, since we only consider K22s formed with a vertex w such that x < w, we only count each K22 once.

Complexity of the used algorithm. The complexity thus is

m+ u d + (u)(d + (u)- 1)
, with m the number of edges. Indeed, each edge is only considered once as an in-arc and d + -1 times as an out-arc. Note that, in the Twitter Snapshot, the sum of the squares of the degrees is equal to 8 • 10 13 . The order of the number of iterations needed to compute the number of K22s was thus massively decreased from the 6.4 × 10 33 iterations of the trivial algorithm.

For graphs following a power-law degree distribution with exponent between 2 and 3, we show in [START_REF] Trolliet | Interest clustering coefficient: a new metric for directed networks like twitter[END_REF] that this gives a complexity between O(m+n) and O(n 2 ), to be compared to the one of the naive method O(n 4 ).

Note that the number of undirected and directed triangles can be easily computed while counting the K22s, see [START_REF] Trolliet | Interest clustering coefficient: a new metric for directed networks like twitter[END_REF].

Algorithm 1 Enumeration of K22s and open K22s

1:

Input: Digraph(V, A) 2: #occ=0 table 3: for x ∈ V do 4:
#internalArcs ← 0 We count the number of arcs internal to N -(x) as these arcs do not form open K22s 5:

for v ∈ N -(x) do 6: #openK22s + = (d + (v) -1)(d -(x) -1) 7: for w ∈ N + (v) \ {x} do 8: #occ[w]+ = 1 9: if w ∈ N -(x)

Approximate Counts

As discussed later in Section 4, the exact count of the number of K22s and open K22s in Twitter implies massive computations. This number can be estimated using Monte Carlo Method and/or computations on a sample of the graph. We discuss both methods below. One of our goals was to see how good computations made in the literature using smaller Twitter snapshots were.

Exact icc on Twitter Samples. We built samples of the TS to estimate the interest clustering coefficient. Several choices can be made to build the samples. To avoid missing nodes of high degrees (which would lead to a high variance), we sampled the arcs (and not the nodes). Given a sampling probability p, we keep an arc in the sample with probability p. We generated samples of different sizes corresponding to sampling probabilities from p = 1/100 to p = 1/16000. Estimator of the number of K22 and open K22s. We use the classic estimator X = A∈A X A , where X A is the random variable which is equal to 1 if all the arcs of pattern A are selected in the sample and 0 otherwise. Theoretical bounds for expectation and variance are given in [START_REF] Trolliet | Interest clustering coefficient: a new metric for directed networks like twitter[END_REF]. The difficulty for the variance comes from the fact that two K22s can share a common link. Results. We present in Figure 2a the results of the algorithm for different sample sizes, corresponding to sampling probabilities from p = 1/100 to p=1/16, 000. For each sample size, we generated 30 samples. The distribution over the samples of the interest clustering coefficient is provided by a boxplot for each value of p. Note that a K22 of the TS appears in a sample with a probability of only p 4 , and of p 3 for an open K22. The clustering coefficient of a sample is thus an estimate of p • icc. We observe that, the clustering coefficient is well estimated using any sample for a sampling probability of 1/1000 or larger. Indeed, for this range of probabilities, the distribution over all samples is very concentrated and around the exact value of the icc. Note that, for p = 1/1000, a K22 is present in the sample with a probability of only 10 -12 . The expectation of the number of nodes with an edge is only 23 million nodes (over 500 million) and the number of edges is also around 23 million. Thus, in the TS, a small sample (5% of the nodes and 0.1% of edges) allows to do an efficient estimation of the icc.

For smaller values of p, the variance increases. The median estimates well the icc for a range of p between 1/8000 and 1/1000, but samples of these sizes may have error of 100% of the value. Lastly, for p = 1/16000, most of the time there is no surviving K22 in the sample, leading to a value of zero for the icc. The icc thus cannot be estimated correctly.

In conclusion, a sample with sampling probability 1/1000 is enough to efficiently estimate the interest clustering coefficient, with a computation time of around 1 minute (instead of days for the whole TS) on a machine of the cluster.

Monte Carlo Method. The difficulty to estimate the clustering coefficients using Monte Carlo Method is that the probability to observe a (closed or open) K22 or a triangle is very small. In the case of triangles, this difficulty can be easily circumvented by knowing the node degrees. This allows to select an open triangle uniformly at random. In the case of K22s, this information is not sufficient to select an open K22 uniformly at random. In fact, achieving this goal is very costly. We thus present a new method in which, by picking only forks (as we do for triangles), we can compute the interest clustering coefficient. The idea is to select a vertex v as a root according to the square of its in-degree (as in the case of triangles), but without knowing its number of open K22s (first step). We then select two arcs u 1 v and u 2 v uniformly at random (second step). We then compute the number of K22s and open K22s with the selected fork (u 1 v, u 2 v) (third step). The formal justification of this new method is developed in [START_REF] Trolliet | Interest clustering coefficient: a new metric for directed networks like twitter[END_REF].

We present here the results of the experiments. Experiments. We carried out two runs with 10 million iterations. It took about 2min30 for one run (60.000 iterations per second). The value of the estimator of the icc for the two runs is plotted as a function of the number of iterations in Figure 2b. We see that the estimator converges as expected to the value of the icc of TS represented by a straight horizontal line (and which was computed exactly in the previous section). We also plotted the estimated standard deviation as a function of the number of iterations. To obtain it, we did one billion iterations. We then estimated the standard deviation σ, and plotted σ √ n . We see that large jumps or discontinuity happen, but only at the beginning. They correspond to the draw of a fork with a lot of K22s and open K22s corresponding to a user who does not have the same icc as the global network. Then, the convergence is quick. After 300 iterations, the standard deviation is below 10% and after 1000 iterations, we do not experience a value of the runs less precise than 10%.

Results: Clustering coefficients in real Datasets

Twitter. To compute the number of K22s, open K22s, directed triangles, and undirected triangles in the Twitter Snapshot, we used a cluster with a rack of 16 Dell C6420 dual-Xeon 2.20GHz (20 cores), with 192 GB RAM, all sharing an NFS Linux partition over Infiniband. It took 51 hours to compute the exact numbers of K22s and open K22s, corresponding to 265h of cumulative computation times on the cluster. We reported the results in Table 1. Number of K22s and triangles. We see that the numbers of K22s and open K22s are huge, 2.6 × 10 16 and 3.1 × 10 18 , respectively. It has to be compared with the number of triangles which are several orders of magnitude smaller: e.g., 2.5 × 10 12 and 1.3 × 10 14 for transitive triangles. Clustering coefficient in the mutual graph. The mutual graph captures the friendship relationships in the social network. The mutual clustering coefficient thus is high (mcc = 10.7%), as cliques of friends are frequent in Twitter. Clustering coefficients in the whole graph. We observe that icc = 3.3% > tcc = 1.9% > ccc = 1.7% > ucc = 0.11%. Directed metrics better capture the interest relationships in the TS as ucc is very low. The highest parameter is the icc. It confirms the hypothesis of this paper that common interests between two users are better captured by the notion of K22 than by a direct link between these users. As expected, the second parameter is the one using transitive triangles. Indeed, they capture a natural way for a user of finding a new interesting user, icc tcc ccc ucc T witter 3.1% 0.51% 0.24% 0.057% that is, considering the followings of a following, especially after having seen retweets. A bit surprisingly, the ccc is not very low. In fact, a large fraction of the cyclic triangles are explained by corresponding triangles in the mutual graph (triangles of bi-directional links). We believe bidirectional links contain a part of the social aspect of Twitter. Indeed, two friends will tend to follow each other, while a celebrity have little chance to follow back a person she does not know. A way to artificially take off the social influence in order to focus exclusively on the directed interest part 2. If we take off those mutual triangles, both the tcc and the ccc values drop to 0.51% and 0.24%, respectively, while the icc stays about the same at 3.1%. This tends to confirm the hypothesis that the directed triangle clusterings somehow measure the friendship part of the TS more than the interest part. We also looked at the distributions of K22, open K22 and icc for each node, using definitions adapted from the triangle ones [START_REF] Duncan | Collective dynamics of 'smallworld'networks[END_REF]. We obtain a value of 7.7% for the local icc. More details can be found in [START_REF] Trolliet | Interest clustering coefficient: a new metric for directed networks like twitter[END_REF].

Other networks. We computed the different metrics on four other directed networks: two social networks, a web network and a citation network. The main dataset characteristics (more details in [START_REF] Trolliet | Interest clustering coefficient: a new metric for directed networks like twitter[END_REF]) as well as their clustering coefficients are reported in Table 3. The main takeaways are the following: -A high value of icc indicates the presence of clusters of interests such as research communities or interest fields.

-A high value of tcc is the sign of an important local phenomena of neighbors' recommendations and/or of a high hierarchical structure in the dataset.

-The ccc has no real social meaning. If its value can be high in a directed graph, this is only due to the presence of bidirectional arcs and triangles.

-Directed networks have a high mcc. Indeed, their bidirectional parts (mutual graph) have strong social communities, leading to a high clustering coefficient.

-The ucc is usually significantly lower, showing that the directed part of the network is better understood using directed clustering coefficients.

-Directed social networks have similar mixes of values of their undirected and directed clustering coefficients, however, with some notable differences, due to their diverse usages and information.

Additional work. As a complement of this study, we also proposed two applications using the K22s, which can be found in [START_REF] Trolliet | Interest clustering coefficient: a new metric for directed networks like twitter[END_REF]: -Recommendations. We propose to use the K22s to carry out link recommendation, as we advocate that the interest clustering coefficient is a good This way, the model is able to build random networks with a high icc, in order to represent the high values of icc found in real-world networks as presented in this paper. We prove that the in-and out-degree distributions of this model follow power-laws, as most of real-world networks, and show empirically the high value of the icc.

Conclusion, Discussion, and Future Work

In this paper, we introduce a new metric, the interest clustering coefficient, to capture the interest phenomena in a directed graph. Indeed, the classical undirected clustering coefficient apprehends the social phenomena that my friends tend to be connected. However, it is not adequate to take into account directed interest links. The interest clustering coefficient is based on the idea that, if two people are following a common neighbor, they have a higher chance to have other common neighbors, since they have at least one interest in common. We computed this new metric on a network known to be at the same time a social and information media, a snapshot of Twitter from 2012 with 505 million users and 23 billion links. The computation was made on the total graph, giving the exact value of the interest clustering coefficient, and using sampling methods. The value of the interest clustering coefficient of Twitter is around 3.3%, higher than (undirected and directed) clustering coefficients introduced in the literature and based on triangles, which we also computed on the snapshot. Since both icc and classical cc represent a probability to close a structure, comparing their values with each other makes sense. However, an additional comparison with random models would be good to quantify what a "high value" means. In a network built with the G(n, p) model, both directed cc and icc are equal to p. For the Twitter Snapshot, p ∼ 10 -7 , way smaller than the found values. An interesting study would be to compute those metrics on preferential attachment models; we keep this for a future work. The icc is defined here for unweighted networks: it would be interesting to generalize it to weighted ones as a future work. We also would like to further investigate link recommendation based on the K22 structure defined for the interest clustering coefficient. Indeed, as there are several order more K22s than triangles in social networks, it could lead to a more diverse recommendation system, than the ones based on triangles. It would be interesting to carry out a real-world user case study to investigate if users are more satisfied by such recommendations.

( a )

 a Undirected triangles. (b) Transitive directed triangles. (c) Cyclic directed triangles. (d) K22s.

Fig. 1 :

 1 Fig. 1: Closed (left) and open (right) undirected and directed triangles and K22s.

  Estimation of the interest clustering coefficient for different sample sizes with Edge Sampling Method. (b) Estimation of the interest clustering coefficient with Monte Carlo Method.

Fig. 2 :

 2 Fig. 2: Estimation of the interest clustering coefficient with Approximate Counts.

#closed #open cc icc 2 . 6 •

 26 10 16 3.1 • 10 18 3.3% tcc 2.5 • 10 12 1.3 • 10 14 1.9% ccc 7.2 • 10 11 1.3 • 10 14 1.7% ucc 6.2 • 10 11 1.6 • 10 15 0.11% mcc 3.2 • 10 11 8.9 • 10 12 10.7%

Table 1 :

 1 Clustering coefficients in the TS. The first (resp. second) column represents the number of closed (resp. open) K22s or triangles in the Twitter Snapshot. Each line corresponds to a clustering coefficient defined in Section 1.

  of the graph is to remove the (open and closed) triangles and K22s contained in the mutual graph from the total count. Indeed, each undirected triangle of the mutual graph induces two cyclic triangles and six transitive triangles, and each undirected open triangle induces two open triangles. In the same way, each undirected K22 induces two K22s and each undirected open K22 induces two open K22s. The obtained results are shown in Table

Table 2 :

 2 Clustering coefficients without the mutual structures.

Table 3 :

 3 Information and clustering coefficients of the directed datasets. SN means Social Network. N is the number of nodes, |E| the number of edges, and |E|m |E| the fraction of edges implied in a bidirectional link. measure of common user interests. The principle is to recommend links closing a large number of K22s (instead, classically, of triangles). We discuss the strengths/weaknesses of this method for a set of Twitter users.-Models with addition of K22s. We propose a new directed random growing model, based on the one introduced by Bollobas et al.[START_REF] Bollobás | Directed scale-free graphs[END_REF], with addition of K22s.

* This work has been supported by the French government through the UCA JEDI (ANR-15-IDEX-01), EUR DS4H (ANR-17-EURE-004) Investments in the Future projects, and ANR DIGRAPHS, by the SNIF project, and by Inria associated team EfDyNet. The authors are grateful to the OPAL infrastructure from Université Côte d'Azur for providing resources and support.


Frédéric Giroire

Stéphane Pérennes

Thibaud Trolliet

A Random Growth Model with any Real or Theoretical Degree Distribution *

Keywords: Complex Networks, Random Growth Model, Preferential Attachment, Degree Distribution, Twitter

The degree distributions of complex networks are usually considered to be power law. However, it is not the case for a large number of them. We thus propose a new model able to build random growing networks with (almost) any wanted degree distribution. The degree distribution can either be theoretical or extracted from a real-world network. The main idea is to invert the recurrence equation commonly used to compute the degree distribution in order to find a convenient attachment function for node connections -commonly chosen as linear. We compute this attachment function for some classical distributions, as the power-law, broken power-law, geometric and Poisson distributions. We also use the model on an undirected version of the Twitter network, for which the degree distribution has an unusual shape.

Introduction

Complex networks appear in the empirical study of real world networks from various domains, such that social, biology, economy, technology, ... Most of those networks exhibit common properties, such as high clustering coefficient, communities, ... Probably the most studied of those properties is the degree distribution (named DD in the rest of the paper), which is often observed as following a powerlaw distribution. Random network models have thus focused on being able to build graphs exhibiting power-law DDs, such as the well-known Barabasi-Albert model [START_REF] Albert | Statistical mechanics of complex networks[END_REF] or the Chun-Lu model [START_REF] Chung | Complex graphs and networks[END_REF], but also models for directed networks [START_REF] Bollobás | Directed scale-free graphs[END_REF] or for networks with communities [START_REF] Sallaberry | Model for generating artificial social networks having community structures with small-world and scale-free properties[END_REF]. However, this is common to find real networks with DDs not perfectly following a power-law. For instance for social networks, Facebook has been shown to follow a broken power-law 3 [START_REF] Gjoka | Walking in facebook: A case study of unbiased sampling of osns[END_REF], while Twitter only has the distribution tail following a power-law and some atypical behaviors due to Twitter's policies, as we report in Section 5.1.

(a) DD of the number of unique callers and callees from a mobile phone operator. [START_REF] Seshadri | Mobile call graphs: beyond power-law and lognormal distributions[END_REF] (b)

In-DD between shop-to-shop recommendations from an online marketplace. [START_REF] Andrew | Explaining the power-law degree distribution in a social commerce network[END_REF] (c) Graphlet DD from a biological model. [START_REF] Pržulj | Biological network comparison using graphlet degree distribution[END_REF] (d) DD of users of Cyworld, the largest online social network of South Korea. [START_REF] Ahn | Analysis of topological characteristics of huge online social networking services[END_REF] (e) DDs of users of Flickr, an online social network. [START_REF] Cha | A measurement-driven analysis of information propagation in the flickr social network[END_REF] (f) DD of the length of the contact list in Microsoft Messenger network. [START_REF] Leskovec | Planetary-scale views on a large instant-messaging network[END_REF] (g) DD of the number of friends from FaceBook, a social network. [START_REF] Gjoka | Walking in facebook: A case study of unbiased sampling of osns[END_REF] (h) Out-DD of the number of followees on Twitter. [START_REF] Trolliet | Interest clustering coefficient: a new metric for directed networks like twitter[END_REF] Fig. 1: DDs extracted from different seminal papers studying networks from various domains.

It is yet crucial to build models able to reproduce the properties of real networks. Indeed, some studies such as fake news propagation or evolution over time of the networks cannot always be done empirically, for technical or ethical reasons. Carrying out simulations with random networks created with well-built models is a solution to study real networks without directly experimenting on them. Those models have to create networks with similar properties as real ones, while staying as simple as possible.

In this paper, we propose a random growth model able to create graphs with almost any (under some conditions) given DD. Classical models usually choose the nodes receiving new edges proportionally to a linear attachment function [START_REF] Albert | Statistical mechanics of complex networks[END_REF][START_REF] Bollobás | Directed scale-free graphs[END_REF]. The theoretical DD of the networks generated by those models is computed using a recurrence equation. The main idea of this paper is to reverse this recurrence equation to express the attachment function f as a function of the DD. This way, for a given DD, we can compute the associated attachment function, and use it in a proposed random growth model to create graphs with the wanted DD. The given DD can either be theoretical, or extracted from a real network.

f (i) = i (or f (i) = i + b)
We compute the attachment function associated with some classical DD, homogeneous ones such as Poisson or geometric distributions, and heterogeneous ones such as exact power-law and broken power-law. We also study the undirected DD of a Twitter snapshot of 400 million nodes and 23 billion edges, extracted by Gabielkov et al. [START_REF] Gabielkov | The complete picture of the twitter social graph[END_REF] and made available by the authors. We notice it has an atypical shape, due to Twitter's policies. We compute empirically the associated attachment function, and use the model to build random graphs with this DD. A necessary condition is that the given DD must be defined for all degrees under the (arbitrary chosen) maximum value. However this condition can be circumvented doing an interpolation between existing points to estimate the missing ones, as discussed in Section 5.

The rest of the paper is organized as follows. We first discuss the related work in Section 2. In Section 3, we present the new model, and invert the recurrence equation to find the relation between the attachment function and the DD. We apply this relation to compute the attachment function associated to a power-law DD, a broken-power law DD, and other theoretical distributions. In Section 5 we apply our model on a real-world DD, the undirected DD of Twitter.

Related Work

The degree distribution has been computed for a lot of networks, in particular for social networks such as Facebook [START_REF] Gjoka | Walking in facebook: A case study of unbiased sampling of osns[END_REF] or Microsoft Messenger [START_REF] Leskovec | Planetary-scale views on a large instant-messaging network[END_REF]. Note that Myers et al. have also studied DDs for Twitter in [START_REF] Myers | Information network or social network?: the structure of the twitter follow graph[END_REF], using a different dataset than the one of [START_REF] Gabielkov | The complete picture of the twitter social graph[END_REF].

Questioning the relevance of power-law fits is not new: for instance, Clauset et al. [START_REF] Clauset | Power-law distributions in empirical data[END_REF] or Lima-Mendez and van Helden [START_REF] Lima-Mendez | The powerful law of the power law and other myths in network biology[END_REF] have already deeply questioned the myth of power-law -as Lima-Mendez and van Helden call it-, and develop tools to verify if a distribution can be considered as a power-law or not. Clauset et al. apply the developed tools on 24 distributions extracted from various domains of literature, which have all been considered to be power-laws. Among them, "17 of the 24 data sets are consistent with a power-law distribution", and "there is only one case in which the power law appears to be truly convincing, in the sense that it is an excellent fit to the data and none of the alternatives carries any weight". In the continuity of this work, Broido and Clauset study in [START_REF] Anna | Scale-free networks are rare[END_REF] the DD of nearly 1000 networks from various domains, and conclude that "fewer than 36 networks (4%) exhibit the strongest level of evidence for scale-free structure".

The study of Clauset et al. [START_REF] Clauset | Power-law distributions in empirical data[END_REF] only considered distributions which have a power-law shape when looking at the distribution in log-log. As a complement, we gathered DDs from literature which clearly do not follow power-law distributions to show their diversity. We extracted from literature DDs of networks from various domains: biology, economy, computer science, ... Each presented DD comes from a seminal well cited paper of the respective domains. They are gathered in Figure 1. Various shapes can be observed from those DDs, which could (by eyes) be associated with exponential (Fig. 1b,1c), broken power-law (Fig. 1a,1e,1g), or even some kind of inverted broken power-law (Fig 1d). We also observe DDs with specific behaviors (Fig. 1f,1h).

The first proposed models of random networks, such as the Erdős-Rényi model [START_REF] Erdős | On the evolution of random graphs[END_REF], build networks with a homogeneous DD. The observation that a lot of real-world networks follow power-law DDs lead Albert and Barabasi to propose their famous model with linear preferential attachment [START_REF] Albert | Statistical mechanics of complex networks[END_REF]. It has been followed by a lot of random growth models, e.g. [START_REF] Bollobás | Directed scale-free graphs[END_REF][START_REF] Chung | Complex graphs and networks[END_REF] also giving a DD in power-law. A few models permit to build networks with any DD: for instance, the configuration model [START_REF] Bollobás | A probabilistic proof of an asymptotic formula for the number of labelled regular graphs[END_REF][START_REF] Mark Ej Newman | Random graphs with arbitrary degree distributions and their applications[END_REF] takes as parameter a DD P and a number of nodes n, creates n nodes with a degree randomly picked following P , then randomly connects the half-edges of every node. Goshal and Newman propose in [START_REF] Ghoshal | Growing distributed networks with arbitrary degree distributions[END_REF] a model generating non-growing networks (where, at each time-step, a node is added and another is deleted) which can achieve any DD, using a method close to the one proposed in this paper. However, both of those models generate non-growing networks, while most real-world networks are constantly growing.

Presentation of the model

The proposed model is a generalization of the model introduced by Chun and Lu in [START_REF] Chung | Complex graphs and networks[END_REF]. At each time step, we have either a node event or an edge event. During a node event, a node is added with an edge attached to it; during an edge event, an edge is added between two existing nodes. Each node to which the edge is connected is randomly chosen among all nodes with a probability proportional to a given function f , called the attachment function. The model is as follows:

We start with an initial graph G 0 . At each time step t:

-With probability p: we add a node u, and an edge (u, v) where the node v is chosen randomly between all existing nodes with a probability

f (deg(v))
w∈V f (deg(w)) ; -With probability (1 -p): we add an edge (u, v) where the nodes u and v are chosen randomly between all existing nodes with a probability

f (deg(u)) w∈V f (deg(w)) and f (deg(v))
w∈V f (deg(w)) . Note that the Chun-lu model is the particular case where f (i) = i for all i ≥ 1. We call generalized Chun-Lu model the proposed model where f (i) = i + b, for all i ≥ 1 with b > -1.

Inversion of the recurrence equation

The common way to find the DD of classical random growth models is to study the recurrence equation of the evolution of the number of nodes with degree i between two time steps. This equation can sometimes be easily solved, sometimes not. But what matters for us is that the common process is to start from a given model -thus an attachment function f -, and use the recurrence equation to find the DD P . In this section, we show that the recurrence equation of the proposed model can be reversed such that, if P if given, we can find an associated attachment function f . Theorem 1. In the proposed model, if the attachment function is chosen as:

∀i ≥ 1, f (i) = 1 P (i) ∞ k=i+1 P (k), (1)
then the DD of the created graph is distributed according to P . § § Note that Equation 1 can also be expressed as f (i) = P (k>i) P (i) .

Proof. We consider the variation of the number of nodes of degree i N (i, t) between a time step from t to (t+1). During this time step, a node with degree i may gain a degree and thus diminishes by 1 the number of nodes of degree i. This happens with a probability p + 2(1 -p) (the mean number of half-edges connected to existing nodes during a time step) ×

f (i)
j≥1 f (j)N (j,t) (the probability for this particular node of degree i to be chosen). Since it is the same for all nodes of degree i, the number of nodes going from degree i to i + 1 during a time step

is p + 2(1 -p) × f (i) j≥1 f (j)N (j,t) × N (i, t).
In the same way, some nodes with degree i -1 may be connected to an edge and increase the number of nodes of degree i. Finally, with probability p, a node of degree 1 is added. Gathering those contributions, taking the expectation, and using concentration results give the following equation:

E[N (i, t + 1)] -E[N (i, t)] = ( 2
)
pδ i,1 + (2 -p) f (i -1) j≥1 f (j)E[N (j, t)] E[N (i -1, t)] -(2 -p) f (i) j≥1 f (j)E[N (j, t)] E[N (i, t)]
where δ i,j is the Kronecker delta. The first term of the right hand is the probability of addition of a node. The second (resp. third) term is the probability that a node of degree i -1 (resp. i) gets chosen to be the end of an edge. The factor (2 -p) = p + 2(1 -p) comes from the fact that this happens with probability p during a node event (connection of a single half-edge) and with probability 2(1 -p) during an edge event (possible connection of 2 half-edges).

Let

P (i) = lim t→+∞ E[N (i,t)] pt
(the p in the denominator comes from the fact that E[N (t)] = pt). We denote g(i) = 2-p p f (i) j≥1 f (j)P (j) . We first show that g(i) = 1 P (i) ∞ k=i+1 P (k). We will then show that we can choose f = g.

We use the following lemma from [START_REF] Chung | Complex graphs and networks[END_REF]: Lemma 1. Let (a t ), (b t ), (c t ) be three sequences such that a t+1 = (1-bt t )a t +c t , lim For i = 1, the equation becomes:

E[N (1, t + 1)] -E[N (1, t)] = p -(2 -p) f (1) j≥1 f (j)E[N (j, t)] E[N (1, t)]. (3)
Taking

a t = E[N (1,t)] p , b t = (2-p)f (1) p j≥1 f (j) E[N (j,t)] pt
, and c t = 1, we have lim

t→+∞ b t =
g(1) > 0 and lim t→+∞ c t = 1. We can thus apply Lemma 1:

lim t→+∞ E[N (1, t)] pt = P (1) = 1 1 + g(1)
.

Now, ∀i ≥ 2, taking

a t = E[N (i,t)] p , b t = (2-p)f (i) p j≥1 f (j) E[N (j,t)] pt
, and

c t = (2-p)f (i-1) p j≥1 f (j) E[N (j,t)] pt E[N (i-1,t)] pt
, we have lim t→+∞ b t = g(i) > 0 and lim t→+∞ c t = g(i -1)P (i -1). Lemma 1 gives:

lim t→+∞ E[N (i, t)] pt = P (i) = g(i -1)P (i -1) 1 + g(i) . (5)
Iterating over Equation 5, we express g as a function of P :

g(i)P (i) = g(i -1)P (i -1) -P (i) = g(1)P (1) - i k=2 P (k) = 1 - i k=1 P (k) =⇒ g(i) = 1 P (i) ∞ k=i+1 P (k) (6)
Now, notice that:

∞ k=1 g(k)P (k) = ∞ k=1 2 -p p f (k) ∞ k =1 f (k )P (k ) P (k) = (2 -p) p . (7)
So

g(i) satisfies g(i) = 2-p p g(i) ∞ k=1 g(k)P (k)
. Hence the attachment function can be chosen as f = g, which concludes the proof.

For a given probability law, Theorem 1 can be used to compute the attachment function which, when used in the model, will give this probability law as DD.

With the presented model, we also have an implicit constraint between the mean degree and the parameter p. Indeed by construction, we have E[N (t)] = pt and E(|E|(t)) = t with |E|(t) the number of edges at time t, leading to a meandegree of 1 p . But the mean-degree can also be expressed as k≥1 kP (k).

Condition 1

The parameter p has to satisfy:

1 p =< k > (8)
We can finally combine the previous results and present the method to build a random network with a fixed DD:

1) Use Equation 1 to compute f from P ; 2) Compute p using Condition 1;

2) Build the graph with the proposed model, given (f, p) as parameters.

Name P(i) f(i) Condition Generalized Chun-Lu C Γ (i+b) Γ (i+b+α) 1 α-1 i + b α-1 p = α-2 α+b-1 Exact Power-Law i -α ζ(α) ζ(α,i+1) i -α p = ζ(α) ζ(α-1)
Geometric Law q(1 -q) i-1

1-q q p = q

Poisson Law 1 e λ -1

λ i i! e λ γ(i+1,λ) λ i p = 1-e -λ λ Broken Power-Law C Γ (i+b 1 ) Γ (i+b 1 +α 1 ) if i ≤ d Cγ Γ (i+b 2 ) Γ (i+b 2 +α 2 ) if i > d
cf eq. 17& 18 cf eq. 16

Application to some distributions

We now apply Equation 1 to compute the attachment function for some classical distributions. We first start in Section 4.1 from the distribution obtained with the generalized Chun-Lu model to show we find a linear dependence, as expected. We then compute in Section 4.2 the associated attachment function of the broken power-law distribution. Using similar computations (which can be found in Report [START_REF] Giroire | A random growth model with any real or theoretical degree distribution[END_REF]), we computed the attachment function of other classical distributions. Table 1 summarizes those results.

Preliminary: Generalized Chun-Lu model

As a first example, by taking a power-law DD, we should be able to find a linear probability distribution for the generalized Chun-Lu model.

In the general Chun-Lu model, we can show that the real DD is not an exact power-law but a fraction of Gamma function -equivalent to a power-law for high degrees-of the form:

∀i ≥ 1, P (i) = C Γ (i + b) Γ (i + b + α) ∼ i 1 i -α (9)
where C = (α -1) Γ (b+α) Γ (b+1) , and α > 2. The choice of α determines the slope of the DD, while the choice of b determines the mean-degree of the graph.

Constraint on p: Condition 1 gives:

1 p = ∞ k=1 kP (k) = (α -1) Γ (b + α) Γ (b + 1) × α 2 + α(2b -1) + b(b -1) (α -2)(α -1) Γ (b + 1) Γ (α + b + 1) =⇒ p = (α -2) α + b -1 ( 10
)
Attachment function f: Using Theorem 1:

f (i) = 1 P (i) k≥i+1 P (k) = Γ (i + b + α) Γ (i + b) Γ (i + b + 1) (α -1)Γ (i + α + b) (11) =⇒ f (i) = 1 α -1 i + b α -1 (12)
As expected, we find a linear attachment function. To create a graph with a wanted slope α and mean-degree p -1 , one only has to choose α as the wanted slope and b following equation 10. In the particular case b = 0, we recover the Chun-Lu model of [START_REF] Chung | Complex graphs and networks[END_REF], with a slope of α = 2 + p 2-p as expected.

Γ (d + b 2 + α 2 ) =⇒ γ = Γ (d + b 1 )Γ (d + b 2 + α 2 ) Γ (d + b 1 + α 1 )Γ (d + b 2 ) . (14)
Constraints on C and p: The value of C can be computed by summing over all degrees:

C = ∞ k=1 P (k) -1 = 1 α 1 -1 Γ (b 1 + 1) Γ (α 1 + b 1 ) + Γ (b 1 + d) Γ (α 1 + b 1 + d) b 2 + d α 2 -1 - b 1 + d α 1 -1 -1 (15)
Using Condition 1, p is defined by the following equation:

1 pC = d k=1 k Γ (k + b 1 ) Γ (k + b 1 + α 1 ) + γ ∞ k=d+1 k Γ (k + b 2 ) Γ (k + b 2 + α 2 ) = α 2 1 + α 1 (2b 1 -1) + b 1 (b 1 -1) (α 1 -2)(α 1 -1) Γ (b 1 + 1) Γ (α 1 + b 1 + 1) (16)
- Attachment function f : For the computation of the attachment function, we have to distinguish two cases:

α 2 1 (d + 1) + α 1 (b 1 (d + 2) + d 2 -1) + b 1 (b 1 -1) -d(d + 1) (α 1 -2)(α 1 -1) Γ (b 1 + d + 1) Γ (α 1 + b 1 + d + 1) + γ α 2 2 (d + 1) + α 2 (b 2 (d + 2) + d 2 -1) + b 2 (b 2 -1) -d(d + 1) (α 2 -2)(α 2 -1) Γ (b 2 + d + 1) Γ (α 2 + b 2 + d + 1)
Case 1: i ≥ d f (i) = Γ (i + b 2 + α 2 ) Γ (i + b 2 ) 1 α 2 -1 Γ (i + b 2 + 1) Γ (i + b 2 + α 2 ) = 1 α 2 -1 i + b 2 α 2 -1 (17)
We find a linear attachment function: indeed for i > d, we only take into account the second power-law, hence we expect to find the same result than in section 4.1.

Case 2: i < d

f (i) = Γ (i + b 1 + α 1 ) Γ (i + b 1 ) d k=i+1 Γ (k + b 1 ) Γ (k + b 1 + α 1 ) + γ ∞ k=d+1 Γ (k + b 2 ) Γ (k + b 2 + α 2 ) = i + b 1 α 1 -1 + Γ (i + b 1 + α 1 )Γ (d + b 1 ) Γ (i + b 1 )Γ (d + b 1 + α 1 ) b 2 + d α 2 -1 - b 1 + d α 1 -1 (18)
In this second case, we have a linear part, in addition to a more complicated part. Note that, for (α 1 , b 1 ) = (α 2 , b 2 ), i.e., when the two power-laws are equals, this second term vanishes, letting as expected only the linear part. Figure 2a shows the shape of f . We see that, while the second part is linear as discussed before, the first part is sub-linear.

We used this attachment function to build a network using our model. The DD is shown in Figure 2b: we see we built a random network with a broken power-law distribution as wanted.

Real degree distributions

The model can also be applied to an empirical DD. Indeed, we observe in Theorem 1 that f (i) only depends on the values P (i) which can be arbitrary, that is not following any classical function. This is a good way to model random networks with an atypical DD. As an example, we apply our model on the DD of an undirected version of Twitter, shown as having atypical behavior due to the Twitter policies. We start with a presentation of this DD, then apply our model to build a random graph with this distribution.

Undirected DD of Twitter

For this study, we use a Twitter snapshot from 2012, recovered by Gabielkov and Legout [START_REF] Gabielkov | The complete picture of the twitter social graph[END_REF] and made available by the authors. This network contains 505 million nodes and 23 billion edges, making it one of the biggest social graph available nowadays. Each node corresponds to an account, and an arc (u, v) exists if the account u follows the account v. The in-and out-DDs are presented in [START_REF] Trolliet | Interest clustering coefficient: a new metric for directed networks like twitter[END_REF].

In our case, we look at an undirected version of the Twitter snapshot. We consider the degree of each node as being the sum of its in-and out-degrees. The distribution of this undirected graph is presented in Figure 3a. We notice two spikes, around d = 20 and d = 2000. We do not know the reason of the first one (which could be social, or due to recommendation system). The second spike is explained by a specificity of Twitter: until 2015, to avoid bots which were following a very large number of users, Twitter limited the number of possible followings to max(2000, number of followers). In other words, a user is allowed to follow more than 2000 people only if he is also followed by more than 2000 people. This leads to a lot of accounts with around 2000 followings. This highlights the fact that some networks have their own specificities, sometimes due to intern policies, which cannot be modeled but by a model specifically built for them.

Modelization

Figure 3c presents the obtained form of the attachment function f computed using Equation 1 with the DD of Twitter. We notice that the overall function is mainly increasing, showing that nodes of higher degrees have a higher chance to connect with new nodes, like in classical preferential attachment models. We also notice two drops, around 20 and 2000. They are associated with the risings on the DD on the same degrees: to increase the amount of nodes with those degrees, the attachment function has to be smaller, so nodes with this degree have less chance to gain new edges.

We finally use our model with the empirical attachment function of Figure 3c. Note that, in an empirical study, P can be equal to zero for some degrees, for which no node has this degree in the network. In Twitter, the smallest of those degrees occurs around 18.000. In that case, f cannot be computed. To get around this difficulty, we interpolate the missing values of P , using the two closest smaller and bigger degrees of the missing points. Since we observe the probability distribution on a log-log scale, we interpolate between the two points as a straight line on a log-log scale, i.e., as a power-law function. We believe this is a fair choice since we only look at the tail of the distribution, which looks like a straight line, and since we interpolate between each pair of closest two points only, instead of fitting on the whole tail of the distribution.

The DD of a random network built with our model is presented in Figure 3b. For time computation reasons, the built network only has N = 2 • 10 5 nodes, to be compared to the 5 • 10 8 nodes of Twitter. However, it is enough to verify that its DD shape follows the one of the real Twitter's DD: in particular we recognize the spikes around d = 20 and d = 2000.

Conclusion

In this paper, we proposed a new random growth model picking the nodes to be connected together in the graph with a flexible probability f . We expressed this f as a function of any distribution P , leading to the possibility to build a random network with any wanted degree distribution. We computed f for some classical distributions, as much as for a snapshot of Twitter of 505 million nodes and 23 billion edges. We believe this model is useful for anyone studying networks with atypical degree distributions, regardless of the domain. If the presented model is undirected, we also believe a directed version of it, based on the Bollobás et al. model [START_REF] Bollobás | Directed scale-free graphs[END_REF], can be easily generalized from the presented one.

  t→+∞ b t = b > 0, and lim t→+∞ c t = c. Then lim t→+∞ at t exists and equals c 1+b .

Fig. 2 :

 2 Fig. 2: Theoretical attachment function f and degree distribution of a random network for the broken power-law distribution. Parameters are N = 5 • 10 5 , b 1 = b 2 = 1, α 1 = 2.1, α 2 = 4 and d = 100.

  (a) DD of the Twitter's undirected network.

#

  Nodes with this degree (b) DD of a random network with 8 • 10 5 nodes using the attachment function of Figure 3c.

  Attachment function f resulting from the undirected DD of Twitter.

Fig. 3 :

 3 Fig. 3: Modelization of the undirected Twitter's graph.

Table 1 :

 1 Attachment functions f and conditions on p for some classical probability distributions P . ζ(s) is the Riemann zeta function, ζ(s, q) the Hurwitz zeta function, and γ(a, x) is the lower incomplete Gamma function.

4.2 Broken Power-lawWe now study the case of a broken power-law, corresponding to the DD of real world complex networks, as discussed in Section 2. which was the one we were interested in initially. We consider a distribution of the form:P (i) = C Γ (i+b1) Γ (i+b1+α1) if i ≤ d Cγ Γ (i+b2) Γ (i+b2+α2) if i > d(13)where d, b 1 , α 1 , b 2 , and α 2 are parameters of our distribution such that α 1 > 2, α 2 > 2, C a normalisation constant, and γ chosen in order to obtain continuity for i = d. As seen in section 4.1, the ratio of gamma functions is close to a power-law as soon as i gets large. Hence, this distribution corresponds to two powers-laws, with different slopes, and a switch between the two at the value d.We can easily find the continuity constant γ, since it verifies:Γ (d + b 1 ) Γ (d + b 1 + α 1 ) = γ Γ (d + b 2 )

This work has been supported by the French government through the UCA JEDI (ANR-15-IDEX-01) and EUR DS4H (ANR-17-EURE-004) Investments in the Future projects, by the SNIF project, and by Inria associated team EfDyNet. 3 We call a broken power-law a concatenation of two power-laws, as defined in [14].