Counting Edges with Target Labels in Online Social Networks via Random Walk

Yang Wu, Cheng Long, Ada Waichee Fu, Zitong Chen

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

94 Downloads (Pure)


Online social network (OSN) analysis has attracted much attention in recent years. One important distinguishing feature of OSNs is that every user provides his/her personal profile online, which can be regarded as the labels or attributes of this user. Knowing the number of nodes or edge with a particular label will give us deeper insight of the OSNs and can provide valuable information in many real-world applications such as web marketing and advertising. 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 efficient algorithms for estimating the number of edges with target labels in OSNs based on random walk. We also derive theoretical bounds on the sample size and the 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 publicationThe 2018 International Conference on Extending Database Technology (EDBT)
PublisherEDBT Association
Number of pages12
Publication statusPublished - 26 Mar 2018
Event EDBT/ICDT 2018 Joint Conference - Vienna, Austria
Duration: 26 Mar 201829 Mar 2018


Conference EDBT/ICDT 2018 Joint Conference


Dive into the research topics of 'Counting Edges with Target Labels in Online Social Networks via Random Walk'. Together they form a unique fingerprint.

Cite this