大规模时序图影响力最大化的算法研究

Influence maximization problem has been widely studied in social networks, and well applied in the scenarios such as viral marketing and epidemic prevention. The influence maximization problem aims to find k influential nodes in graphs that maximize the dissemination of information. Recently, in most existing works, the social network is abstracted as static graph, then implement the influence maximization problem in the static graph, and finally return k nodes as the social network's influential nodes. However, the most former researchers ignored the truth that most networks in real life cannot be simply denoted as static graphs, such as social networks, traffic networks, brain networks, and so forth, due to the connections between nodes in these networks are time related. Therefore, in this work we study the influence maximization problem on temporal graph(IMTG), that is, IMTG aims to find k influential nodes in temporal graph that maximize the number of influenced nodes. The information propagation model and propagation probability is the fundamental of influence maximization problem. So, firstly, we design a new propagation model based on IC(Independent Cascade) propagation model, named ICT(Independent Cascade model on Temporal graph) propagation model, to make information spread on temporal graphs, since the static graph-based IC propagation model cannot be directly applied to temporal graphs. Secondly, we propose a new method based on PageRank algorithm to compute the propagation probability. We improve the PageRank algorithm by taking the node's communication frequency into account, because the higher connection frequency between two nodes, the closer they are, which means they are more influenced by each other. After the issues of propagation model and propagation probability have been solved, we study the influence maximization problem on temporal graph through two steps. In the first step, we focus on the computation of single node influence probability, and propose an algorithm, named SIC(Single node Influence Computation), to implement the computation of single node influence, then we propose an improved algorithm ISIC(Improved SIC) by researching the characteristic that the connections among the nodes on temporal graph are time related. In the second step, we implement the influence maximization problem on temporal graph by using the result of the first step, and propose a basic method BIMT(Basic Method for IMTG). However, the BIMT algorithm will cost plenty of time when deal with large scale temporal graphs. So we propose an effective algorithm AIMT(Advanced Method for IMTG) by mapping each id of node's in the graph to nature numbers. Compared with IMT method, AIMT can deal with large scale graph with high efficiency. Though the research of the computation of nodes' marginal effect we find that some nodes' marginal effect is unnecessary to be recomputed during the seed node selection process, so we improve the AIMT algorithm and propose a more effective algorithm IMIT(Improved method for IMTG) to avoid multiple computation of the marginal effects of certain nodes. Finally, the experiment results verify the high efficiency and scalability of AIMT and IMIT algorithms, AIMT and IMIT algorithms can handle influence maximization on large temporal graph with less time than BIMT.