Prema članku C, Moler, Google PageRank.
Algoritam koristi teoriju grafova i linearnu algebru.
Graf $\mathcal{G}$ ima $n$ čvorova i $m$ grana.
Matrica susjedstva $G$ grafa $\mathcal{G}$ je definirana s
$$ g_{ij}=\begin{cases} 1, \text{ako postoji grana iz čvora $j$ u čvor $i$},\\ 0, \text{inače} \end{cases} $$Na primjer, neka je zadan graf $\mathcal{G}$
In [2]:
using Graphs
using IJuliaPortrayals
In [4]:
G=simple_graph(3,is_directed=true)
add_edge!(G,1,2)
add_edge!(G,1,3)
add_edge!(G,2,3)
GraphViz(to_dot(G),"neato","svg")
Out[4]:
Matrica susjedstva je
$$ G=\begin{bmatrix} 0 & 0 & 0 \\ 1 & 0 & 0\\ 1& 1& 0\end{bmatrix} $$Definirajmo vektor $e_i$ kao $i$-ti stupac jedinične matrice. Neka je $x=G \cdot e_i$. Tada je
$$ x_{j}=\begin{cases} 1, \text{ako postoji grana iz čvora $i$ u čvor $j$},\\ 0, \text{inače} \end{cases} $$Na primjer (objasnite zašto):
$$ G\cdot e_1 = \begin{bmatrix} 0 & 0 & 0 \\ 1 & 0 & 0\\ 1& 1& 0\end{bmatrix} \cdot \begin{bmatrix}1 \\ 0 \\ 0\end{bmatrix} = \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix}, \quad G\cdot e_2 = \begin{bmatrix} 0 & 0 & 0 \\ 1 & 0 & 0\\ 1& 1& 0\end{bmatrix} \cdot \begin{bmatrix}0 \\ 1 \\ 0\end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}, \\ G\cdot e_3 = \begin{bmatrix} 0 & 0 & 0 \\ 1 & 0 & 0\\ 1& 1& 0\end{bmatrix} \cdot \begin{bmatrix}0 \\ 0 \\ 1\end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix}. $$
In [5]:
G=simple_graph(6,is_directed=true)
add_edge!(G,1,2)
add_edge!(G,1,6)
add_edge!(G,2,3)
add_edge!(G,2,4)
add_edge!(G,3,4)
add_edge!(G,3,5)
add_edge!(G,3,6)
add_edge!(G,4,1)
add_edge!(G,6,1)
GraphViz(to_dot(G),"fdp","svg")
Out[5]:
Koristit ćemo sparse zapis matrice susjedstva u kojem se zapisuju samo indeksi retka i stupca i vrijednost elementa.
In [6]:
i = vec([ 2 6 3 4 4 5 6 1 1])
j = vec([ 1 1 2 2 3 3 3 4 6])
G=sparse(i,j,1)
Out[6]:
In [7]:
full(G)
Out[7]:
In [8]:
# Prebacimo G u "realne" brojeve (Float64)
G=map(Float64,G)
full(G)
Out[8]:
Od ove matrice se napravi matrica slučajne šetnje (random walk) na grafu sa sljedećim uvjetima:
Google koristi $p=0.85$ ?
In [9]:
# Konačna sparse matrica G
p = 0.85
c=sum(G,1)
n=size(G,1)
for j=1:n
if c[j]>0
G[:,j]=G[:,j]/c[j]
end
end
full(G)
Out[9]:
Neka je $e$ vektor sa svim elementima jednakim $1$,
$$ e=\begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix}. $$Matrica $A$ je matrica slučajne šetnje po zadanom grafu, tzv. Markovljeva matrica:
$$ A=pG+ e\cdot z \tag{1} $$
In [10]:
# Definirajmo vektor z
ee=ones(n)
z = ((1-p)*(c.!=0) + (c.==0))/n
Out[10]:
In [11]:
# Definirajmo matricu A
A=p*G+ee*z
Out[11]:
Matrica $A$ ima sljedeća svojstva:
Drugo svojstvo možemo zapisati kao
$$ e^T A = e^T $$odnosno
$$ e^T (I-A)=0. $$Transponiranje jednadžbe daje
$$(I-A^T) e=0.$$Radi se o homogenom sustavu koji ima netrivijalno rješenje pa iz Kronecker-Capelli-jevog teorema slijedi
$$\mathrm{\mathop{rang}}\, (I-A^T)<n.$$No, tada je i
$$\mathrm{\mathop{rang}}\, (I-A)<n$$pa i homogeni sustav
$$(I-A)x=0 \tag{2} $$ima netrivijalno rješenje za koje vrijedi
$$ Ax=x. \tag{3} $$Vektor $x$ s ovim svojstvom zove se vektor stanja Markovljeve matrice. Vrijedi $x_i>0$, a $x$ možemo odabrati tako da je $\sum x_i=1$. Naime, ako je $Ax=x$, onda je i $A(\alpha x)=\alpha x$.
Za tako odabrani $x$, element $x_i$ je težina ili rang stranice $i$.
Težina stranice daje vjerojatnost da se tijekom šetnje po webu posjeti stranica $i$ pa su stranice s većom težinom važnije.
Homogeni sustav (2), odnosno jednadžbu (3), možemo riješiti na nekoliko načina.
Uvrštavanjem oblika (1) u jednadžbu (3) dobivamo
$$ (pG + e \cdot z)x=I\cdot x $$odnosno
$$ (I-pG)x=e(z\cdot x)\equiv \gamma e. \tag{4} $$$\gamma=z\cdot x$ je nepoznati broj pa uzmimo $\gamma=1$.
Ako je $p<1$, onda je matrica $I-pG$ regularna (dokaz preskačemo) pa sustav (4) ima jedinstveno rješenje $x$. PageRank vektor je onda vektor
$$ \frac{x}{\sum x_i}. $$
In [12]:
x=(I-p*G)\ee
Out[12]:
In [13]:
x/=sum(x)
Out[13]:
Možemo i pomnožiti $e$ s inverznom matricom (ne preporuča se):
$$ y=(I-pG)^{-1} e \\ x=\frac{y}{\sum y_i} $$
In [14]:
M=inv(full(I-p*G))
x=M*ee
x/sum(x)
Out[14]:
Ni jedan od prethodnih načina nije moguć za jako velike matrice. Umjesto toga, rješenje jednadžbe $Ax=x$ se može dobiti iterativnom metodom na sljedeći način:
krenimo u slučajnu šetnju od početnog vektora $x_0=\begin{bmatrix} 1/n \\ 1/n \\ \vdots \\ 1/n \end{bmatrix}$ (možemo uzeti i prethodni vektor težina).
formiramo vektore
Matrica $A$ se nikad ne formira već se umnožak $A$ računa kao
$$ Ax=(pG)\cdot x + e \cdot (z\cdot x). $$
In [15]:
function myPageRank(G::SparseMatrixCSC{Float64,Int64},steps::Int)
p=0.85
c=sum(G,1)/p
n=size(G,1)
for i=1:n
G.nzval[G.colptr[i]:G.colptr[i+1]-1]./=c[i]
end
e=ones(n)
x=e/n
z = vec(((1-p)*(c.!=0) + (c.==0))/n)
for j=1:steps
x=G*x+(z⋅x)
end
x/sum(x)
end
Out[15]:
In [16]:
myPageRank(G,15)
Out[16]:
Riješimo malo veći testni problem.
In [17]:
W=readdlm("web-Stanford.txt",Int)
Out[17]:
In [18]:
S=sparse(W[:,2],W[:,1],1.0)
Out[18]:
In [19]:
@time x100=myPageRank(S,100);
In [20]:
x101=myPageRank(S,101)
maxabs((x100-x101)./x100)
Out[20]:
In [21]:
sortperm(x100,rev=true), sort(x101,rev=true)
Out[21]:
In [ ]: