L’obiettivo è studiare la centralità degli attori di una rete sociale di delfini appartenenti ad una comunità che vive nel fiordo di Doubtful Sound in Nuova Zelanda. Le condizioni inusuali di questo fiordo, con acqua relativamente fredda e con uno strato di acqua dolce in superficie, hanno limitato le uscite di esemplari e l’arrivo di nuovi delfini nel gruppo, facilitando una intensa relazione sociale tra i delfini della comunità. La rete è un grafo indiretto che contiene 62 nodi delfini e 159 connessioni tra coppie di delfini. Due delfini sono associati da un arco se, nel periodo di osservazione durato dal 1994 al 2001, essi sono stati avvistati assieme più frequentemente di quanto il caso avrebbe voluto. E’ noto il sesso di quasi tutti gli esemplari.

Preliminari

Avviare R da un terminale con l’omonimo comando e, se non già fatto, installare il pacchetto:

install.packages(c("igraph", "rgl", "scales", "lsa", "ineq", "moments", "shiny"))

Quindi caricare i pacchetti installati:

library(igraph)
library(rgl)
library(scales)
library(lsa)
library(ineq)
library(moments)
library(shiny)

e leggere la rete dolphin.gml:

g = read_graph(file="dolphin.gml", format="gml")

Notate che i nodi hanno tre attributi: id (un identificatore numerico), label (il nome del delfino), e sex (il sesso, M per maschio, F per femmina, U per sconosciuto).

Visualizzazione della rete

Visualizzare il numero di nodi e il numero di archi del grafo. Calcolare la densità del grafo (numero di archi del grafo fratto numero massimo di archi del grafo). Il grafo è sparso o denso? Contare il numero di esemplari maschi e femmine e la relativa percentuale.

n = vcount(g)
n
## [1] 62
m = ecount(g)
m
## [1] 159
graph.density(g)
## [1] 0.0840825
sex = V(g)$sex
male = sex == "M"
female = sex == "F"
shemale = sex == "U"

n.male = sum(male)
n.female = sum(female)

round(100 * (n.male / n))
## [1] 53
round(100 * (n.female / n))
## [1] 40

Visualizzare la rete con il metodo di Fruchterman e Reingold usando come etichette dei nodi il nome del delfino, oppure il suo identificatore numerico, oppure nessuna etichetta. Visualizzare i nodi femmina in rosa e i nodi maschi in blu. Visualizzare il sottografo delle femmine e quello dei maschi. Provare altre visualizzazioni: casuale, circolare e sferica.

coords = layout_with_fr(g)
plot(g, layout=coords, vertex.label=V(g)$label, vertex.shape="none")

plot(g, layout=coords, vertex.label=V(g)$id, vertex.size=12)

plot(g, layout=coords, vertex.label=NA, vertex.size=5)

V(g)[male]$color = "blue"
V(g)[female]$color = "pink"
V(g)[shemale]$color = "green"
plot(g, layout=coords, vertex.label=NA, vertex.size=5)

g.male = induced_subgraph(g, V(g)[male])
coords.male = layout_with_fr(g.male)
plot(g.male, layout=coords.male, vertex.label=NA, vertex.size=5)

g.female = induced_subgraph(g, V(g)[female])
coords.female = layout_with_fr(g.female)
plot(g.female, layout=coords.female, vertex.label=NA, vertex.size=5)

plot(g, layout=layout_randomly(g), vertex.label=NA, vertex.size=5)

plot(g, layout=layout_in_circle(g), vertex.label=NA, vertex.size=5)

plot(g, layout=layout_on_sphere(g), vertex.label=NA, vertex.size=5)

Visualizzare la rete in 3D con il metodo di Fruchterman e Reingold usando come etichette dei nodi il nome del delfino.

Scrivere in Shiny una applicazione che visualizza la rete dei delfini. L’utente:

  1. sceglie il layout di visualizzazione;
  2. sceglie se evidenziare con un colore i nodi dei delfini maschi, femmina, o di sesso non noto.

L’applicazione visualizza la rete in base alle scelte dell’utente. La soluzione di può scaricare qui

Misure di centralità

