Diffusion Range Prediction In Temporal Diffusion Networks

Information diffusion and influence problems have been studied for many years in networks.Diffusion range prediction,i.e.discovering the influenced nodes,is a basic problem in information diffusion.According to the fact that information is diffused through contacts and these contacts are varying over time and have delays,so we define the temporal diffusion network and study diffusion range prediction in this paper.However,it is hard to predict which nodes and when they will become influenced,because of the uncertainty of information diffusion.So it is necessary to discover influenced nodes via tracking and verifying the state of nodes.To a large extent,it is costly to verify the states of nodes in temporal diffusion network and the total count of verifications is usually limited in existing applications.So the main purpose of discovering influenced nodes is to discover more influenced nodes under the limited k verifications.Although there are many works in information diffusion,few of them can be used to predict diffusion range and the performances of existing methods are not good.In this paper,we propose IPH algorithm to predict diffusion range in temporal diffusion network.The works in this paper are as follows:(1)We formalize the diffusion range prediction problem in temporal diffusion network based on the studies of information diffusion prediction and temporal networks.And we analyze the main problems of exiting methods which have laid the groundwork for our works.(2)We formalize the computation of infection probability in temporal diffusion network with IC model.The infection probability is used to predict the influenced nodes.We prove that is NP-hard to compute infection probability in temporal diffusion network.To solve this NP-hard problem,we propose path length limited approximative method to compute infection probability approximatively.(3)Considering the uncertainty of information diffusion,we propose IPH algorithm to predict and verify the diffusion range.IPH algorithm will compute infection probability of nodes in temporal diffusion network and verify the state of node that has maximum probability.And candidate node set will be updated in IPH algorithm after each verification.To solve the disadvantage of IPH algorithm,we propose an IPH-based algorithm AIPH.Experiment results show our approaches have better performance in predicting diffusion range.In conclusion,we study the diffusion range prediction problem in temporal diffusion network and propose two better heuristic algorithms IPH and AIPH to solve this problem.And our work can be used in related studies.