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

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

\newenvironment{proof}{\noindent{\bf Bizonyítás:}}{\qed\bigskip}
\newenvironment{proof_sketch}{\noindent{\bf Sketch of Proof}\hspace*{1em}}{\qed\bigskip}

\newtheorem{thm}{Tétel}
\newtheorem{corollary}{Következmény}
\newtheorem{lemma}{Lemma}
\newtheorem{claim}{Állítás}
\newtheorem{definition}{Definíció}
\newtheorem{example}{Példa}
\newtheorem{algorithm}{Algoritmus}
\newtheorem{note}{Megjegyzés}
\newcommand{\qed}{$\Box$}

\newcommand{\eloadas}[2]{
%\pagestyle{myheadings}[Hálózatok és a World Wide Web matematikája][#1 \hfill #2]
\thispagestyle{empty}

\noindent
\begin{center}\framebox{
\vbox{
\hbox to 5.875in { {Hálózatok és a World Wide Web matematikája \hfill
        2003/2004 I. félév} }
\vspace{4mm}
\hbox to 5.875in {\hfill {\Large #1}
        \hfill  #2}
\vspace{2mm}
\hbox to 5.875in { {\it Előadó: Benczúr András\quad \texttt{benczur@sztaki.hu} \hfill  } }
\hbox to 5.875in { {\it Jegyzetíró: Megyesi Zoltán\quad \texttt{megyesi@sztaki.hu}} \hfill }
}}\end{center}

\vspace*{4mm} }

\begin{document}
\eloadas{Első előadás}{19103. május 35.}

\section{A félév tematikája}
\begin{enumerate}
\item Rangsorolások hiperlink struktúra alapján
  \begin{enumerate}
  \item Page Rank
    \begin{enumerate}
    \item Definíció
    \item Véletlen bolyongás
    \item Friss eredmények
    \end{enumerate}
  \item Kleinberg algoritmus (HITS/SALSA)
    \begin{enumerate}
    \item Definíció
    \item Véletlen bolyongás, mátrixok spektrál- és szinguláris felbontása
    \end{enumerate}
  \end{enumerate}
  \item Gráfklaszterezés, spektrál-klaszterezés
  \item Webgráf modellek
  \item Tartalom cache-elés, gyorsítás
\end{enumerate}

\section{Rangsorolások hiperlink struktúra alapján}
\subsection{Bevezetés}
A fejezetben tárgyalt probléma webes keresésre ad megoldást. A
klasszikus probléma szabad-szavas keresés, azaz megtalálni minden olyan
oldalt amiben szerepel a keresett szó. Például a Budapest szót
keressük, ami legalább 1,2 millió weboldalon szerepel. Mivel rengeteg
oldalon lehet találat, szükség van a weboldalak rangsorolására úgy,
hogy lehetőleg az első 10-ben benne legyen amit keresünk.
Erre a problémára több megoldás is lehetséges. A keresés futhat az
alábbiak alapján:
\begin{enumerate}
\item szóelőfordulás

  Az az oldal kap több pontot, amelyben a szó többször szerepel. (Így
  működik pl. az \emph{Altavista} kereső)

  Módosítások:
  \begin{enumerate}
    \item HTML elemek vizsgálatával (pl. \url{www.budapest.hu} értékesebb)
    \item title-ben, header-ben értékesebbek a találatok (ezt a \emph{google}
    is használja)
  \end{enumerate}
\item Anchor szövegek értékelése (ebben is jó a \emph{google})

  Találatok hiperlinkekben általában a legjobb oldalakra mutatnak. Pl.
  a \\ \emph{<a href=''...''>Budapest</a>} link által mutatott oldal lehet hogy
  sokkal jobb mint az amelyikben csak szerepel a szó.
\item Hiperlink struktúra alapján

  Az értékelés az alapján történik, hogy hány link mutat az adott
  oldalra. Ez a legjobb módszer a keresett oldalak rangsorolására.
  A web oldalaknak egy gráf struktúrát kell megfeleltetni, ami alapján
  számolható a pontszám (pl.: szót tartalmazó és legnagyobb $be-fok$ú
  csúcsokat keressük). Sajnos az egyszerűbb modellek könnyen
  manipulálhatóak, ezért a cél minél robusztusabb módszerek
  kialakítása. Az alábbi gráfmodellek elterjedtek:

  \begin{enumerate}
    \item Minden HTML oldal egy csúcs, minden hiperlink egy él

      Ezzel a modellel az a tapasztalat, hogy a linkgyűjtemények, vagy
      erős belső link struktúrájú webhelyek könnyen előtérbe kerülnek.
    \item Minden \emph{site} (pl.: \url{www.budapest.hu}) egy csúcs.

      A tapasztalat azt mutatja, hogy olyan helyek kerülnek előtérbe,
      ahova sok hiperlink mutat (pl.: \url{www.freeweb.hu}).

    \item URL elemzés: minden felhasználó egy csúcs
      
      Ehhez döntési fával meg kell tanítani mi tartozik egy
      felhasználó oldalához. Pl.: \url{www.freeweb.hu/username}, vagy
      \url{cs.elte.hu/~username}. 
  \end{enumerate}
\end{enumerate}

\subsection{Page Rank}

\begin{definition}

  {\bf Népszerűség:}

  \begin{itemize} 
    \item Egy oldal {\bf népszerű}, ha sok link mutat rá. ($be-fok$)
    \item Egy oldal még népszerűbb, ha népszerű oldalakból mutat rá
    sok link
  \end{itemize}

\begin{note}
A definíció első pontja egy könnyen manipulálható feltétel, ezért van
szükség a másodikra. A definíció alapján egy iteratív algoritmussal
megállapítható egy oldal népszerűsége.
\end{note}

\smallskip
   {\bf Népszerűség iteratív definíciója:}
\bigskip

  Van $n$ weboldalunk, amit szeretnénk
  pontozni. A weboldalakat feleltessük meg egy $G$ gráf csúcsaival, és
  a hiperlink hivatkozásokat a gráf irányított éleivel.
  Jelölje $E$ az élek halmazát. 

  Pontozzuk a csúcsokat, kezdetben minden csúcs pontja legyen
  $1/n$. Mivel az összeg 1 ez egy valószínűség eloszlás.

\begin{note}
  Ha külön nem jelöljük, a vektorokat sorvektorként használjuk.
\end{note}

  Jelölje $v^{(t)}=(v_{1},..,v_{n})$ a csúcsok pontjait a $t$-edik lépés
  után. 
  \smallskip

  A jelölést használva:
  $v^{(0)}=(\frac{1}{n},..,\frac{1}{n})$
  \smallskip

  A $t+1$. iteráció:
  
  $$v_{i}^{(t+1)}=\sum _{(j,i)\in E}\frac{v_{i}^{(t)}}{ki-fok(j)}$$
  
\smallskip

A weboldalak népszerűsége megállapítható kellő számú iteráció után a
gráfcsúcsok pontjai alapján.
\end{definition}

\begin{definition}
  $A$ adjecencia mátrix, ha 
  $[A]_{ij}=\left\{ \begin{array}{cc}
  1 & \textrm{ha}\, (i,j)\in E\\
  0 & \textrm{különben}\end{array}
  \right.$
\end{definition}
\begin{definition}
  $M$ bolyongás, vagy Markov lánc mátrix, ha
  $[M]_{ij}=\left\{ \begin{array}{cc}
  \frac{1}{ki-fok(i)} & \textrm{ha}\, (i,j)\in E\\
  0 & \textrm{különben}\end{array}
  \right.$
\end{definition}
\begin{definition}
  A fenti jelöléseket használva az iterációt így írhatjuk:
  $v^{(t+1)}=v^{(t)}\cdot M$
\end{definition}

\begin{note}
  A fenti definícióval több probléma is van, például nyelő és forrás esetén:
\begin{enumerate}
  \item Nyelő ($ki-fok$ 0, $be-fok$ nem 0 ): Elnyelik a pontokat
  \item Források ($be-fok$ nem 0, $ki-fok$ 0): Nem kapnak pontot és gyorsan kifogynak
\end{enumerate}
\end{note}
\begin{definition}
  Véletlen szörföző modell. 

  Indulunk $v$ eloszlás szerint, lépünk egyet a gráfon az aktuális
  csúcsból uniform véletlen $\textrm{ki-élen}$, vagy uniform véletlen helyre ugrunk. 
  Azaz $d$ paramétertől függően 
\begin{enumerate}
  \item $1-d$ valószínűséggel uniform véletlen lépés $\textrm{ki-élen}$
    (azaz $\frac{1}{ki-fok(\textrm{aktuális
    csúcs})}$ valószínűséggel választunk egy élt).
  \item $d$ valószínűséggel uniform véletlen helyre ugrunk.
\end{enumerate}
\begin{note}
  A $d$ paraméter az angol \emph{damping} szóból jön. A szörföző
  elunja magát és beír egy véletlen internet címet. Tipikusan $0.1$
  és $0.2$ közötti értékekkel használják.

  Haszna, hogy kiszabadul a csapdákból és forrásba is kerülhet.
\end{note}
\end{definition}
\begin{definition}
  A fenti definíció határeloszlása (Markov-lánc terminológiával) a
  {\bf Page Rank} pontozás. (Brin -- Page stanfordi szerzőpáros után))
\begin{note}
  A gyakorlatban $v^{(t)}=(v_{1},..,v_{n})$
  eloszlásból indulva elég sok (pl. 100) iteráció utáni eredményt
  veszik pontozásként.
\end{note}
\end{definition}

\begin{thm}
  A Page Rank iteráció konvergens, és minél nagyobb $d$, annál
  gyorsabban konvergál.
\end{thm}

\begin{proof}
  Az eredeti definíció szerint egy iteráció:
  $v^{(t+1)}=v^{(t)}\cdot M$ volt. 

  Legyen $[U]_{ij}=\frac{1}{n}
  \ \textrm{minden}\ (i,j)\in E$-re. 

  Ezeket a jelöléseket használva a módosított
  bolyongás így írható:
  $$v^{(t+1)}=(1-d)v^{(t)}\cdot M+dv^{(t)}\cdot U$$ 

  Ha $v^{t}$ valószínűségi eloszlás, akkor
  $v^{(t)}\cdot U=(\frac{1}{n},..,\frac{1}{n})=u$. 
  \bigskip

  Egyszerűsítve a fenti képletet
  $$v^{(t+1)}=v^{(t)}\cdot ((1-d)M+dU)$$ ahol
  $$v^{(t)}=v^{(0)}\cdot ((1-d)M+dU)^{t}=v^{(0)}\cdot \sum _{X\in \{M,U\}^{t}}
  (1-d)^{\#_{M}(X)}d^{\#_{U}(X)}X.$$ 
  A képletben $\{M,U\}^{t}$ az $M$ és $U$
  -ból álló $t$ hosszú sorozatokat jelöli (pl. $MUUM..UMM$), $\#_{M}(X)$ az $M$-ek,
  $\#_{U}(X)$ pedig az
  $U$-k száma az $X$ sorozatban.


  Észrevehetjük, hogy $M$-ben minden
  sorösszeg 1 (azaz minden sor valószínúségi eloszlás), így $MU=U$ (és $UU=U$ is igaz). Ezt használva
  $$v^{(t)}=v^{(0)}\cdot \sum _{l=0}^{t-1}((1-d)^{l}dUM^{l}+(1-d)^{t}M^{t}),$$
  ahol $l$ az utolsó $U$ utáni $M$-ek száma, mivel csak az utolsó $U$
  utáni rész számít. 
  \bigskip
  
  Így:
  $$v^{(t)}=u\cdot \sum
  _{l=0}^{t-1}(1-d)^ldM^{l}+v^{(0)}\cdot (1-d)^{t}M^{t}.$$ Ahol az
  összeg első tagja nem függ $v^{(0)}$-tól és nem nő nagyra, a második tag pedig tart
  0-hoz, ha $t$ tart a végtelenhez.
\end{proof}

\end{document}