In nature we never see anything isolated, but everything in connection with something else which is before it, beside it, under it and over it. – Johann Wolfgang von Goethe

Che cos’è la densità di un grafo?

La densità di un grafo è un valore che rappresenta quanto le entità di un grafo sono interconnesse tra di loro. Questo indice quindi mette a confronto il numero dei nodi (n) e il numero degli archi (L).

La densità di un grafo non orientato è definita come:

Δ = 2L / n(n-1)

La densità di un grafo orientato è definita come:

Δ = L / n(n-1)

Esiste un pagina di Wikipedia sull’argomento.

Il valore varia tra 0 e 1. Dove:

  • 0 rappresenta un grafo totalmente scollegato, senza interconnessioni tra i nodi; di fatto un non-grafo.
  • 1 rappresenta un grafo ad alta densità in cui tutti i nodi sono collegati a tutti gli altri nodi; il grafo in questione è detto grafo completo.

Densità di un grafo tramite query SPARQL

In questo post prenderò come caso d’uso un grafo RDF (è un grafo orientato!) e utilizzando alcune query SPARQL vi mostrerò come si possa calcolarne la densità. Procedendo per gradi, spezziamo il problema in due, cercando prima di ottenere il numero dei nodi e quello degli archi. Le query che seguono sono generiche, possono infatti essere utilizzate su un qualunque grafo RDF.

Numero dei nodi unici di un grafo

SELECT (COUNT (DISTINCT ?vertex) as ?nVertex)
WHERE {
  {
    ?vertex ?p []             # tutti i vertici nella posizione di soggetto
  }
  UNION
  {
    [] ?p ?vertex             # tutti i vertici nella posizione di oggetto
    FILTER(IsURI(?vertex))    # solo entità, non literals
  }
}

Questa query SPARQL conta il numero di nodi (o vertici, che dir si voglia) di un grafo, cercandoli sia nella posizione di soggetto sia in quella di oggetto. Il DISTINCT poi collasserà i duplicati. L’uso della variabile anonima [] è volto a evidenziare il fatto che l’oggetto della prima parte di query e il soggetto della seconda non ci interessano. Il filtro è applicato solo nella seconda sezione perché nella posizione di oggetto può esserci anche un literal, mentre in quella di soggetto è data, per costruzione, la presenza di un’entità provvista di URI.

Numero degli archi di un grafo

SELECT (COUNT(*) AS ?nEdges) { ?s ?p ?o }

Si tratta certamente di una query SPARQL più nota. Infatti calcolare il numero di archi di un grafo è calcolarne il numero di triple. Non si tratta dunque di conoscere quali sono i predicati distinti, analisi spesso utile per determinare l’ambito di un grafo, ma proprio ogni arco tracciato, e quindi ogni istanza di tutti i predicati. Un sottoinsieme di questa query è il numero dei soli archi che collegano entità, decidendo di escludere le triple con oggetto un literal. Quest’ultima è quella che ci interessa ai fini del calcolo della densità.

SELECT (COUNT(*) AS ?nEdgesBetweenNodes) 
WHERE {
  ?s ?p ?o 
  FILTER (isURI(?o))
}

Calcolare la densità di un RDF

SELECT (( ?nrEdges / ( ?nrNodes * ( ?nrNodes - 1.0 ) ) ) AS ?graphDensity)
WHERE { 
  { 
    SELECT (COUNT(DISTINCT ?node) AS ?nrNodes)
    WHERE {
      { 
        ?node ?p []
      }
      UNION
      { 
        [] ?p ?node
        FILTER isURI(?node)
      }
    }
  }
  { 
    SELECT  (count(*) AS ?nrEdges)
    WHERE { 
      ?s  ?p  ?o
      FILTER isURI(?o)
    }
  }
}

Con tutte quelle parentesi graffe sembra una query molto complicata, ma è solo l’unione delle due precedentemente studiate! Nella SELECT invece puoi notare la formula della densità dei grafi orientati che abbiamo visto nel primo paragrafo.

Conclusioni

Grafi densi e grafi sparsi

Un grafo può essere denso, quando le entità presenti sono molto connesse tra loro, o sparso, nel caso in cui gli archi siano materia rara. La densità può essere un criterio per confrontare due grafi dello stesso ambito. Un grafo più sparso tuttavia non è necessariamente meno appetibile: potrebbe trattarsi di un dataset molto ricco di entità, tra loro poco “vicine”.

Densità locale

Restando però all’interno di un singolo grafo, la densità può essere utile per capire quali parti di un singolo RDF sono più connesse e quali sono più sparse. Un modo per farlo è restringere questo calcolo a dei sotto-grafi di interesse. Calcolare la densità di una porzione di grafo è facile con SPARQL, potendo aggiungere altre triple o filtri alla query di partenza, per limitare il raggio d’azione del calcolo. Ad esempio andando a specificare i nodi sui quali compiere l’analisi o limitando gli archi ad un insieme predefinito.

grafo RDF SPARQL topologia