CONTROLLO DELLA DIFFUSIONE DELL'INFLUENZA NELLE RETI SOCIALI

Social networks (SNS) are nowadays a key factor in the spread of influence. In particular, what is known as influence maximisation (IM), i.e., the problem of maximising social influence within the network, is of great relevance here. The objective is to identify the strategic nodes that can potentially influence the greatest number of other nodes. This problem finds application in a variety of contexts, such as viral marketing, politics and information dissemination in general. The study of IM therefore plays a crucial role in aiding the understanding of influence propagation in SNS and providing tools to maximise its desired effect. For the analysis of influence propagation in SNSs, graph-based models are widely used, allowing for an efficient abstraction by means of nodes -- representing people (or users) -- and arcs -- expressing the relationships between nodes. Among the various models, the linear threshold model (LTM) is one of the main models used to solve the IM problem. This model describes the spread of influence within a network of nodes: each node has an associated weight, which represents its activation threshold, known as the threshold, and the arcs between nodes also have a weight. Activation of a node occurs when the sum of the weights of the arcs of the activating nodes exceeds the corresponding threshold. It is in the context outlined above that this thesis work arises, the aim of which is to develop an innovative version of the LTM that takes into account the fact that some nodes may be indifferent to a given opinion. Starting with the LTM, an advanced version of it was defined called the monotone LTM and from the latter, two further variants were subsequently derived: the non-monotone LTM and the LTM with indifferent nodes. In monotone LTM, it is assumed that the nodes, once influenced, no longer change their opinion. In non-monotonic LTM, on the other hand, nodes can be influenced towards a given opinion or its opposite. Finally, in the LTM with indifferent nodes, some nodes may be indifferent towards a given opinion. The latter model is characterised by the fact that some nodes may become indifferent when surrounded by opposing influences; therefore, it allows us to consider and study the effect of these indifferent nodes on the propagation of the influence that is intended to spread in the network. This makes the model more faithful to the real social dynamics of SNSs and allows the model to be applied to a wide range of scenarios, including the diffusion of new products, the propagation of news and information, the adoption of healthy behaviours and the spread of political ideas. Finally, the three models were implemented numerically and compared to a scenario based on realistic data in order to highlight their effectiveness and limitations.

I social network (SN) rappresentano al giorno d'oggi un fattore chiave nella diffusione dell'influenza. In particolare, in tale ambito assume grande rilevanza la cosiddetta influence maximization (IM), i.e., il problema di massimizzare l'influenza sociale all'interno della rete. L'obiettivo è individuare i nodi strategici che, potenzialmente, possono influenzare il maggior numero di altri nodi. Tale problema trova applicazione in svariati contesti, come il viral marketing, la politica ed in generale la diffusione delle informazioni. Lo studio dell'IM svolge quindi un ruolo cruciale nel favorire la comprensione della diffusione dell'influenza nei SN e nel fornire strumenti per massimizzarne l'effetto desiderato. Per l'analisi della propagazione dell'influenza nei SN sono largamente utilizzati i modelli basati su grafi, che ne permettono un'astrazione efficiente per mezzo di nodi -- che rappresentano le persone (o gli utenti) -- e di archi -- che esprimono le relazioni tra i nodi. Tra i vari modelli, il linear threshold model (LTM) è uno dei principali modelli utilizzati per risolvere il problema dell'IM. Tale modello descrive la diffusione dell'influenza all'interno di una rete di nodi: ogni nodo ha associato un peso, che rappresenta la sua soglia di attivazione, nota come threshold, e gli archi tra i nodi hanno anch'essi un peso. L'attivazione di un nodo avviene quando la somma dei pesi degli archi dei nodi attivanti supera la threshold corrispondente. Nel contesto sopra delineato si pone il presente lavoro di tesi, il cui scopo è sviluppare una versione innovativa del LTM, che tenga conto del fatto che alcuni nodi possono essere indifferenti rispetto ad una data opinione. A partire dal LTM, ne è stata definita una versione avanzata denominata LTM monotono e da quest'ultima ne sono successivamente state derivate altre due varianti: il LTM non-monotono e il LTM con nodi indifferenti. Nel LTM monotono si suppone che i nodi, una volta influenzati, non cambino più opinione. Nel LTM non-monotono, invece, i nodi possono essere influenzati verso una data opinione o il suo contrario. Infine, nel LTM con nodi indifferenti, alcuni nodi possono essere indifferenti rispetto ad una data opinione. Quest'ultimo modello è caratterizzato dal fatto che alcuni nodi possono diventare indifferenti se circondati da influenze contrastanti; pertanto, permette di considerare e studiare l'effetto di questi nodi indifferenti alla propagazione dell'influenza che si intende diffondere nella rete. Ciò rende il modello più aderente alle dinamiche sociali reali dei SN e consente di applicare il modello ad una vasta gamma di scenari, tra cui la diffusione di nuovi prodotti, la propagazione di notizie e informazioni, l'adozione di comportamenti salutari e la diffusione di idee politiche. Infine, i tre modelli sono stati implementati in ambito numerico e confrontati su uno scenario basato su dati realistici al fine di evidenziarne efficacia e limiti.