Counting Edges and Triangles in Online Social Networks via Random Walk

Yang Wu, Cheng Long, Ada Wai-Chee Fu, Zitong Chen

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

1 Citation (Scopus)
583 Downloads (Pure)

Abstract

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.
Original languageEnglish
Title of host publication2017 APWeb-WAIM Joint Conference on Web and Big Data
PublisherSpringer
Pages346-361
DOIs
Publication statusPublished - 03 Aug 2017

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Counting Edges and Triangles in Online Social Networks via Random Walk'. Together they form a unique fingerprint.

  • Cite this

    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