			Home About us Contact

Random Graph (random + graph)

Distribution by Scientific Domains

Mathematics and Statistics	97%

Selected Abstracts

Uncountable graphs and invariant measures on the set of universal countable graphs

RANDOM STRUCTURES AND ALGORITHMS, Issue 3 2010
Fedor Petrov
Abstract We give new examples and describe the complete lists of all measures on the set of countable homogeneous universal graphs and Ks -free homogeneous universal graphs (for s , 3) that are invariant with respect to the group of all permutations of the vertices. Such measures can be regarded as random graphs (respectively, random Ks -free graphs). The well-known example of Erdös,Rényi (ER) of the random graph corresponds to the Bernoulli measure on the set of adjacency matrices. For the case of the universal Ks -free graphs there were no previously known examples of the invariant measures on the space of such graphs. The main idea of our construction is based on the new notions of measurable universal, and topologically universal graphs, which are interesting themselves. The realization of the construction can be regarded as two-step randomization for universal measurable graph : "randomization in vertices" and "randomization in edges." For Ks -free, s , 3, there is only randomization in vertices of the measurable graphs. The completeness of our lists is proved using the important theorem by Aldous about S, -invariant matrices, which we reformulate in appropriate way. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010 [source]

Continuum limits for classical sequential growth models

RANDOM STRUCTURES AND ALGORITHMS, Issue 2 2010
Graham Brightwell
Abstract A random graph order, also known as a transitive percolation process, is defined by taking a random graph on the vertex set {0,,,n , 1} and putting i below j if there is a path i = i1,ik = j in the graph with i1 < , < ik. Rideout and Sorkin Phys. Rev. D 63 (2001) 104011 provide computational evidence that suitably normalized sequences of random graph orders have a "continuum limit." We confirm that this is the case and show that the continuum limit is always a semiorder. Transitive percolation processes are a special case of a more general class called classical sequential growth models. We give a number of results describing the large-scale structure of a general classical sequential growth model. We show that for any sufficiently large n, and any classical sequential growth model, there is a semiorder S on {0,,,n - 1} such that the random partial order on {0,,,n - 1} generated according to the model differs from S on an arbitrarily small proportion of pairs. We also show that, if any sequence of classical sequential growth models has a continuum limit, then this limit is (essentially) a semiorder. We give some examples of continuum limits that can occur. Classical sequential growth models were introduced as the only models satisfying certain properties making them suitable as discrete models for spacetime. Our results indicate that this class of models does not contain any that are good approximations to Minkowski space in any dimension , 2. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010 [source]

Random dense bipartite graphs and directed graphs with specified degrees

RANDOM STRUCTURES AND ALGORITHMS, Issue 2 2009
Catherine Greenhill
Abstract Let s and t be vectors of positive integers with the same sum. We study the uniform distribution on the space of simple bipartite graphs with degree sequence s in one part and t in the other; equivalently, binary matrices with row sums s and column sums t. In particular, we find precise formulae for the probabilities that a given bipartite graph is edge-disjoint from, a subgraph of, or an induced subgraph of a random graph in the class. We also give similar formulae for the uniform distribution on the set of simple directed graphs with out-degrees s and in-degrees t. In each case, the graphs or digraphs are required to be sufficiently dense, with the degrees varying within certain limits, and the subgraphs are required to be sufficiently sparse. Previous results were restricted to spaces of sparse graphs. Our theorems are based on an enumeration of bipartite graphs avoiding a given set of edges, proved by multidimensional complex integration. As a sample application, we determine the expected permanent of a random binary matrix with row sums s and column sums t. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 [source]

Corrigendum: The cover time of the giant component of a random graph, Random Structures and Algorithms 32 (2008), 401,439

