I grafi – la matematica delle relazioni ? ( cenni introduttivi )

Voglio scrivere un articoletto per dare alcune nozioni sui grafi, visto che nei post precedenti ho parlato di collaborazione, amicizia, follower, collaboratori ed altro.

Ma che relazione c’è fra grafi ed interazioni sociali ?

Nessuna ?

A dire il vero NO: i grafi sono uno strumento ottimo per rappresentare le relazioni all’interno di un gruppo ( di individui, di ditte, di società, di scambi economici, di reazioni chimiche, di scambi gravitazionali, di interazioni quantistiche… ) basta selezionare il gruppo e l’interazione che si vuole rappresentare. A quel punto un grafo ci aiuta a capire a vedere in modo chiaro quello che prima era nebuloso.

Ma cosa è un grafo ? Santa Wikipedia recita:

“I grafi sono strutture matematiche discrete che rivestono interesse sia per la matematica che per un’ampia gamma di campi applicativi.”

Molto rigoroso, ma ai profani questo dice ben poco. Un grafo è una “cosa” che può essere rappresentata da un grafico, ma non è solo un grafico: è una struttura informativa composta di 2 sotto gruppi connessi fra loro: i “nodi” ed i “collegamenti” [in alcune diciture si può trovar scritto “vertici” ed “archi” oppure “nodes” e “link” oppure “nodes &hedges” ma sono nomi diversi per indicare le solite cose.] Nelle figure sottostanti ( credits Wikipedia ) illustriamo alcuni grafi.

Grafo 1 ( esempio )

Grafo 2 ( caso reale )

A sinistra un semplice grafo.

A destra la rappresentazione ( reale ) della interconnessione di alcun siti web.

Come si può facilmente vedere la complessità di un grafo può essere estremamente elevata

Oa vediamo di porci alcune domande che ci consentano di chiarire cosa e’ un grafo.

Cosa è un nodo?

Sostanzialmente è un “record” ( dicendolo banalmente: una riga di un foglio di calcolo)  in cui devono esistere almeno le seguenti informazioni

  • ID ( un numero sequenziale che va da 1 a….. )
  • Etichetta ( ad esempio il nome del nodo )
  • Dimensione del nodo ( quanto grande deve essere rappresentato )

Quando non esplicitamente richiesto queste grandezze possono essere vuote ( nel caso dell’etichetta ) oppure impostate ad 1 o ad un altro valore di comodo ( la dimensione del nodo ). Opzionalmente al nodo possono essere associate altre informazioni, tipo ad esempio la posizione, un colore di rappresentazione, un hiperlink, una immagine ed altro, ma comunque restano “opzioni” usate più che altro in fase di realizzazione di un programma che utilizzi i grafi per degli scopi applicati al caso concreto.

Cosa è un collegamento ?

Un collegamento è un segmento, un arco ( una linea è un particolare segmento, che ha la proprietà di essere rettilineo ) che collega 2 nodi. Anche il collegamento è un record, come il nodo, ma le informazioni che contiene sono diverse:

  • ID ( un numero sequenziale che va da 1 a….. – non e’ lo stesso numero rappresentato nel campo ID del nodo )
  • Punto di Partenza
  • Punto di Destinazione
  • Etichetta
  • Verso
  • …..

Esiste un solo tipo di grafo ?

No, esistono diversi tipi di grafi, che vengono classificati in base alle loro proprietà topologiche :  i primi 2 tipi di grafo che cominciamo a considerare sono i grafi semplici ed i grafi orientati. Nei secondi il collegamento presente fra due nodi ha un “verso di percorrenza” – se fossimo in presenza di una strada, questa strada sarebbe a senso unico. Si puo’ pensare dal nodo A a quello B ma non viceversa. Un esempio di grafo orientato è il seguente

Il grafo semplice è un grafo che non presenta questa direzionalità nei collegamenti fra nodi. Come si puo’ vedere da questo esempio a seconda del punto di partenza si puo’ andare a raggiungere certi nodi come destinazione e certi altri NO.

Grafici diversi corrispondono allo stesso grafo ?

Si, e’ possibile per alcuni grafi avere rappresentazioni equivalenti, spostando i nodi e mantenendo i collegamenti fra i nodi stessi.

