Computing Clustering Coefficients in Data Streams

We present random sampling algorithms that with probability at least 1 - δ compute a (1 ± ǫ)- approximation of the clustering coefficient, the transitiv ity coefficient, and of the number of bipartite cliques in a graph given as a stream of edges. Our methods can be extended to approximately count the number of occurences of fixed constant-size subgraphs. Our a lgorithms only require one pass over the input stream and their storage space depends only on structural parameters of the graphs, the approxi- mation guarantee, and the confidence probability. For examp le, the algorithms to compute the clustering and transitivity coefficient depend on that coefficient but n ot on the size of the graph. Since many large social networks have small clustering and transitivity coe fficient, our algorithms use space independent of the size of the input for these graphs. We implemented our algorithms and evaluated their performance on networks from different appli- cation domains. The sizes of the considered input graphs varied from about 8, 000 nodes and 40, 000 edges to about 135 million nodes and more than 1 billion edges. For both algorithms we run experiments with a sample set size varying from 100, 000 to 1, 000, 000 to evaluate running time and approximation guarantee. Our algorithms appear to be time efficient for the se sample sizes.