RANDOM STRUCTURES AND ALGORITHMS, Issue 2 2009
Colin Cooper
Abstract The above paper gives an asymptotically precise estimate of the cover time of the giant component of a sparse random graph. The proof as it stands is not tight enough, and in particular, Eq. (64) is not strong enough to prove (65). The o(1) term in (64) needs to be improved to o(1/(lnn)2) for (65) to follow. The following section, which replaces Section 3.6, amends this oversight. The notation and definitions are from the paper. A further correction is needed. Property P2 claims that the conductance of the giant is whp, ,(1/lnn). The proof of P2 in the appendix of the paper is not quite complete. A complete proof of Property P2 can be found in 1,2. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009 [source]

The evolution of the mixing rate of a simple random walk on the giant component of a random graph

RANDOM STRUCTURES AND ALGORITHMS, Issue 1 2008
N. Fountoulakis
Abstract In this article we present a study of the mixing time of a random walk on the largest component of a supercritical random graph, also known as the giant component. We identify local obstructions that slow down the random walk, when the average degree d is at most O(), proving that the mixing time in this case is ,((n/d)2) asymptotically almost surely. As the average degree grows these become negligible and it is the diameter of the largest component that takes over, yielding mixing time ,(n/d) a.a.s.. We proved these results during the 2003,04 academic year. Similar results but for constant d were later proved independently by Benjamini et al. in 3. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 [source]

What is the furthest graph from a hereditary property?

RANDOM STRUCTURES AND ALGORITHMS, Issue 1 2008
Noga Alon
Abstract For a graph property P, the edit distance of a graph G from P, denoted EP(G), is the minimum number of edge modifications (additions or deletions) one needs to apply to G to turn it into a graph satisfying P. What is the furthest graph on n vertices from P and what is the largest possible edit distance from P? Denote this maximal distance by ed(n,P). This question is motivated by algorithmic edge-modification problems, in which one wishes to find or approximate the value of EP(G) given an input graph G. A monotone graph property is closed under removal of edges and vertices. Trivially, for any monotone property, the largest edit distance is attained by a complete graph. We show that this is a simple instance of a much broader phenomenon. A hereditary graph property is closed under removal of vertices. We prove that for any hereditary graph property P, a random graph with an edge density that depends on P essentially achieves the maximal distance from P, that is: ed(n,P) = EP(G(n,p(P))) + o(n2) with high probability. The proofs combine several tools, including strengthened versions of the Szemerédi regularity lemma, properties of random graphs and probabilistic arguments. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 [source]

Large-deviations/thermodynamic approach to percolation on the complete graph

RANDOM STRUCTURES AND ALGORITHMS, Issue 3 2007
Marek Biskup
Abstract We present a large-deviations/thermodynamic approach to the classic problem of percolation on the complete graph. Specifically, we determine the large-deviation rate function for the probability that the giant component occupies a fixed fraction of the graph while all other components are "small." One consequence is an immediate derivation of the "cavity" formula for the fraction of vertices in the giant component. As a byproduct of our analysis we compute the large-deviation rate functions for the probability of the event that the random graph is connected, the event that it contains no cycles and the event that it contains only small components. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007 [source]

The phase transition in inhomogeneous random graphs

RANDOM STRUCTURES AND ALGORITHMS, Issue 1 2007
Béla Bollobás
Abstract The "classical" random graph models, in particular G(n,p), are "homogeneous," in the sense that the degrees (for example) tend to be concentrated around a typical value. Many graphs arising in the real world do not have this property, having, for example, power-law degree distributions. Thus there has been a lot of recent interest in defining and studying "inhomogeneous" random graph models. One of the most studied properties of these new models is their "robustness", or, equivalently, the "phase transition" as an edge density parameter is varied. For G(n,p), p = c/n, the phase transition at c = 1 has been a central topic in the study of random graphs for well over 40 years. Many of the new inhomogeneous models are rather complicated; although there are exceptions, in most cases precise questions such as determining exactly the critical point of the phase transition are approachable only when there is independence between the edges. Fortunately, some models studied have this property already, and others can be approximated by models with independence. Here we introduce a very general model of an inhomogeneous random graph with (conditional) independence between the edges, which scales so that the number of edges is linear in the number of vertices. This scaling corresponds to the p = c/n scaling for G(n,p) used to study the phase transition; also, it seems to be a property of many large real-world graphs. Our model includes as special cases many models previously studied. We show that, under one very weak assumption (that the expected number of edges is "what it should be"), many properties of the model can be determined, in particular the critical point of the phase transition, and the size of the giant component above the transition. We do this by relating our random graphs to branching processes, which are much easier to analyze. We also consider other properties of the model, showing, for example, that when there is a giant component, it is "stable": for a typical random graph, no matter how we add or delete o(n) edges, the size of the giant component does not change by more than o(n). © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 31, 3,122, 2007 [source]

