Graphs are used to model interactions in a variety of contexts, and there is a growing need to quickly assess the structure of a graph. Some of the most useful graph metrics, especially those measuring social cohesion, are based on triangles. Despite the importance of these triadic measures, associated algorithms can be extremely expensive. We propose a new method based on wedge sampling. This versatile technique allows for the fast and accurate approximation of all current variants of clustering coefficients and enables rapid uniform sampling of the triangles of a graph. Our methods come with provable and practical time-approximation tradeoffs for all computations. We provide extensive results that show our methods are orders of magnitude faster than the state-of-the-art, while providing nearly the accuracy of full enumeration. Our results will enable more wide-scale adoption of triadic measures for analysis of extremely large graphs, as demonstrated on several real-world examples.
Most relevant to our work are sampling mechanisms. @cite_9 started the use of sparsification methods, the most important of which is Doulion @cite_3 . This method sparsifies the graph by keeping each edge with probability @math ; counts the triangles in the sparsified graph; and multiplies this count by @math to predict the number of triangles in the original graph. Various theoretical analyses of this algorithm (and its variants) have been proposed @cite_1 @cite_5 @cite_12 . One of the main benefits of Doulion is that it reduces large graphs to smaller ones that can be loaded into memory. However, their estimate can suffer from high variance @cite_2 . Alternative sampling mechanisms have been proposed for streaming and semi-streaming algorithms @cite_24 @cite_31 @cite_8 @cite_30 .
@cite_30 @cite_8 @cite_9 @cite_1 @cite_3 @cite_24 @cite_2 @cite_5 @cite_31 @cite_12
2112090702 1542957328 2158432527 2002576896 89448491 2050137450 2002205566
Networks of coupled dynamical systems have been used to model biological oscillators1,2,3,4, Josephson junction arrays5,6, excitable media7, neural networks8,9,10, spatial games11, genetic control networks12 and many other self-organizing systems. Ordinarily, the connection topology is assumed to be either completely regular or completely random. But many biological, technological and social networks lie somewhere between these two extremes. Here we explore simple models of networks that can be tuned through this middle ground: regular networks ‘rewired’ to introduce increasing amounts of disorder. We find that these systems can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs. We call them ‘small-world’ networks, by analogy with the small-world phenomenon13,14 (popularly known as six degrees of separation15). The neural network of the worm Caenorhabditis elegans, the power grid of the western United States, and the collaboration graph of film actors are shown to be small-world networks. Models of dynamical systems with small-world coupling display enhanced signal-propagation speed, computational power, and synchronizability. In particular, infectious diseases spread more easily in small-world networks than in regular lattices. In this paper we present an efficient triangle counting algorithm which can be adapted to the semistreaming model [12]. The key idea of our algorithm is to combine the sampling algorithm of [31,32] and the partitioning of the set of vertices into a high degree and a low degree subset respectively as in [1], treating each set appropriately. We obtain a running time (O ( m + m^ 3 2 n t ^2 ) ) and an e approximation (multiplicative error), where n is the number of vertices, m the number of edges and Δ the maximum number of triangles an edge is contained. Furthermore, we show how this algorithm can be adapted to the semistreaming model with space usage (O (m^ 1 2 n + m^ 3 2 n t ^2 ) ) and a constant number of passes (three) over the graph stream. We apply our methods in various networks with several millions of edges and we obtain excellent results. Finally, we propose a random projection based method for triangle counting and provide a sufficient condition to obtain an estimate with low variance. Counting the number of triangles in a graph is a beautiful algorithmic problem which has gained importance over the last years due to its significant role in complex network analysis. Metrics frequently computed such as the clustering coefficient and the transitivity ratio involve the execution of a triangle counting algorithm. Furthermore, several interesting graph mining applications rely on computing the number of triangles in the graph of interest. In this paper, we focus on the problem of counting triangles in a graph. We propose a practical method, out of which all triangle counting algorithms can potentially benefit. Using a straightforward triangle counting algorithm as a black box, we performed 166 experiments on real-world networks and on synthetic datasets as well, where we show that our method works with high accuracy, typically more than 99 and gives significant speedups, resulting in even ≈ 130 times faster performance. We introduce reductions in the streaming model as a tool in the design of streaming algorithms. We develop the concept of list-efficient streaming algorithms that are essential to the design of efficient streaming algorithms through reductions.Our results include a suite of list-efficient streaming algorithms for basic statistical primitives. Using the reduction paradigm along with these tools, we design streaming algorithms for approximately counting the number of triangles in a graph presented as a stream.A specific highlight of our work is the first algorithm for the number of distinct elements in a data stream that achieves arbitrary approximation factors. (Independently, Trevisan [Tre01] has solved this problem via a different approach; our algorithm has the advantage of being list-efficient.) The problem of counting the number of triangles in a graph has gained importance in the last few years due to its importance in many data mining applications. Recently, Tsourkakis, et al proposed DOULION, which is based on a simple sampling idea but works very well on many of the important graphs. In this preliminary report, we show that DOULION may not be very correct on special cases of graphs and argue that it may not fulfill the main purpose of the triangle counting problem for real-world graphs. We then present improvements on DOULION and show that it works better, much better in some cases, than DOULION. Modern search engines answer keyword-based queries extremely efficiently. The impressive speed is due to clever inverted index structures, caching, a domain-independent knowledge of strings, and thousands of machines. Several research efforts have attempted to generalize keyword search to keytree and keygraph searching, because trees and graphs have many applications in next-generation database systems. This paper surveys both algorithms and applications, giving some emphasis to our own work. In this note we introduce a new randomized algorithm for counting triangles in graphs. We show that under mild conditions, the estimate of our algorithm is strongly concentrated around the true number of triangles. Specifically, let G be a graph with n vertices, t triangles and let @D be the maximum number of triangles an edge of G is contained in. Our randomized algorithm colors the vertices of G with N=1 p colors uniformly at random, counts monochromatic triangles, i.e., triangles whose vertices have the same color, and scales that count appropriately. We show that if p>=max(@Dlognt,lognt) then for any constant @e>0 our unbiased estimate T is concentrated around its expectation, i.e., Pr[|T-E[T]|>=@eE[T]]=o(1). Finally, our algorithm is amenable to being parallelized. We present a simple MapReduce implementation of our algorithm.