An Analytical Model for Information Gathering and Propagation in Social Networks using Random Graphs

Abstract

In this paper, we propose an analytical model for information gathering and propagation in social networks using random sampling. We represent the social network using the Erdos–Renyi model of the random graph. When a given node is selected in the social network, information about itself and all of its neighbors are obtained and these nodes are considered to be discovered. We provide an analytical solution for the expected number of nodes that are discovered as a function of the number of nodes randomly sampled in the graph. We use the concepts of combinatorics, probability, and inclusion–exclusion principle for computing the number of discovered nodes. This is a computationally-intensive problem with combinatorial complexity. This model is useful when crawling and mining of the social network graph is prohibited. Our work finds application in several important real-world decision support scenarios such as survey sample selection, construction of public directory, and crowdsourced databases using social networks, targeted advertising, and recommendation systems. It can also be used for finding a randomized dominating set of a graph that finds applications in computer networks, document summarization, and biological networks. We have evaluated the performance both analytically as well as by means of simulation, and the results are comparable. The results have an accuracy of around 96% for random graphs and above 87% for the power-law graphs.

Department(s)

Computer Science

Research Center/Lab(s)

Center for High Performance Computing Research

Second Research Center/Lab

Intelligent Systems Center

Keywords and Phrases

Business intelligence; Data models; Data sharing; Information gathering; Node discovery in graphs; Social networks

International Standard Serial Number (ISSN)

0169-023X

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2020 Elsevier, All rights reserved.

Publication Date

01 Sep 2020

Link to Full Text

Share

 
COinS