Модели Интернета

Долгопрудный: Издательский Дом «Интеллект», 2013. — 64 с. : Учебное пособие. ISBN 978-5-91559-143-0Учебное пособие посвящено моделированию Интернета, который был диковинкой для большинства из нас еще каких-то 15 лет назад. Сейчас мы ежедневно пользуемся ресурсами Интернета - поиском, электронной почтой, блогами и др. Сеть динамично развивается, растет и усложняется, а потому рядовому пользователю может казаться, что в Интернете царит полный хаос. Однако в реальности все устроено намного интереснее. Многочисленные статистические исследования показывают, что есть ряд законов, которым подчиняется «всемирная паутина». В частности, эти законы связаны с интерпретацией Интернета как графа, вершины которого - сайты, а ребра - гиперссылки. В книге описаны основные законы такого типа и рассказано, как современная математика помогает их моделировать.Для понимания книги читателю понадобится знание основ комбинаторики, теории графов и теории вероятностей. Книга будет полезна студентам, аспирантам и преподавателям технических ВУЗов, а также всем, кто интересуется приложениями математики к моделированию «сложных сетей» - Интернета, социальных, биологических, транспортных и других сетей.ОГЛАВЛЕНИЕВведение Свойства Интернета Основные объекты и общая идеология их изучения Количество ребер Гигантская компонента Устойчивость и уязвимость Диаметр Степени вершин Вторые степени вершин Пейджранк Количество ребер между вершинами заданных степеней Корреляции степеней вершин Кластерные коэффициенты Число копий фиксированного графа Модели хост-rрафов Общая концепция Модель Эрдеша-Реньи Модели Барабаши-Альберт Модель Боллобаша-Риордана: определения Динамическое определение модели Статическое определение модели Модель Боллобаша-Риордана: результаты Гигантская компонента, устойчивость и уязвимость Диаметр Степени вершин Вторые степени вершин Пейджранк Количество ребер между вершинами заданных степеней Кластерные коэффициенты Число копий фиксированного графа Уточнения модели Боллобаша- Риордана : начальная притягательность вершины Несколько вводных замечаний Модель Бакли-Остгуса Модель Мори Степени вершин Вторые степени вершин Количество ребер между вершинами заданных степеней Кластерные коэффициенты Число копий фиксированного графа Удивительное соответствие модели Бакли-Остгуса реальному хост-графу Классификация ссылочного спама Дальнейшие уточнения модели Боллобаша-Риордана Несколько вводных замечаний Модель Боллобаша-Боргса-Риордана-Чайес Модель копирования Модель Купера-Фриза Модель Холма-Кима Схемы и идеи некоторых доказательств Несколько вводных слов Схема доказательства теоремы Схема доказательства теоремы Неравенства плотной концентрации и теоремы об асимптотическом распределении Несколько вступительных слов Неравенство Чебышёва Неравенство Азумы-Хёффдинга Неравенство ТалагранаСписок литературы Долгопрудный: Издательский Дом «Интеллект», 2013. — 64 с. : Учебное пособие. ISBN 978-5-91559-143-0Учебное пособие посвящено моделированию Интернета, который был диковинкой для большинства из нас еще каких-то 15 лет назад. Сейчас мы ежедневно пользуемся ресурсами Интернета - поиском, электронной почтой, блогами и др. Сеть динамично развивается, растет и усложняется, а потому рядовому пользователю может казаться, что в Интернете царит полный хаос. Однако в реальности все устроено намного интереснее. Многочисленные статистические исследования показывают, что есть ряд законов, которым подчиняется «всемирная паутина». В частности, эти законы связаны с интерпретацией Интернета как графа, вершины которого - сайты, а ребра - гиперссылки. В книге описаны основные законы такого типа и рассказано, как современная математика помогает их моделировать.Для понимания книги читателю понадобится знание основ комбинаторики, теории графов и теории вероятностей. Книга будет полезна студентам, аспирантам и преподавателям технических ВУЗов, а также всем, кто интересуется приложениями математики к моделированию «сложных сетей» - Интернета, социальных, биологических, транспортных и других сетей. **ОГЛАВЛЕНИЕ** Введение **Свойства Интернета** Основные объекты и общая идеология их изучения Количество ребер Гигантская компонента Устойчивость и уязвимость Диаметр Степени вершин Вторые степени вершин Пейджранк Количество ребер между вершинами заданных степеней Корреляции степеней вершин Кластерные коэффициенты Число копий фиксированного графа **Модели хост-rрафов** Общая концепция Модель Эрдеша-Реньи Модели Барабаши-Альберт Модель Боллобаша-Риордана: определения Динамическое определение модели Статическое определение модели Модель Боллобаша-Риордана: результаты Гигантская компонента, устойчивость и уязвимость Диаметр Степени вершин Вторые степени вершин Пейджранк Количество ребер между вершинами заданных степеней Кластерные коэффициенты Число копий фиксированного графа Уточнения модели Боллобаша- Риордана : начальная притягательность вершины Несколько вводных замечаний Модель Бакли-Остгуса Модель Мори Степени вершин Вторые степени вершин Количество ребер между вершинами заданных степеней Кластерные коэффициенты Число копий фиксированного графа Удивительное соответствие модели Бакли-Остгуса реальному хост-графу Классификация ссылочного спама Дальнейшие уточнения модели Боллобаша-Риордана Несколько вводных замечаний Модель Боллобаша-Боргса-Риордана-Чайес Модель копирования Модель Купера-Фриза Модель Холма-Кима **Схемы и идеи некоторых доказательств** Несколько вводных слов Схема доказательства теоремы Схема доказательства теоремы Неравенства плотной концентрации и теоремы об асимптотическом распределении Несколько вступительных слов Неравенство Чебышёва Неравенство Азумы-Хёффдинга Неравенство Талаграна **Список литературы** Долгопрудный: Издательский Дом «Интеллект», 2013. — 64 с. : Учебное пособие. ISBN 978-5-91559-143-0 Учебное пособие посвящено моделированию Интернета, который был диковинкой для большинства из нас еще каких-то 15 лет назад. Сейчас мы ежедневно пользуемся ресурсами Интернета - поиском, электронной почтой, блогами и др. Сеть динамично развивается, растет и усложняется, а потому рядовому пользователю может казаться, что в Интернете царит полный хаос. Однако в реальности все устроено намного интереснее. Многочисленные статистические исследования показывают, что есть ряд законов, которым подчиняется «всемирная паутина». В частности, эти законы связаны с интерпретацией Интернета как графа, вершины которого - сайты, а ребра - гиперссылки. В книге описаны основные законы такого типа и рассказано, как современная математика помогает их моделировать. Для понимания книги читателю понадобится знание основ комбинаторики, теории графов и теории вероятностей. Книга будет полезна студентам, аспирантам и преподавателям технических ВУЗов, а также всем, кто интересуется приложениями математики к моделированию «сложных сетей» - Интернета, социальных, биологических, транспортных и других сетей. ОГЛАВЛЕНИЕ Введение Свойства Интернета Основные объекты и общая идеология их изучения Количество ребер Гигантская компонента Устойчивость и уязвимость Диаметр Степени вершин Вторые степени вершин Пейджранк Количество ребер между вершинами заданных степеней Корреляции степеней вершин Кластерные коэффициенты Число копий фиксированного графа Модели хост-rрафов Общая концепция Модель Эрдеша-Реньи Модели Барабаши-Альберт Модель Боллобаша-Риордана: определения Динамическое определение модели Статическое определение модели Модель Боллобаша-Риордана: результаты Гигантская компонента, устойчивость и уязвимость Диаметр Степени вершин Вторые степени вершин Пейджранк Количество ребер между вершинами заданных степеней Кластерные коэффициенты Число копий фиксированного графа Уточнения модели Боллобаша- Риордана : начальная притягательность вершины Несколько вводных замечаний Модель Бакли-Остгуса Модель Мори Степени вершин Вторые степени вершин Количество ребер между вершинами заданных степеней Кластерные коэффициенты Число копий фиксированного графа Удивительное соответствие модели Бакли-Остгуса реальному хост-графу Классификация ссылочного спама Дальнейшие уточнения модели Боллобаша-Риордана Несколько вводных замечаний Модель Боллобаша-Боргса-Риордана-Чайес Модель копирования Модель Купера-Фриза Модель Холма-Кима Схемы и идеи некоторых доказательств Несколько вводных слов Схема доказательства теоремы Схема доказательства теоремы Неравенства плотной концентрации и теоремы об асимптотическом распределении Несколько вступительных слов Неравенство Чебышёва Неравенство Азумы-Хёффдинга Неравенство Талаграна Список литературы