Graphs are used to model interactions in a variety of contexts, and there is a growing need to quickly assess the structure of such graphs. Some of the most useful graph metrics are based on triangles, such as those measuring social cohesion. Algorithms to compute them can be extremely expensive, even for moderately-sized graphs with only millions of edges. Previous work has considered node and edge sampling; in contrast, we consider wedge sampling, which provides faster and more accurate approximations than competing techniques. Additionally, wedge sampling enables estimation local clustering coefficients, degree-wise clustering coefficients, uniform triangle sampling, and directed triangle counts. Our methods come with provable and practical probabilistic error estimates for all computations. We provide extensive results that show our methods are both more accurate and faster than state-of-the-art alternatives.
Most relevant to our work are sampling mechanisms. @cite_11 started the use of sparsification methods, the most important of which is Doulion @cite_5 . 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_3 @cite_7 @cite_14 . One of the main benefits of Doulion is that it reduces large graphs to smaller ones that can be loaded into memory. However, the Doulion estimate can suffer from high variance @cite_4 . Alternative sampling mechanisms have been proposed for streaming and semi-streaming algorithms @cite_27 @cite_35 @cite_10 @cite_34 . Yet, all these fast sampling methods only estimate the number of triangles and give no information about other triadic measures.
@cite_35 @cite_14 @cite_4 @cite_7 @cite_3 @cite_27 @cite_5 @cite_34 @cite_10 @cite_11
1542957328 2536223246 89448491 2114244473
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. 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. 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. A statistical approach to a posteriori blockmodeling for graphs is proposed. The model assumes that the vertices of the graph are partitioned into two unknown blocks and that the probability of an edge between two vertices depends only on the blocks to which they belong. Statistical procedures are derived for estimating the probabilities of edges and for predicting the block structure from observations of the edge pattern only. ML estimators can be computed using the EM algorithm, but this strategy is practical only for small graphs. A Bayesian estimator, based on Gibbs sampling, is proposed. This estimator is practical also for large graphs. When ML estimators are used, the block structure can be predicted based on predictive likelihood. When Gibbs sampling is used, the block structure can be predicted from posterior predictive probabilities. A side result is that when the number of vertices tends to infinity while the probabilities remain constant, the block structure can be recovered correctly with probability tending to 1. (Less)