Познакомить студентов с основными понятиями теории графов, ключевыми метриками анализа сетей и классическими моделями случайных графов, лежащими в основе современного анализа сложных сетей.
- Что такое сеть (граф)?
- Определение: граф как множество узлов (вершин) и связей (рёбер).
- Примеры реальных сетей: социальные сети, интернет, транспортные сети, биологические сети (белковые взаимодействия), сети научных цитирований.
- Почему важно изучать сетевые структуры?
- Понимание распространения информации, устойчивости, влияния, кластеризации.
- Моделирование сложных систем.
- Граф $ G = (V, E) $:
- $ V $ — множество вершин (узлов),
- $ E $ — множество рёбер (связей).
- Типы графов:
- Направленные (ориентированные) и ненаправленные (неориентированные).
- Взвешенные и невзвешенные.
- Простые графы (без петель и кратных рёбер).
- Смежность, инцидентность, степени вершин.
- Подграфы, компоненты связности.
Рассмотрение ключевых метрик, описывающих структуру сетей:
- Определение: количество рёбер, инцидентных вершине.
- Для ориентированных графов: входящая и исходящая степени.
- Распределение степеней $ P(k) $ — важнейшая характеристика структуры сети.
- $ \rho = \frac{2|E|}{|V|(|V|-1)} $ для неориентированного графа.
- Интерпретация: насколько "связной" является сеть.
- Кратчайший путь между двумя вершинами.
- Эксцентриситет, диаметр (максимальное расстояние), радиус.
- Среднее геодезическое расстояние (average shortest path length).
- Коэффициент кластеризации (clustering coefficient):
- Локальный: вероятность, что два соседа вершины соединены между собой.
- Глобальный: среднее значение по всем вершинам.
- Интерпретация: наличие "треугольников", групп, сообществ.
- Степенная центральность (degree centrality).
- Центральность по посредничеству (betweenness centrality).
- Центральность по близости (closeness centrality).
- Степень влияния (influence), релевантность узлов.
- Сильная и слабая связность (для ориентированных графов).
- Размер гигантской компоненты.
- Два варианта:
- $ G(n, p) $: каждый возможный ребро существует с вероятностью $ p $.
- $ G(n, m) $: граф с $ n $ вершинами и $ m $ рёбрами, выбранными равновероятно.
- Свойства:
- Распределение степеней — биномиальное (приближённо пуассоновское).
- Порог связности: при $ p > \frac{\ln n}{n} $ граф почти наверняка связен.
- Наличие гигантской компоненты.
- Критика: не соответствует реальным сетям (низкая кластеризация, экспоненциальное распределение степеней).
- Идея: новые узлы предпочитают присоединяться к уже "популярным" (с высокой степенью).
- Процесс:
- На каждом шаге добавляется новый узел с $ m $ рёбрами.
- Вероятность соединения с вершиной $ i $: $ \frac{k_i}{\sum_j k_j} $.
- Свойства:
- Распределение степеней — степенное (power-law): $ P(k) \sim k^{-\gamma} $, обычно $ \gamma \approx 3 $.
- Наличие "хабов" (высокостепенных узлов).
- Соответствует наблюдаемым свойствам многих реальных сетей (масштабно-инвариантные сети).
- Цель: объяснить сочетание малого диаметра и высокой кластеризации (свойство "малого мира").
- Процесс:
- Начинаем с регулярного кольца (каждый узел соединён с $ k $ ближайшими соседями).
- С вероятностью $ p $ "перематываем" каждое ребро (меняем один конец на случайный узел).
- Свойства:
- При $ p = 0 $: регулярная сеть, высокая кластеризация, большой диаметр.
- При $ p = 1 $: случайный граф Эрдёша–Реньи.
- При малых $ p $: сохраняется высокая кластеризация, но диаметр резко падает ("малый мир").
- Примеры: социальные сети, нейронные сети.
- Частный случай модели предпочтительного присоединения.
- Два принципа:
- Рост сети (постоянное добавление узлов).
- Предпочтительное присоединение.
- Приводит к масштабно-инвариантным (scale-free) сетям.
- Реализация алгоритма (пошагово).
- Обсуждение: устойчивость, уязвимость, распространение информации.
| Характеристика | Эрдёш–Реньи | Уаттс–Строгац | Барабаши–Альберта |
|---|---|---|---|
| Распределение степеней | Пуассон | Близко к пуассону | Степенное |
| Кластеризация | Низкая | Высокая | Низкая |
| Диаметр | Малый | Малый | Малый |
| Реалистичность | Низкая | Средняя | Высокая |
| Применение | Базовая модель | Социальные сети | Веб, цитирования |
- Случайные графы — инструмент для понимания структуры и динамики сетей.
- Каждая модель отражает определённые аспекты реальных сетей.
- Реальные сети часто сочетают свойства нескольких моделей.
- Дальнейшие темы: сообщества, динамические сети, анализ центральностей, машинное обучение на графах.
- Краткий обзор современных моделей: случайные графы с заданным распределением степеней (configuration model), блок-модели (stochastic block models), графы с геометрическим укладом.
- Упоминание о программных инструментах: NetworkX (Python), igraph, Gephi.
- Newman, M.E.J. Networks: An Introduction. Oxford University Press, 2010.
- Barabási, A.-L. Network Science. Cambridge University Press, 2016. (Доступно бесплатно онлайн)
- Watts, D.J., Strogatz, S.H. Collective dynamics of ‘small-world’ networks. Nature, 1998.
- Erdős, P., Rényi, A. On random graphs. Publicationes Mathematicae, 1959.
- Barabási, A.-L., Albert, R. Emergence of scaling in random networks. Science, 1999.
- В чём разница между $ G(n,p) $ и $ G(n,m) $?
- Почему модель Эрдёша–Реньи не подходит для описания веб-графа?
- Как работает механизм предпочтительного присоединения?
- Что такое "эффект малого мира" и как его объясняет модель Уаттса–Строгаца?
- Какие реальные сети лучше всего описываются каждой из рассмотренных моделей?