Central nodes search with cooperative game-theory algorithm

In this thesis recent results showing that many centrality indices of nodes can be calculated in a polynomial time are presented. The classical algorithm can be applied and it would give the correct result showing the most central node in a network and the more isolated ones, but this is not affordable in a real case scenario. The big problem of applying a theoretic notion in common problem is the time computation which it takes. Classical algorithms that outputs the Shapley Value of an agent are based on simply computation based on sums that are done for every coalition present in the game. Basically, there are no difficulties in computing it, but in how much does it takes, since the coalition present in a game are exponentially in the number of the agents. Thus, the algorithm which is presented in this paper, helps finding the same value that are obtainable with the classical algorithm, but in polynomial time. This very important result makes a big step toward the resolution of high dimensional network with game theory methods since, even if the computation becomes heavier (affordable for nowadays server), the result are shown in a time that is polynomial in the number of nodes presented in the network. This result is done with two different steps: the first one is the theoretic part which includes the creation of the hypothesis which guarantee the computability polynomial and the model proof of correctness, while the second one shows the development of a python based software which allows the computation of Shapley Values on an undirected unweighted network. Summing up, this paper is divided in a mathematical part that crates the model and a computer-science one that develops it. Moreover, there are few example of an application of the following framework on two different real case scenario, which are useful to seen the correctness of this and make a comparison with the classical algorithm. In the end, there is the documentation of the software including the guide in order to explain how to use the framework for a common case. As a final remark, there are few hint on future possible work that can extend the framework efficacy. Notice that this application was thought as a starting point for the solution discovered in the mathematical model. Multiple solution based on the algorithm that is shown are possible, and this framework allows with a python hierarchy based structure a simple extension of it, just creating the preprocessing functions that are applied before the semi algorithm.

In questa tesi sono presentati risultati recenti che mostrano che molti indici di centralità dei nodi possono essere calcolati in un tempo polinomiale. L’algoritmo classico può essere applicato ottenendo un risultato corretto mostrando in una rete i nodi più centrali e quelli più isolati; tuttavia questo non è conveniente in uno scenario reale e quotidiano. Il grande problema risultante dall'applicazione di una nozione teorica ad un problema comune è il calcolo del tempo che l’algoritmo creato richiede. Gli algoritmi classici che calcolano lo Shapley Value di un agente si basano semplicemente su un calcolo composto da somme fatte per ogni coalizione presente nel gioco. Fondamentalmente non ci sono difficoltà intrinseche nel calcolo, ma nel tempo impiegato, poiché il numero di coalizioni presente in un gioco risulta essere esponenziale nel numero degli agenti. Pertanto, l’algoritmo che viene presentato in questa tesi, ci aiuta a trovare lo stesso risultato che sarebbe ottenuto con l’applicazione dell’algoritmo classico, ma in tempo polinomiale. Questo risultato molto importante fa un grande passo verso la risoluzione di reti di grandi dimensioni per mezzo di metodi provenienti da Game Theory. Infatti, anche appesantendo il calcolo (comunque abbordabile per i server o computer dei nostri giorni), il risultato è mostrato in un tempo polinomiale nel numero di nodi presenti in questa rete. Questo è ricavato fondamentalmente attraverso due diversi passaggi: il primo include la parte teorica con la creazione delle ipotesi di appartenenza ad una determinata classe al fine di garantire la polinomialità della computazione e la sua relativa prova della correttezza, mentre il secondo passaggio mostra lo sviluppo di un software basato su Python che consente il calcolo di Shapley Values su una rete non direzionata e non pesata (o binaria). Riassumendo quindi, questo tesi è divisa in due parti: una matematica creante il modello e una informatica che lo sviluppa. Inoltre, verso la fine, ci sono alcuni esempi di un'applicazione del citato framework su due diversi scenari di casi reali, utili per valutare la correttezza e l’efficienza rispetto all'algoritmo classico. La parte finale ´e dedicata alla documentazione del framework corredata di guida sull'utilizzo per un caso comune. Inoltre, ci sono alcuni suggerimenti su possibili lavori futuri in grado di estendere l’efficacia del progetto. Si noti che questo framework è stato pensato come punto di partenza per la soluzione scoperta nel modello matematico. Esistono diverse soluzioni basate sull'algoritmo che viene mostrato. In questo modo, il framework consente con una struttura basata sull'ereditarietà di python una semplice estensione, creando semplicemente le funzioni di pre-elaborazione che sono applicate prima del algoritmo polinomiale sui semivalori.