Estimating the degrees of neighboring nodes in online social networks

Jooyoung Lee, Jae C. Oh

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

4 Scopus citations

Abstract

We propose an agent centric algorithm that each agent (i.e., node) in a social network can use to estimate each of its neighbor’s degree. The knowledge about the degrees of neighboring nodes is useful for many existing algorithms in social networks studies. For example, algorithms to estimate the diffusion rate of information spread need such information. In many studies, either such degree information is assumed to be available or an overall probabilistic distribution of degrees of nodes is presumed. Furthermore, most of these existing algorithms facilitate a macro-level analysis assuming the entire network is available to the researcher although sampling may be required due to the size of the network. In this paper, we consider the case that the network topology is unknown to individual nodes and therefore each node must estimate the degrees of its neighbors. In estimating the degrees, the algorithm correlates observable activities of neighbors to Bernoulli trials and utilize a power-law distribution to infer unobservable activities. Our algorithm was able to estimate the neighbors’ degrees in 92% accuracy for the 60867 number of nodes. We evaluate the mean squared error of accuracy for the proposed algorithm on a real and a synthetic networks.

Original languageEnglish (US)
Title of host publicationPRIMA 2014
Subtitle of host publicationPrinciples and Practice of Multi-Agent Systems - 17th International Conference, Proceedings
EditorsYang Xu, Jeremy Pitt, Hoa Khanh Dam, Guido Governatori, Takayuki Ito
PublisherSpringer Verlag
Pages42-56
Number of pages15
ISBN (Electronic)9783319131900
StatePublished - Jan 1 2014
Event17th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2014 - Gold Coast, Australia
Duration: Dec 1 2014Dec 5 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8861
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other17th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2014
CountryAustralia
CityGold Coast
Period12/1/1412/5/14

Keywords

  • Degree estimations
  • Distributed computation
  • Online social networks

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Estimating the degrees of neighboring nodes in online social networks'. Together they form a unique fingerprint.

  • Cite this

    Lee, J., & Oh, J. C. (2014). Estimating the degrees of neighboring nodes in online social networks. In Y. Xu, J. Pitt, H. K. Dam, G. Governatori, & T. Ito (Eds.), PRIMA 2014: Principles and Practice of Multi-Agent Systems - 17th International Conference, Proceedings (pp. 42-56). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8861). Springer Verlag.