Capitolo 3. Il grafo come modello della conoscenza
3.2. Alcune strutture a grafo notevoli
3.2.1. Le principali proprietà dei grafi reali
A partire dalla fine degli anni ‘90 alcuni ricercatori hanno evidenziato che le reti sociali sono, come molte altre reti reali (per esempio Internet e il Web, ma anche le reti neurali, o quelle metaboliche e delle proteine), “grafi complessi” poiché mostrano una struttura irregolare, che si evolve nel tempo e che è “a più dimensioni”. L’interesse focale degli studi si è dunque spostato nell’ultimo ventennio alle reti che presentano migliaia o milioni di nodi, che sono composte da unità dinamiche, e i cui archi possono essere anche paralleli. Differenti “dimensioni” possono rappresentare, per esempio, diversi tipi di relazione (amicizia, parentela, interessi comuni, ecc.), op-pure diversi valori (pesi) dello stesso tipo di relazione (come per esempio la collabo-razione in diverse conferenze). Due articoli hanno dato inizio a questo filone di ricer-ca: il primo, quello di Watts and Strogatz sulle reti cosiddette “small world”, pubbli-cato sulla rivista Nature nel 1998; il secondo, di Barabási and Albert sulle reti “scale free”, apparso un anno dopo sulla rivista Science.131 L’interesse per le reti complesse è stato certamente alimentato dalle accresciute capacità di calcolo dei moderni compu-ter e dalla possibilità di studiare le proprietà di una grande quantità di ricchi database di reti reali. L’analisi sistematica e comparativa delle reti appartenenti a campi differenti ha prodotto una serie di risultati inattesi e degni di nota, e per questi si rimanda alla descrizione informale presente nel già citato libro di Barabási.132
La ricerca sui sistemi complessi ha inizialmente cercato di definire nuovi con-cetti e nuove misure per descrivere e caratterizzare la struttura delle reti reali: fra le altre, la distribuzione del grado dei nodi, la connettività, la centralità e il diametro del grafo. Comunque il risultato principale è stato sicuramente l’identificazione di una serie di proprietà comuni alla maggior parte delle reti considerate. La prima, già
131 Steven Strogatz, “Exploring Complex Networks.” Nature 410 (2001): 268-276. Duncan J. Watts, Steven Strogatz, “Collective dynamics of 'small-world' networks.” Nature 393 (1998): 440-442. Albert-László Barabási, Reca Albert, “Emergence of Scaling in Random Networks.” Science 286 (1999): 509-512.
ta, è quella di “mondo piccolo” che sorprendentemente si applica anche a sistemi completamente diversi dalle reti sociali fin qui descritte, quali ad esempio: i sistemi di trasporto in cui il grafo è formato da città e località turistiche collegate da strade, ferrovie, collegamenti marittimi e aerei; i sistemi biologici quali le reti di proteine do-ve i nodi sono differenti proteine presenti nel nucleo della cellula e gli archi sono in-terazioni proteiche;
i
sistemi ecologici, quali le catene alimentari dove i nodi sono le differenti specie presenti in un ecosistema e gli archi sono le predazioni.Un’altra proprietà rilevante riguarda la distribuzione del grado dei nodi, vale a
dire il numero di archi incidenti in ciascuno di essi: molte reti complesse soddisfano
la proprietà di essere “scale free” e quindi reti in cui i vertici hanno un grado che se-gue una legge a potenza, della forma f(d)=c/dx. Questa formula indica con f(d) il nu-mero di nodi della rete che hanno d archi incidenti; x è invece un parametro caratte-ristico della rete (tipicamente intorno a 1.5 nel caso del Web), e c è un fattore di nor-malizzazione che garantisce che la somma dei valori di f(d), su tutti i possibili gradi d, sia uguale al numero di nodi della rete. Quindi in questi grafi ci sono c nodi di grado 1 (ossia f(1)), c/2x nodi di grado 2 (ossia f(2)), c/3x nodi di grado 3, ecc.. La caratteristi-ca più interessante della funzione f(d) è che ci saranno pochi nodi con un grado molto elevato, e moltissimi nodi con un grado piccolo. Questo implicitamente dimostra che queste reti, pur essendosi formate in modo “distribuito” e “anarchico”, non sono “ca-suali” altrimenti tutti i nodi avrebbero un grado pressoché identico.
A prima vista questa formula può apparire del tutto astratta, e scorrelata dalle ca-ratteristiche delle varie reti su menzionate. Ma sorprendentemente una sua analisi attenta ci permette di giungere a delle conclusioni che sarebbero state di difficile de-rivazione se non si fosse proceduto a una rappresentazione di queste reti tramite ap-punto i grafi. Infatti, la forma di f(d) ci fa concludere che nelle reti scale-free la stra-grande maggioranza dei nodi ha un grado molto piccolo, mentre esistono pochi nodi detti hub che hanno un grado molto elevato; a ciò si aggiunga che i nodi di grado pic-colo occorrono in sotto-grafi estremamente densi e questi sotto-grafi sono collegati tra loro tramite i nodi hub.
Figura 3.10 Distribuzione del numero di nodi di grado k in una rete scale free. La scala è logaritmi-ca su entrambi gli assi e, quindi, la distribuzione segue un andamento lineare.
Questa struttura parzialmente gerarchica ha una profonda influenza, per esem-pio, sulla robustezza della rete Internet rispetto ai fallimenti casuali dei suoi compu-ter, proprietà questa fondamentale per garantire che il mal funzionamento di un solo computer non infici la connettività, e quindi l’utilizzabilità, dell’intera rete. Infatti un fallimento casuale coinvolgerà con elevata probabilità un nodo di grado piccolo e quindi un nodo che può essere facilmente “sostituito” da un altro nodo nel suo sotto-grafo denso di appartenenza.
È interessante notare che questa stessa struttura porta a conclusioni diverse se la rete in esame è una rete sociale o il Web. Nel primo caso i sotto-grafi densi rappre-sentano comunità di utenti fortemente connessi tra loro, e quindi con evidenti affini-tà; la loro individuazione risulta cruciale se si vogliono studiare le caratteristiche di queste comunità per propositi sociali o di pubblicità. Nel caso del Web gli hub costi-tuiscono i nodi dai quali i motori di ricerca fanno partire la visita del grafo (cosiddet-to crawling o spidering) per l’individuazione delle pagine interessanti da indicizzare e quindi restituire come risultati delle ricerche degli utenti. Conoscere gli hub vuol di-re ridurdi-re il tempo richiesto per il crawling del Web, e quindi l’aggiornamento delle informazioni disponibili all’interno di un motore di ricerca.
Figura 3.11 La struttura a “farfallino” del Web.
L’analisi del grafo del Web ha portato a dimostrare tante altre proprietà sorpren-denti, la più interessante è sicuramente quella riportata nel lavoro pubblicato nel 1999 e svolto da tre gruppi di ricercatori americani afferenti a tre importanti aziende del settore informatico: IBM, Altavista e Digital.133 In questo lavoro si analizzava la struttura connettiva di un sotto-grafo del Web formato da circa 200 milioni di pagi-ne, e si dimostrava che questo aveva la forma di un “farfallino”, come riportato nella Figura 3.11, consistente di 5 componenti principali denominate IN, OUT, CORE, Ten-tacoli e Isole. Le prime quattro componenti risultavano pressoché della stessa dimen-sione, pari a circa 40-50 milioni di pagine, la quinta componente consisteva di circa 17 milioni di pagine sconnesse dal resto della rete. La definizione delle componenti era abbastanza intuitiva: IN e OUT consistevano di pagine Web possibilmente con-nesse tra loro che potevano condurre a, o erano la destinazione di, pagine del CORE; i Tentacoli erano sequenze di pagine che non passavano dal CORE del Web e connet-tevano possibilmente pagine di IN con pagine di OUT; il CORE era un agglomerato di pagine fortemente connesse tra loro. Le pagine hub menzionate precedentemente
133 I riferimenti più significativi sono i seguenti: Ravi Kumar et al., “Trawling the Web for Emerging Cyber-Communities.” Computer Networks 31 (1999): 1481-1493. Ravi Kumar et al. “Random graph models for the Web graph.” In Proceedings of the IEEE Symposium on Foundations of Computer Sci-ence (2000): 57-65.
fanno parte del CORE. La conoscenza di questa strutturazione del Web, confermata più volte da studi compiuti successivamente e su sottografi di dimensione maggiore, ha avuto delle conseguenze importanti nella progettazione dei motori di ricerca. In aggiunta a quanto anticipato precedentemente, questa struttura suggerisce che il crawling del Web dovrebbe evidentemente partire non soltanto dagli hub presenti nel CORE, ma anche da pagine dell’IN. Infatti, la non indicizzazione delle pagine pre-senti nell’IN porterebbe il motore “a perdere” circa un quarto di tutto il Web, con conseguente limitatezza nella quantità e possibilmente qualità delle risposte restitui-te alle inrestitui-terrogazioni degli urestitui-tenti. Sarebbe facile trovare una pagina dell’IN se quesrestitui-te potessero essere campionate a caso, poiché 1 pagina su 4 ricade in quella zona (44 milioni sul totale di 200 milioni), ma effettuare campionamenti casuali di pagine Web è un problema difficile e ancora non totalmente risolto. Né d’altra parte basta generare una stringa a caso e usarla come URL della pagina di cui verificare l’appartenenza a IN, perché non tutte le stringhe corrispondono a una URL, inoltre più stringhe possono corrispondere alla stessa URL. Per questa ragione non è facile a tutt’oggi partire da pagine dell’IN e quindi garantire una efficace copertura del grafo del Web. Questo è senz’altro un altro esempio di problema scientifico interessante o-riginato dall’analisi della struttura di un grafo, quello del Web appunto.
D’altra parte esistono numerosi esempi di grafi originati da strutture che apparen-temente non hanno la forma di una rete, come invece risulta evidente da quelle citate precedentemente. Si consideri per esempio una pagina Web, scritta nel linguaggio HTML: essa consiste di un contenuto testuale e di una serie di tag che codificano me-ta-informazioni utili per la visualizzazione della pagina (quali titolo, tabelle, font, co-lori, ...). Questi tag hanno una struttura “innestata”, ossia sono disposti all’interno della pagina Web in modo tale che ciascuno sia contenuto in un altro. Tutto ciò de-termina una relazione di discendenza che è propria delle strutture gerarchiche ad albero. La figura che segue indica in modo pittorico sia la struttura ad albero libero che si deriva analizzando la pagina principale di Wikipedia, sia la natura dei nodi che vengono colorati in base al tipo di tag a cui corrispondono: ad esempio, il blu corri-sponde agli hyper-link (quindi il tag A), il rosso alle tabelle, il nero al tag HTML radi-ce del documento. È interessante notare che il grafico risultante è particolarmente in-formativo sulla strutturazione della pagina sia in termini di innestamento dei tag sia in termini di distribuzione e varietà dell’informazione codificata in essa. Un’analisi di
questo tipo, effettuata sulle pagine contenute in un sito, potrebbe permettere a un progettista di pagine Web di derivare indicazioni sulla complessità del sito da lui progettato e quindi sull’efficienza di indicizzazione dei motori di ricerca per i suoi contenuti.
Figura 3.12 Codice sorgente della pagina principale di Wikipedia modellato come un albero libero, i cui nodi sono colorati in base al tipo di tag HTML che rappresentano.
Il paragrafo che segue illustrerà altri due esempi particolarmente significativi di grafi sintetici, ossia originati da strutture che non hanno la forma di una rete.