The phase transition in the cluster-scaled model of a random graph

RANDOM STRUCTURES AND ALGORITHMS, Issue 2 2006
Malwina Luczak
Abstract For 0 < p < 1 and q > 0 let Gq(n,p) denote the random graph with vertex set [n]={1,,,n} such that, for each graph G on [n] with e(G) edges and c(G) components, the probability that Gq(n,p)=G is proportional to . The first systematic study of Gq(n,p) was undertaken by Bollobás, Grimmett, and Janson (Probab Theory Relat Fields 104 (1996), 283,317), who analyzed the phase transition phenomenon corresponding to the emergence of the giant component. In this paper we describe the structure of Gq(n,p) very close the critical threshold. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006 [source]

Maximum weight independent sets and matchings in sparse random graphs.

RANDOM STRUCTURES AND ALGORITHMS, Issue 1 2006
Exact results using the local weak convergence method
Let G(n,c/n) and Gr(n) be an n -node sparse random graph and a sparse random r -regular graph, respectively, and let I(n,r) and I(n,c) be the sizes of the largest independent set in G(n,c/n) and Gr(n). The asymptotic value of I(n,c)/n as n , ,, can be computed using the Karp-Sipser algorithm when c , e. For random cubic graphs, r = 3, it is only known that .432 , lim infnI(n,3)/n , lim supnI(n,3)/n , .4591 with high probability (w.h.p.) as n , ,, as shown in Frieze and Suen [Random Structures Algorithms 5 (1994), 649,664] and Bollabas [European J Combin 1 (1980), 311,316], respectively. In this paper we assume in addition that the nodes of the graph are equipped with nonnegative weights, independently generated according to some common distribution, and we consider instead the maximum weight of an independent set. Surprisingly, we discover that for certain weight distributions, the limit limnI(n,c)/n can be computed exactly even when c > e, and limnI(n,r)/n can be computed exactly for some r , 1. For example, when the weights are exponentially distributed with parameter 1, limnI(n,2e)/n , .5517, and limnI(n,3)/n , .6077. Our results are established using the recently developed local weak convergence method further reduced to a certain local optimality property exhibited by the models we consider. We extend our results to maximum weight matchings in G(n,c/n) and Gr(n). For the case of exponential distributions, we compute the corresponding limits for every c > 0 and every r , 2. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006 [source]

Distances in random graphs with finite variance degrees

RANDOM STRUCTURES AND ALGORITHMS, Issue 1 2005
Remco van der Hofstad
In this paper we study a random graph with N nodes, where node j has degree Dj and {Dj} are i.i.d. with ,(Dj , x) = F(x). We assume that 1 , F(x) , cx,,+1 for some , > 3 and some constant c > 0. This graph model is a variant of the so-called configuration model, and includes heavy tail degrees with finite variance. The minimal number of edges between two arbitrary connected nodes, also known as the graph distance or the hopcount, is investigated when N , ,. We prove that the graph distance grows like log,N, when the base of the logarithm equals , = ,,[Dj(Dj , 1)]/,,[Dj] > 1. This confirms the heuristic argument of Newman, Strogatz, and Watts [Phys Rev E 64 (2002), 026118, 1,17]. In addition, the random fluctuations around this asymptotic mean log,N are characterized and shown to be uniformly bounded. In particular, we show convergence in distribution of the centered graph distance along exponentially growing subsequences. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005 [source]

