Indietro

ⓘ Densità di un grafo




                                     

ⓘ Densità di un grafo

Sia definito il grafo G= come coppia dei due insiemi N:={1.2.3.,n} ed A sottinsieme del prodotto cartesiano N×N. N sarà linsieme degli n nodi che compongono il suddetto grafo e A linsieme degli archi.

  • sia n la cardinalità di N ovvero il numero dei nodi di un dato
  • sia L la cardinalità di A ovvero il numero degli archi dello stesso grafo

Se le coppie di nodi si considerano ordinate il grafo è detto orientato o digrafo, altrimenti non orientato o semplice. Il grafo è detto pesato se ad ogni arco è associato un peso o costo.

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

Δ = 2L / nn-1

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

Δ = L / nn-1

Nel caso di grafi pesati ad L occorre sostituire la sommatoria dei pesi di ciascun arco.

La densità di un grafo assume valori compresi tra 0 ed 1 e pertanto si può ricollegare facilmente al concetto di probabilità. La densità di un grafo misura la probabilità che una qualsiasi coppia di nodi sia adiacente, mentre la connessione di un grafo dipende dalla distribuzione degli archi tra i nodi.

Un grafo disconnesso può avere densità maggiore di uno connesso a causa della concentrazione degli archi tra un ristretto numero di nodi.

                                     

1. Esempi

Grafi completi non orientati

Si abbia un grafo completo non orientato K n {\displaystyle \,K_{n}} con n =1.2.3.,8.

La densità del grafo completo monopartito K n {\displaystyle K_{n}} è sempre pari ad uno.

Grafi bipartiti

Supponiamo di considerare il seguente grafo non orientato ciclico detto grafo bipartito. È possibile facilmente verificare che la sua densità è circa uguale a 0.28.

                                     

2. Applicazione alle reti sociali

Un gruppo di individui tra cui esistano o meno delle relazioni è rappresentabile matematicamente attraverso un grafo. Anche più gruppi di individui sono schematizzabili in egual maniera.

In generale:

  • Diversi attori entità sociali instaurano o meno tra loro delle relazioni.
  • Le relazioni possono essere di tipo emozionale
  • Gli attori non coincidono necessariamente con le singole persone, ma possono essere enti, città, nazioni, ecc.

oppure possono esprimere connessioni fisiche ponti, strade o ancora trasferimenti di risorse. La densità nel grafo che rappresenta una rete sociale può essere un parametro che rappresenta lefficienza nello scambio di informazioni e lutilità per i singoli individui. Nelle opere di Mark Granovetter inoltre è evidenziato come reti piccole e dense possono essere meno utili di reti costituite da legami deboli, perché queste ultime sono più flessibili prestandosi quindi a un miglior scambio di idee e opportunità.

                                     

3. Riferimenti

  • I. Streinu e L. Theran, Sparse hypergraphs and pebble game algorithms, in European Journal of Combinatorics special issue for Oriented Matroids 05, 2008, arΧiv:math/0703921.
  • Bruno Preiss, Data Structures and Algorithms with Object-Oriented Design Patterns in C++, John Wiley & Sons, 1998, ISBN 0-471-24134-2.
  • Thomas F. Coleman e Jorge J. Moré, Estimation of sparse Jacobian matrices and graph coloring Problems, in SIAM Journal on Numerical Analysis, vol. 20, nº 1, 1983, pp. 187–209, DOI:10.1137/0720013.
  • Reinhard Diestel, Graph Theory, Graduate Texts in Mathematics, Springer-Verlag, 2005, ISBN 3-540-26183-4, OCLC 181535575.
  • Paul E. Black, Sparse graph, from Dictionary of Algorithms and Data Structures, Paul E. Black ed., NIST. Retrieved on 29 September 2005.