  Influence analysis is a fundamental problem in social network analysis and
mining. The important applications of the influence analysis in social network
include influence maximization for viral marketing, finding the most
influential nodes, online advertising, etc. For many of these applications, it
is crucial to evaluate the influenceability of a node. In this paper, we study
the problem of evaluating influenceability of nodes in social network based on
the widely used influence spread model, namely, the independent cascade model.
Since this problem is #P-complete, most existing work is based on Naive
Monte-Carlo (\nmc) sampling. However, the \nmc estimator typically results in a
large variance, which significantly reduces its effectiveness. To overcome this
problem, we propose two families of new estimators based on the idea of
stratified sampling. We first present two basic stratified sampling (\bss)
estimators, namely \bssi estimator and \bssii estimator, which partition the
entire population into $2^r$ and $r+1$ strata by choosing $r$ edges
respectively. Second, to further reduce the variance, we find that both \bssi
and \bssii estimators can be recursively performed on each stratum, thus we
propose two recursive stratified sampling (\rss) estimators, namely \rssi
estimator and \rssii estimator. Theoretically, all of our estimators are shown
to be unbiased and their variances are significantly smaller than the variance
of the \nmc estimator. Finally, our extensive experimental results on both
synthetic and real datasets demonstrate the efficiency and accuracy of our new
estimators.
