Centralità di Influenza Armonica su networks di larga taglia: calcolo esatto ed approsimato

In questa tesi studiamo una innovativa misura di centralità sui networks, che emerge naturalmente nel contesto della diffusione di opinioni in presenza di agenti ¿testardi¿ (stubborn), la Harmonic Influence Centrality (HIC). Questa misura quantifica l'influenza a lungo raggio di un agente sulla opinione asintotica media dell'intero network. Il nostro modello di influenza sociale caratterizza la dinamica di formazione delle opinioni in un network costituito sia da agenti regolari che aggiornano la loro opinione in base alle informazioni che ricevono dai loro vicini, sia da agenti stubborn che mantengono una opinione fissata, uguale a zero od a uno (da cui il nome: agenti di tipo zero e agenti di tipo uno). Consideriamo il caso particolare del modello dove è presente un set fissato di stubborn agents di tipo zero ed un singolo stubborn agent di tipo uno. Dunque la Harmonic Influence Centrality fornisce una risposta precisa al problema del ¿posizionamento ottimo dello stubborn agent¿ (OSAP problem) dove la posizione dell'agente di tipo uno è scelta in modo da massimizzare la sua influenza sulle opinioni asintotiche degli agenti regolari. Usando una intuitiva analogia tra networks sociali ed elettrici, introduciamo una algoritmo centralizzato per la soluzione esatta dell'OSAP problem, in cui caratteriziamo la HIC in termini della matrice di Green associata al network elettrico considerato. Mostriamo inoltre, sia teoricamente, sia tramite un elevato numero di simulazioni che il nostro algoritmo ha una complessità computazionale molto minore dell'algoritmo recentemente proposto in [32] da Yildiz and Acemoclu. In seguito analiziamo degli algoritmi decentralizzati in cui ciacun agente calcola la propria HIC sulla base soltanto di infomazioni locali. Presentiamo il message passing algorithm recentemente proposto in [26] da Fagnani e Vassio per il calcolo della HIC e che lavora con un approccio parallelo e distribuito. Nonostante fosse originariamente costruito per lavorare sugli alberi, l'algoritmo può essere utilizzato anche sui networks in generale. In questo caso ciascun nodo calcola ad ogni iterazione un valore approssimato della sua HIC. Tuttavia la presenza di cicli può abbassare il livello di approssimazione. Andiamo infine a proporre una versione modificata del precedente message passing algorithm con lo scopo preciso di ridurre le problematicità introdotte dalla presenza di cicli e mostriamo, tramite numerose simulazioni, che l'algoritmo proposto ha una dinamica di convergenza molto più rapida e, in molti casi, riesce anche a calcolare le HICs in modo più accurato.

In this thesis we study an innovative measure of centrality on networks, which emerges naturally in the context of opinion dynamics in presence of stubborn agents, the Harmonic Influence Centrality. This measure quantifies the long-run influence of a node on the average asymptotic opinion of the global network. Our model of social influence characterizes opinion dynamics in a network consisting of regular agents who update their opinions according to information that they receive from their social neighbors and stubborn agents who hold a fixed opinion equal to zero or one (i.e., type zero and type one stubborn agents) . We consider a special case of this model wherein a fixed subset of the agents are type zero stubborn agents and a single agent is the type one. Therefore the Harmonic Influence Centrality provides a precise answer to the problem of the ¿optimal placement of a stubborn agent¿ (OSAP problem) where the location of the type one stubborn agent is chosen to have the maximum impact on the long-run opinions of agents. Using an intuitive analogy between social and electrical networks we introduce a centralized algorithm to solve OSAP problem, which characterizes the HIC in terms of the Green matrix associated to the electrical network. We show through extensive simulations that our algorithm outperforms the centralized algorithm recently proposed in [32]. Then we consider decentralized algorithms whereby each agent computes its own Harmonic Influence Centrality based on local information. We present the message passing algorithm recently proposed in [26] to compute the HIC which runs in parallel and distribuited way. Although originally designed for trees, the algorithm can be employed in general networks where each agent can compute at every time step an approximate Harmonic Influence Centrality. However the presence of a large number of cycles may worses the computed approximation. We propose a modified version of the previous algorithm with the precise purpose of reducing the issues caused by the presence of cycles and we show, through extensive simulations, that the proposed algorithm exhibits a much faster dynamics than the original algorithm and, in many cases, computes the Harmonic Influence Centrality with more accuracy.