\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ó: Kőmíves Zoltán\quad \texttt{zolaemil@elte.hu}} \hfill }
}}\end{center}

\vspace*{4mm} }

\begin{document}


\eloadas{Hatodik előadás}{2003. nov. 20.}

\section{Bevezetés a webgráf modellhez}
  
  A modell egzakt definícója a következő előadás anyaga, Egyelőre egy intuitív definíciót adunk:

\begin{definition}
  Rögzítsünk egy $d>0$ egész számot! A gráf minden csúcsa véletlen szerűen választ 
  magának $d$ db szomszédot.
\end{definition}

\subsection{A modell tulajdonságai}
\begin{enumerate}
  \item A fokszám eloszlás binomiális, ui.: egy adott csúcs egy másikat rögzített $p=d/n$
  valószínűséggel választ, és összesen n ilyen választás van. A határeloszlása \emph{Poisson}, 
  nagy k fokszámok valószínűságe ~$ exp$.
  \item Homogénen néz ki, nincsen klaszterződés:
  \smallskip
  
  \begin{claim}
    G webgráf esetén legyen $S \subset G$ úgy, hogy $|S|<n/2$
    Ekkor minden  $v \in S$-hez létezik $\epsilon$, hogy van legalább $\epsilon |S|$ szomszédja $S$-en kívül.
  \end{claim}
  \item Kicsik a távolságok: A definícióból ill. az előző tulajdonságból adódóan az i lépéses szomszédok 
  száma $(1+\epsilon)^i$. Ebből adódik, hogy $\forall v \in G$ csúcsból $O(\log n)$ lépést téve $G$ csúcsainak 
  több mint fele elérhető.
  \item Teljes páros részgráfok kialakulása nagyon valószínűtlen.
\end{enumerate}


\subsection{A webgráf modell kritikája}
\begin{enumerate}
  \item Mérések szerint, amíg a webgráfban óriási fokszámú csúcsok is vannak (pl. \emph{google}), jelenleg 
  a csúcsok átlagos fokszáma 7-9 közé tehető. A modellben ezzel szemben a nagy fokszámú csúcsok száma 
  exponenciálisan cseng le.
  \item Homogenitás, expanzió: A modellel ellentétben a valóságban nyilvánvalóan léteznek olyan csoportok, 
  melyek sokkal inkább egymásra mutatnak csak, mint a külvilág felé.
  \item Az átmérő tekintetében a modell jól működik. Jelenleg a magyar web (irányítatlan) átmérője 9, világ 
  viszonylatban ugyanez a szám 20.
  \item Páros klikkek: Egy 1998-as mérés során (100 millió oldalas minta) 1000 db $K_{7,20}$ klikket találtak.
  ($K_{i,j}$ klikk esetén $i$ és $j$ a komponensek csúcsszámait jelölik.) A modell szerint egy db $K_{7,20}$ klikk
  létrejöttének valószínűsége $(7!(\frac{1}{n})^7)^{20}$ ~ $O(n^{-140})$.
\end{enumerate}

\subsection{Észrevételek történeti sorrendje}
  
  \begin{enumerate}
  \item  Már 1926-ban vizsgálták a tudományos citációk gráfját, és arra a sejtésre jutottak, hogy a nagy fokszámú
  csúcsok arányának lecsengése polinomiális sebességű. Később foglalkoztak a telefonhívások hálózatának vizsgálatával is.
  \item 1998: Kleinberg - páros klikkek vizsgálata
  \item 1999: Albert-Barabási - polinomiális lecsengés kimérése.
  \item 2000: Kumar és társai - \emph{Stochastic Models for the Web Graph}
  \item1997(98??): Watts-Strogatz - átmérő és klasztereződés. Ők szociális hálózatokkal foglalkoztak, és megmutatták,
  kis átmérő mellett jelen van a klasztereződés. 
  \end{enumerate}