Divide and conquer martingales and the number of triangles in a random graph

RANDOM STRUCTURES AND ALGORITHMS, Issue 2 2004
J. H. Kim
The goal of this paper is to present a novel application of a recent and useful martingale inequality. As an illustration, we prove an essentially sharp bound for the probability that a random graph contains significantly more triangles than expected. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004 [source]

Deviation inequality for monotonic Boolean functions with application to the number of k -cycles in a random graph

RANDOM STRUCTURES AND ALGORITHMS, Issue 1 2004
Dmitry PanchenkoArticle first published online: 31 OCT 200
Using Talagrand's concentration inequality on the discrete cube {0, 1}m we show that given a real-valued function Z(x) on {0, 1}m that satisfies certain monotonicity conditions one can control the deviations of Z(x) above its median by a local Lipschitz norm of Z at the point x. As one application, we obtain a deviation inequality for the number of k -cycles in a random graph. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2004 [source]

Phase transition for Parking blocks, Brownian excursion and coalescence

RANDOM STRUCTURES AND ALGORITHMS, Issue 1 2002
P. Chassaing
Abstract In this paper, we consider hashing with linear probing for a hashing table with m places, n items (n < m), and , = m , n empty places. For a noncomputer science-minded reader, we shall use the metaphore of n cars parking on m places: each car ci chooses a place pi at random, and if pi is occupied, ci tries successively pi + 1, pi + 2, until it finds an empty place. Pittel [42] proves that when ,/m goes to some positive limit , < 1, the size B of the largest block of consecutive cars satisfies 2(, , 1 , log ,)B = 2 log m , 3 log log m + ,m, where ,m converges weakly to an extreme-value distribution. In this paper we examine at which level for n a phase transition occurs between B = o(m) and m , B = o(m). The intermediate case reveals an interesting behavior of sizes of blocks, related to the standard additive coalescent in the same way as the sizes of connected components of the random graph are related to the multiplicative coalescent. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 76,119, 2002 [source]

Vertex-distinguishing edge colorings of random graphs

RANDOM STRUCTURES AND ALGORITHMS, Issue 1 2002
P. N. Balister
A proper edge coloring of a simple graph G is called vertex-distinguishing if no two distinct vertices are incident to the same set of colors. We prove that the minimum number of colors required for a vertex-distinguishing coloring of a random graph of order n is almost always equal to the maximum degree ,(G) of the graph. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 89,97, 2002 [source]

On the connectivity of Bluetooth-based ad hoc networks

CONCURRENCY AND COMPUTATION: PRACTICE & EXPERIENCE, Issue 7 2009
P. Crescenzi
Abstract We study the connectivity properties of a family of random graphs that closely model the Bluetooth's device discovery process, where each device tries to connect to other devices within its visibility range in order to establish reliable communication channels yielding a connected topology. Specifically, we provide both analytical and experimental evidence that when the visibility range of each node (i.e. device) is limited to a vanishing function of n, the total number of nodes in the system, full connectivity can still be achieved with high probability by letting each node connect only to a ,small' number of visible neighbors. Our results extend previous studies, where connectivity properties were analyzed only for the case of a constant visibility range, and provide evidence that Bluetooth can indeed be used for establishing large ad hoc networks. Copyright © 2008 John Wiley & Sons, Ltd. [source]

The 2-dimensional rigidity of certain families of graphs

JOURNAL OF GRAPH THEORY, Issue 2 2007
Bill Jackson
Abstract Laman's characterization of minimally rigid 2-dimensional generic frameworks gives a matroid structure on the edge set of the underlying graph, as was first pointed out and exploited by L. Lovász and Y. Yemini. Global rigidity has only recently been characterized by a combination of two results due to T. Jordán and the first named author, and R. Connelly, respectively. We use these characterizations to investigate how graph theoretic properties such as transitivity, connectivity and regularity influence (2-dimensional generic) rigidity and global rigidity and apply some of these results to reveal rigidity properties of random graphs. In particular, we characterize the globally rigid vertex transitive graphs, and show that a random d -regular graph is asymptotically almost surely globally rigid for all d , 4. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 154,166, 2007 [source]

