Webanalízis,avagy melyik a legértékésebb csúcs egy gráfban?

Mátyás Péter

BME-TTK, mérnök-fizikus és matematikus hallgató

A Webcrawler

A Webcrawler egy függvény, amely egy megadott weboldal címéből kiindulva bejárja annak szomszédait egy megadott mélységig. Nem optimlizált, de a célnak megfelel.

Needs["Combinatorica`"];
Needs["GraphUtilities`"];
webcrawler[rooturl_,depth_]:=Flatten[
Rest[
NestList[
Union[
Flatten[
Thread[#->Import[#,"Hyperlinks"]]&/@Last/@#]]&,{""->rooturl},depth]]];

Egy Webgráf

style={System`VertexStyle->White,VertexShapeFunction->"Point",System`EdgeStyle->Directive[Opacity[.5],Hue[.15,.5,.8]],Background->Black,EdgeShapeFunction->(Line[#1]&),ImageSize->500,DirectedEdges->True};

webgraf=webcrawler["http://www.math.bme.hu/~empe/index.xhtml",3];
W=AdjacencyMatrix[webgraf];
%//MatrixForm
GraphPlot[W,style]
GraphPlot3D[W, style, VertexRenderingFunction->({Sphere[#1,.05]}&),PlotStyle->Directive[Specularity[White,50]]]

webgraf2=webcrawler["http://www.math.bme.hu",2];
W2=AdjacencyMatrix[webgraf2];
GraphPlot[W2,style]
GraphPlot3D[W2, style, VertexRenderingFunction->({Sphere[#1,.05]}&),PlotStyle->Directive[Specularity[White,50]]]

Egy véletlen gráf

veletlen=RandomGraph[10,0.4, Directed];

Am=ToAdjacencyMatrix[veletlen]
%//MatrixForm
GraphPlot[veletlen,style]

PageRank

PageRankVector[webgraf]

Véletlen bolyongás

Függvény,  amely az adjacencia mátrixból kiszámolja az átmeneti mátrixot: If

f[Adj_]:=Table[Adj[[i]][[j]]/Norm[Adj[[i]],1],{i,1,Length[Adj]},{j,1,Length[Adj]}]

Egy, a gráf csúcsai számával (n) egyező méretű sorvektor, melynek minden eleme 1/n:

u[dim_]:=Table[1/dim,{i,1,dim}]

p meghatározása adott t esetén:

pt[Atmeneti_,t_]:=u[Length[Atmeneti]].MatrixPower[Atmeneti,t]

“Stacionárious” eloszlás meghatározása :

stac[atmenet_,t_,pontossag_]:= N[Table[pt[atmenet,i],{i,1,t}],pontossag]

Példa:

f[Am]//MatrixForm
stac[f[Am],10,3]//MatrixForm

PageRank

Az U mátrix:

Um[di_]:=Table[u[di],{i,1,di}]

A módosított átmeneti mátrix, ahol d az elugrás valószínǻsége:

B[Atmenet_,d_]:=(1-d)Atmenet+d Um[Length[Atmenet]]

Példa:

stac[B[f[Am],0.15],20,3]//MatrixForm

PageRankVector[veletlen]