\documentclass[twoside,12pt]{article}
\usepackage{graphics,latexsym,a4wide}

\usepackage[latin2]{inputenc}
\usepackage{t1enc}
\usepackage[magyar]{babel}

\newenvironment{proof}{\noindent{\bf Bizony\'{\i}t\'as:}}{\qed\bigskip}
\newenvironment{proof_sketch}{\noindent{\bf Sketch of Proof}\hspace*{1em}}{\qed\bigskip}

\newtheorem{thm}{T\'etel}
\newtheorem{corollary}{K\"ovetkezm\'eny}
\newtheorem{lemma}{Lemma}
\newtheorem{claim}{\'All\'{\i}t\'as}
\newtheorem{definition}{Defin\'{\i}ci\'o}
\newtheorem{example}{P\'elda}
\newtheorem{algorithm}{Algoritmus}
\newtheorem{note}{Megjegyz\'es}
\newcommand{\qed}{$\Box$}

\newcommand{\eloadas}[2]{
%\pagestyle{myheadings}[H\'al\'ozatok \'es a World Wide Web matematik\'aja][#1 \hfill #2]
\thispagestyle{empty}

\noindent
\begin{center}\framebox{
\vbox{
\hbox to 5.875in { {H\'al\'ozatok \'es a World Wide Web matematik\'aja \hfill
        2003/2004 I. f\'el\'ev} }
\vspace{4mm}
\hbox to 5.875in {\hfill {\Large #1}
        \hfill  #2}
\vspace{2mm}
\hbox to 5.875in { {\it El\H{o}ad\'o: Bencz\'ur Andr\'as\quad \texttt{benczur@sztaki.hu} \hfill  } }
\hbox to 5.875in { {\it Jegyzet\'{\i}r\'o: Ber\'enyi Melinda\quad \texttt{melcsi@inf.elte.hu}} \hfill }
}}\end{center}

\vspace*{4mm} }

\begin{document}
\eloadas{Harmadik el\H{o}ad\'as}{2003. okt\'ober 16.}

\begin{center}
\section* 
{A Page Rank újrafogalmazása és két alkalmazása}
\end{center}

\begin{itemize}
   \item Jeh, Widom: SimRank: A Measure of Structural-Context Similarity, KDD2002 Conference 
   \item Jeh, Widom: Scaling Personalized Web Search, WWW2003 Conference
\end{itemize} 
\section{Page Rank újrafogalmazása}

Véletlen bolyongás (véletlen szörföző modellje) \\
\vspace*{3mm}
$r^{(0)}$ : kezdeti eloszlás, sorvektor a weboldalakon \\
A szörföző $(1-d)$ valószínűséggel(uniform véletlen) követ egy linket (egy ki-élen lép), $d$ 
valószínűséggel uniform véletlen helyre ugrik (megunja a dolgot, beír egy URL-t). 
\begin {note}
  Igazából nem uniform véletlen, a barangoló a kedvencei közül választ.
\end{note}

\noindent Múlt órai eredmények: Markov láncok \\

Page Rank:
\begin{itemize} 
    \item erősen összefüggő (sőt teljes) gráfon zajlik (erősen súlyozott)
    \item aperiodikus Markov lánc
    \item mindenféle körhossz előfordul 1-től n-ig
\end{itemize} 

\begin {corollary}
Létezik stacionárius eloszlás ($\pi$). A bolyongás valamilyen sebességgel konvergálni 
fog ehhez. 
\end {corollary}

\noindent Miért kell az uniform véletlen ugrás?
\begin{itemize} 
    \item Zsákutca miatt
    \item Nincs be-él
    \item Ha nem erősen összefüggő a webgráf, akkor az, hogy hova jutunk, erősen függne 
          attól, hogy honnan indulunk. Egy elszigetelt komponensből nem jutnánk ki. 
\end{itemize} 

\noindent A véletlen bolyongás során $(1-d)$ valószínűséggel lép egy ki-élen: 
$$[M]_{ij}=\left\{ \begin{array}{ll}
  0 & \mbox {ha $i$-ből $j$-be nem mutat link} \\
  \frac{1}{ki-fok(i)} & \mbox {k\"ul\"onben} \end{array}\right.,$$
ahol $M$: ki-fokokkal súlyozott adjecencia mátrix\\

\noindent Vagy $d$ valószínűséggel uniform véletlen helyre ugrik: 
$$U= \left(
\begin{array}{ccc}
   \frac{1}{n} & \cdots & \frac{1}{n} \\
   \vdots & \ddots & \vdots \\
   \frac{1}{n} & \cdots & \frac{1}{n} \\
\end{array}
\right)=\left(
\begin{array}{c}
  $u$ \\
  $u$ \\
  \vdots \\
  $u$ \\
\end{array}
\right),$$
ahol $U$: elugrás mátrix ($U$ $\rightarrow$ ,,ugrás'' ), \\
és $u$: tetszőleges eloszlás a weboldalakon \\

\noindent Ezekkel a jelölésekkel az eloszlás a következő rekurzív képlettel számolható:
$$r^{(t)} = r^{(0)} \cdot \left( \left( 1-d \right) \cdot M+d \cdot u \right)^{(t)}=
r^{(0)} \cdot \sum_{\{M,U\}^{t}} (1-d)^x \cdot d^{t-x} \underbrace{MMUMUU}_{t db}$$


\begin{note}
Az utolsó $U$ előtti dolog érdektelen.
\end{note}

\begin{claim}
$XU=U$ \, $\forall$  $X$ olyan mátrixra, melynek oszlopösszege $1$.
\end{claim}

$$r^{(t)} = r^{(0)} \cdot \left( \sum_{t=0}^{n-1} e_t \cdot U \cdot M^t + 
(1-d)^{t} \cdot M^t \right) = $$

$r^{(0)} \cdot U = u $ \\
\hspace*{5mm} $e_t$ : együttható

$$ = u \cdot \sum_{t=0}^{n-1} {e_t \cdot M^t} + 
\underbrace{r^{(0)} \cdot (1-d)^t \cdot M^t}_{\to 0 \mbox{ ha } t \to \infty}$$

Tehát
$$ \pi = u \cdot \sum_{t=0}^{\infty} e_t \cdot M^t $$ Erről tudjuk, hogy konvergál.\\ 


Adott $M$-ek és $U$-k $t$ hosszú sorozata, ahol $M$-et $(1-d)$, $U$-t $d$ valószínűséggel
választjuk (az a súly szorzó kerül elé). \\
Mekkora a valószínűsége (súlya) annak, hogy pontosan $t$ db $M$ legyen a végén?
$$d \cdot (1-d)^t \mbox{ ha } t<n$$

\noindent Tehát:
$$ \pi = u \cdot \sum_{t=0}^{\infty} d \cdot (1-d)^t \cdot M^t$$

\noindent Értelmezés: \\
$M^t$ : $t$ (bolyongó) uniform véletlen lépés a webgráfon (ki-éleken). \\
Összegezzük az $u$ kiinduló helyről tett $t$ hosszú utak végpontjait valamilyen súllyal.
A súly annak felel meg, hogy $d$ valószínűséggel megállok, $(1-d)$ valószínűséggel továbblépek.
Ez geometriai eloszlás az utak hosszán. \\

\begin{corollary}
  Azok a nagy Page Rank-ű oldalak, ahova a lehetséges indulási helyekről rövid utakon el lehet
  jutni.
\end{corollary}

\noindent Page Rank jelentése: \\
A kiindulási helyekről rövid utakon elérhető oldalak a jók.\\

\noindent A megfordított gráfon: \\
Rövid utakon nagyon sok helyre érünk. (Ezek a jó kiinduló helyek.)\\

\begin{note}
  A Page Rank és a fordított gráfon vett Page Rank által jónak talált oldalak általában
  egybeesnek, pedig nem kellene ennek feltétlen így lennie.
\end{note}


A jó kiinduló helyek általában blokkolják a rövid utakat. Ha kevés nagy fordított (vagy 
normál) Page Rank-ű oldalt elhagyunk, akkor nagyon meghosszabbodnak az utak, sőt szétesik
a gráf. (Nem kellene így lennie, de így van.) A fordított jobban ejti szét a webet. \\

\noindent A kiinduló elképzelés megegyezik a végső képlettel: 

\begin{center}
A szörföző megunja magát $\equiv$ célba ér.
\end{center}

\noindent Kérdés: Akarom-e újrakezdeni a bolyongást? \\
Válasz: Végtelennél nem számít.
 
\newpage
\section {Sim Rank}

G:

\begin{picture}(200,120)(0,0)
\put(40,60){\circle{3}}
\put(0,60){\makebox(0,0)[l]{\footnotesize Egyetem}}
\put(80,100){\circle{3}}
\put(80,105){\makebox(0,0)[rb]{\footnotesize Prof A}}
\put(80,20){\circle{3}}
\put(80,15){\makebox(0,0)[rt]{\footnotesize Prof B}}
\put(160,100){\circle{3}}
\put(160,105){\makebox(0,0)[lb]{\footnotesize Diák A}}
\put(160,20){\circle{3}}
\put(160,15){\makebox(0,0)[lt]{\footnotesize Diák B}}
\put(45,62){\vector(1,1){33}}
\put(45,58){\vector(1,-1){33}}
\put(85,100){\vector(1,0){70}}
\put(85,22){\vector(1,0){70}}
\put(155,18){\vector(-1,0){70}}
\put(155,97){\vector(-3,-1){105}}
\end{picture}

\noindent Kérdés: Mennyire hasonlítanak a linkstruktúra alapján ezek az oldalak?

\begin{definition}\  
  \begin{itemize} 
    \item Elsődlegesen azok a  {\bf hasonlók}, akikre minél több közös hivatkozás van. \\
          (Prof A, Prof B hasonlóak, Diák A, Diák B nem hasonlóak) 
    \item Vigyük tovább a hasonlóságot linkek mentén. Ha két olsal hasonló, akkor azok
          is hasonlók valamennyire, akikre mutatnak. 
          Azaz propagáljuk a hasonlóságot linkek mentén.
  \end{itemize}
\end{definition}

\noindent Értemezés: \\
Hasonlóság érték csúcspárra vonatkozik ( az $(a,b)$ vagy $(i,j)$ csúcspárokon). \\
\begin{picture}(400,60)(0,0)
\put(20,30){\circle{3}}
\put(22,35){\makebox(0,0)[rb]{\footnotesize $(a,b)$}}
\put(80,30){\circle{3}}
\put(78,35){\makebox(0,0)[lb]{\footnotesize $(i,j)$}}
\put(75,30){\vector(-1,0){50}}
\put(200,30){\makebox(0,0)[l]{\footnotesize Ha $(i,a)$ $\in$ $G$ és $(j,b)$ $\in$ $G$}}
\end{picture}

Az ilyen élek mentén visszük tovább a hasonlóság értékeket Page Rank-szerűen.\\
Leghasonlóbbak az $(i,i)$-k.\\
\newpage
\noindent$G^2$ lényeges részgráfja \\(ha $1-d=0.8$): \\
\begin{picture}(250,200)(0,0)
\put(150,190){\oval(35,15)}
\put(150,190){\makebox(0,0){\footnotesize E,E}}
\put(165,198){\makebox(0,0)[lb]{\footnotesize $0.1$}}
\put(150,150){\oval(35,15)}
\put(150,150){\makebox(0,0){\footnotesize PA,PB}}
\put(165,158){\makebox(0,0)[lb]{\footnotesize $0.414$}}
\put(150,110){\oval(35,15)}
\put(150,110){\makebox(0,0){\footnotesize DA,DB}}
\put(165,118){\makebox(0,0)[lb]{\footnotesize $0.331$}}
\put(150,70){\oval(35,15)}
\put(150,70){\makebox(0,0){\footnotesize E,PB}}
\put(165,78){\makebox(0,0)[lb]{\footnotesize $0.132$}}
\put(100,40){\oval(35,15)}
\put(100,40){\makebox(0,0){\footnotesize PA,DB}}
\put(115,32){\makebox(0,0)[lt]{\footnotesize $0.106$}}
\put(200,40){\oval(35,15)}
\put(200,40){\makebox(0,0){\footnotesize PB,DB}}
\put(215,32){\makebox(0,0)[lt]{\footnotesize $0.088$}}
\put(50,70){\oval(35,15)}
\put(50,70){\makebox(0,0){\footnotesize DA,PB}}
\put(65,78){\makebox(0,0)[lb]{\footnotesize $0.042$}}
\put(50,110){\oval(35,15)}
\put(50,110){\makebox(0,0){\footnotesize E,DB}}
\put(65,102){\makebox(0,0)[lt]{\footnotesize $0.034$}}
\put(150,180){\vector(0,-1){20}}
\put(150,140){\vector(0,-1){20}}
\put(150,100){\vector(0,-1){20}}
\put(170,70){\vector(1,-1){20}}
\put(130,70){\vector(-1,-1){20}}
\put(80,40){\vector(-1,1){20}}
\put(50,80){\vector(0,1){20}}
\put(70,120){\vector(2,1){55}}
\put(225,50){\oval(20,20)[r]}
\put(225,50){\oval(20,20)[lt]}
\put(225,40){\vector(-1,0){6}}
\end{picture}

\noindent A Sim Rank pontszámot utak összegeként határozzuk meg (exponenciálisan súlyozva). \\
Nem adjuk át az egész hasonlóságot, az élek mentén a hasonlóság $(1-d)$-szeresét adjuk csak át.
Iteratív képlet ($S$: Sim Rank):
$$S(a,b)=\left\{ \begin{array}{ll}
  1 & \mbox {ha $a=b$ (ne vezessen vissza él)} \\
  \frac{1-d}{be-fok(a) \cdot be-fok(b)} \cdot \sum_{(i,a) \in G} \sum_{(j,b \in G)} S(i,j) 
   & \mbox {k\"ul\"onben} \end{array}\right. $$\\

\noindent Kapcsolat a Page Rank-kel a csúcspárok gráfon:
\begin{itemize}
  \item (a,a)-ba vezető éleket töröljük
  \item Indulás: (a,a) típusú éleken uniform
\end{itemize}
$$u=\left(\underbrace{1}_{(a,a)} 0 \ldots 0 \underbrace{1}_{(b,b)} 0 \ldots \, \right)$$
Ez egy kicsit módosított Page Rank.

\section{Personalized Page Rank} 
Cél: Egy \emph{Google} típusú és méretű kereső személyre szabottan rangsoroljon.\\
A felhasználók kedvenc helyei (1000-10.000 URL) a Page Rank-nél úgy legyenek figyelembe véve, 
hogy elugrás mindig a kedvencekre legyen (ezekről indulva jussak célba) a Page Rank definícióban.

\begin{note}
  A Page Rank ma már nem olyen fontos (szűrő szerepe van inkább).
\end{note}

\noindent Méretek a Page Rank-ben:\\
\hspace*{20mm} $n=10^{10}$ weboldal\\
\hspace*{20mm} ($n=3 \cdot 10^9$ a \emph{Google} szerint)

\noindent Ha a site-okat egy csúcsnak tekintem: \\
\hspace*{20mm} Magyarországon: $n=10^7 \rightarrow 30.000$\\
\hspace*{20mm} A teljes web-en: $n=3 \cdot 10^9 \rightarrow 10^8$\\
Ezek nagyon nagy számok, időigényes velük a számolás, ezért előre ki kell számolni.
\begin{enumerate}
  \item ötlet: $\pi=u \cdot \sum d \cdot (1-d)^t \cdot M^t$ képlet $u$-ban lineáris.\\
        Ezért elég egy bázist tárolni és abból számolni. De egy $10^8 \times 10^8$-as 
        mátrix is túl nagy. \\
        Korlátozás: $u$ csak a top párszázezer Page Rank-ű oldalak közül lehet.
  \item ötlet: (utána még sok algoritmikus trükk jön)\\
        \begin{picture}(400,75)(0,0)
        \put(45,45){\circle{40}}
        \put(45,60){\makebox(0,0){\footnotesize $H$}}
        \put(50,45){\makebox(0,0){\footnotesize $h$}}
        \put(40,40){\circle*{2}}
        \put(10,10){\line(1,1){30}}
        \put(10,10){\line(1,0){30}}
        \put(40,40){\line(0,-1){30}}
        \put(50,40){\circle*{2}}
        \put(50,40){\line(-1,-2){17}}
        \put(50,40){\line(1,-2){17}}
        \put(34,7){\line(1,0){33}}
        \put(60,40){\circle*{2}}
        \put(60,40){\line(-1,-4){7}}
        \put(60,40){\line(1,-2){14}}
        \put(53,13){\line(1,0){22}}
        \put(120,60){\makebox(0,0)[l]{\footnotesize $H$: top párszázezer}}
        \put(120,40){\makebox(0,0)[l]{\footnotesize $h \in H$-ból ($H-h$) érintése nélkül 
         elérhető részek kicsik,}}
        \put(120,30){\makebox(0,0)[l]{\footnotesize kicsi átfedéssel (összesen is kicsik).}}
        \put(120,10){\makebox(0,0)[l]{\footnotesize Tapasztalat szerint jól szétdarabolják a 
         maradék oldalakat.}}
        \end{picture}
        
        Page Rank képlete, ha $u=\left( 0 \ldots 0 1 0 \ldots 0 \right)$ (1 db $h \in H$).
\end{enumerate}
\begin{definition}\
\begin{itemize}
  \item ${\bf r_h^*}$: Page Rank csak a $h$-ból elérhető részgráfon.
  \item ${\bf r_h}$: $h$-ba elugró Page Rank
  \item $r_h-r_h^*={\bf r_h^H}$: Page Rank csak az olyan utakon, amelyek tartalmaznak a $h$ után még 
  egy $H$-belit.
\end{itemize}
\end{definition}

\noindent
$r_h^H(h^{'})$: központ personalizált Page Rank vektorai. $h,h^{'} \in H$ jól lehet számolni.\\

\noindent$r_h^H(x)$ \, $x \notin H$\\

\begin{picture}(400,85)(0,0)
        \put(0,0){\line(1,0){85}}
        \put(0,0){\line(0,1){85}}
        \put(85,85){\line(-1,0){85}}
        \put(85,85){\line(0,-1){85}}
        \put(35,45){\circle{40}}
        \put(75,75){\makebox(0,0){\footnotesize $G$}}
        \put(45,55){\makebox(0,0){\footnotesize $H$}}
        \put(30,80){\makebox(0,0){\footnotesize $x$}}
        \put(25,40){\makebox(0,0){\footnotesize $h^{'}$}}
        \put(45,38){\makebox(0,0){\footnotesize $h$}}
        \put(57,20){\makebox(0,0){\footnotesize $r_h^*$}}
        \put(30,75){\circle*{2}}
        \put(30,45){\circle*{2}}
        \put(40,35){\circle*{2}}
        \put(40,35){\vector(-1,1){10}}
        \put(30,48){\vector(0,1){25}}
        \put(40,35){\line(-1,-2){15}}
        \put(40,35){\line(1,-2){15}}
        \put(25,5){\line(1,0){30}}
        \put(110,50){\makebox(0,0)[l]{\footnotesize Meg kell nézni az utolsó kilépést a $H$-ból.}}
        \put(110,30){\makebox(0,0)[l]{\footnotesize Az utakat szétbontjuk a $H$-ból való 
         utolsó $h^{'}$ kilépésig,}}
        \put(110,15){\makebox(0,0)[l]{\footnotesize és utána ($r_{h^{'}}^*$).}}
        \end{picture}
\end{document}