A branch-and-cut algorithm for partition coloring

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2010
Yuri Frota
Abstract Let G = (V, E, Q) be a undirected graph, where V is the set of vertices, E is the set of edges, and Q = {Q1,,,Qq} is a partition of V into q subsets. We refer to Q1,,,Qq as the components of the partition. The partition coloring problem (PCP) consists of finding a subset V, of V with exactly one vertex from each component Q1,,,Qq and such that the chromatic number of the graph induced in G by V, is minimum. This problem is a generalization of the graph coloring problem. This work presents a branch-and-cut algorithm proposed for PCP. An integer programing formulation and valid inequalities are proposed. A tabu search heuristic is used for providing primal bounds. Computational experiments are reported for random graphs and for PCP instances originating from the problem of routing and wavelength assignment in all-optical WDM networks. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010 [source]

Solving the minimum-weighted coloring problem

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2001
Massimiliano Caramia
Abstract Weighted coloring is a generalization of the well-known vertex (unweighted) coloring for which a number of exact algorithms have been presented in the literature. We are not aware of any optimal method specifically designed for the minimum-weighted coloring problem on arbitrary graphs. Only a few heuristics have been developed with the goal of finding tighter upper bounds for the maximum-weighted clique problem. Moreover, as shown in the paper, a straightforward reduction of a weighted instance into an unweighted one permits us to solve only very small instances. In this paper, we present a branch-and-bound algorithm for the weighted case capable of solving random graphs of up to 90 vertices for any edge density with integer weights uniformly drawn from the range [1, ,,10]. Likewise, we have used properly modified benchmark instances borrowed from vertex coloring as a further test bed for our algorithm. © 2001 John Wiley & Sons, Inc. [source]

Uncountable graphs and invariant measures on the set of universal countable graphs

Asymptotic equivalence and contiguity of some random graphs

RANDOM STRUCTURES AND ALGORITHMS, Issue 1 2010
Svante Janson
Abstract We show that asymptotic equivalence, in a strong form, holds between two random graph models with slightly differing edge probabilities under substantially weaker conditions than what might naively be expected. One application is a simple proof of a recent result by van den Esker, van der Hofstad, and Hooghiemstra on the equivalence between graph distances for some random graph models. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010 [source]

Rapid mixing of Gibbs sampling on graphs that are sparse on average

RANDOM STRUCTURES AND ALGORITHMS, Issue 2 2009
Elchanan Mossel
Abstract Gibbs sampling also known as Glauber dynamics is a popular technique for sampling high dimensional distributions defined on graphs. Of special interest is the behavior of Gibbs sampling on the Erd,s-Rényi random graph G(n,d/n), where each edge is chosen independently with probability d/n and d is fixed. While the average degree in G(n,d/n) is d(1 - o(1)), it contains many nodes of degree of order log n/log log n. The existence of nodes of almost logarithmic degrees implies that for many natural distributions defined on G(n,p) such as uniform coloring (with a constant number of colors) or the Ising model at any fixed inverse temperature ,, the mixing time of Gibbs sampling is at least n1+,(1/log log n). Recall that the Ising model with inverse temperature , defined on a graph G = (V,E) is the distribution over {±}Vgiven by . High degree nodes pose a technical challenge in proving polynomial time mixing of the dynamics for many models including the Ising model and coloring. Almost all known sufficient conditions in terms of , or number of colors needed for rapid mixing of Gibbs samplers are stated in terms of the maximum degree of the underlying graph. In this work, we show that for every d < , and the Ising model defined on G (n, d/n), there exists a ,d > 0, such that for all , < ,d with probability going to 1 as n ,,, the mixing time of the dynamics on G (n, d/n) is polynomial in n. Our results are the first polynomial time mixing results proven for a natural model on G (n, d/n) for d > 1 where the parameters of the model do not depend on n. They also provide a rare example where one can prove a polynomial time mixing of Gibbs sampler in a situation where the actual mixing time is slower than npolylog(n). Our proof exploits in novel ways the local tree like structure of Erd,s-Rényi random graphs, comparison and block dynamics arguments and a recent result of Weitz. Our results extend to much more general families of graphs which are sparse in some average sense and to much more general interactions. In particular, they apply to any graph for which every vertex v of the graph has a neighborhood N(v) of radius O(log n) in which the induced sub-graph is a tree union at most O(log n) edges and where for each simple path in N(v) the sum of the vertex degrees along the path is O(log n). Moreover, our result apply also in the case of arbitrary external fields and provide the first FPRAS for sampling the Ising distribution in this case. We finally present a non Markov Chain algorithm for sampling the distribution which is effective for a wider range of parameters. In particular, for G(n, d/n) it applies for all external fields and , < ,d, where d tanh(,d) = 1 is the critical point for decay of correlation for the Ising model on G(n, d/n). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 [source]

