\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: Belcsik Judit\quad \texttt{jutka@inf.elte.hu}} \hfill } }}\end{center} \vspace*{4mm} } \begin{document} \eloadas{Kilencedik el\H{o}ad\'as}{2003. december 11.} \begin{center} \section* {A kis világ modell jellemzése és az ad hoc mobil hálózatok} \end{center} \begin{itemize} \item Kleinberg: The Small-World Phenomenon: An Algorithmic Perspective \item Karger és tsai: A Scalable Location Service for Geographic Ad Hoc Routing \end{itemize} \section{A kis világ modell jellemzése} \noindent Múlt órán: Kis világ modell bevezető \\ \paragraph*{Modell} A gráf csúcsai $2$ dimenziós $n \times n$-es rácspontokon helyezkednek el. Egy csúcsra koordinátáival hivatkozhatunk. Paraméterek: \begin{itemize} \item $p$: rácsbeli $\Delta x+\Delta y$; $p$-nél nem távolabbiakkal mindenki összekötve (ha $p=1$ : mindenki összekötve a szomszédaival, rács élek) \item $q$: hosszú távú élek száma; minden csúcsból $q$ db irányított hosszú távú él indul \item $r$: az eloszlás paramétere; annak a valószínűsége, hogy egy $u$ csúcs egy hosszú távú szomszédjának egy $v$ csúcsot választok: $$ Pr[\textit{v az u q'-edik hosszú távú szomszédja, ahol } q' \leq q] = \frac {d(u,v)^{-r}}{\sum_{u' \neq u} d(u,u')^{-r} }$$ Ha $r=0$: Minden hosszú távú szomszédot egyforma valószínűséggel választok. \end{itemize} \paragraph*{Feladat} Üzenetet eljuttatni adott koordinátájú csúcsnak, rövid úton. \paragraph*{Mit engedünk meg az algoritmusnak} \begin{itemize} \item Tudjon minden hosszú távú éléről azoknak a csúcsoknak, amelyekben már járt. \item Bármikor visszaléphessen oda, ahol már járt. \end{itemize} \begin {note} Ha az algoritmus minden hosszú távú élről tud, akkor szélességi kereséssel megtalálható a legrövidebb út. \end {note} \begin{thm} Ha $r=0$ , akkor a várható lépésszám, amíg adott véletlen célpontot elérünk legalább $ \alpha \cdot n^{\frac 2 3}$, ahol az $\alpha$ konstans a $p$ és $q$-tól függ, de $n$-től nem. \end{thm} \begin {proof} Az $s$ csúcsból indulok, $t$ a véletlenszerűen választott cél. Ilyenkor $$Pr[d(s,t) \geq \frac n 4] \geq \frac 3 4$$ Cél: ezekre az $s$, $t$-kre megmutatni, hogy $\theta (n^{\frac 2 3})$ hosszú távú lépés nem visz t-hez elég közel legalább $\frac 3 4$ valószínűséggel. Legyen ez az "elég közel" $p \cdot n^{\frac 2 3}$. Ebből következni fog a tétel, hiszen így lesz legalább $\frac 1 4$ esély, hogy kezdetben sem vagyunk közel és $\theta (n^{\frac 2 3})$ lépésben sem érünk $p \cdot n^{\frac 2 3}$-nál közelebb, vagyis nem érünk célba $\theta (n^{\frac 2 3})$ lépésben. Legyen $\mathcal{E}_{i}$: az i-edik lépésben olyan $u$ ($u \neq t$) csúcsba érünk, hogy u-nak van v hosszú távú szomszédja, amelyre $d(v,t)

2^j \}$ Cél: $\alpha \cdot \log n$ várható lépésben közelebbi szomszédságba kerüljünk. Egy fázis egy szomszédságnak felel meg, összesen $\log_{2}n$ db fázis van. Ekkor, ha $u$ a $v$ hosszú távú szomszédja: $$Pr[\textit{adott v csúcsban vagyunk, és a fázis véget ér}] \geq Pr[2^j \geq d(u,t)| 2^{j+1} \geq d(v,t) > 2^j]$$ Bizonyítandó: Ha $j>\log_{2}{\log_{2}n}$ : $$Pr[\textit{adott v csúcsban vagyunk, és a fázis véget ér}] \geq \frac 1 {128 \ln(6n)}$$ Ekkor következik a tétel, mert: \begin {itemize} \item A $j>\log_{2}{\log_{2}n}$ fázisok várhatóan $128 \ln(6n)$ lépésben véget érnek. \item Ha $0 \leq j \leq \log_{2}{\log_{2}n}$, akkor a rácson legfeljebb $log_{2}n$ lépés már célba ér. \end {itemize} $$Pr[2^j \geq d(u,t)| 2^{j+1} \geq d(v,t) > 2^j] \geq \sum_{d(v',t) \leq 2^j} Pr[\textit{v' hosszú távú szomszédja v-nek}]=$$ $$=\sum_{d(v',t) \leq 2^j}\frac {d(v,v')^{-2}}{\sum_{v'' \neq v} d(v,v'')^{-2} }$$ A számlálóra alsó becslés: $$d(v,v') \leq d(v,t)+d(v',t) \leq 2^{j+1}+2^j <2^{j+2}$$ Ezért: $$d(v,v')^{-2} \geq 2^{-2(j+2)}$$ \newpage A nevezőre felső becslés: $$\sum_{v'' \neq v} d(v,v'')^{-2} \leq \sum_{d=1}^{2n-2} \sum_{d(v,v'')=d} d(v,v'')^{-2}=\sum_{d=1}^{2n-2}\sum_{d(v,v'')=d}d^{-2} \leq \sum_{d=1}^{2n-2}4dd^{-2}=$$ $$=4 \cdot \sum_{d=1}^{2n-2}\frac 1 d \leq 4(1+{\ln (2n-2)} \leq 4 \ln(6n)$$ Ebből: $$\sum_{d(v',t) \leq 2^j}\frac {d(v,v')^{-2}}{\sum_{v'' \neq v} d(v,v'')^{-2} } \geq \sum_{d(v',t) \leq 2^j}\frac {2^{-2(j+2)}} {4\ln(6n)}$$ És mivel a $v'$-k száma legalább $\frac {(2j)^2} 2$: $$\sum_{d(v',t) \leq 2^j}\frac {2^{-2(j+2)}} {4\ln(6n)} \geq \frac {2^{2j-1} \cdot 2^{-2(j+2)}} {4 \ln(6n)} = \frac 1 {128 \ln(6n)}$$ \end {proof} \section {Ad hoc mobil hálózatok} \paragraph {Location service} Szolgáltatás, ami központi infrastruktúra nélkül (ad hoc) meghatározza a cél földrajzi helyzetét. \paragraph {Feladat} Központi infrastruktúra nélkül találjuk meg kevés ($\log n$) lépésben a cél földrajzi helyzetét. \paragraph {Stratégia} Mindenki kevés ($\log n$) másik állomásnak folyamatosan adja meg a helyét (tehát mindenki location server lesz). \paragraph {Gráf} Minden location serverből él vezet azokhoz, akiknek ismeri a helyét (vagyis minden csúcsból indulnak élek). Az élek irányítatlannak tekinthetők, mert az állomások kölcsönösen ismerik egymás földrajzi helyzetét. \end{document}