DidaWiki

Questa pagina è in sola lettura. Puoi visualizzare il sorgente, ma non puoi modificarlo. Contatta l'amministratore se pensi che ci sia un errore.
===== Progetto di ASD, anno accademico 2017/18 =====

Questo progetto sostituisce l'esame scritto del corso o il seminario, e non necessita la presentazione del mini-progetto. Quest'anno sono disponibili due progetti su grafi, di cui ne va scelto uno. 

In entrambi i progetti, ciascun grafo di input è memorizzato in un file testuale nel seguente formato: la prima linea contiene due interi separati da uno spazio: il numero N di vertici e il numero M degli archi del grafo; le M linee successive contengono ciascuna una coppia di interi I e J separati da uno spazio, a indicare che l'arco (I,J) appartiene al grafo (ignorare i self-loop del tipo I I).  
 
==== Progetto 1 ====

Questo progetto utilizza la rete NetInf come grafo (preso da http://snap.stanford.edu/netinf/), i cui nodi rappresentano siti web di informazione e gli archi sono orientati e indicano chi ha copiato chi. Inoltre sono disponibili i ranking di tali siti, forniti dal servizio Alexa di Amazon (https://www.alexa.com). Utilizzando queste informazioni, occorre definire una nozione di similitudine tra i nodi del grafo, utilizzando soltanto la struttura del grafo (nodi e archi) e il ranking dei nodi. Per verificare se il risultato ottenuto ha senso, si può successivamente guardare il nome del sito e l'eventuale contenuto sul web.

  * Dati da scaricare: {{ :matematica:asd:asd_17:netinf.zip |}}
  * Lettura consigliata (scaricabile dal dominio unipi.it): https://www.sciencedirect.com/science/article/pii/S037843711000991X


==== Progetto 2 ====

Questo progetto utilizza reti sociali come grafi in input (presi da http://snap.stanford.edu/). Lo scopo è quello di definire una nozione di comunità (ossia un grafo coeso, in cui i nodi sono più collegati tra di loro che rispetto agli altri). Esempi noti sono le clique, k-plessi, quasi-clique, k-core, ecc. Definizioni originali introdotte nel progetto sono apprezzate. Scelta una nozione, occorre progettare e implementare un algoritmo efficiente per identificare tali comunità all'interno della rete.

  * Dati da scaricare: http://snap.stanford.edu/data/
  * Letture consigliate: https://arxiv.org/pdf/0906.0612.pdf, http://www.faculty.ucr.edu/~hanneman/nettext/C11_Cliques.html


==== Conversione di formati ====

Per convertire il formato testuale dei grafi (essendocene diversi), è possibile usare il seguente comando

<code>gutil convert input.nde output.oly</code>

È possibile scaricarsi l'eseguibile (compilato per Linux e Mac OS X) oppure compilarsi il sorgente (da github dove c'è anche il readme):

  * {{ :matematica:asd:asd_17:gutil.zip |gutil eseguibile}}
  * [[https://github.com/veluca93/graph_utils|gutil sorgente]]