Information spreading with network augmentation

When a new idea or innovation arises in a network of individuals, it can either quickly propagate to a large part of the network and be adopted by many individuals or immediately expire. Understanding the dynamics that regulate these behaviours has been one of the main goals in the field of complex network analysis and has been studied under the name of influence spreading or information diffusion problem. This problem is motivated by many applications in different fields from marketing to epidemiology, going through the study of adoption of innovations and the analysis of social networks. Several studies have been conducted with the aim of shaping a given diffusion process so as to maximize or minimize the number of nodes that spread the information, called active nodes, at the end of the process by taking intervention actions. One of the most studied problems has been formalized by Kempe et al. [40] and consists in finding a set of initial nodes, called seeds, that maximizes the expected number of active nodes under a budget constraint. Beside it, other intervention actions may be used to facilitate or limit the diffusion processes such as inserting or deleting edges and adding or deleting nodes in the network. In this work we present two possible intervention actions. First, we study the problem of maximizing the information spread in a network by creating a limited amount of new edges incident to a given initial set of active nodes. We show that the problem cannot be approximated within a constant factor greater than 1 − 1 2e , unless P = NP. We then propose an algorithm that guarantees an approximation factor of 1 − 1 e − , where is any positive real number. We experimentally show that, with a small number of added edges our algorithm increases by far the expected number of active nodes with respect to an initial set of seeds. Moreover, our algorithm outperforms several other baselines. The experiments have been conducted both on artificial and real-world instances. Then, we focus on a generalization of the problem of Kempe et al. in which we are allowed to spend the budget to buy seeds or new edges incident to the seeds according to a cost function. The problem does not admit a P T AS, unless P = NP. We propose two approximation algorithms: the former one gives an approximation ratio that depends on the edge costs and increases when such costs are high, the latter algorithm gives a constant approximation guarantee which is greater than that of the first algorithm when the edge costs can be small.