Tesi di Laurea Specialistica / Master Thesis
Tecniche di ottimizzazione per l'analisi della diffusione delle innovazioni nei social networks [pdf] [slides]
Relatori / Advisors
Prof. Alessandro
Giua (DIEE-UNICA).
Software
Matlab source code
Optimization techniques for the analysis of diffusion of innovations in social networks
Abstract
The central question of this thesis is influence maximization in social networks. In particular will be implemented in OPL the following problems:
Identify the set of r innovators which maximizes the diffusion of innovation in finite time.
Identify the smallest set of innovators wich maximize the spread of
innovation through a target of users in finite time.
Identify the maximum choesive set.
These problems mentioned above are of type NP hard ie characterized by
a computational time that increases non linearly with the size of the data.
Related to problem 1 were developed following strategies:
A greedy algorithm implemented in Matlab based on the construction of acyclic graphs of network by analyzing the processes developed
locally.
Change the behavior of the algorithm solver CPLEX branch & cut in
order to improve the efficiency calculation.
For the second problem was implemented in Matlab an algorithm by reducing
the size of the network to improve the performance of the simulator.
Tecniche di ottimizzazione per l'analisi della diffusione delle innovazioni nei social networks
Sommario
Il tema centrale di questa tesi è il problema della massimizzazione dell’influenza nei social networks.
In particolare sono stati implementati in
linguaggio OPL i seguenti problemi:
Identificare il set di innovatori di partenza di numero pari ad r che
massimizzano la diffusione dell’innovazione in un orizzonte temporale
limitato.
Identificare il set di innovatori di partenza più piccolo che consente di
diffondere l’innovazione attraverso un target di utenti in un orizzonte
temporale limitato.
Identificare il set coesivo massimale a partire da un set di innovatori.
I problemi sopracitati presentano un’elevata complessità computazionale, in
particolare per il primo problema sono state sviluppate le seguenti strategie:
Un algoritmo greedy implementato in Matlab basato sulla costruzione
di grafi aciclici locali per stimare l’evoluzione della rete analizzando
dei processi che in essa si sviluppano localmente.
Modifica del comportamento dell’algoritmo branch and cut del risolutore
CPLEX in modo da ottenere una soluzione subottima con un
carico computazionale minore.
Per quanto riguarda il secondo problema è stato implementato un algoritmo
in Matlab che riduce la dimensione della rete basato sul fatto che non tutti
i nodi sono in grado di raggiungere gli utenti obbiettivo nell’orizzonte temporale prefissato.
Il terzo problema non è stato oggetto di alcuna ottimizzazione ma è stato comunque
implementato in linguaggio OPL per completare
il set di strumenti software per l’analisi della diffusione dell’innovazione nei
social networks.
back