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.
|Title of host publication||The 2018 International Conference on Extending Database Technology (EDBT)|
|Number of pages||12|
|Publication status||Published - 26 Mar 2018|
|Event|| EDBT/ICDT 2018 Joint Conference - Vienna, Austria|
Duration: 26 Mar 2018 → 29 Mar 2018
|Conference||EDBT/ICDT 2018 Joint Conference|
|Period||26/03/2018 → 29/03/2018|