K-clique and k-cycle counting in the streaming model.

摘要

In this thesis, we give algorithms for two graph problems: k -clique (Kk) and k-cycle (Ck) counting in the streaming model. The streaming model is a computational model to solve problems on large sequential data sets. Compared to the conventional computational model, the streaming model requires efficient space and small time per item.;The input of the problems is the number of vertices n v, for a given graph G, constants epsilon', delta > 0, an integer k ∈ (0, nv), and a sequential set of edges of G in "an arbitrary order. The algorithm reduces the counting problems to Frequency Moment problems using a sketch over alpha - stable random variables for alpha ∈ (1,1.9] and pseudorandom generators. Our algorithm is based on Indyk's technique. Indyk claims his technique is provably correct for general alpha other than 1 or 2 but he does not aware any practical applications [16]. This thesis shows that k-clique (Kk) and k-cycle (C k) counting are such applications involving general alpha ∈ (1,1.9]. Our algorithm achieves space efficiency when k is small and the density of Kk or C k in G is large.