\section{Alber-Barabási modell}
\begin{definition} {\bf Véletlen folyamat}:
  \begin{enumerate}
    \item A csúcsok időben egymás után érkeznek.
    \item Minden csúcs választ m db szomszédot.
    \item Minden $(i,j) \in G$-t $fok(i,j)$-vel arányos valószínűséggel választ.    
  \end{enumerate}
  \begin{note}
    \begin{enumerate}
      \item A modellben irányítatlan gráf szerepel, amely nem felel meg a valóságnak. Ezzel a kérdéssel a modell 
      alkotói nem foglalkoztak.
      \item A definíció nem teljesen precíz. Precíz definíciót Bollobás és társai adtak. Ők megoldották az irányítás
      kérdését is, és nem utolsó sorban ők adtak helyes bizonyítást a következő tételre.
    \end{enumerate}
  \end{note}
\end{definition}

\begin{thm}
  $P(fok(v)=k)~ k^{-3}, \mbox{ha $k$ nem nagyon nagy}$
\end{thm}

Elsőként Albert és Barabási bizonyítását tárgyaljuk, de mint látni fogjuk, ez a bizonyítás rossz:
\begin{proof}
  $$P_k=\{v: E(fok^{(n)}(v)>k\}.$$
  Ekkor
  \begin{eqnarray} 
    |P_k|=\frac{m^2n}{k^2},
  \end{eqnarray}
  ahol $fok^{(n)}(v)$ a v fokszámát jelöli n lépés (újabb csúcs érkezése) után. Tekintve $P_{k+1}$ és $P_k$ külömbségét
  $$m^2n(\frac{1}{k^2}-\frac{1}{(k+1)^2}) \ \frac{m^2n}{k^2}$$
\end{proof}
Alber és Barabási ezzel bizonyítottnak tekintik az állítást, holott az csupán ebből még nem következik: legyen 
$$X_i=\left\{ \begin{array}{cc}
 2i & \mbox{$\frac{1}{2}$ valószínűséggel} \\
 0 & \mbox{$\frac{1}{2}$ valószínűséggel} \end{array}
\right. $$ Ekkor nyilván $E(X_i)=i$ és
$$|\{i: E(X_i)=i\}|=1,$$ vagyis ha $fok^{(n)}(v)$-k szórása nagyon nagy, akkor $(1)$ nem mond semmit az állításról.
\smallskip

\begin{proof} \\
  $i \in {\bf N}$ jelentse most azt a $v \in G$ csúot, amit $i$-edikként választottunk, $n$ pedig legyen a csúcsok száma!
  $$E(fok^{(n+1)}(i)-fok^{(n)}(i))=m\frac{fok^{(n)}(i)}{\sum_{j\leq n}{fok^{(n)}(j)}}=
  m\frac{fok^{(n)}(i))}{2nm}=\frac{1}{2n}fok^{(n)}(i)$$
  Az egyenlet mindkét oldalának várható értékét véve (?)
 \begin{eqnarray}
   E(fok^{(n+1)}(i)-fok^{(n)}(i))&=&\frac{1}{2n}E(fok^{(n)}(i)) \nonumber\\
    E(fok^{(n+1)}(i))&=&(1+\frac{1}{2n})E(fok^{(n)}(i). \nonumber
 \end{eqnarray}  
 Egy rekurzív formulát kaptunk, amiből
 \begin{eqnarray}
   E(fok^{(n+1)}(i)-fok^{(n)}(i)) = m(1+\frac{1}{2i})(1+\frac{1}{2(i+1)})\cdots(1+\frac{1}{2(n-1)}) = \nonumber\\ 
   m\frac{1+2i}{2i}\frac{3+2i}{2i+2}\frac{5+2i}{2i+4}\cdots\frac{2n-1}{2n-2} = \theta(m\sqrt{\frac{n}{i}}). \nonumber
 \end{eqnarray}
 Az állításra nézve tehát az adódik, hogy
   $$|P_k| = |\{i: m\sqrt{\frac{n}{i}}>k\}|=|\{i: \frac{m^2n}{k^2}>i\}| = \frac{m^2n}{k^2},$$
 amit látni akartunk.
\end{proof}
\end{document}