Listing all triangles is a fundamental graph operation. Triangles can have important interpretations in real-world graphs, especially social and other interaction networks. Despite the lack of provably efficient (linear, or slightly super-linear) worst-case algorithms for this problem, practitioners run simple, efficient heuristics to find all triangles in graphs with millions of vertices. How are these heuristics exploiting the structure of these special graphs to provide major speedups in running time? We study one of the most prevalent algorithms used by practitioners. A trivial algorithm enumerates all paths of length @math , and checks if each such path is incident to a triangle. A good heuristic is to enumerate only those paths of length @math where the middle vertex has the lowest degree. It is easily implemented and is empirically known to give remarkable speedups over the trivial algorithm. We study the behavior of this algorithm over graphs with heavy-tailed degree distributions, a defining feature of real-world graphs. The erased configuration model (ECM) efficiently generates a graph with asymptotically (almost) any desired degree sequence. We show that the expected running time of this algorithm over the distribution of graphs created by the ECM is controlled by the @math -norm of the degree sequence. Norms of the degree sequence are a measure of the heaviness of the tail, and it is precisely this feature that allows non-trivial speedups of simple triangle enumeration algorithms. As a corollary of our main theorem, we prove expected linear-time performance for degree sequences following a power law with exponent @math , and non-trivial speedup whenever @math .
Configuration models for generating random graphs with given degree sequences have a long history. Bender and Canfield @cite_21 study this model for counting graphs with a given degree sequence. Wormald @cite_5 looks at the connectivity of these graphs. Molloy and Reed @cite_9 @cite_20 study various properties like the largest connected component of this graph distribution. Physicists studying complex networks have also paid attention to this model @cite_40 . Britton, Deijfen, and Martin-L " o f @cite_3 show that the simple graph generated by the ECM asymptotically matches the desired degree sequence. Aiello, Chung, and Lu @cite_10 give a model for power-law graphs, where edge @math are independent inserted with probability @math . This was studied for more general degree sequences in subsequent work by Chung, Lu, and Vu @cite_27 @cite_28 . Mihail and Papadimitriou @cite_15 independently discuss this model. Most of this work focused on eigenvalues and average distances in these graphs. Newman @cite_26 gives an excellent survey of these models, their similarities, and applications.
@cite_26 @cite_28 @cite_9 @cite_21 @cite_3 @cite_40 @cite_27 @cite_5 @cite_15 @cite_10 @cite_20
1978479505 2138359578 2012184276 2169015768
Random graphs with a given degree sequence are a useful model capturing several features absent in the classical Erd˝os-Renyi model, such as dependent edges and non-binomial degrees. In this paper, we use a characterization due to Erd˝os and Gallai to develop a sequential algorithm for generating a random labeled graph with a given degree sequence. The algorithm is easy to implement and allows surprisingly ecient sequential importance sampling. Applications are given, in- cluding simulating a biological network and estimating the number of graphs with a given degree sequence. 1. Introduction. Random graphs with given vertex degrees have recently attracted great interest as a model for many real-world complex networks, including the World Wide Web, peer-to-peer networks, social networks, and biological networks. Newman (58) contains an excellent survey of these networks, with extensive references. A common approach to simulating these systems is to study (empirically or theoretically) the degrees of the vertices in instances of the network, and then to generate a random graph with the appropriate degrees. Graphs with prescribed degrees also appear in random matrix theory and string theory, which can call for large simulations based on random k-regular graphs. Throughout, we are concerned with generating simple graphs, i.e., no loops or multiple edges are allowed (the problem becomes considerably easier if loops and multiple edges are allowed). The main result of this paper is a new sequential importance sampling algorithm for generating random graphs with a given degree sequence. The idea is to build up the graph sequentially, at each stage choosing an edge from a list of candidates with probability proportional to the degrees. Most previously studied algorithms for this problem sometimes either get stuck or produce loops or multiple edges in the output, which is handled by starting over and trying again. Often for such algorithms, the probability of a restart being needed on a trial rapidly approaches 1 as the degree parameters grow, resulting in an enormous number of trials being needed on average to obtain a simple graph. A major advantage of our algorithm is that it never gets stuck. This is achieved using the Erd˝os- Gallai characterization, which is explained in Section 2, and a carefully chosen order of edge selection. 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 Consider the random graph models G(n, #edges = M) and G(n, Prob(edge) = p) with M = M(n) = (1 + )n-1 3)n 2 and p = p(n) = (1 +An-1 3) n . For 1 > -1 define an i-component of a random graph as a component which has exactly I more edges than vertices. Call an i-component with I > 1 a complex component. For both models, we show that when A is constant, the expected number of complex components is bounded, almost surely (a.s.) each of these components (if any exist) has size of order n2 3, and the maximum value of I is bounded in probability. We prove that a.s. the largest suspended tree in each complex component has size of order n2 3, and deletion of all suspended trees results in a "smoothed" graph of size of order n 3, with the maximum vertex degree 3. The total number of branching vertices, i.e., of degree 3, is bounded in probability. Thus, each complex component is almost surely topologically equivalent to a 3-regular multigraph of a uniformly bounded size. Lengths of the shortest cycle and of the shortest path between two branching vertices of a smoothed graph are each of order n 3. We find a relatively simple integral formula for the limit distribution of the numbers of complex components, which implies, in particular, that all values of the "complexity spectrum" have positive limiting probabilities. We also answer questions raised by Erdos and Renyi back in 1960. It is proven that there exists p(A), the limiting planarity probability, with 0 < p(A) < 1, p(-oo) = 1, p(oo) = 0. In particular, G(n, M) (G(n, p), resp.) is almost surely nonplanar iff (M n 2)n-213 -* 00 ((np I)n-1 3) -+ oo, resp.). Recent work on the structure of social networks and the internet has focused attention on graphs with distributions of vertex degree that are significantly different from the Poisson degree distributions that have been widely studied in the past. In this paper we develop in detail the theory of random graphs with arbitrary degree distributions. In addition to simple undirected, unipartite graphs, we examine the properties of directed and bipartite graphs. Among other results, we derive exact expressions for the position of the phase transition at which a giant component first forms, the mean component size, the size of the giant component if there is one, the mean number of vertices a certain distance away from a randomly chosen vertex, and the average vertex-vertex distance within a graph. We apply our theory to some real-world graphs, including the worldwide web and collaboration graphs of scientists and Fortune 1000 company directors. We demonstrate that in some cases random graphs with appropriate distributions of vertex degree predict with surprising accuracy the behavior of the real world, while in others there is a measurable discrepancy between theory and reality, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph.