text: 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 .
  @cite_26: Inspired by empirical studies of networked systems such as the Internet, social networks, and biological networks, researchers have in recent years developed a variety of techniques and models to help us understand or predict the behavior of these systems. Here we review developments in this field, including such concepts as the small-world effect, degree distributions, clustering, network correlations, random graph models, models of network growth and preferential attachment, and dynamical processes taking place on networks.
  @cite_28: Many graphs arising in various information networks exhibit the "power law" behavior — the number of vertices of degree k is proportional to k −β for some positive β. We show that if β > 2.5, the largest eigenvalue of a random power law graph is almost surely (1+ o(1)) √ m where m is the maximum degree. Moreover, the k largest eigenvalues of a random power law graph with exponent β have power law distribution with exponent 2β − 1 if the maximum degree is sufficiently large, where k is a function depending on β, m and d, the average degree. When 2< β < 2.5, the largest eigenvalue is heavily concentrated at cm 3−β for some constant c depending on β and the average degree. This result follows from a more general theorem which shows that the largest eigenvalue of a random graph with a given expected degree sequence is determined by m, the maximum degree, and ˜ d, the weighted average of the squares of the expected degrees. We show that the k-th largest eigenvalue is almost surely (1+ o(1)) √ m k where mk is the k-th largest expected degree provided mk is large enough. These results have implications on the usage of spectral techniques in many areas related to pattern detection and information retrieval.
  @cite_9: Given a sequence of nonnegative real numbers λ0, λ1… which sum to 1, we consider random graphs having approximately λi n vertices of degree i. Essentially, we show that if Σ i(i - 2)λi > 0, then such graphs almost surely have a giant component, while if Σ i(i -2)λ. < 0, then almost surely all components in such graphs are small. We can apply these results to Gn,p,Gn.M, and other well-known models of random graphs. There are also applications related to the chromatic number of sparse random graphs. © 1995 Wiley Periodicals, Inc.
  @cite_21: Abstract Asymptotics are obtained for the number of n × n symmetric non-negative integer matrices subject to the following constraints: (i) each row sum is specified and bounded, (ii) the entries are bounded, and (iii) a specified “sparse” set of entries must be zero. The result can be interpreted in terms of incidence matrices for labeled graphs.
  @cite_3: Let F be a probability distribution with support on the non-negative integers. Four methods for generating a simple undirected graph with (approximate) degree distribution F are described and compared. Two methods are based on the so called configuration model with modifications ensuring a simple graph, one method is an extension of the classical Erdos-Renyi graph where the edge probabilities are random variables, and the last method starts with a directed random graph which is then modified to a simple undirected graph. All methods are shown to give the correct distribution in the limit of large graph size, but under different assumptions on the degree distribution F and also using different order of operations.
  @cite_40: 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.
  @cite_27: Abstract Random graph theory is used to examine the “small-world phenomenon”; any two strangers are connected through a short chain of mutual acquaintances. We will show that for certain families of random graphs with given expected degrees the average distance is almost surely of order log n log d, where d is the weighted average of the sum of squares of the expected degrees. Of particular interest are power law random graphs in which the number of vertices of degree k is proportional to 1 kβ for some fixed exponent β. For the case of β > 3, we prove that the average distance of the power law graphs is almost surely of order log n log d. However, many Internet, social, and citation networks are power law graphs with exponents in the range 2 < β < 3 for which the power law random graphs have average distance almost surely of order log log n, but have diameter of order log n (provided having some mild constraints for the average distance and maximum degree). In particular, these graphs contain a dense subgraph, which we call the core, having nc log log n vertices. Almost all vertices are within distance log log n of the core although there are vertices at distance log n from the core.
  @cite_5: It is shown that almost all labelled r -regular graphs are r -connected, for any fixed r ≥3. This is an instance of a more general result which applies to labelled locally restricted graphs whose points have degrees lying between r and R , where r and R are fixed, 3≤ r ≤ R . The proof employs a known asymptotic formula for the numbers of these locally restricted graphs. It is also demonstrated that for fixed k >0 and r ≥3, almost all labelled r -regular graphs with girth at least [ k ( r −2)] are cyclically k -connected. This provides an asymptotic formula for the number of labelled cyclically k -connected r -regular graphs with p points, for fixed k and r .
  @cite_15: We show that the largest eigenvalues of graphs whose highest degrees are Zipf-like distributed with slope a are distributed according to a power law with slope α 2. This follows as a direct and almost certain corollary of the degree power law. Our result has implications for the singular value decomposition method in information retrieval.
  @cite_10: We propose a random graph model which is a special case of sparserandom graphs with given degree sequences which satisfy a power law. This model involves only a small number of paramo eters, called logsize and log-log growth rate. These parameters capture some universal characteristics of massive graphs. From these parameters, various properties of the graph can be derived. For example, for certai n ranges of the parameters, we wi II compute the expected distribution of the sizes of the connected components which almost surely occur with high probability. We illustrate the consistency of our model with the behavior of some massive graphs derived from data in telecommunications. We also discuss the threshold function, the giant component, and the evolution of random graphs in this model.
  @cite_20: 
summary: 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.