Calcolare la centralità per grado dei nodi. Calcolare le seguenti statistiche descrittive della distribuzione dei gradi: minimo, massimo, media, mediana, primo e terzo quartile. Notare come si posiziona la media rispetto alla mediana. Generare un istogramma dei gradi dei nodi. Etichettare il vettore dei gradi con i nomi dei delfini e visualizzarlo in ordine decrescente rispetto al grado. Visualizzare inoltre i tre delfini con grado maggiore. Sono femmine o maschi? Calcolare il grado medio degli esemplari femmina e maschio. Visualizzare la rete con i nodi di dimensione proporzionale al loro grado.

d = degree(g)
summary(d)
##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##   1.000   3.000   5.000   5.129   7.000  12.000
hist(d, xlab="Degree", main="Histogram of node degree centrality", breaks=0:max(d))

names(d) = V(g)$label
sort(d, decreasing=TRUE)
##        Grin         SN4     Topless       Scabs     Trigger         Jet 
##          12          11          11          10          10           9 
##     Kringel   Patchback         Web  Beescratch    Gallatin        SN63 
##           9           9           9           8           8           8 
##         SN9     Feather    Haecksel       Jonah       SN100     Stripes 
##           8           7           7           7           7           7 
##        TR99      Upbang        Beak        DN21      Double        Hook 
##           7           7           6           6           6           6 
##       MN105        MN83        SN96        TR77        DN63        Fish 
##           6           6           6           6           5           5 
##     Number1       Oscar          PL    Shmuddel        SN90         Zap 
##           5           5           5           5           5           5 
##      Bumper        DN16        Knit     Thumper      TSN103         CCL 
##           4           4           4           4           4           3 
##        MN60         Mus       Notch Ripplefluke      Zipfel        SN89 
##           3           3           3           3           3           2 
##       TR120        TR88       TSN83         Vau        Wave       Cross 
##           2           2           2           2           2           1 
##        Five        Fork        MN23       Quasi        SMN5        TR82 
##           1           1           1           1           1           1 
##    Whitetip         Zig 
##           1           1
top = sort(d, decreasing=TRUE)[1:3]
id.top = match(names(top), V(g)$label)
V(g)[id.top]$sex
## [1] "F" "F" "M"
mean(d[male])
## [1] 5.060606
mean(d[female])
## [1] 5.6
mean(d[female]) / mean(d[male])
## [1] 1.106587
plot(g, layout=coords, vertex.label=NA, vertex.size = (d / max(d)) * 10)

Fare lo stesso per la centralità per autovettore e pagerank. Notate una differenza?

e = eigen_centrality(g)$vector
summary(e)
##     Min.  1st Qu.   Median     Mean  3rd Qu.     Max. 
## 0.001697 0.057960 0.150200 0.287500 0.503200 1.000000
hist(e, xlab="Eigenvector", main="Histogram of node eigenvector centrality", breaks=seq(min(e), max(e), (max(e) - min(e))/10))

names(e) = V(g)$label
sort(e, decreasing=TRUE)
##        Grin         SN4     Topless       Scabs        TR99   Patchback 
## 1.000000000 0.951799805 0.902535447 0.890164531 0.689371799 0.670597148 
##     Trigger        Hook         SN9       MN105       Jonah        SN63 
## 0.667174334 0.658662305 0.658274865 0.656626545 0.641246650 0.622635601 
##        MN83     Stripes     Kringel    Haecksel      Double    Shmuddel 
## 0.611855811 0.602753892 0.584190651 0.519900956 0.453166274 0.439631520 
##       SN100      TSN103        Beak         Zap        MN60        SN96 
## 0.420422139 0.410295522 0.406936369 0.354099734 0.276652586 0.256347364 
##        TR77         CCL     Thumper        Fish       Oscar         Vau 
## 0.254512313 0.251231996 0.246379351 0.238307667 0.216045624 0.165017929 
##      Zipfel        DN63  Beescratch          PL      Bumper        Fork 
## 0.164642902 0.135855976 0.133243924 0.129035668 0.125900178 0.123743716 
##       TSN83       TR120        SMN5       Cross        Five    Whitetip 
## 0.106677505 0.094104252 0.093221175 0.092745362 0.092745362 0.086553935 
##        TR88      Upbang        SN89        Knit         Jet         Web 
## 0.074195776 0.072841218 0.066093022 0.065471512 0.055457225 0.055025554 
##     Number1        SN90    Gallatin     Feather        DN21       Notch 
## 0.051672193 0.048272317 0.047515861 0.038625862 0.038606459 0.028323131 
##        DN16         Mus Ripplefluke        Wave        MN23       Quasi 
## 0.020771413 0.018829555 0.012210714 0.008254248 0.007709230 0.007709230 
##        TR82         Zig 
## 0.007649223 0.001697438
top = sort(e, decreasing=TRUE)[1:3]
id.top = match(names(top), V(g)$label)
V(g)[id.top]$sex
## [1] "F" "F" "M"
mean(e[male])
## [1] 0.2103415
mean(e[female])
## [1] 0.4160132
mean(e[female]) / mean(e[male])
## [1] 1.977799
plot(g, layout=coords, vertex.label=NA, vertex.size = (e / max(e)) * 10)

