Influence maximization on temporal networks

Research on the co-evolution of temporal networks structure and public opinion propagation

Under the new media environment, social platforms, as the carrier of information propagation, have shown a drastic change in their form and structure, endowing public opinion with unique propagation characteristics. In view of this, considering the dynamic changes of online social network (OSN) structure, this article intends to analyse the spreading mechanism of public opinion in temporal networks and improve the applicability of public opinion governance strategies. Combing the changes of OSN topology with the classical susceptible–infected–recovered (SIR) dynamics model, we constructed a co-evolution model of temporal networks structure and public opinion propagation, and the propagation threshold of public opinion was derived with the help of Markov process. Then, the propagation characteristics of public opinion in temporal networks and their co-evolution process under different factors were discussed through simulation experiments. The results show that the propagation of public opinion in temporal networks has faster speed and wider scope compared with that in static networks; netizens’ social activity has a phased impact on the evolution process of public opinion and with its significant heterogeneity, the propagation of public opinion is gradually suppressed; compared with [Formula: see text], the evolution process of public opinion in temporal networks is more sensitive to the state change of public opinion [Formula: see text]. Our research can further enrich the theoretical research system of network science and information science and also provide a certain decision-making reference for the regulators to reasonably govern the propagation of public opinion in social platforms.

Effective submodularity of influence maximization on temporal networks

We study influence maximization on temporal networks. This is a special setting where the influence function is not submodular, and there is no optimality guarantee for solutions achieved via greedy optimization. We perform an exhaustive analysis on both real and synthetic networks. We show that the influence function of randomly sampled sets of seeds often violates the necessary conditions for submodularity. However, when sets of seeds are selected according to the greedy optimization strategy, the influence function behaves effectively as a submodular function. Specifically, violations of the necessary conditions for submodularity are never observed in real networks, and only rarely in synthetic ones. The direct comparison with exact solutions obtained via brute-force search indicates that the greedy strategy provides approximate solutions that are well within the optimality gap guaranteed for strictly submodular functions. Greedy optimization appears, therefore, to be an effective strategy for the maximization of influence on temporal networks.