What is the furthest graph from a hereditary property?

The game chromatic number of random graphs

RANDOM STRUCTURES AND ALGORITHMS, Issue 2 2008
Tom Bohman
Given a graph G and an integer k, two players take turns coloring the vertices of G one by one using k colors so that neighboring vertices get different colors. The first player wins iff at the end of the game all the vertices of G are colored. The game chromatic number ,g(G) is the minimum k for which the first player has a winning strategy. In this study, we analyze the asymptotic behavior of this parameter for a random graph Gn,p. We show that with high probability, the game chromatic number of Gn,p is at least twice its chromatic number but, up to a multiplicative constant, has the same order of magnitude. We also study the game chromatic number of random bipartite graphs. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008 [source]

The phase transition in inhomogeneous random graphs

A spectral heuristic for bisecting random graphs,

RANDOM STRUCTURES AND ALGORITHMS, Issue 3 2006
Amin Coja-OghlanArticle first published online: 27 DEC 200
The minimum bisection problem is to partition the vertices of a graph into two classes of equal size so as to minimize the number of crossing edges. Computing a minimum bisection is NP-hard in the worst case. In this paper we study a spectral heuristic for bisecting random graphs Gn(p,p,) with a planted bisection obtained as follows: partition n vertices into two classes of equal size randomly, and then insert edges inside the two classes with probability p, and edges crossing the partition with probability p independently. If , where c0 is a suitable constant, then with probability 1 , o(1) the heuristic finds a minimum bisection of Gn(p,p,) along with a certificate of optimality. Furthermore, we show that the structure of the set of all minimum bisections of Gn(p,p,) undergoes a phase transition as . The spectral heuristic solves instances in the subcritical, the critical, and the supercritical phases of the phase transition optimally with probability 1 , o(1). These results extend previous work of Boppana Proc. 28th FOCS (1987) 280,285. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006 [source]

The degree sequences and spectra of scale-free random graphs

RANDOM STRUCTURES AND ALGORITHMS, Issue 2 2006
Jonathan Jordan
Abstract We investigate the degree sequences of scale-free random graphs. We obtain a formula for the limiting proportion of vertices with degree d, confirming non-rigorous arguments of Dorogovtsev, Mendes, and Samukhin (Phys Rev Lett 85 (2000), 4633). We also consider a generalization of the model with more randomization, proving similar results. Finally, we use our results on the degree sequence to show that for certain values of parameters localized eigenfunctions of the adjacency matrix can be found. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006 [source]

Maximum weight independent sets and matchings in sparse random graphs.

Distances in random graphs with finite variance degrees

On the asymmetry of random regular graphs and random graphs

RANDOM STRUCTURES AND ALGORITHMS, Issue 3-4 2002
Jeong Han Kim
This paper studies the symmetry of random regular graphs and random graphs. Our main result shows that for all 3 , d , n , 4 the random d -regular graph on n vertices almost surely has no nontrivial automorphisms. This answers an open question of N. Wormald [13]. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 216,224, 2002 [source]