Un grafo come questo rappresentato nell’esempio viene detto grafo planare, perchè ha la “gradevole” proprietà che spostando un nodo  posso fare in modo che i collegamenti non si intreccino. Ma esistono altri grafi, tipo quello di seguito ( a stella ), per cui ciò non e’ possibile.

Per questo motivo questo grafo e’ detto “non planare“. Esistono intere classi di grafi non planari. Chi fosse interessato a vederli puo’ guardare il link seguente: “Grafi non planari” (in inglese, credits MathWorld.Wolfram.com)

Un’altra cosa che possiamo dire dei grafi è la seguente: esistono due classificazioni di grafi basati su un’altra proprietà. Nelle tre figure riportate sopra abbiamo rappresentato dei grafi in cui tutti in nodi sono “connessi” agli altri da almeno un collegamento,tipo quello sotto.

Grafo connesso

Ma se immaginiamo che nel grafo ( visto che il grafo non è solo un grafico, ma una struttura informativa composta da nodi e collegamenti ) ci siano nodi che non siano connessi con tutti gli altri allora parleremo di grafo NON connesso. Una definizione rigorosa di grafo connesso puo’ essere quella riportata da wikipedia:

In teoria dei grafi, un grafo G = (V, E) è detto connesso se, per ogni coppia di vertici (u, v) ∈ V, esiste un cammino che collega u a v[1]. Un sottografo connesso massimale di un grafo non orientato è detto componente connessa di tale grafo. Di conseguenza, un grafo è connesso se esso è composto di una sola componente connessa.

oppure

Un grafo G si dice connesso se due suoi vertici qualsiasi sono connessi in G, cioè se sono collegati da un cammino. Si dice componente connessa di un grafo G un sottografo connesso massimale di G, cioe’ un sottografo di G che sia connesso e non sia propriamente contenuto in un sottografo connesso di G.

Di seguito un esempio di un grafo connesso (a sinistra)  ed uno non connesso (a destra).

Un altro grafo particolare è il cosiddetto “albero“, di cui Santa Wikipedia ci da una efficace definizione:

In teoria dei grafi un albero è un grafo non orientato nel quale due vertici qualsiasi sono connessi da uno e un solo cammino (grafo non orientato, connesso e privo di cicli).

Un tipico esempio do grafo ad albero è il cosiddetto “albero genealogico”  che non serve solo a “mappare” i legami di parentele familiari, ma anche a descrivere come si evolvono mode, stili musicali, relazioni sociali politiche ed economiche e tanto altro. Di seguito 2 esempi: il primo è l’albero genealogico della famiglia Romanov, il secondo  è l’albero genealogico di alcuni generi musicali ( strano vero ? ma i grafi si possono usare anche in questo campo 😉 )

Se qualcuno volesse approfondire l’argomento a livello teorico puo’ andare a vedere la pagina “Teoria dei grafi

Ora, torniamo a quanto ho scritto all’inizio: parlero’ dei grafi perchè nei post precedenti ho parlato di relazioni sociali,  follower, collaborazione ed altro.

Consideriamo l’ultimo grafico ( ovvero quello dell’albero genealogico della musica Punk/Metal – prendiamo per buono che rappresenti corrattamente ed esaustivamente le relazioni fra le varie correnti ). Cosa abbiamo qui ? Abbiamo svariati nodi che rappresentano le varie correnti musicali del genere. Il posizionamento ( alto – basso ) indica la sequenza temporale con cui queste correnti si sono evolute. I rami rappresentano quali correnti/generi hanno infuenzato/generato i successivi. Si può vedere quale dei generi è stato piuù prolifico e quale meno:

lo Heavy Metal, pur non derivando direttamente dal punk ( non ci sono archi fra “punk” ed “heavy metal” ) ha avuto ben 5 derivazioni, due dirette (Doom e Speed) e tre di “seconda” generazione (power, gotich e trash). Due di queste si sono ibridate direttamente o indirettamente con discendenti dal punk (Gothic Metal e Trash Metal). Il primo di questi, però è rimasto “sterile”, il secondo invece ha generato quattro “figli” di cui 3 “puri” (Death, Black e Groove Metal) ed uno che e’ nato da una ulteriore ibridazine con lo Hardcore (Grindcore).

