MOSS-5: A Fast Method of Approximating Counts of 5-Node Graphlets in Large Graphs (Extended Abstract)

Pinghui Wang, Junzhou Zhao, Xiangliang Zhang, Zhenguo Li, Jiefeng Cheng, John C.S. Lui, Don Towsley, Jing Tao, Xiaohong Guan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


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 languageEnglish (US)
Title of host publication2018 IEEE 34th International Conference on Data Engineering (ICDE)
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages2
ISBN (Print)9781538655207
StatePublished - Oct 25 2018

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01


Dive into the research topics of 'MOSS-5: A Fast Method of Approximating Counts of 5-Node Graphlets in Large Graphs (Extended Abstract)'. Together they form a unique fingerprint.

Cite this