\documentclass[twoside,12pt]{article}
\usepackage{graphicx,latexsym,a4wide,amssymb,amsmath,array}

\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{\Pbold}{\mathbf{P}}
\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: N\'emeth G\'abor \quad
\texttt{gab@complex.elte.hu}} \hfill } }}\end{center}

\vspace*{4mm} }

\newcommand{\vek}[1]{\ensuremath{\mathbf{#1}}}
\newcommand{\T}{\ensuremath{^\mathrm T}}
\newcommand{\kifok}{\textit{kifok}}
\newcommand{\befok}{\textit{befok}}

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

\section{Weboldalak rangsorol\'asa tekint\'elyek (authorities) \'es gy\H
ujt\H ooldalak (hubs) alapj\'an}

K\'et \'uj m\'ert\'eket vezet\"unk be weboldalak \'ert\'ekel\'es\'ere. Az
els\H ot az n\"oveli, ha min\'el t\"obb \'es min\'el jobb oldal linkel
az adott lapra -- ez a tekint\'elym\'ert\'ek, a fontos tartalom m\'er\H oje.
A m\'asodik a gy\H ujt\H ooldalm\'ert\'ek, ami akkor magas, ha az adott
lap min\'el t\"obb nagy tekint\'ely\H u oldalra mutat, azaz j\'o linkgy\H
ujtem\'eny.

A fenti \'ert\'ekel\'est indokolja az a megfigyel\'es, hogy a web
linkszerkezete a fenti modellt k\"oveti. P\'elda erre a h\'arom
magyarorsz\'agi telefont\'arsas\'ag honlapjainak viszonya: a
\texttt{www.matav.hu}, \texttt{www.pannongsm.hu} \'es a
\texttt{www.westel.hu} lapjai egym\'asra nem nagyon mutogatnak, viszont sok olyan
(pld. telefonk\"onyv) oldal van, amelyek mindh\'armukra linkelnek; ez\'ert
ez ut\'obbi oldalak j\'o oldalaknak sz\'am\'itanak azok sz\'am\'ara, akik
magyarorsz\'agi telefont\'arsas\'agok ir\'ant \'erdekl\H odnek. Sz\'amos hasonl\'o,
egy-egy t\'em\'ara koncentr\'al\'o  tekint\'ely- \'es gy\H ujt\H ooldalcsoport
l\'etezik a weben, \'es l\'eteznek algoritmusok, melyek ilyen csoportokat
keresnek. 
% FIXME ausztral tuzoltos pelda

A k\"ovetkez\H okben k\'et algoritmust ismertet\"unk, melyek a fenti
m\'ert\'ekeket haszn\'alj\'ak. A m\'er\H osz\'amokat k\'et l\'ep\'eses
rekurzi\'oval \'all\'itjuk el\H o.

\subsection{A SALSA algoritmus}
Stochastic Approach for Link-Structure Analysis 

%\begin{figure}[!h]
%\includegraphics[keepaspectratio,width=.1\linewidth]{ah}
%\caption{Tekint\'ely- (a) \'es gy\H ujt\H om\'ert\'ekek (h)
%sz\'am\'it\'asa.}
%\end{figure}

\begin{definition}
Legyen \(\vek a=(a_1,\ldots a_n)\) a vizsg\'alt oldalak tekint\'ely-, \(\vek
h=(h_1,\ldots h_n)\) pedig azok gy\H ujt\H osz\'amvektora.
\end{definition}

Tegy\"unk egy bolyong\'ast \'ugy, hogy 
\[\vek a=\vek h\vek M\text{ , ahol } M_{ij}=\left\{
	\begin{array}{cl}
	\frac1{\kifok(i)} & \text{ ha } (i,j)\in E(G),\\
	0 & \text{ egy\'ebk\'ent.}
	\end{array}
	\right.
\]
Ekkor
\[a_j=\sum_{(i,j)\in E(G)}\frac1{\kifok(i)}h_i,\]
azaz \(a_j\) a \(j\) oldalra linket tartalmaz\'o oldalak gy\H ujt\H osz\'am\"osszege.

Hasonl\'o m\'odon vehet\H o az az \(\tilde M\) m\'atrix, amire
\[\vek h=\vek a\vek{\tilde M}\text{, hogy } \tilde M_{ij}=\left\{
	\begin{array}{cl}
	\frac1{\befok(i)} & \text{ ha } (j,i)\in E(G),\\
	0 & \text{ egy\'ebk\'ent.}
	\end{array}
	\right.
\]

A \(t\)-ik l\'ep\'es ut\'an a fenti vektorok
\[\begin{array}{lll}
\vek a^{(t+1)}&=\vek h^{(t)}\vek M&=\vek a^{(t)}\vek{\tilde M}\vek M\\
\vek h^{(t+1)}&=\vek a^{(t)}\vek{\tilde M}&=\vek h^{(t)}\vek M\vek{\tilde M}.
\end{array}\]

\begin{note}
Az \(\left[\vek a^{(t)}\right]_{t\in \mathbb{N}}\) sorozat olyan bolyong\'asnak felel meg, ahol egy
l\'ep\'es az iter\'aci\'o sor\'an
 egy \(\vek a^{(t)}\)-b\H ol indul\'o egyenletes v\'eletlen eloszl\'as\'u be-\'elen val\'o l\'ep\'es,
majd egy onnan egyenletes v\'eletlen ki-\'elen val\'o tov\'abbl\'ep\'es.
\end{note}

Vizsg\'aljuk meg azokat a gr\'afokat, melyeken mozgunk a bolyong\'as sor\'an. Az els\H o az \(\vek
{\tilde MM}\) \emph{tekint\'elygr\'af}, melynek \(ii'\) eleme megadja, hogy h\'any k\"oz\"os hivatkoz\'oja van az \(i\) \'es
\(i'\) oldalaknak. A m\'asik az \(\vek{M\tilde M}\) \emph{gy\H ujt\H ooldalgr\'af}, melynek elemei
pedig a k\"oz\"os hivatkozottak sz\'am\'at adj\'ak. L\'atszik, hogy mindk\'et gr\'af szimmetrikus,
\'es a k\"ovetkez\H okben megmutatjuk, hogy amennyiben nem p\'arosak, akkor van stacion\'arius
eloszl\'asuk.

\begin{claim}
\(\vek{\tilde MM}\)-nek a be-fok \'es \(\vek{M\tilde M}\)-nek a ki-fok.
\end{claim}
\begin{proof}
Az al\'abbiakban csak a tekint\'alygr\'affal foglalkozunk; a gy\H ujt\H ooldalgr\'af anal\'og
m\'odon kezelhet\H o.
\[
a_j=\sum_{(k,j)\in E(G)}\frac1{\kifok(i)}\,h_k
=\sum_{(k,j)\in E(G)}\frac1{\kifok(i)}\sum_{(k,i)\in E(G)}\frac1{\befok(i)}\,a_i,
\]
\'es \(a_i\) hely\'ere \(\befok(i)\)-t helyettes\'itve
\[
a_j=\sum_{(k,j)\in E(G)}\frac1{\kifok(i)}\sum_{(k,i)\in E(G)}1
=\sum_{(k,j)\in E(G)}\frac1{\kifok(i)}\,\kifok(i)
=\befok(i).
\]
\end{proof}

\begin{note}
A ,,k\"olcs\"on\"osen er\H os\'it\H o'' tulajdons\'ag -- a tekint\'ely- a gy\H ujt\H ooldalt \'es
viszont -- elt\H unik az algoritmusb\'ol.
\end{note}

\subsection{A HITS algoritmus}
Hyperlinked Induced Topic Search -- Kleinberg m\'atrixok spektr\'al- \'es szingul\'aris felbont\'asa

M\'odos\'itsuk a SALSA algoritmus \'ugy, hogy az \"osszegz\'esekn\'el nem norm\'alunk a foksz\'ammal.
Ekkor az tekint\'elym\'atrix megegyezik a tekint\'elygr\'af adjacenciam\'atrix\'aval:
\[A_{ij}=\left\{
	\begin{array}{cl}
	1 & \text{ ha } (i,j)\in E(G),\\
	0 & \text{ egy\'ebk\'ent.}
	\end{array}
	\right.
\]
\begin{align*}
\vek a^{(t+1)} &= \vek h^{(t)} \vek A\\
\vek h^{(t+1)} &= \vek a^{(t+1)} \vek A\T
\end{align*}

Az \'igy nyert folyamat nem bolyong\'as; az \"osszegsz\'amok v\'arhat\'oan az \'atlagszorosukra n\H
onek minden l\'ep\'esben. Ha valamilyen hat\'areloszl\'ast keres\"unk, akkor le kell norm\'alni.
(Mindegy, hogy milyen norma szerint.)

Vonjunk \"ossze k\'et l\'ep\'est, \'igy:
\begin{align*}
\vek a^{(t+1)} &= \vek a^{(t)} \vek A\T \vek A\\
\vek h^{(t+1)}&=\vek h^{(t)}\vek{AA}\T
\end{align*}

A tov\'abbiakban csak a tekint\'elyvektorral foglalkozunk; a gy\H ujt\H om\'ert\'ek megfelel\H o
tulajdons\'agai anal\'og m\'odon sz\'armaztathat\'ok.

\begin{claim}
Az \(\vek A\T\vek A\) m\'atrix pozit\'iv szemidefinit \'es szimmetrikus.
\end{claim}
\begin{proof}

\begin{tabular}{ll}
\((\vek A\T\vek A)\T=\vek A\T(\vek A\T)\T=\vek A\T\vek A\) & (szimmetrikus)\\
\(\vek x\T\vek A\T\vek{Ax}=\|\vek{Ax}\|^2\geqslant0\) & (pozit\'iv szemidefinit)
\end{tabular}

\end{proof}

\begin{corollary}
\strut

\begin{enumerate}
\item \(\vek A\T\vek A\) minden saj\'at\'ert\'eke val\'os \'es nemnegat\'iv.
\item \(\vek A\T\vek A\) felbonthat\'o egy \(\vek U\) unit\'er m\'atrix seg\'its\'eg\'evel:
\[\vek A\T\vek A=\vek U\T\left(
	\begin{array}{ccc}
	\lambda_1&&0\\
	&\ddots&\\
	0&&\lambda_n
	\end{array}
	\right).
\]
\end{enumerate}
\end{corollary}

\'All\'itsuk teh\'at el\H o a tekint\'elyvektort az \vek U m\'atrix seg\'its\'eg\'evel. A
\((t+1)\)-ik l\'ep\'esben
\begin{equation*}
\begin{split}
\vek a^{(t+1)}&=\vek a^{(t)}\vek A\T\vek A=\vek a^{(1)}(\vek A\T\vek A)^t
=\vek a^{(1)}\left(\vek U\T\left(
        \begin{array}{ccc}
        \lambda_1&&0\\
        &\ddots&\\
        0&&\lambda_n
        \end{array}
        \right)
	\vek U\right)^t= \\
&=\vek a^{(1)}\vek U\T\left(
        \begin{array}{ccc}
        \lambda_1^t&&0\\
        &\ddots&\\        
        0&&\lambda_n^t
        \end{array}   
        \right)
	\vek U.
\end{split}
\end{equation*}

Ha \(\lambda_1>\lambda_2\geqslant\dots\geqslant\lambda_n\), akkor \(\lambda_1^t\)-val leosztva
kapjuk, hogy:
\[\vek a^{(t+1)}=\vek a^{(1)}\vek U\T\left(
        \begin{array}{ccc}
        1&&0\\
        &\left(\tfrac{\lambda_2}{\lambda_1}\right)^t&\\
        0&&\ddots
        \end{array}
        \right)
	\vek U.
\]
Tekintve, hogy a rangsort nem befoly\'asolja a konstans, amivel osztunk, ez\'ert mindegy, hogy
milyen norm\'at haszn\'alunk. A gyakorlatban ink\'abb az okoz val\'odi probl\'em\'at, hogy gyakran
k\"ozel egyenl\H oek a (legnagyobb) saj\'at\'ert\'ekek.
%
Megmutathat\'o tov\'abb\'a, hogy \vek a \(t\to\infty\) hat\'areloszl\'asa \(\vek a^{(1)}\) \(\vek u_1\)-re es\H o vet\"ulet\'evel
lesz ar\'anyos. Mindenk\'eppen van teh\'at egy sorrendje az oldalaknak, azonban
\'altal\'anoss\'agban nem tudunk ennek sebess\'eg\'er\H ol t\"obbet, mint hogy exponenci\'alis.

\begin{note}
El\H ofordulhat tov\'abb\'a, hogy a vet\"ulet z\'erus, azaz a norma nem megfelel\H o. Ekkor azt a legnagyobb
\(\lambda_i\)-t kell venni, amire igaz, hogy \(\vek a^{(1)}\vek{u_i}\T\neq0\).
\end{note}

P\'elda instabil megold\'asra ha a gr\'afban van k\'et ugyanakkora teljes p\'aros r\'eszgr\'af. Ha a gr\'af nem
\"osszef\"ugg\H o, akkor a k\'et legnagyobb saj\'at\'ert\'ek egyenl\H o lesz. Ha felvesz\"unk egy olyan \'elt, ami
\'atmutat az egyik r\'eszgr\'afb\'ol a m\'asikba, akkor az el\H obbi \"osszes pontsz\'ama
\'atker\"ul az ut\'obbihoz. 

Ebb\H ol a megfigyel\'esb\H ol k\"ovetkezik a HITS t\'emasodr\'od\'asi
tulajdons\'aga (\emph{topic drift}), azaz ha a Web el\'eg nagy r\'eszgr\'afj\'an \'ert\'ekel\"unk
ki, akkor el\'eg val\'osz\'in\H u, hogy a Micro\$oft lesz a j\'o tal\'alat, mert ha k\"ozel ker\"ul
egy nagy p\'aros k\"oz\"oss\'eghez, akkor elsz\'ivja azok pontsz\'am\'at.
Lehets\'eges jav\'it\'asa az algoritmusnak, ha nem csak az els\H o saj\'atvektorra vett vet\"uletet
vessz\"uk, hanem ind\'itunk egy m\'asodik iter\'aci\'ot egy mer\H oleges alt\'eren. Ekkor kapunk
egy m\'asik \vek a \'es \vek h vektort, melyek az els\H o p\'arost\'ol f\"uggetlen szempont
szerinti \'ert\'ekel\'es eredm\'enyei. \'Altal\'anoss\'agban c\'elszer\H ubb egy \(k\)-dimenzi\'os
alteret tekinteni \vek a \'es \vek h helyett.

\end{document}