pr = page_rank(g)$vector
summary(pr)
##     Min.  1st Qu.   Median     Mean  3rd Qu.     Max. 
## 0.004835 0.009688 0.015780 0.016130 0.021390 0.032140
hist(pr, xlab="Pagerank", main="Histogram of node Pagerank centrality", breaks=seq(min(pr), max(pr), (max(pr) - min(pr))/10))

names(pr) = V(g)$label
sort(pr, decreasing=TRUE)
##        Grin         Jet     Trigger         Web         SN4     Topless 
## 0.032144493 0.031728140 0.031299357 0.030095371 0.029875339 0.029514204 
##       Scabs   Patchback    Gallatin  Beescratch     Kringel        SN63 
## 0.028423070 0.026458550 0.026156876 0.024650717 0.024640919 0.023939244 
##     Feather         SN9     Stripes      Upbang       SN100        DN21 
## 0.023458479 0.021966366 0.021691125 0.021650877 0.020613389 0.020053629 
##    Haecksel       Jonah        TR99        SN96        TR77     Number1 
## 0.019883081 0.019395551 0.019231945 0.017618650 0.017339518 0.017130091 
##      Double        Beak       MN105        MN83        Hook        SN90 
## 0.017098301 0.016965392 0.016938990 0.016905756 0.016626816 0.016137567 
##    Shmuddel        DN63          PL        Fish       Oscar         Zap 
## 0.015919936 0.015643030 0.015302095 0.015108398 0.014845739 0.014767920 
##        DN16      Bumper Ripplefluke        Knit     Thumper      TSN103 
## 0.014428048 0.013338080 0.013308677 0.012928200 0.012830828 0.012072591 
##         Mus       Notch      Zipfel        MN60         CCL        TR88 
## 0.011504223 0.011210139 0.011039191 0.009863498 0.009629062 0.008876750 
##       TR120        Wave       TSN83        SN89         Vau         Zig 
## 0.008825896 0.008326246 0.008181048 0.007764750 0.007494174 0.006190147 
##       Quasi        MN23        TR82       Cross        Five    Whitetip 
## 0.005415901 0.005415901 0.005261695 0.005079800 0.005079800 0.004962900 
##        SMN5        Fork 
## 0.004918218 0.004835316
top = sort(pr, decreasing=TRUE)[1:3]
id.top = match(names(top), V(g)$label)
V(g)[id.top]$sex
## [1] "F" "M" "F"
mean(pr[male])
## [1] 0.01621522
mean(pr[female])
## [1] 0.01693514
mean(pr[female]) / mean(pr[male])
## [1] 1.044398
plot(g, layout=coords, vertex.label=NA, vertex.size = (pr / max(pr)) * 10)

Ripetere le analisi per la centralità per vicinanza. A cosa corrispondono i due picchi nella distribuzione della centralità? Identificare nella rete i delfini con massima e minima centralità. Come sono posizionati rispetto agli altri?

c = closeness(g)
summary(c)
##     Min.  1st Qu.   Median     Mean  3rd Qu.     Max. 
## 0.002924 0.004288 0.005181 0.005037 0.005556 0.006849
hist(c, xlab="Closeness", main="Histogram of node closeness centrality", breaks=seq(min(c), max(c), (max(c) - min(c))/10))

