An analytical model for information gathering and propagation in social networks using random graphs

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.