TY - GEN
T1 - Counting Edges and Triangles in Online Social Networks via Random Walk
AU - Wu, Yang
AU - Long, Cheng
AU - Fu, Ada Wai-Chee
AU - Chen, Zitong
PY - 2017/8/3
Y1 - 2017/8/3
N2 - Online social network (OSN) analysis has attracted much attention in recent years. Edge and triangle counts are both fundamental properties in OSNs. However, for many OSNs, one can only access parts of the network using the application programming interfaces (APIs). In such cases, conventional algorithms become infeasible. In this paper, we introduce ecient algorithms for estimating the number of edges and triangles in OSNs based on random walk sampling on OSNs. We also derive a theoretical bound on the sample size and number of APIs calls needed in our algorithms for a probabilistic accuracy guarantee. We ran experiments on several publicly available real-world networks and the results demonstrate the effectiveness of our algorithms.
AB - Online social network (OSN) analysis has attracted much attention in recent years. Edge and triangle counts are both fundamental properties in OSNs. However, for many OSNs, one can only access parts of the network using the application programming interfaces (APIs). In such cases, conventional algorithms become infeasible. In this paper, we introduce ecient algorithms for estimating the number of edges and triangles in OSNs based on random walk sampling on OSNs. We also derive a theoretical bound on the sample size and number of APIs calls needed in our algorithms for a probabilistic accuracy guarantee. We ran experiments on several publicly available real-world networks and the results demonstrate the effectiveness of our algorithms.
U2 - 10.1007/978-3-319-63579-8_27
DO - 10.1007/978-3-319-63579-8_27
M3 - Conference contribution
T3 - Lecture Notes in Computer Science
SP - 346
EP - 361
BT - 2017 APWeb-WAIM Joint Conference on Web and Big Data
PB - Springer
ER -