names(c) = V(g)$label
sort(c, decreasing=TRUE)
##       SN100         SN9         SN4     Kringel        Grin  Beescratch 
## 0.006849315 0.006622517 0.006535948 0.006410256 0.006172840 0.006097561 
##        DN63       Oscar       Scabs      Double        TR99        Beak 
## 0.005988024 0.005988024 0.005988024 0.005952381 0.005747126 0.005681818 
##     Topless      TSN103         Zap    Haecksel        TR77       Jonah 
## 0.005681818 0.005617978 0.005617978 0.005555556 0.005555556 0.005524862 
##     Stripes        SN89       MN105        MN60        Hook        SN63 
## 0.005524862 0.005494505 0.005464481 0.005464481 0.005405405 0.005405405 
##        SN96     Trigger      Upbang   Patchback          PL        Knit 
## 0.005405405 0.005405405 0.005319149 0.005291005 0.005291005 0.005181347 
##     Number1    Shmuddel        Fish        MN83     Thumper         Jet 
## 0.005181347 0.005181347 0.005128205 0.005128205 0.005102041 0.005076142 
##         CCL         Web      Zipfel        SN90      Bumper       Notch 
## 0.005050505 0.004950495 0.004950495 0.004878049 0.004629630 0.004545455 
##    Gallatin         Vau        Fork        DN21       TSN83       TR120 
## 0.004444444 0.004444444 0.004405286 0.004385965 0.004255319 0.004201681 
##         Mus     Feather       Cross        Five    Whitetip        TR88 
## 0.004184100 0.004132231 0.004081633 0.004081633 0.004081633 0.004048583 
##        SMN5        DN16        MN23       Quasi        TR82 Ripplefluke 
## 0.004016064 0.003906250 0.003891051 0.003891051 0.003816794 0.003546099 
##        Wave         Zig 
## 0.003496503 0.002923977
top = sort(c, decreasing=TRUE)[1:3]
id.top = match(names(top), V(g)$label) 
V(g)[id.top]$sex
## [1] "F" "F" "F"
mean(c[male])
## [1] 0.004931279
mean(c[female])
## [1] 0.005292332
mean(c[female]) / mean(c[male])
## [1] 1.073217
plot(g, layout=coords, vertex.label=NA, vertex.size = (c / max(c)) * 10)

Ripetere le analisi per la centralità per intermediazione. Identificare nella rete il delfino con massima centralità. Come è posizionato rispetto agli altri?

b = betweenness(g)
summary(b)
##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##   0.000   5.641  39.580  71.890 102.600 454.300
hist(b, xlab="Betweenness", main="Histogram of node betweenness centrality", breaks=seq(min(b), max(b), (max(b) - min(b))/10))

names(b) = V(g)$label
sort(b, decreasing=TRUE)
##       SN100  Beescratch         SN9         SN4        DN63         Jet 
##  454.274069  390.383717  261.963619  253.582713  216.376673  209.169298 
##     Kringel      Upbang     Trigger         Web        SN89       Oscar 
##  187.841704  181.392614  154.959376  154.094571  129.045705  122.165227 
##   Patchback     Stripes        Grin       Scabs    Gallatin        SN63 
##  119.918587  114.980006  113.408769  104.614585   96.708781   82.994597 
##        MN60     Topless        TR99    Haecksel          PL Ripplefluke 
##   77.194498   74.426906   61.142194   60.924764   60.482343   60.000000 
##    Shmuddel        DN21     Number1        SN96        SN90        TR77 
##   59.831410   53.751742   53.503455   53.359052   42.550429   42.458701 
##      Double     Feather         Zap      TSN103        Beak        Fish 
##   40.929300   38.236716   37.208978   35.198851   34.921151   29.448398 
##       Jonah      Zipfel        Knit       MN105     Thumper      Bumper 
##   27.184466   25.976818   24.365341   23.242197   22.029185   16.603247 
##        MN83        DN16       Notch        Hook       TR120         CCL 
##   13.510970    8.015949    7.983333    6.047619    5.505495    4.344048 
##         Mus       TSN83        TR88         Vau        Wave       Cross 
##    3.008730    2.183333    1.700000    1.605769    0.250000    0.000000 
##        Five        Fork        MN23       Quasi        SMN5        TR82 
##    0.000000    0.000000    0.000000    0.000000    0.000000    0.000000 
##    Whitetip         Zig 
##    0.000000    0.000000
top = sort(b, decreasing=TRUE)[1:3]
id.top = match(names(top), V(g)$label)
V(g)[id.top]$sex
## [1] "F" "M" "F"
mean(b[male])
## [1] 66.77166
mean(b[female])
## [1] 86.16572
mean(b[female]) / mean(b[male])
## [1] 1.290453
plot(g, layout=coords, vertex.label=NA, vertex.size = (b / max(b)) * 10)

