Grafi, Reti e Connettività PDF

INFORMATICA PER LA COMUNICAZIONE Reti e grafi Reti e grafi ¨ Reti: rappresentazione di elementi e delle possibili relazioni tra elementi considerati ¤ Relazioni fisiche ¤ Relazioni immateriali ¨ Internet: rete fisica ¨ World Wide Web: rete immateriale Reti e grafi ¨ Grafi – Re...

INFORMATICA PER LA COMUNICAZIONE Reti e grafi Reti e grafi ¨ Reti: rappresentazione di elementi e delle possibili relazioni tra elementi considerati ¤ Relazioni fisiche ¤ Relazioni immateriali ¨ Internet: rete fisica ¨ World Wide Web: rete immateriale Reti e grafi ¨ Grafi – Reti: applicazioni in diversi ambiti ¤ Reti di telecomunicazioni/trasporto ¤ Alberi evolutivi ¤ Sistemi biologici ¤ Reti sociali ¤ Rete neurale ¤ … Scienza delle reti – Brevi cenni storici ¨ Nel 1741 Eulero ¤ Risoluzione del problema dei ponti di Königsberg ¤ Utilizzo tecniche di teoria dei grafi ¨ Nel 1959: modello grafi casuali (Erdos- Renyi) ¨ Nel 1999: reti a invarianza di scala/legge di potenza (Barabasi) Scienza delle reti – Brevi cenni storici ¨ A partire dalla fine degli anni ‘90: ¤ Strumenti per costruire una mappa delle reti ¤ Dati per l’analisi della struttura delle reti n Internet n Web n Piattaforme social network n Reti di proteine n… Teoria dei grafi Definizioni e applicazioni Teoria dei grafi ¨ Grafo: costituito da due tipi di elementi ¤ Nodi (punti): a, b, c, d, e ¤ Archi collegamento tra coppie di nodi: (a,e), (a,b), (b,e), (b,c), (d,e), (c,d) ¤ Due nodi a,b sono adiacenti se esiste l’arco (a,b) e d a b c Grafi non diretti In un grafo non diretto ogni arco è biunivoco e d a b c Grafi diretti ¨ In un grafo diretto ad ogni arco viene associata una direzione e d a b c Grafi pesati ¨ Peso associato a un arco: intensità della relazione tra i nodi collegati ¨ Grafi con archi pesati → grafi pesati ¨ In alcuni casi: pesi associati ai nodi e 1 d 0,6 0,5 0,5 a 0,3 1 b c Teoria dei grafi Archi incidenti nel nodo x: uno degli estremi in x ¤ Archi incidenti in a: (a,b), (a,e) ¤ Archi incidenti in b: (a,b), (b,e), (b,c) e d a b c Grado di un nodo ¨ Grado di un nodo (in un grafo non diretto): numero di archi incidenti in quel nodo ¤ Grado di a = 2 ¤ Grado di e? ¤ Grado di f? e d f a b c Grado di un nodo ¨ In un grafo diretto ¤ Numero di archi diretti verso il nodo (indegree) ¤ Numero di archi che escono dal nodo (outdegree) n Nodo b: indegree = 1, outdegree = 2 n Nodo a? n Nodo e? e d a b c Grado medio: rete non diretta ¨ In un grafo non diretto: ) 2𝐸 = ∑&() k & 𝐸= ∑&() k & * ¨ Il grado medio di una rete o di un grafo non diretto 1 2𝐸 𝑘, = / k & = N 𝑁 &() Grado medio: rete non diretta a d b c ) ) ¨ 𝐸= ∑&() k & = 8=4 * * ¨ Il grado medio di una rete o di un grafo non diretto 1 2𝐸 8 𝑘, = / k & = = =2 N 𝑁 4 &() Grado medio: rete diretta ¨ In un grafo diretto: 𝐸 = / k 4& = / k 5& &() &() ¨ Il grado medio di una rete o di un grafo diretto 1 𝐸 𝑘, = / k & =4 N 𝑁 &() Reti esistenti 𝑁 𝐸 𝑘, Da A. L. Barabasi, Network Science Distribuzione del grado ¨ Distribuzione del grado: porzione di nodi con grado k ¨ Posso considerarla come una distribuzione di probabilità ¨ Essendo una probabilità: / 𝑝7 = 1 7(8 ¨ La probabilità che un nodo abbia grado k è: 97 𝑝𝑘 = e 𝑁𝑘 = 𝑝7 𝑁 9 Distribuzione del grado Da A. L. Barabasi, Network Science Grado medio e distribuzione ¨ Considerando il grado dei nodi e la distribuzione del grado, posso definire il grado medio di una rete: 𝑘, = / 𝑖 𝑝& &(8 Grado medio e distribuzione Esercizio: Abbiamo un grafo con 5 nodi dove ogni nodo ha un grado che varia da 1 a 3. Supponiamo che i nodi siano distribuiti in questo modo: - 1 nodo ha grado 1 - 3 nodi hanno grado 2 - 1 nodo ha grado 3 - Il grado medio? Grado medio e distribuzione Soluzione: La probabilità 𝑝& di ogni grado si calcola dividendo il numero di nodi con quel grado per il numero totale di nodi. Quindi avremo: ) 𝑝) = perché c'è 1 nodo con grado 1 ; < 𝑝* = perché ci sono 3 nodi con grado 2 ; ) 𝑝< = perché c'è 1 nodo con grado 3 ; Il grado medio 𝑘, si calcola moltiplicando il grado per la probabilità corrispondente e sommando i risultati: ) < ) ) @ < 𝑘, = 1. + 2. + 3. = + + =2 ; ; ; ; ; ; Grado medio e distribuzione Esercizio: Abbiamo un grafo con 6 nodi dove ogni nodo ha un grado che varia da 1 a 4. Supponiamo che i nodi siano distribuiti in questo modo: 2 nodi hanno grado 1 1 nodo ha grado 2 2 nodi hanno grado 3 1 nodo ha grado 4 - Il grado medio? Grado medio e distribuzione Soluzione: La probabilità 𝑝& di ogni grado si calcola dividendo il numero di nodi con quel grado per il numero totale di nodi. Quindi avremo: * 𝑝) = perché ci sono 2 nodi con grado 1 @ ) 𝑝* = perché c'è 1 nodo con grado 2 @ * 𝑝< = perché ci sono 2 nodi con grado 3 @ ) 𝑝A = perché c'è 1 nodo con grado 4 @ Il grado medio 𝑘, si calcola moltiplicando il grado per la probabilità corrispondente e sommando i risultati: * ) * ) )A 𝑘, = 1. + 2. + 3. + 4. = = 2.33 @ @ @ @ @ Matrice di adiacenza Per rappresentare la topologia di un grafo: ¨ Matrice di adiacenza: matrice binaria per rappresentare presenza/assenza archi Da A. L. Barabasi, Network Science Matrice di adiacenza Da A. L. Barabasi, Network Science Grado massimo ¨ Il grado di un nodo è al più N-1 ¨ In un grafo non diretto: N(N − 1) 𝐸≤ 2 ¨ Un grafo con N(N-1)/2 archi è un grafo completo Grafo completo e d a b c Grado e reti esistenti ¨ Se tutti i link fossero presenti nella rete WWW: 5*1010 archi ¨ Nella realtà circa 15*105 archi ¨ Esistono circa 3*10-5 dei possibili archi 𝑁 𝐸 𝑘, Da A. L. Barabasi, Network Science Reti sparse ¨ Molte delle reti reali sono sparse: numero limitato di archi ¨ Di conseguenza, anche le matrici di adiacenza sono sparse ¨ Esiste una modalità più efficiente di memorizzazione: liste di adiacenza Grafi bipartiti Definizione e proprietà Grafo bipartito ¨ Grafo bipartito: i nodi appartengono a due insiemi/categorie ¨ Non vi sono collegamenti interni a un insieme Grafo bipartito ¨ Grafo bipartito: due categorie di elementi ¤ Utenti – siti visitati ¤ Consumatori – merci acquistate ¤ Attori – film ¤ …. Grafo bipartito e proiezioni ¨ A partire dal grafo bipartito: proiezioni ¨ Proiezione: grafo (non necessariamente bipartito) ¤ Nodi: elementi di un insieme ¤ Archi: esiste un collegamento se due elementi sono collegati a un elemento comune Grafo bipartito e proiezioni Da A. L. Barabasi, Network Science Grafi multipartiti ¨ Un grafo multipartito è costituito da diversi insiemi (2, 3, …) ¤ Collegamenti tra nodi di insiemi differenti ¤ Nessun collegamento interno agli insiemi Cammini e distanze Definizioni e proprietà Distanze e cammini ¨ Determinare la distanza tra due punti in una rete è di importanza fondamentale: ¤ Distanza tra due città ¤ Distanza tra due utenti di una piattaforma ¤ Distanza tra due pagine web ¤… ¨ Per definire la distanza in una rete: definizione di cammino Cammino ¨ Cammino in un grafo: sequenza di nodi ¤ Adiacenti ¤ Distinti ¤ Nodo sorgente ¤ Nodo destinazione e d a: sorgente a c: destinazione b c Cammino a, e, d, c Percorso ¨ Percorso in un grafo: sequenza di nodi ¤ Adiacenti ¤ Nodo sorgente ¤ Nodo destinazione ¨ Nodi possono essere ripetuti e d a: sorgente a b: destinazione b c Percorso a, e, d, c, e, b Cammini e percorsi ¨ Lunghezza di un cammino (percorso): numero di archi tra sorgente e destinazione ¨ Cammino a, e, d, c: lunghezza 3 e d Cammino a, e, d, c a b c Cammini e percorsi ¨ In un grafo diretto un percorso deve seguire la direzione degli archi ¤ Differenza tra grafi diretti e non diretti e d e d a a b c b c Cammino a, e, d, c Cammino a, e, b, c Ciclo ¨ Ciclo: percorso i cui nodi sono distinti eccetto il primo e l’ultimo e d a b c Ciclo a, e, d, c, b, a Circuito ¨ Circuito: percorso in cui il primo e l’ultimo nodo coincidono e d a b c Circuito a, e, d, c, e, b, a Cammino minimo ¨ Un cammino tra due nodi è minimo quando nessun altro cammino tra i due nodi è composto da un numero inferiore di archi ¨ Possono esistere più cammini minimi e d a b c Cammini minimi tra a e d: (1) a, e, d (2) a, b, d Distanza La distanza tra due nodi u e v è la lunghezza del cammino minimo tra u e v e d a b c Distanza tra a e d: 2 Cammino ¨ Cammino (minimo): caso pesato → somma dei pesi sugli archi e 1 d 0,5 1 0,3 0,1 a 1 0,1 b c Cammino minimo tra a e d: a, e, b, c, d costo: 1 Diametro ¨ Il diametro di un grafo è costituito dal valore della massima distanza, cioè dal numero di archi che compongono il cammino minimo più lungo presente nel grafo e d e d f a a b c b c Diametro = 2 Diametro = 3 Teoria dei grafi Diametro? e d a b c Teoria dei grafi Diametro? e d f a b c Distanza media ¨ In un grafo possiamo considerare anche la distanza media: 1 𝑑𝑖𝑠𝑡 = / d𝑖𝑠𝑡&,K N(N − 1) &,L Distanza media Esercizio: Immagina un grafo con 5 nodi etichettati A, B, C, D ed E, collegati come segue: A è connesso a B e D B è connesso a A, C ed E C è connesso a B e D D è connesso a A, C ed E E è connesso a B e D Distanza media ? Distanza media Soluzione: Le distanze tra ciascuna coppia sono: AaB=1 AaC=2 AaD=1 AaE=2 BaC=1 BaD=2 BaE=1 CaD=1 CaE=2 DaE=1 distanza media = 14/20 = 0.7 Connettività Definizioni e proprietà Connessioni ¨ Una delle proprietà fondamentali delle reti: possibilità di comunicare tra elementi del sistema ¤ Connessione tra elaboratori ¤ Connessione tra due utenti ¤… ¨ Quali elementi possono essere messi in comunicazione? Componente connessa ¨ Componente connessa: insieme dei nodi del grafo ¤ Per ogni coppia di nodi esiste un cammino che li collega ¨ Grafo connesso: esiste una sola componente connessa ¨ Grafi diretti/ Grafi non diretti? e d Nodo isolato f a b c Componenti connesse: (1) f (2) a, b, c, d, e Componente fortemente connessa ¨ Nei grafi diretti si parla di componente fortemente connessa: da ogni nodo della componente è possibile raggiungere gli altri nodi della componente e d a b c Alberi ¨ Albero: grafo connesso privo di cicli ¤ Traogni coppia di nodi esiste uno e un solo cammino ¤ Foglie: nodi di grado 1 ¤ Presenza o meno di radice r radice e d a b a b c c d e f g Alberi ¨ Applicazioni alberi: ¤ Alberievolutivi ¤ Procedure decisionali Ponti di Könisberg Problema e soluzione Ponti di Könisberg ¨ Könisberg (Kalingrad): città natale di Kant sul fiume Pregel ¨ Sette ponti attraversano il fiume Pregel Ponti di Könisberg Problema: esiste un modo per attraversare tutti i ponti percorrendone ognuno una e una sola volta? Ponti di Könisberg Rappresentazione del problema tramite un grafo: ¨ Nodi: parti della città ¨ Archi: ponti Ponti di Könisberg Il problema ammette una soluzione? d c a b Ponti di Könisberg Impossibilità attraversamento sette ponti (Eulero, 1741) Consideriamo un percorso che attraversa i ponti 1. Esiste un nodo intermedio nel percorso 2. Consideriamo gli archi che attraversano quel nodo n Tutti gli archi sono percorsi n Complessivamente sono percorsi un numero pari di volte 3. Tutti i nodi hanno grado dispari Ponti di Könisberg Consideriamo il nodo c d c a b Teoria dei grafi Proprietà generale: esiste un percorso che attraversa tutti gli archi di un grafo una e una sola volta, solo se il grafo contiene al più due nodi di grado dispari. Ogni nodo intermedio deve essere attraversato un numero pari di volte Ponti di Könisberg Aggiunta di un arco d a c b