Semplicemente con un colpo d’occhio si puo’ vedere che fra i “discendenti” dello Heavy Metal quelli piu’ “punk” sono il Gothic Metal ed il Grindcore. Questo si puo’ dire in quanto se definiamo come “distanza” il numero di “nodi” che attraversiamo per andare dal “genitore” al “discendente” per entrambi abbiamo solo un “nodo” inframesso.

Nota bene: la distanza che definiamo in questa occasione è un altro tipo di distanza rispetto a quelle di cui abbiamo parlato nei post precedenti ( “Scusi… quanto dista?” e “Scusi… quanto dista? – 2”  ), ma con la stessa identica validità di utilizzo.

Giunto a questo punto, penso sia bene fermarsi un po’ riguardo all’argomento “grafi”, ma lo riprenderò in altri post, in cui ( spero presto ) cercherò di  spiegare come farne uno utilizzando uno dei tenti software gratuiti ed open source a disposizione sulla rete.

Ma prima di terminare questo post…….


…a puro titolo di esempio, allego a questo post un grafo REALE rappresentante lungo l’asse verticale di sinistra il tempo medio ( per paese ) trascorso collegati ad un sito che fa sharing di filmati  mentre a destra abbiamo il numero di ricerche effettuate in ordine decrescente. Il grafo di seguito è il classico esempio di un grafo “non orientato”, “non connesso” e non “planare”

Tali risultati potrebbero essere tranquillamente rappresentati sotto forma di tabella numerica, ma in questo modo ( come grafo ) abbiamo una visione d’insieme chiara e sintetica, e non solo dal punto di vista matematico. 🙂

Lascio a Voi il divertimento di interpretarlo in base a quanto ho scritto sopra 😉

E se qualcuno, oltre a qualche considerazione logico matematica fosse in grado di trarre qualche conclusione sociale sarei ben lieto di sentire a quali conclusioni è giunto 😉

Annunci

9 pensieri su “I grafi – la matematica delle relazioni ? ( cenni introduttivi )

  1. Domanda sui grafi non connessi: se, come nell’esempio della figura “H:” sopra, c’è un nodo non connesso al resto del grafo, che senso ha dire che appartiene comunque al grafo?
    Io (forse per deformazione professionale…) lo vedo semplicemente come un elemento esterno che non ha influenza o non ha un ruolo nel processo schematizzato.

    @Alkimias: direi che siamo un continente di segaioli, e che il genere “a**l” va per la maggiore… (maschero la parola per evitare a Num3ri flussi di spam, lo dico per esperienza)

    • Bhe, me lo son sempre giustificato cosi’: il grafo si costruisce da dati preesistenti ad esempio l’insieme delle persone che frequentano un circolo, e poi si tracciano le relazioni esistenti fra loro, ad esempio chi gioca a briscola con qualcu altro. In questo caso il nodo isolato potrebbe rappresentare un bembro del circolo che non gioca, ma magari sta solo a guardare….
      Spero di non aver preso una cantonata inventandomi questa spiegazione 😀

      • La logica mi sembra corretta, però perché non “cancellare” il nodo isolato dal grafo una volta stabilito che non ha connessioni? Aggiunge informazioni a quelle già veicolate dal grafo? È come se scrivessi nella ricetta di una torta gli ingredienti da NON usare insieme a quelli da usare. Non è che per caso la fig. H rappresenta semplicemente 3 grafi distinti?

      • quello di eliminare un nodo e’ una cosa che puoi fare a posteriori, ad esempio per rappresentare solo coloro che giocano effettivamente a carte all’interno del circolo.
        la presenza di nodi disgiunti indica la effettiva numerosità dei frequentatori del circolo stesso.

        Si puo’ dire che h rappresenta tutta la popolazione, e si vede che in questa ci sono 3 gruppetti che non interagiscono fra loro…. un po’ come dei siti web che non sono mutuamente linkati ma appartenenti tutti allo stesso provider, come compare nel grafo 2 ( in blu all’inizio pagina )

  2. Pingback: Le Reti Sociali | Num3ri v 2.0

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...