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

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

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

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

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

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

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

7

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

9

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

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

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

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

14

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

16

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

18 Human Sexual Contacts

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

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

21

22

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

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

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

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