'

Безмасштабные сети (scale-free networks)

Понравилась презентация – покажи это...





Слайд 0

Безмасштабные сети (scale-free networks) Валерий Петрунин vpetrunin@inbox.ru


Слайд 1

Граф Граф или неориентированный граф G — это упорядоченная пара G: = (V,E), для которой выполнены следующие условия: V это множество вершин или узлов, E это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.


Слайд 2

Диаметр графа — это максимум расстояния между вершинами для всех пар вершин. Расстояние между вершинами — наименьшее число рёбер, которые необходимо пройти, чтобы добраться из одной вершины в другую.


Слайд 3

Граф называется связным, если любые две несовпадающие вершины графа соединены маршрутом. Очевидно, что для связности графа необходимо и достаточно, чтобы произвольная фиксированная вершина графа соединялась маршрутом с каждой из оставшихся вершин этого графа.


Слайд 4

Числом реберной связности  графа  называется число, равное наименьшему числу ребер, удаление которых приводит к несвязному графу. Число реберной связности одновершинного графа полагается равным нулю


Слайд 5

Числом вершинной связности (или просто числом связности)  графа  называется число, равное наименьшему числу вершин, удаление которых приводит к несвязному или одновершинному графу


Слайд 6


Слайд 7

Две категории сетей Классические(случайные) - новые узлы присоединяются к существующим примерно с одинаковой вероятностью, Безмасштабные - существуют узлы притягивающие непропорционально большое число новых узлов (концентраторы) Пример классической сети Пример безмасштабной сети


Слайд 8


Слайд 9

Число связей у отдельно взятого узла распределяется не по Пуассону, а по логарифмическому закону. Отсюда следует, что в большинстве реальных сетей основная часть узлов имеет ограниченное число связей, а отдельные узлы-концентраторы (Барабаши называет их hub) имеют аномально большое число связей


Слайд 10

Число связей у отдельно взятого узла распределяется не по Пуассону, а по логарифмическому закону


Слайд 11

Где мы можем увидеть безмасштабные сети? Техника: Сети электропередачи, Интернет, Веб, ... Социум: половые контакты, связи, организации, дороги, авиамаршруты ... Биология: нейроны; пищевые, экологические, метаболические сети, ... Физика: молекулы, галактики…


Слайд 12

Сеть цитируемости статей


Слайд 13


Слайд 14

Транспортная сеть


Слайд 15


Слайд 16

Социальная сеть


Слайд 17

Human Sexual Contacts


Слайд 18

Надежность сетей При удалении некоторого процента узлов, скажем 5%, граф рассыпается на мелкие кусочки, гигантский кластер перестаёт существовать Рост безмасштабной сети не приводит к увеличению ее устойчивости к случайным воздействиям


Слайд 19

Надежность сетей


Слайд 20

Надежность сетей


Слайд 21

Надежность сетей


Слайд 22

Вирусология Лечить случайные узлы ни к чему не приводит Если лечить хабы, то можно быстро погасить эпидемию СПИД, компьютерные вирусы


Слайд 23

Предсказание Кто с кем напишет следующую статью? Где проложат новые дороги? Кто присоединится к группе риска?


Слайд 24

СУБД Кластеризация: запросы к сетям будут бегать по соседям. Что делать с хабами? С костяком? Зависит от кластеризации или s-метрики.


Слайд 25

Выводы Таким структурам свойственна масштабная инвариантность, поэтому мы дали им название "безмасштабные сети" (scale-free networks). необычайно стойки к случайным отказам, но чрезвычайно уязвимы для скоординированных атак. многие прикладные задачи - от разработки эффективных лекарственных средств и борьбы с эпидемиями до защиты пользователей Интернета от хакеров ...


×

HTML:





Ссылка: