Inferring range of information diffusion based on historical frequent items

摘要

To estimate the range of information diffusion is critical for social network and user behavior analysis. Selecting nodes to constitute the range of information diffusion is challenging by the classic independent cascade and linear threshold models, due to the unknown topology of large-scale online social networks (OSNs). In this paper, we start from the mining of frequent itemsets in historical records of information diffusion, and adopt Bayesian network (BN) as the framework to represent and infer the implied dependence relations among frequent items. To make probabilistic inferences to infer the range, we first propose a greedy algorithm to select the observed nodes as the evidence of BN inference, for which we propose the metric of proximity degree and prove its submodularity. Then, we give the algorithm to construct the item-association BN (IABN) to represent the dependencies among frequent items. Following, we present an approximate algorithm to infer the range of information diffusion w.r.t. the observed nodes. Experimental results show that the observed nodes could be selected and the range of information diffusion could be inferred effectively. Empirical studies also demonstrate that our proposed IABN outperforms some state-of-the-art methods to obtain relatively complete nodes in the range of information diffusion.