Driving exploration in online influence maximization with semi-bandit feedback

Influence Maximization (IM) in social networks is the problem of finding the best seed nodes to activate under a fixed budget such that the number of users influenced in the end is maximized. Solutions to this problem rely on the probability with which users influence each other. However, in most real applications this information may be inaccessible or incomplete. In this thesis, we study the IM problem under the independent cascade model when influence probabilities are unknown and need to be estimated from the feedback provided by the environment (Online Influence Maximization, OIM). Specifically, we adopt a combinatorial multi-armed bandit paradigm that aims at finding the best seeds by repeatedly interacting with the social network itself. We study the case in which semi-bandit feedback is accessible, that can be either at edge-level, if provides information about the activated edges, or node-level, if provides information about the activated nodes. We provide two different strategies for the OIM problem depending on the semi-bandit feedback available. For the edge-level feedback case, we propose a new method that intrinsically drives the exploration by assigning weights on nodes. For the less studied problem of learning influence probabilities when only node-level feedback is available, we propose a new attribution model for which we provide theoretical bounds on the attribution error. Having regard to the complexity introduced by the credit assignment problem, we present a new approach with the double objective of maximizing influence spread while reducing the error on the attribution. To solve this problem, we propose a topology-based approach, with a (1-epsilon)/2 approximation factor of the optimal solution and a probability-based approach. Finally, we describe practical implementations of our algorithms and experimentally demonstrate their efficiency and effectiveness in different settings.

Con il nome Influence Maximization (IM) indichiamo il problema di trovare i migliori nodi seed da attivare in una rete sociale avendo un budget fisso in modo tale da massimizzare il numero di utenti influenzati. Le soluzioni a questo problema si basano sulle probabilità con cui ogni utente influenza gli altri. Tuttavia, nella maggior parte dei contesti reali, queste informazioni potrebbero essere inaccessibili o incomplete. In questa tesi studiamo il problema di IM sotto il modello independent cascade, nel caso in cui le probabilità di influenza siano sconosciute e necessitino di essere stimate utilizzando il feedback fornito dall'ambiente. Nello specifico, adottiamo un paradigma multi-armed bandit combinatorio, che mira a trovare i migliori seed interagendo ripetutamente con il social network stesso (Online Influence Maximization, OIM). Il nostro studio è focalizzato sul caso in cui si ha accesso a un feedback di tipo semi-bandit, che può essere sia edge-level, se fornisce informazioni sugli archi attivati, sia node-level, se fornisce informazioni sui nodi attivati. A seconda del feedback disponibile, presentiamo due diverse strategie per il problema di OIM. Per il caso di feedback edge-level, proponiamo un nuovo metodo che guida intrinsecamente l'esplorazione assegnando pesi sui nodi. Per il caso meno studiato di feedback node-level, proponiamo un nuovo modello di attribuzione per il quale forniamo limiti teorici sull'errore di attribuzione. Data la complessità introdotta dall'incertezza sull'assegnamento del credito, presentiamo un approccio al problema con il duplice obiettivo di massimizzare l'influenza e, al contempo, ridurre l'errore sull'attribuzione. Inoltre, introduciamo un metodo basato sulla topologia, con un fattore di approssimazione di (1-epsilon)/2 della soluzione ottima, e un metodo basato sulle probabilità per risolvere tale problema. Infine, descriviamo le implementazioni pratiche dei nostri algoritmi e dimostriamo sperimentalmente la loro efficienza ed efficacia su diverse ambientazioni.