Studiare la correlazione tra le centralità usando il coefficiente di correlazione di Pearson e i grafici di dispersione.

m = cbind(d,pr,e,c,b)
round(cor(m, method="pearson"),2)
##       d   pr    e    c    b
## d  1.00 0.98 0.72 0.71 0.59
## pr 0.98 1.00 0.61 0.62 0.60
## e  0.72 0.61 1.00 0.70 0.28
## c  0.71 0.62 0.70 1.00 0.67
## b  0.59 0.60 0.28 0.67 1.00
pairs(m)

plot(d, pr, xlab="Degree centrality", ylab="Pagerank centrality")
abline(lm(pr~d), col="red")

Scrivere in Shiny una applicazione che visualizza le misure di centralità calcolate sui nodi di una rete generica. L’utente:

  1. sceglie il formato e il file che contiene il grafo;
  2. sceglie una misura di centralità e gli eventuali parametri.

L’applicazione visualizza la rete con i nodi di grandezza proporzionale al rispettivo valore della misura di centralità scelta. Il nodo con massimo valore di centralità viene visualizzato in rosso. La soluzione di può scaricare qui

Similarità e comunità

Calcolare le misure di similarità locali basate sul coseno e sul coefficiente di correlazione di Pearson, nonché la misura di similarità globale, usando la rete sociale dei delfini. Identificare le coppie di delfini più simili rispetto alle misure calcolate. Studiare la correlazione tra le misure di similarità calcolate usando il coefficiente di correlazione e i grafici di dispersione.

A = as_adjacency_matrix(g, sparse=FALSE)

# cosine similarity
S1 = cosine(A)
# remove self-similarity
T1 = S1 + diag(-1, vcount(g))
# which are the most similar nodes?
which(T1 > 0.8 & T1 <= 1, arr.ind=TRUE)
##      row col
## [1,]  12   5
## [2,]   7   6
## [3,]   6   7
## [4,]  14  10
## [5,]   5  12
## [6,]  10  14
## [7,]  32  23
## [8,]  23  32
S1[7,6]
## [1] 0.8164966
neighbors(g, 7)
## + 6/62 vertices:
## [1] 10 14 18 55 57 58
neighbors(g, 6)
## + 4/62 vertices:
## [1] 10 14 57 58
# Pearson similarity
S2 = cor(A, method="pearson")
# remove self-similarity
T2 = S2 + diag(-1, n)
# which are the most similar nodes?
which(T2 > 0.8 & T2 <= 1, arr.ind=TRUE)
##      row col
## [1,]  12   5
## [2,]   7   6
## [3,]   6   7
## [4,]   5  12
## [5,]  32  23
## [6,]  23  32
S2[7,6]
## [1] 0.8022956
neighbors(g, 7)
## + 6/62 vertices:
## [1] 10 14 18 55 57 58
neighbors(g, 6)
## + 4/62 vertices:
## [1] 10 14 57 58
# correlation between local similarity measures
cor(as.vector(S1), as.vector(S2))
## [1] 0.9837139
plot(as.vector(S1), as.vector(S2), xlab="cosine", ylab = "Pearson")

# global similarity
I = diag(1, vcount(g));
# leading eigenvalue
l = eigen(A)$values[1]
# 85% of leading eigenvalue
alpha = 0.85 * 1/l
# global similarity
S3 = solve(I - alpha * A)

