查看文章

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 …