Модели случайных веб-графов

Модели случайных графов очень интенсивно изучались в течение последних пятидесяти лет. Так, П. Эрдеш и А. Реньи предложили в районе 1960 года две модели, которые сейчас принято называть классическими. В первой модели мы фиксируем два натуральных числа $n$, $M$, удовлетворяющих условию $0<M<C_n^2$. Мы также фиксируем множество вершин $V_n=(1,\dots,n)$ и выбираем случайное множество ребер $E$ мощности $M$ в соответствии с равномерным распределением, т.е. вероятность возникновения $E$ равна $\frac{1}{C_{C_n^2}^M}$. Во второй модели ребра выбираются взаимно независимо с одной и той же вероятностью $p\in[0,1]$, так что мы получаем конкретное множество ребер $E$ с вероятностью $p^{|E|}(1-p)^{C_n^2-|E|}$.
К сожалению, обе модели Эрдеша-Реньи не подходят для адекватного описания многих «реальных» сетей, среди которых социальные сети, биологические сети и Интернет. В последние примерно 15 лет появилось несколько важных новых моделей, использующих различные случайные графовые процессы, которые имеют те или иные статистики, близкие к аналогичным статистикам веба.
В нашем докладе мы дадим обзор моделей так называемых веб-графов. Мы также представим некоторые «классические» и совсем свежие вероятностные результаты, касающиеся этих моделей.