# correlation between local and global similarity measures
cor(as.vector(S1), as.vector(S3))
## [1] 0.7586525
plot(as.vector(S1), as.vector(S3), xlab="cosine", ylab = "Katz")

cor(as.vector(S2), as.vector(S3))
## [1] 0.7228262
plot(as.vector(S2), as.vector(S3), xlab="Pearson", ylab = "Katz")

Calcolare le comunità sulla rete dei delfini usando gli algoritmi cluster_leading_eigen, cluster_fast_greedy e cluster_edge_betweenness. Visualizzare le comunità nel grafo e identificare eventuali differenze tra i vari algoritmi. Calcolare le comunità usando l’algoritmo ottimo optimal.community. Calcolare la modularità delle soluzioni. Quale algoritmo approssimato fornisce la soluzione che si avvicina di più all’ottimo? Calcolare un clustering gerarchico con la funzione hclust usando il coseno come misura di similarità tra i nodi e visualizzare il relativo dendrogramma.

coords = layout_with_fr(g)

fgc = cluster_fast_greedy(g)
modularity(fgc)
## [1] 0.4954907
plot(fgc, g, layout=coords, vertex.label=NA, vertex.size=5)

ebc = cluster_edge_betweenness(g)
modularity(ebc)
## [1] 0.5193821
plot(ebc, g, layout=coords, vertex.label=NA, vertex.size=5)

lec = cluster_leading_eigen(g)
modularity(lec)
## [1] 0.4911989
plot(lec, g, layout=coords, vertex.label=NA, vertex.size=5)

# This method is computationally heavy
oc = cluster_optimal(g)
modularity(oc)
plot(oc, g, layout=coords, vertex.label=NA, vertex.size=5)
# hierarchical clustering
A = get.adjacency(g, sparse=FALSE)
# cosine similarity
S = cosine(A)
# distance matrix
D = 1-S
# distance object
d = as.dist(D)
# average-linkage clustering method
cc = hclust(d, method = "average")
# plot dendrogram
plot(cc)
# cut dendrogram at 2 clusters
clusters = cutree(cc, k = 2)
# draw dendogram with red borders around the 2 clusters
clusters.list = rect.hclust(cc, k = 2, border="blue")

Scrivere in Shiny una applicazione che visualizza le comunità di una rete generica. L’utente:

  1. sceglie il formato e il file che contiene il grafo;
  2. sceglie il metodo per rivelare le comunità (tra quelli dispobibili in igraph).

L’applicazione visualizza la rete con le comunità evidenziate e la modularità della soluzione. La soluzione di può scaricare qui

Struttura della rete

Verificare che la rete è connessa. Calcolare le componenti biconnesse. Calcolarne il numero e isolare la più grande. Visualizzare il grafo con i nodi della bicomponente gigante colorati in rosso. Quali nodi rimangono fuori? Calcolare le componenti k-connesse.

# is the graph connected?
is.connected(g)
## [1] TRUE
# compute biconnected components
bc = biconnected_components(g)
cl = bc$components
size = sapply(cl, length)
length(size)
## [1] 10
table(size) 
## size
##  2 53 
##  9  1
# highlight the largest bi-component
giant = cl[[which.max(size)]]
V(g)$color  = "white"
V(g)[giant]$color = "red"
plot(g, layout=coords, vertex.label=NA, vertex.size=5)

# This is computationally heavy
b = cohesive_blocks(g)

# print hieararchy of blocks
print(b)
## Cohesive block structure:
## B-1            c 1, n 62
## '- B-2         c 2, n 53
##    '- B-3      c 3, n 44
##       '- B-5   c 4, n  7
##       '- B-6   c 4, n 24
##    '- B-4      c 3, n  5
# plot hieararchy of blocks
plot_hierarchy(b) 

# graphs from blocks
bg = graphs_from_cohesive_blocks(b, g)

# plot most cohesive and largest graph
plot(bg[[6]], layout=layout_with_fr(bg[[6]]), vertex.size = 3, vertex.label=NA, vertex.color="white")

Trovare il grado di separazione (distanza media tra due nodi) e il diametro (distanza massima tra due nodi) del grafo. Visualizzare il grafo con i nodi e gli archi del diametro colorati in rosso. Produrre un istogramma con le distanze tra i nodi del grafo. Come sono distribuite le distanze?

