Mining Graphlet Counts in Online Social Networks
Authors:
- Xiaowei ChenXCXiaowei Chen
- John C. S. LuiJLJohn C. S. Lui
- 2 February 2017
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 71-80
Abstract
Counting subgraphs is a fundamental analysis task for online social networks (OSNs). Given the sheer size and restricted access of online social network data, efficient computation of subgraph counts is highly challenging. Although a number of algorithms have been proposed to estimate the relative counts of subgraphs in OSNs with restricted access, there are only few works which try to solve a more general problem, i.e., counting subgraph frequencies. In this paper, we propose an efficient random walk-based framework to estimate the subgraph counts. Our framework generates samples by leveraging consecutive steps of the random walk as well as by observing neighbors of visited nodes. Using the importance sampling technique, we derive unbiased estimators of the subgraph counts. To make better use of the degree information of visited nodes, we also design an improved estimator, which increases the efficiency of the estimate at no additional cost. We conduct extensive experimental evaluation on real-world OSNs to confirm our theoretical claims. The experiment results show that our estimators are unbiased, accurate, efficient and better than the state-of-the-art algorithm. For the Weibo graph with more than 58 million nodes, our method produces estimate of triangle count with an error less than 5% using only 20 thousands sampled nodes. Detailed comparison with the state-of-the-art method demonstrates that our algorithm is 4 to 5 times more accurate.Keywords
This publication has 29 references indexed in Scilit:
- Beyond Triangles2015
- MASCOT2015
- On random walk based graph sampling2015
- A Space-Efficient Streaming Algorithm for Estimating Transitivity and Triangle Counts Using the Birthday ParadoxACM Transactions on Knowledge Discovery From Data, 2015
- Efficiently Estimating Motif Statistics of Large NetworksACM Transactions on Knowledge Discovery From Data, 2014
- A combinatorial approach to graphlet countingBioinformatics, 2014
- Graft: An Efficient Graphlet Counting Method for Large Graph AnalysisIEEE Transactions on Knowledge and Data Engineering, 2014
- Triadic Measures on Graphs: The Power of Wedge Sampling2013
- Beyond random walk and metropolis-hastings samplersACM SIGMETRICS Performance Evaluation Review, 2012
- The mixing time of the Newman–Watts small world2012