Комплексные сети реального мира: моделирование, анализ, программное обеспечение Гродно, 6 апреля 2012

Общее понятие сети Множество членов сети и заданных связей между ними Связи в сети могут быть дискретными (0-есть, 1 –нет), взвешенными (неотрицательные веса) также симметричными (связь A с B такая же, что и B c A) направленными (связи A с B и B c A могут быть различны)

Сети реального мира Социальные сети – в т.ч., сети взаимодействия Информационные сети Транспортные сети Технологические сети Биологические сети и др.

Социальные сети Множество людей (членов сети) связанных определенными отношениями: родство, знакомство, дружба, сотрудничество, соавторство, взаимодействие, принадлежность общей группе и др. Пример – одноклассники, facebook

Примеры социальных сетей Сеть друзей/знакомых Сеть родства, дети-родители Сеть авторов (соавторство) Сеть актеров (съемка в одном фильме) Сеть одноклассников (учились в одном классе)

Сеть соавторства Число соавторов: Статья написана без соавторов и более

Сети взаимодействия (коммуникаций) Множество людей связанных посредством одного из видов их двусторонних взаимодействий (коммуникаций): сети телефонных взаимодействий (стационарные, мобильные, смс) cкайп, msm почтовые отправления, электронная почта денежные переводы

Сеть взаимосвязей в компании посредством электронной почты

Информационные сети Сети цитирования (статьи с направленными связями цитирования) Сеть web-страниц (отношения – гиперсвязь)

Транспортные сети Сеть авиа-, авто-, ж/д- сообщений (члены– города/станции, связи – наличие прямого сообщения) Сеть грузоперевозок (члены – склады, связи – наличие прямых рейсов) Сеть утилизации мусора (члены – пункты сбора/переработки, связи – транспортировка)

Сеть авиаперевозок Indian Airlines

Сеть авиаперевозок Delta

Сеть авиаперевозок America West Airlines

Сеть аэропортов мира

Технологические сети Сети энергоснабжения Телекоммуникационные сети Инфраструктурная составляющая транспортных или информационных сетей

Представления технологической инфраструктуры сети Интернет

Сеть энергоснабжения

Местная телекоммуникационная сеть

Биологические сети Сети метаболических путей (члены - метаболические субстраты и продукты, связи – наличие известной метаболической реакции получения заданного продукта) Генные регуляторные сети Пищевые сети животного мира

Сеть взаимодействий протеинов

Пищевые сети

Пример глобальной сети Instant Messaging Network (IMN) Покрытие сети 242 млн. пользователей, в т.ч. 180 млн. активных в течение июня 2006 г

Распределение силы связей сети IMN по странам Число разговоров Средняя продолжительность

Концепция малого мира Средняя длина пути от одного члена сети к другому – 6,6; для 90% пар не превышает 8 шагов, максимальная длина – 29 шагов

Теоретическая модель Взвешенный ориентированный граф; вершины - члены сети; ребра (их веса )- отношения между ними;

Информационные представления сети Матрица смежности Список смежности Список связей

Основные характеристики сетей Среднее геодезическое расстояние или глобальная эффективность Распределение степеней Кластерность Цикличность Связность «богатого клуба» Центрированность Модулярность Уязвимость

Распределение активности членов сети

Проблема определения сообществ Сообщество – подмножество сети, внутренние связи которого в целом сильнее внешних

Прямые алгоритмы поиска сообществ Иерархическая кластеризация Алгоритм Гирвана-Ньюмэна

Модульность Полный вес сети Сила вершины Разбиение Модульность

Сеть взаимодействий по стационарному телефону Великобритании, Италии

Сеть взаимодействий по мобильному телефону Бельгии, Португалии

Двудольные сети Члены сети разделены на две группы Связи устанавливаются между членами различных групп Пример – сеть транзакций пластиковых карт банка. Одна группа- клиенты, вторая - бизнесы

Пакет Matlab как удобная среда сетевого анализа Привычный синтаксис (близок к Pascal) Богатый набор стандартных математических процедур Мощные встроенные средства обработки матричных данных Удобная реализация процедур обработки больших массивов данных Лаконичность кода

Возможные приложения Общие законы активности людей в современном мире Понимание принципов построения городов Планирование городов Маркетинг Оптимизация бизнеса (тарифные планы, развитие)

Спасибо за внимание!