Critical Node Analysis For Information Diffusion Networks

With the rapid development of Internet and information technology,the information diffusion manners between human beings are coming into a new era.People can publish fresh news,share thoughts,and communicate with each other instantly in online social network services such as Weibo,Wechat and Twitter,at any time and any place.Thus,these online social services have become one of the most important place for information exchange and propagation.If we treat every user in the online social services as a network node,then they will form an open information diffusion network enriched with a large number of network nodes and the large-scaled data stream between them.In recent years,the analyses on such information diffusion network are attracting researchers' interests as it can produce great social and practical values.The research work in this thesis is mainly focused on three important issues in information diffusion network,namely the real-time detection of trending topic,the prediction of topic's future popularity,and the prediction of each node's future participation state with every topic.The main contributions of this thesis can be summarized in the following three aspects:First,to accomplish the task of detecting emerging trending topics in information diffusion networks in a cost-effective way,we design the corresponding detection algorithms based on selecting and utilizing a subset of critical and representative network nodes.Comparing to the traditional detection algorithms that spend huge costs in continuously gathering and processing full data stream by all nodes,we propose node selection algorithms to find a small group of critical subset nodes with maximized expected topic detection rewards under cost constraints.Afterwards,the proposed algorithms will gather and utilize real-time online data stream by the selected subset nodes to detect the trending topics in information diffusion networks in real time.Experimental results with real dataset from Sina Weibo show that our method is efficient in finding suitable subset nodes,and it can significantly reduce the detection costs while keeping good real-time detection performance.Second,to accomplish the task of predicting topic's future popularity in information diffusion networks as early as possible,and in a cost-effective way,we design the corresponding prediction algorithms based on selecting and utilizing a subset of critical network nodes as well.The prediction algorithms can use the subset nodes' data stream in the “known” time periods as inputs to predict the topics' future popularities among all network nodes.In the meanwhile,we also merge the tasks of real-time trending topic detection and topic popularity prediction into a combined optimization task with cost constraints,and then propose node selection algorithms to solve the combined optimization problem.According to the experimental results in Weibo dataset,the proposed algorithms can utilize the selected subset nodes to detect the trending topics in real time and then predict their future popularities in early stages,and the results can be several hours earlier than they appear in the Weibo official results.At last,to accomplish the task of predicting every node's future participation state with each emerging topic in a cost-effective way,we design a joint prediction algorithm to predict every unknown node-topic relation and each topic's future hotness index at the same time based on selecting and utilizing a subset of critical network nodes again,where the topic's future hotness index can be regarded as a form of the topic's popularity at a future time point.Considering the diversity of nodes' preferences in various kinds of topics,as well as the cold-start prediction problem of lacking node-topic relations of new emerging topics to infer their feature profiles,we extend the functional matrix factorization method and propose algorithms using training dataset to build and optimize a decision tree model that can be used in selecting critical subset nodes for topic latent profile estimation and joint prediction tasks.The experimental results in Weibo and movie ratings dataset show that the proposed algorithms can utilize the selected subset nodes' relations with emerging topics to infer their latent topic profiles.Thus,the unknown node-topic relations and topic hotness index can be jointly predicted in real time under cost constraints,and the results are also better than peer methods.In the light of the above,this thesis is devoted to the three important issues in information diffusion network analysis,and proposes innovative frameworks and algorithms to solve the problems by selecting and utilizing the critical and representative subset nodes.As costeffectiveness is an important factor in subset node selection,our algorithms can produce better real-time results under cost constraints than baseline methods when analyzing information diffusion networks that have relatively large numbers of nodes and large-scaled data stream.