# average distance (degree of separation)
mean_distance(g)
## [1] 3.356954
# maximum distance (diameter)
diameter(g)
## [1] 8
# highlight the diameter
d = get_diameter(g)
E(g)$color = "grey"
E(g)$width = 1
E(g, path=d)$color = "red"
E(g, path=d)$width = 2
V(g)$color  = "white"
V(g)[d]$color = "red"
plot(g, layout=coords, vertex.label = NA, vertex.size=5)

# histogram of distances
paths = distance_table(g)$res
names(paths) = 1:length(paths)
barplot(paths / sum(paths), xlab="Distance", ylab="Frequency")

Studiare la distribuzione dei gradi dei nodi. Come si pone la media rispetto alla mediana e agli altri quartili? Calcolare l’indice di asimmetria (skewness) e di Gini della distribuzione. Studiare la concentrazione delle connessioni con la curva di Lorenz. Calcolare e visualizzare la CCDF in scala bi-logaritmica. Possiamo dire che la rete sociale dei delfini è scale-free?

d = degree(g)

# mean and median
summary(d)
##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##   1.000   3.000   5.000   5.129   7.000  12.000
# skewness
skewness(d)
## [1] 0.2915325
# Gini
Gini(d)
## [1] 0.3250152
# Lorenz curve
lc = Lc(d, plot=TRUE)

#CCDF
# Cumulative distribution
ccdf = function(d) {
  n = length(d)
  max = max(d)
  P = rep(0, max);
  for (i in 1:length(P)) {
    P[i] = length(d[d >= i]) / n;
  } 
  return(P)
}
P = ccdf(d)
plot(1:max(d), P, log="xy", type = "l", xlab="Degree", ylab="CCDF");

Trovare il coefficiente di transitività della rete.

transitivity(g)
## [1] 0.3087757

Calcolare l’assortatività della rete per sesso e per grado.

# the subgraph of dolphins with known sex
h = induced_subgraph(g, V(g)[male | female])

# males and females of the new graph
male.h = V(h)$sex == "M"
female.h = V(h)$sex == "F"

# assortativity
modularity(h, membership=as.integer(male.h) + 1)
## [1] 0.1994156
# edges as a matrix
edge = as_edgelist(h)

# all first nodes of the edges 
# each edge is considered twice since it is undirected
l = c(edge[,1], edge[,2])

# all second nodes of the edges
# each edge is considered twice since it is undirected
r = c(edge[,2], edge[,1])

# sex of all first nodes of the edges 
sl = male.h[l]

# sex of all second nodes of the edges
sr = male.h[r]

# male to male edges
m2m = sum(sl & sr) / 2
m2m
## [1] 58
# female to female edges
f2f = sum(!(sl | sr)) / 2
f2f
## [1] 46
# male to female edges
m2f = sum(xor(sl, sr)) / 2
m2f
## [1] 44
# check
ecount(h) ==  (m2m + f2f + m2f)
## [1] TRUE
# percentage of same sex edges
(m2m +f2f) / ecount(h)
## [1] 0.7027027
# degree assortativity
d = degree(g)
edge = as_edgelist(g)
l = c(edge[,1], edge[,2])
r = c(edge[,2], edge[,1])
dl = d[l]
dr = d[r]
cor(dl, dr)
## [1] -0.04359403

Scrivere in Shiny una applicazione che prova diverse strategie di rimozione di nodi da una rete al fine di determinare qual è la più efficace nello scottenntere la rete (percolazione). Le strategie di rimozione sono: casuale, per grado, per autovettore, per vicinanza, per intermediazione. L’utente:

  1. sceglie il formato e il file che contiene il grafo;
  2. sceglie una strategia di percolazione e il numero di nodi da rimuovere.

L’applicazione visualizza la rete risultante dopo aver rimosso un numero di nodi pari a quello specificato scelti in modo casuale oppure corrispondenti ai nodi più centrali rispetto alla misura scelta, evidenziando anche il numero di componenti connesse e la dimensione della componente più grande del grafo.

La soluzione di può scaricare qui