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 .
Explicit triangle enumerations have been used for various applications on large graphs. Fudos and Hoffman @cite_30 use triangle enumeration for a graph-based approach for solving systems of geometric constraints. @cite_4 touch every triangle as part of their community detection algorithm for large graphs.
@cite_30 @cite_4
1968546622 1967022297
Triangle-free graphs play a central role in graph theory, and triangle detection (or triangle finding) as well as triangle enumeration (triangle listing) play central roles in the field of graph algorithms. In distributed computing, algorithms with sublinear round complexity for triangle finding and listing have recently been developed in the powerful CONGEST clique model, where communication is allowed between any two nodes of the network. In this paper we present the first algorithms with sublinear complexity for triangle finding and triangle listing in the standard CONGEST model, where the communication topology is the same as the topology of the network. More precisely, we give randomized algorithms for triangle finding and listing with round complexity O(n2 3(log n)2 3) and O(n3 4log n), respectively, where n denotes the number of nodes of the network. We also show a lower bound Ω(n1 3 log n) on the round complexity of triangle listing, which also holds for the CONGEST clique model. Motivated by the need to understand the algorithmic foundations of distributed large-scale graph computations, we study some fundamental graph problems in a message-passing model for distributed computing where @math machines jointly perform computations on graphs with @math nodes (typically, @math ). The input graph is assumed to be initially randomly partitioned among the @math machines. Communication is point-to-point, and the goal is to minimize the number of communication rounds of the computation. We present (almost) tight bounds for the round complexity of two fundamental graph problems, namely PageRank computation and triangle enumeration. Our tight lower bounds, a main contribution of the paper, are established through an information-theoretic approach that relates the round complexity to the minimal amount of information required by machines for correctly solving a problem. Our approach is generic and might be useful in showing lower bounds in the context of similar problems and similar models. We show a lower bound of @math rounds for computing the PageRank. (Notation @math hides a @math factor.) We also present a simple distributed algorithm that computes the PageRank of all the nodes of a graph in @math rounds (notation @math hides a @math factor and an additive @math term). For triangle enumeration, we show a lower bound of @math rounds, where @math is the number of edges of the graph. Our result implies a lower bound of @math for the congested clique, which is tight up to logarithmic factors. We also present a distributed algorithm that enumerates all the triangles of a graph in @math rounds. Listing all triangles in an undirected graph is a fundamental graph primitive with numerous applications. It is trivially solvable in time cubic in the number of vertices. It has seen a significant body of work contributing to both theoretical aspects (e.g., lower and upper bounds on running time, adaption to new computational models) as well as practical aspects (e.g. algorithms tuned for large graphs). Motivated by the fact that the worst-case running time is cubic, we perform a systematic parameterized complexity study of triangle enumeration, providing both positive results (new enumerative kernelizations, “subcubic” parameterized solving algorithms) as well as negative results (uselessness in terms of possibility of “faster” parameterized algorithms of certain parameters such as diameter). 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. In this paper we study the problem of local triangle counting in large graphs. Namely, given a large graph G = (V;E) we want to estimate as accurately as possible the number of triangles incident to every node υ ∈ V in the graph. The problem of computing the global number of triangles in a graph has been considered before, but to our knowledge this is the first paper that addresses the problem of local triangle counting with a focus on the efficiency issues arising in massive graphs. The distribution of the local number of triangles and the related local clustering coefficient can be used in many interesting applications. For example, we show that the measures we compute can help to detect the presence of spamming activity in large-scale Web graphs, as well as to provide useful features to assess content quality in social networks. For computing the local number of triangles we propose two approximation algorithms, which are based on the idea of min-wise independent permutations ( 1998). Our algorithms operate in a semi-streaming fashion, using O(jV j) space in main memory and performing O(log jV j) sequential scans over the edges of the graph. The first algorithm we describe in this paper also uses O(jEj) space in external memory during computation, while the second algorithm uses only main memory. We present the theoretical analysis as well as experimental results in massive graphs demonstrating the practical efficiency of our approach. Vertex coloring is a central concept in graph theory and an important symmetry-breaking primitive in distributed computing. Whereas degree-Δ graphs may require palettes of Δ + 1 colors in the worst case, it is well known that the chromatic number of many natural graph classes can be much smaller. In this paper we give new distributed algorithms to find ( Δ k ) -coloring in graphs of girth 4 (triangle-free graphs), girth 5, and trees. The parameter k can be at most ( 1 4 - o ( 1 ) ) ln ? Δ in triangle-free graphs and at most ( 1 - o ( 1 ) ) ln ? Δ in girth-5 graphs and trees, where o ( 1 ) is a function of Δ. Specifically, for Δ sufficiently large we can find such a coloring in O ( k + log * ? n ) time. Moreover, for any Δ we can compute such colorings in roughly logarithmic time for triangle-free and girth-5 graphs, and in O ( log ? Δ + log Δ ? log ? n ) time on trees. As a byproduct, our algorithm shows that the chromatic number of triangle-free graphs is at most ( 4 + o ( 1 ) ) Δ ln ? Δ , which improves on Jamall's recent bound of ( 67 + o ( 1 ) ) Δ ln ? Δ . Finally, we show that ( Δ + 1 ) -coloring for triangle-free graphs can be obtained in sublogarithmic time for any Δ. We present efficient algorithms for releasing useful statistics about graph data while providing rigorous privacy guarantees. Our algorithms work on datasets that consist of relationships between individuals, such as social ties or email communication. The algorithms satisfy edge differential privacy, which essentially requires that the presence or absence of any particular relationship be hidden. Our algorithms output approximate answers to subgraph counting queries. Given a query graph H, for example, a triangle, k-star, or k-triangle, the goal is to return the number of edge-induced isomorphic copies of H in the input graph. The special case of triangles was considered by [2007] and a more general investigation of arbitrary query graphs was initiated by [2009]. We extend the approach of to a new class of statistics, namely k-star queries. We also give algorithms for k-triangle queries using a different approach based on the higher-order local sensitivity. For the specific graph statistics we consider (i.e., k-stars and k-triangles), we significantly improve on the work of : our algorithms satisfy a stronger notion of privacy that does not rely on the adversary having a particular prior distribution on the data, and add less noise to the answers before releasing them. We evaluate the accuracy of our algorithms both theoretically and empirically, using a variety of real and synthetic datasets. We give explicit, simple conditions under which these algorithms add a small amount of noise. We also provide the average-case analysis in the Erdős-Renyi-Gilbert G(n,p) random graph model. Finally, we give hardness results indicating that the approach used for triangles cannot easily be extended to k-triangles (hence justifying our development of a new algorithmic approach). Triangle counting is an important problem in graph mining with several real-world applications. Interesting metrics, such as the clustering coefficient and the transitivity ratio, involve computing the number of triangles. Furthermore, several interesting graph mining applications rely on computing the number of triangles in a large-scale graph. However, exact triangle counting is expensive and memory consuming, and current approximation algorithms are unsatisfactory and not practical for very large-scale graphs. In this paper we present a new highly-parallel randomized algorithm for approximating the number of triangles in an undirected graph. Our algorithm uses a well-known relation between the number of triangles and the trace of the cubed adjacency matrix. A Monte-Carlo simulation is used to estimate this quantity. Each sample requires O(|E|) time and O(ǫ 2 log(1 δ)ρ(G) 2 ) samples are required to guarantee an (ǫ, δ)-approximation, where ρ(G) is a measure of the triangle sparsity of G (ρ(G) is not necessarily small). Our algorithm requires only O(|V |) space in order to work efficiently. We present experiments that demonstrate that in practice usually only O(log 2 |V |) samples are required to get good approximations for graphs frequently encountered in data-mining tasks, and that our algorithm is competitive with state-of-the-art approximate triangle counting methods both in terms of accuracy and in terms of running-time. The use of Monte-Carlo simulation support parallelization well: our algorithm is embarrassingly parallel with a critical path of only O(|E|), achievable on as few as O(log 2 |V |) processors. Counting the frequency of small subgraphs is a fundamental technique in network analysis across various domains, most notably in bioinformatics and social networks. The special case of triangle counting has received much attention. Getting results for 4-vertex patterns is highly challenging, and there are few practical results known that can scale to massive sizes. Indeed, even a highly tuned enumeration code takes more than a day on a graph with millions of edges. Most previous work that runs for truly massive graphs employ clusters and massive parallelization. We provide a sampling algorithm that provably and accurately approximates the frequencies of all 4-vertex pattern subgraphs. Our algorithm is based on a novel technique of 3-path sampling and a special pruning scheme to decrease the variance in estimates. We provide theoretical proofs for the accuracy of our algorithm, and give formal bounds for the error and confidence of our estimates. We perform a detailed empirical study and show that our algorithm provides estimates within 1 relative error for all subpatterns (over a large class of test graphs), while being orders of magnitude faster than enumeration and other sampling based algorithms. Our algorithm takes less than a minute (on a single commodity machine) to process an Orkut social network with 300 million edges. The number of triangles in a graph is an important metric for understanding the graph. It is also directly related to the clustering coefficient of a graph, which is one of the most important indicator for social networks. Counting the number of triangles is computationally expensive for very large graphs. Hence, estimation is necessary for large graphs, particularly for graphs that are hidden behind searchable interfaces where the graphs in their entirety are not available. For instance, user networks in Twitter and Facebook are not available for third parties to explore their properties directly. This paper proposes a new method to estimate the number of triangles based on random edge sampling. It improves the traditional random edge sampling by probing the edges that have a higher probability of forming triangles. The method outperforms the traditional method consistently, and can be better by orders of magnitude when the graph is very large. The result is demonstrated on 20 graphs, including the largest graphs we can find. More importantly, we proved the improvement ratio, and verified our result on all the datasets. The analytical results are achieved by simplifying the variances of the estimators based on the assumption that the graph is very large. We believe that such big data assumption can lead to interesting results not only in triangle estimation, but also in other sampling problems. In the past, the fundamental graph problem of triangle counting and listing has been studied intensively from a theoretical point of view. Recently, triangle counting has also become a widely used tool in network analysis. Due to the very large size of networks like the Internet, WWW or social networks, the efficiency of algorithms for triangle counting and listing is an important issue. The main intention of this work is to evaluate the practicability of triangle counting and listing in very large graphs with various degree distributions. We give a surprisingly simple enhancement of a well known algorithm that performs best, and makes triangle listing and counting in huge networks feasible. This paper is a condensed presentation of [SW05]. We study property testing in the context of distributed computing, under the classical CONGEST model. It is known that testing whether a graph is triangle-free can be done in a constant number of rounds, where the constant depends on how far the input graph is from being triangle-free. We show that, for every connected 4-node graph H, testing whether a graph is H-free can be done in a constant number of rounds too. The constant also depends on how far the input graph is from being H-free, and the dependence is identical to the one in the case of testing triangle-freeness. Hence, in particular, testing whether a graph is (K_4 )-free, and testing whether a graph is (C_4 )-free can be done in a constant number of rounds (where (K_k ) denotes the k-node clique, and (C_k ) denotes the k-node cycle). On the other hand, we show that testing (K_k )-freeness and (C_k )-freeness for (k 5 ) appear to be much harder. Specifically, we investigate two natural types of generic algorithms for testing H-freeness, called DFS tester and BFS tester. The latter captures the previously known algorithm to test the presence of triangles, while the former captures our generic algorithm to test the presence of a 4-node graph pattern H. We prove that both DFS and BFS testers fail to test (K_k )-freeness and (C_k )-freeness in a constant number of rounds for (k 5 ). How can we quickly find the number of triangles in a large graph, without actually counting them? Triangles are important for real world social networks, lying at the heart of the clustering coefficient and of the transitivity ratio. However, straight-forward and even approximate counting algorithms can be slow, trying to execute or approximate the equivalent of a 3-way database join. In this paper, we provide two algorithms, the eigentriangle for counting the total number of triangles in a graph, and the eigentrianglelocal algorithm that gives the count of triangles that contain a desired node. Additional contributions include the following: (a) We show that both algorithms achieve excellent accuracy, with up to sime 1000x faster execution time, on several, real graphs and (b) we discover two new power laws (degree-triangle and triangleparticipation laws) with surprising properties. 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 say an algorithm on n by n matrices with entries in [-M, M] (or n-node graphs with edge weights from [-M, M]) is truly sub cubic if it runs in O(n^ 3- ( M)) time for some > 0. We define a notion of sub cubic reducibility, and show that many important problems on graphs and matrices solvable in O(n^3) time are equivalent under sub cubic reductions. Namely, the following weighted problems either all have truly sub cubic algorithms, or none of them do: - The all-pairs shortest paths problem (APSP). - Detecting if a weighted graph has a triangle of negative total edge weight. - Listing up to n^ 2.99 negative triangles in an edge-weighted graph. - Finding a minimum weight cycle in a graph of non-negative edge weights. - The replacement paths problem in an edge-weighted digraph. - Finding the second shortest simple path between two nodes in an edge-weighted digraph. - Checking whether a given matrix defines a metric. - Verifying the correctness of a matrix product over the ( , +)-semiring. Therefore, if APSP cannot be solved in n^ 3- time for any > 0, then many other problems also need essentially cubic time. In fact we show generic equivalences between matrix products over a large class of algebraic structures used in optimization, verifying a matrix product over the same structure, and corresponding triangle detection problems over the structure. These equivalences simplify prior work on sub cubic algorithms for all-pairs path problems, since it now suffices to give appropriate sub cubic triangle detection algorithms. Other consequences of our work are new combinatorial approaches to Boolean matrix multiplication over the (OR, AND)-semiring (abbreviated as BMM). We show that practical advances in triangle detection would imply practical BMM algorithms, among other results. Building on our techniques, we give two new BMM algorithms: a derandomization of the recent combinatorial BMM algorithm of Bansal and Williams (FOCS'09), and an improved quantum algorithm for BMM. Let G=(V,E) be an n-vertex graph and Md a d-vertex graph, for some constant d. Is Md a subgraph of G? We consider this problem in a model where all n processes are connected to all other processes, and each message contains up to @math bits. A simple deterministic algorithm that requires @math communication rounds is presented. For the special case that Md is a triangle, we present a probabilistic algorithm that requires an expected @math rounds of communication, where t is the number of triangles in the graph, and @math with high probability. We also present deterministic algorithms that are specially suited for sparse graphs. In graphs of maximum degree Δ, we can test for arbitrary subgraphs of diameter D in @math rounds. For triangles, we devise an algorithm featuring a round complexity of @math , where A denotes the arboricity of G. Graphs and networks are used to model interactions in a variety of contexts, and there is a growing need to be able to quickly assess the qualities of a graph in order to understand its underlying structure. Some of the most useful metrics are triangle based and give a measure of the connectedness of “friends of friends.” Counting the number of triangles in a graph has, therefore, received considerable attention in recent years. We propose new sampling-based methods for counting the number of triangles or the number of triangles with vertices of specified degree in an undirected graph and for counting the number of each type of directed triangle in a directed graph. The number of samples depends only on the desired relative accuracy and not on the size of the graph. We present extensive numerical results showing that our methods are often much better than the error bounds would suggest. In the undirected case, our method is generally superior to other approximation approaches; in the undirected case, ours is the first approximation method proposed. Triangle listing is one of the fundamental algorithmic problems whose solution has numerous applications especially in the analysis of complex networks, such as the computation of clustering coefficient, transitivity, triangular connectivity, etc. Existing algorithms for triangle listing are mainly in-memory algorithms, whose performance cannot scale with the massive volume of today's fast growing networks. When the input graph cannot fit into main memory, triangle listing requires random disk accesses that can incur prohibitively large I O cost. Some streaming and sampling algorithms have been proposed but these are approximation algorithms. We propose an I O-efficient algorithm for triangle listing. Our algorithm is exact and avoids random disk access. Our results show that our algorithm is scalable and outperforms the state-of-the-art local triangle estimation algorithm. A cohesive subgraph is a primary vehicle for massive graph analysis, and a newly introduced cohesive subgraph, k-truss, which is motivated by a natural observation of social cohesion, has attracted more and more attention. However, the existing parallel solutions to identify the k-truss are inefficient for very large graphs, as they still suffer from huge communication cost and large number of iterations during the computation. In this paper, we propose a novel parallel and efficient truss detection algorithm, called PeTa. The PeTa produces a triangle complete subgraph (TC-subgraph) for every computing node. Based on the TC-subgraphs, PeTa can detect the local k-truss in parallel within a few iterations. We theoretically prove, within this new paradigm, the communication cost of PeTa is bounded by three times of the number of triangles, the total computation complexity of PeTa is the same order as the best known serial algorithm and the number of iterations for a given partition scheme is minimized as well. Furthermore, we present a subgraph-oriented model to efficiently express PeTa in parallel graph computing systems. The results of comprehensive experiments demonstrate, compared with the existing solutions, PeTa saves 2X to 19X in communication cost, reduces 80 to 95 number of iterations and improves the overall performance by 80 across various real-world graphs. Let G = (V,E) be an n-vertex graph and M_d a d-vertex graph, for some constant d. Is M_d a subgraph of G? We consider this problem in a model where all n processes are connected to all other processes, and each message contains up to O(log n) bits. A simple deterministic algorithm that requires O(n^((d-2) d) log n) communication rounds is presented. For the special case that M_d is a triangle, we present a probabilistic algorithm that requires an expected O(ceil(n^(1 3) (t^(2 3) + 1))) rounds of communication, where t is the number of triangles in the graph, and O(min n^(1 3) log^(2 3) n (t^(2 3) + 1), n^(1 3) ) with high probability. We also present deterministic algorithms specially suited for sparse graphs. In any graph of maximum degree Delta, we can test for arbitrary subgraphs of diameter D in O(ceil(Delta^(D+1) n)) rounds. For triangles, we devise an algorithm featuring a round complexity of O(A^2 n + log_(2+n A^2) n), where A denotes the arboricity of G.