OCTAVE
Octave
http://octave.sourceforge.net/
Octave è uno stumento di calcolo di alto livello. Permette di risolvere
problemi di analisi numerica lineari e non lineari. Il linguaggio usato è
compatibile con Matlab
Alternative a Matlab
http://www.dedoimedo.com/computers/scientific.html
Scilab
FeeMat
Etc..
OCTAVE
• Aprire un file di Octave: dalla finestra di Octave:
>>edit prova5.m
• Per cambiarlo:
>>edit prova5  save
• Per lanciarlo
>> prova5
• Per vedere la directory corrente
>>pwd
• Per risalire
>>cd ..
• Per entrare:
>>cd nomedir
• Per aggiungere un path
addpath(genpath(‘C:/mfiles/’));
savepath;
OCTAVE
• Come si inseriscono matrici e vettori
;,
• Come si opera con matrici e vettori
• Grafici 2-d
plot, hist (help)
Programmi Matlab per il calcolo di misure di reti (G. Bounova)
http://www.mit.edu/~gerganaa/downloads.html
G. Bounova ha sviluppato diversi programmi MATLAB per il calcolo delle proprietà delle reti
Li ho raccolti in «Bounova_nuovo».
Calcolo dell’mst (algoritmo Prim’s)
Calcolo del cammino minimo (Dijkstra)
Calcolo del Clustering
Calcolo del diametro
Calcolo della lunghezza caratteristica
Calcolo della distribuzione dei gradi
Generare una ER network
Generare una SF network
Etc..
Esercizio
2
2
1
Dato seguente grafo
Calcolare con Octave il
cammino minimo
l’albero di ricoprimento
minimo, flusso massimo
3
1
4
3
2
2
3
8
3
9
2
6
7
4
2
Aggiungiamo il percorso
addpath(genpath(‘C:/programmi/Bounova_nuovo’));
savepath;
A=[0 2 0
Inseriamo la matrice di adiacenza
2 0 1
0 1 0
0 0 0
0 0 3
0 0 0
0 0 0
2 0 0
3 0 0
0
0
0
0
3
3
0
0
0
0
0
3
3
0
0
0
3
0
0
0
0
3
0
0
2
0
0
0
0
0
0
0
2
0
0
2
2
0
0
0
3
0
0
0
0
3
3
3
0
0
0
0
0
2
0
0]
5
% prova1000.m
clear
A=[0 2 0 0 0 0 0 2 3
2 0 1 0 0 0 0 0 0
0 1 0 0 3 0 0 0 0
0 0 0 0 3 3 0 0 0
0 0 3 3 0 0 0 3 0
0 0 0 3 0 0 2 0 0
0 0 0 0 0 2 0 0 2
2 0 0 0 3 0 0 0 0
3 0 0 0 0 0 2 0 0];
%draw_circ_graph(A)
% cammino minimo
s=1; target=4;
[dist,P]=dijkstra(A,s,target),
% flusso massimo
source=1; sink=4; capacity=A; nodes_number=9;
max_flow=ff_max_flow(source,sink,capacity,nodes_number),
% minimum spanning tree
tr = min_span_tree(A),
Output:
dist=8
P=1 8 5 4
max_flow =5
2
3
3
max (5=2+1+2)
min(2,3,3)=2
min(2,1,3,3)=1
min(3,2,2,3)=2
Albero di ricoprimento minimo
2
2
3
1
1
4
3
2
2
3
8
9
3
2
6
7
2
3
3
4
5
Esercizio
Della rete precedente. Calcolare il diametro, la distanza caratteristica, i valori dei
gradi di clustering, di betweennes e di closeness centrality. Fare gli istogrammi dei
gradi, dei clustering,delle betweennes e delle closeness centrality.
% prova2000.m
clear
A=[0 2 0 0
2 0 1 0
0 1 0 0
0 0 0 0
0 0 3 3
0 0 0 3
0 0 0 0
2 0 0 0
3 0 0 0
…….
0
0
3
3
0
0
0
3
0
0
0
0
3
0
0
2
0
0
0
0
0
0
0
2
0
0
2
2
0
0
0
3
0
0
0
0
3
0
0
0
0
0
2
0
0];
……..
% grado medio
m=numedges(A); n=numnodes(A);
km =2*m/n;
d2=link_density(A) ; %2*m/n/(n-1)
diam= diameter(A);
apl=ave_path_length(A);
deg=degrees(A); subplot(221),hist(deg),
title('degree');
clo=closeness(A);
subplot(222),hist(clo), title('closeness');
bet=node_betweenness_slow(A);
subplot(223),hist(bet), title('betweenness');
[C1,C2,C] = clust_coeff(A);
subplot(224),hist(C), title('clustering');
%figure
%draw_circ_graph(A)
Proviamo a rifare lo stesso esercizio con Pajek:
Da Octave generiamo il file provaPajek.net
adj2pajek(A,’provaPajek.net’)
*Vertices
1 "v1"
2 "v2"
3 "v3"
4 "v4"
5 "v5"
6 "v6"
7 "v7"
8 "v8"
9 "v9"
*Edges
2 1
8 1
9 1
1 2
3 2
2 3
5 3
........
9
0.5776
0.3545
0.3451
0.2520
0.9702
0.5191
0.3946
0.5388
0.0498
2
2
3
2
1
1
3
0.7561
0.9017
0.1743
0.4123
0.0730
0.6884
0.2572
0.0573
0.8002
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
Proviamo a rifare lo stesso esercizio con Pajek:
Aprire Pajek
Posizionarsi su C:…./bin/ProvaPajek.net
Net/transform/remove/multiple Line (max)
Info/net/general
Output Octave
Km=5.3333
D2=0.6667
Diam=9
apl=5.1944
E=0.0046
2*m/n=48/9=5.3333
Considera gli archi di
peso 1
m=10; n=9
2*m/n=2.22
Diametro=4
Studiare la rete dining-table_partners.net del cap 1
Da Octave generiamo un file .m con la matrice di adiacenza
%Pajek2adj.m
% This program extracts an adjacency matrix from a pajek text (.net) file
% INPUT .net text filename, n - number of nodes in the graph
% OUTPUT: adjacency matrix, nxn, n - # nodes
adj = pajek2adj(filename,n)
adj = pajek2adj(dining-table_partners.net,26)
Esercizio A
Verificare che l’albero minimo del seguente grafo:
è:
Esercizio B
Si consideri il seguente grafo
Verificare che il cammino minimo da A a G è ABEG ed ha lunghezza 18
Esercizio C
Verificare che nel seguente grafo
Nota: Octave ne fornisce uno dei 2. per ottenere l’albero di ricoprimento minimo si deve
aggiungere un arco da H ad esempio ad A con peso 6 (peso max)
Esercizio
Inventare un grafo non diretto con 7 nodi
Inserire la matrice di adiacenza in Octave e calcolare
Cammino minimo tra due nodi a caso
Flusso massimo tra gli stessi nodi
Albero di ricoprimento minimo
Distribuzione dei gradi
Distribuzione delle betweenness e
Distribuzione dei valori di clustering