[Matlab] Un bel gioco (matematica inside)

[wlog]

Salve ragazzi,

sono 20 ore che non dormo per finire questo programma e finalmente sono riuscito a farlo andare. Riguarda una simulazione che ho fatto per il mio ultimo paper, che ho intitolato "Playing with the markov chains: game theory and pagerank".

Il programma si divide in due parti fondamentali:

A) una parte che si occupa di generare un grafo rappresentante il web, di normalizzarlo, di calcolarne il pagerank, di disegnarlo, ....

B) il gioco vero e proprio:

ad un determinato momento la rete è formata da N nodi, aventi ciascuno un massimo di 3 link in uscita. Ad ogni turno la singola pagina prova a spostare solo il proprio primo link sulle altre pagine, vedendo ogni volta come varia il proprio pagerank e di conseguenza scegliendo di posizionare il link in modo da massimizzare il proprio pagerank.

Come avrete capito, ad ogni turno ogni pagina cerca di massimizzare il proprio pagerank basandosi sullo stato del grafo al turno prima.

Il gioco ha molti limiti (solo 3 link, sposta un solo link, ...) perchè sale di complessità molto in fretta e quindi su un normale personal computer ci metterebbe troppo. In realtà quello in matlab è il prototipo di un programma scritto usando MPI/PETSC.


Il programma è stato fatto girare su 64 processori su un grafo rappresentante 100 milioni di pagine web del dominio .uk, per confrontare l'andamento del mio gioco con il reale andamento del web, trovando delle affascinanti similitudini.

In realtà però il mio gioco tende ad una situazione di equilibrio. Ho dimostrato che l'equilibrio è un equilibrio di nash di un gioco particolare, la domanda però è: quando tende all'equilibrio e quando no? Insomma, il classico halting problem... Però queste sono dettagli noiosi. La parte bella è che il mio programma permette di vedere graficamente l'andamento del grafo, passo per passo.

[wlog]

Vi ricordo che il programma è rilasciato sotto licenza GPL.

Come installare il programma:

Il programma è stato scritto usando l'ultima versione di matlab disponibile quando ho iniziato a scrivere il codice, la 2008a.

Create una cartella e assicuratevi che sia nella path di matlab. Assicuratevi di mettere nella cartella la libreria:

http://www.mathworks.com/matlabcentral/fileexchange/18443

A questo punto aggiungete il programma vero e proprio, che trovate a fondo pagina. Io ho incollato i file l'uno con l'altro per comodità, ma se avete problemi a lanciarlo provate a salvare ogni funzione in un singolo file di testo, sempre nella cartella sopracitata.


Come lanciare il programma

Semplice, aprite il vostro matlab e scrivete:

game1(nodi)

dove nodi è il numero di nodi che volete usare.

Cosa fare con il programma

Una volta che avrete lanciato il programma, vi apparirà una finestra con il disegno del grafo.

I puntini rappresentano i nodi, le linee tratteggiate rosse rappresentano i link univoci, cioè non reciproci, mentre le linee blu rappresentano i link reciproci.

La spirale verde è una spirale logaritmica sui cui vengono posizioniati i nodi in ordine di pagerank: al centro il nodo piu importante, in ordine decrescente fino al nodo meno importante.

Il programma disegna un turno del gioco, poi aspetta che voi premiate spazio prima di passare allo step successivo.

Cosa posso fare io per il programma

Il programma è ancora embrionale, manca la documentazione (che però ho sulla versione PETSC/MPI) e si possono aggiungere tanti dettagli interessanti per rendere il gioco piu interessante.

Magari se il gioco vi piace, e avete un po di tempo, potremmo metterlo apposto insieme cosi lo potremo pubblicare su mathcentral per condividerlo con gli altri. Ovviamente tutto sotto licenza GPL.

[wlog]

Il programma:


