TY - GEN
T1 - MOSS-5: A Fast Method of Approximating Counts of 5-Node Graphlets in Large Graphs (Extended Abstract)
AU - Wang, Pinghui
AU - Zhao, Junzhou
AU - Zhang, Xiangliang
AU - Li, Zhenguo
AU - Cheng, Jiefeng
AU - Lui, John C.S.
AU - Towsley, Don
AU - Tao, Jing
AU - Guan, Xiaohong
N1 - KAUST Repository Item: Exported on 2020-10-01
PY - 2018/10/25
Y1 - 2018/10/25
N2 - 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.
AB - 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.
UR - http://hdl.handle.net/10754/630322
UR - https://ieeexplore.ieee.org/document/8509465
UR - http://www.scopus.com/inward/record.url?scp=85057125910&partnerID=8YFLogxK
U2 - 10.1109/ICDE.2018.00244
DO - 10.1109/ICDE.2018.00244
M3 - Conference contribution
SN - 9781538655207
SP - 1773
EP - 1774
BT - 2018 IEEE 34th International Conference on Data Engineering (ICDE)
PB - Institute of Electrical and Electronics Engineers (IEEE)
ER -