This project aims to discuss the Social Influence Maximization on different Social Networks.
-
Imagine three social networks with, respectively, 102, 103 and 104 nodes. Every edge can be characterised by 4 features and the probability of the edge is given by a linear combination of the features. Assign a cost of every node and define a reasonable budget for the social influencer. We suggest using 3 different values of the budget for the 3 social networks.
-
Apply, to the three scenarios, the greedy algorithm to solve approximately the in- fluence maximization problem in the case in which the probabilities of the edges are known. In doing that, use Monte Carlo simulations and show how the value of the objective function varies for different values of the approximation bound.
-
Assume that the probabilities of the edges are not known. Apply: combinato- rial bandit algorithms (TS and UCB1-like) in the case the linear structure of the probabilities is not exploited (and therefore the probability of every edge is estimated by using only samples related to that edge), the UBC1-like algorithm exploiting the linear structure of the probabilities of the edge. Show how the expected regret varies as the number repetitions of the problem increases.
-
Modify the social networks to assure that every node has at most 15 neighbors. Apply a UCB1-like algorithm when edges cannot be observed and have to be esti- mated from data. Show how the expected regret varies as the number repetitions of the problem increases.
Students Leonardo Febbo, Gabriele Ghiringhelli. Project for the course on 'Data Intelligence Application' held at Politecnico di Milano by Prof. Nicola Gatti, A.Y. 2019/2020