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.
|Title of host publication||2017 APWeb-WAIM Joint Conference on Web and Big Data|
|Publication status||Published - 03 Aug 2017|
|Name||Lecture Notes in Computer Science|
Wu, Y., Long, C., Fu, A. W-C., & Chen, Z. (2017). Counting Edges and Triangles in Online Social Networks via Random Walk. In 2017 APWeb-WAIM Joint Conference on Web and Big Data (pp. 346-361). (Lecture Notes in Computer Science ). Springer. https://doi.org/10.1007/978-3-319-63579-8_27