Despite recent efforts in counting 3-node and 4-node graphlets, little attention has been paid to characterizing 5-node graphlets. In this paper, we develop a computationally efficient sampling method to estimate 5-node graphlet counts. We not only provide a fast sampling method and unbiased estimators of graphlet counts, but also derive simple yet exact formulas for the variances of the estimators which are of great value in practice-the variances can be used to bound the estimates' errors and determine the smallest necessary sampling budget for a desired accuracy. We conduct experiments on a variety of real-world datasets, and the results show that our method is several orders of magnitude faster than the state-of-The-Art methods with the same accuracy.
|Original language||English (US)|
|Title of host publication||2018 IEEE 34th International Conference on Data Engineering (ICDE)|
|Publisher||Institute of Electrical and Electronics Engineers (IEEE)|
|Number of pages||2|
|State||Published - Oct 25 2018|