Laurea Magistrale
Obiettivi
Distribuire il campo Network presente in MASON rendendo così possibile implementare simulazioni massive basate su Grafi in D-MASON.
Metodologie
Layout Linearization
La prima metodologia applicata durante il mio percorso di tesi è stata quella del Layout Linearization mirata a ripartire un Grafo su distribuzione Horizontal in D-MASON. Questa metodologia nasce dalla fusione di due concetti già presenti nella teoria dei Grafi: Graph Drawing e Graph Layout. Dato un Grafo si applica un algoritmo di Drawing per evidenziare cluster di nodi altamente connessi ed isolarli dalla restante parte del Grafo. L'algoritmo di Drawing posiziona i vertici in uno spazio 2D o 3D che viene successivamente discretizzato e riportato su di una superficie piana. Una volta discretizzati i vertici su di un piano bisogna procedere alla linearizzazione dei vertici, ovvero passare da una superficie piana 2D ad una retta monodimensionale. Il passaggio da superficie 2D a retta monodimensionale può essere effettuato seguendo diverse strategie elencate nei paragrafi qui di seguito. I metodi di Graph Drawing esaminati sono i seguenti:
L'obiettivo principale del Layout Linearization è di ottenere linerizzazioni del grafo in cui due nodi connessi siano disposti quanto più vicino possibile. Supponiamo di avere un anello composto da 3 nodi con archi (1,2) (2,3) (3,1) e la seguente linearizzazione {1,2,3}. Lo stretch della linearizzazione {1,2,3} è pari a 1 perchè l'arco teso tra i nodi 3 e 1 passa attraverso un nodo nella linearizzazione (il nodo 2). Una linearizzazione con stretch alto rende difficile la distribuzione del Network in D-MASON dato che un Worker per comunicare dovrà attraversare più Worker per recapitare il messaggio e non solo i suoi diretti vicini.
Snake Walk
Permette il passaggio da superficie 2D a retta monodimensionale. Lo spazio 2D viene mappato all'interno di una matrice A n x m ed ogni vertice viene inserito nella cella A[i,j] se le sue coordinate nello spazio 2D hanno come parte intera della coordinata x, i e come parte intera della coordinata y, j. La matrice A viene successivamente linearizzata concatenando la riga i alla riga i+1 letta da destra verso sinistra, simulando lo stesso movimento del "serpente" nel gioco Snake, da qui il nome Snake Walk.
Hilbert Curve
Permette il passaggio da superficie 2D a retta monodimensionale. I vertici vengono linearizzati eseguendo una visita dello spazio 2D secondo la Curva di Hilbert che "riempie" completamente lo spazio.
Conclusioni
I risultati ottenuti da questa metodologia sono risultati scadenti sia in termini di performance che di stretch. Per questi motivi la metodologia Layout Linearization è stata abbandonata per procedere allo sviluppo di un nuovo approccio basato su Community Detection.
Community Detection
Al momento sono impegnano nello sviluppo di una metodologia basata su Louvain Method. Futuri sviluppi ed ulteriori dettagli saranno aggiunti in seguito.
Software
- Eclipse, what else!
- Gephi, software per gestione e visualizzazione di Grafi, Grafi Gerarchici e Dinamici.
- JGraphT, libreria gratuita Java che fornisce svariate implementazioni dell'oggetto Grafo (Directed, Undirected, Weighted, Unweighted, ecc...) ed una moltitudine di algoritmi (Floyd-Warshall Shortest Paths, Prim MST, Kruskal MST, Hamiltonian Cycle TSP, ecc...)
- Graphviz, software per la visualizzazione di Grafi.
Bibliografia
- Fast unfolding of communities in large networks, Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre, J. Stat. Mech., October 2008.
- A smart local moving algorithm for large-scale modularity-based community detection, Ludo Waltman, Nees Jan van Eck, The European Physical Journal B, November 2013.
- Finding and evaluating community structure in networks, MEJ Newman, M Girvan, Physical Review E, February 2004.
- Fast algorithm for detecting community structure in networks, MEJ Newman, Physical Review E, June 2004.
- Narrow scope for resolution-limit-free community detection, VA Traag, P Van Dooren, Y Nesterov, Physical Review E, August 2011.
- A survey of graph layout problems, J Díaz, J Petit, M Serna, ACM Computing Surveys (CSUR), September 2002.
- Graph layout using queues, LS Heath, 1989.
- Comparing Queues and Stacks As Machines for Laying Out Graphs, LS Heath, FT Leighton, AL Rosenberg, SIAM Journal on Discrete Math, 1992.
- OpenOrd: an open-source toolbox for large graph layout, Shawn Martin, W. Michael Brown, Richard Klavans, Kevin W. Boyack, Visualization and Data Analysis 2011, January 2011.
- Efficient, high-quality force-directed graph drawing, Yifan Hu, Mathematica Journal, 2005.
- ForceAtlas2, A Continuous Graph Layout Mathieu Jacomy, Sebastien Heymann, Tommaso Venturini, Mathieu Bastian, August 2012.
- Graph drawing by forcefidirected placement, Thomas MJ Fruchterman, Edward M Reingold, Software: Practice and experience, 1991.