Fast and frugal targeting with incentives (Q2297851)

This paper introduces a notion of `incentives' to augment models of influence diffusion in social networks. The work carries an interpretation in graph theory with the ultimate goal of minimizing the incentives required to guarantee that information in the network diffuses uniformly after a certain number of rounds. The results presented include algorithms of optimal polynomial complexity for paths, cycles, trees, and complete graphs. The importance of this kind of application to the study of the influence within social networks can be seen nowadays in recommender systems, viral marketing, and also in information dissemination, for example for a public health campaign. Social networks in this context are modelled by undirected graphs; nodes represent actors, edges the relationships between them. Campaigns to communicate information in the network are defined in fixed time spans, therefore a `Time-bounded targeting with incentives' problem is relevantly analyzed. One of the main contributions of this work is an optimal polynomial-time algorithm for allocation of incentives. A detailed analysis for the case of paths yields an algorithm of linear complexity, explained in Algorithm 1 and Theorem 2. For the case of complete graphs, a dynamic programming algorithm of complexity O(ln log n) is presented (see their Theorem 4). Here n is the number of nodes, and l a time bound. For the case of trees, a solution is proposed of order O(lmn), where m is the maximum degree of the nodes in the network. Some social networks are certainly completely connected, for example groups of collaborators, academic departments, or sports teams. Thus the results contained, even though they are framed as theoretical, can have direct applications in some domains. For other applications to more generic social networks, that lean towards a degree distribution that is scale-free or that have small-world properties (small diameter, for example), these results do not provide any information. However, they motivate and rigorously contextualize the problem, thereby motivating further investigations. Given the explicit presentation in the pseudo-codes shown in the description of the algorithms presented, it should be possible to implement these and experiment with empirical data. Therefore researchers interested in the theoretical developments of influence in social networks, as well as practitioners willing to put in the effort to code these ideas, should benefit from the contributions of this paper.