%A game theory approach to pagerank.
%This file simulates the game, starting with a web adjacency matrix p,
%having step as the number of allowed step, or 0 if the game has to go on
%indefinetly.


function game1 ( p, step )

if nargin < 2, step=+inf; end;



if isscalar(p)
p=randgengraph(p, 3);
end;

while step>0



[p pr]=nextsteprank(p);


%pr = PRank(p, 0.85, 0) ;

webgraphplot(p, pr);

pause

step=step-1
end;

end


function [p1, pr] = nextsteprank ( p )

sum(diag(p))

n=length(p);

p1=zeros(n);

for i=1:n

p1(i, :)=maxpagerank(p, i);

end;

sum(diag(p))

pr=PRank(p1, 0.85, 0);
end

function [result] = maxpagerank(p, i)

p3=p;

n=length(p3);


j=firstnonzeroinline( p3, i);

z=p3(i,j);
p3(i,j)=0;


vec=zeros(n-j+1, 1);


for k = 1:n-j+1

p2=p3;

if k ~= i

p2(i, k-1+j)=z;
prtemp=PRank(p2, 0.85, 0);
vec(k)=prtemp(i);
else
vec(k)=-1;
end;






end;

[trash y]=max(vec);
while y +j -1 == i
vec(y)=-1;
[trash y]=max(vec);
end;
p3(i, y+j-1)=z;

result=p3(i, :);

end

function [j] = firstnonzeroinline( p, i)

n=length(p);

for j=1:n

if p(i,j) > 0
break;
end;

end;


end


%This function normalizes the web adjacency matrix so that the sum of each
%row is one.

function [p] = graphnorm (a)


k=sum(a')';

n=length(a);

for i=1:n
if ( k(i) > 0)
k(i)=1/k(i);
end;
end;

p=a'*diag(k);

p=p';



%Computes the pagerank vector of a given web adjacency matrix A, with
%teleportation costant alpha and a preference vector v. If v is 0, then the
%uniform distribution is choosen for the vector, otherwise, if v is 1, the
%normal distribution is the choice.
%Pagerank is calculated as the solution of a linear system, check
%literature for references. The matrix is row-normalized, through graphnorm.

function [x] = PRank ( A , alpha , v )

n=length(A);

A=graphnorm(A);

if v == 0
v=ones(n,1)./n;
elseif v == 1
v=ones(n,1)./n;
end;



P = eye(n) - (alpha)*full(A)';

x = P \ v;


x = x./norm(x,1);


%This function generates a random graph representing a web adjacency
%sparse matrix of density dens.

function [a] = randgengraph ( n, dens )

a=zeros(n);

for i=1:n
pos=rand_int(1, n, dens)';
for j=1:dens
a(i, pos(j))=1;
end;
end;



for i=1:n
a(i, i)=0;
end;



%This function plots the web adjacency matrix, whose pagerank is pr. The
%nodes are placed on a logaritmic spiral, with the node with the highest
%pagerank in the center, the one with the lowest on the outermost point,
% and the others placed accordingly. The link are red and dashed if they
% are not reciprocal, and blue otherwise.

function webgraphplot (p, pr)

n=length(p);

%Here we build the coordinates for the spiral and for the nodes.

t=(1-pr./max(pr))*10*pi;

ti=0:0.01:max(t);

x = ((exp(0.1*t)).*(cos(t)));
y = ((exp(0.1*t)).*(sin(t)));

xi = ((exp(0.1*ti)).*(cos(ti)));
yi = ((exp(0.1*ti)).*(sin(ti)));

cor=[x , y];

%Here we look for symmetric nodes

q=zeros(n);


for i=1:n
for j=1:n
if p(i, j) == p(j, i) && p( i, j) > 0
q(i, j)=1;
q(j, i)=1;
end;
end;
q(i, i)=0;
end;

%Those are the actual plot options.

gplot(p-q, cor, '--rs' );
hold on
gplot(q, cor, '-s');
plot(xi, yi, 'g')
hold off