Лекция «Основы концепции Complex Networks и ее примененений» ЛАНДЭ Д.В., д.т.н., профессор НТУУ «КПИ», ведущий научный сотрудник ИПРИ НАН Украины Летняя школа Компьютерной лингвистики 5-11 июля 2011 г.

Complex Networks В настоящее время наряду с традиционным теориями графов, систем и сетей массового обслуживания активно развивается теория сложных сетей (от англ. – Complex Networks), в рамках которой предлагаются подходы к решению вычислительно сложных задач, характерных для современных сетей. Основной причиной актуальности теории сложных сетей являются результаты современных работ по описанию реальных компьютерных, биологических и социальных сетей. Cвойства многих реальных сетей существенно отличаются от свойств классических случайных графов с равновероятной связностью узлов, а строятся на основе связных структур, степенных распределений.. Летняя школа Компьютерной лингвистики 5-11 июля 2011 г.

Основы концепции Практически все современные сети можно считать сложными. Так, например, известная задача синтеза топологии сети допускает комбинаторный подход, опирающийся на представление сети в виде конечного графа, вершины которого соответствуют узлам сети, а ребра – линиям связи. Летняя школа Компьютерной лингвистики 5-11 июля 2011 г. Например, использование методов перечисления графов для решения задачи топологической оптимизации считается неперспективным, так как необходимо исследовать огромное количество возможных вариантов соединения узлов линиями связи. Например, в сети из 10 узлов существует 2 45 вариантов размещения линий связи (для 10 узлов теоретически возможно С 2 10 линий соединений. Каждая из этих возможных линий связи может реально существовать – состояние «1», или не существовать – состояние «0», то есть всего возможностей ). Варианты размещения линий связи при n=3

Направления теории сложных сетей В теории сложных сетей выделяют три основных направления: - исследование статистических свойств, которые характеризуют поведение сетей; - создание модели сетей; - предсказание поведения сетей при изменении структурных свойств. Летняя школа Компьютерной лингвистики 5-11 июля 2011 г.

Параметры сложных сетей Изучения таких параметров сложных сетей, как кластеризация, посредничество или уязвимость напрямую относятся к живучести, так как именно от этих свойств зависит способность сетей сохранять работоспособность при деструктивном воздействии на их отдельные узлы или ребра. В прикладных исследованиях обычно применяют такие типичные для сетевого анализа характеристики, как размер сети, сетевая плотность, степень центральности и т.п. При анализе сложных сетей как и в теории графов исследуются параметры отдельных узлов; параметры сети в целом; параметры сетевых подструктур. Летняя школа Компьютерной лингвистики 5-11 июля 2011 г.

Параметры узлов сети Выделяют следующие параметры: - входная степень связности узла – количество ребер графа, которые входят в узел; - выходная степень связности узла – количество ребер графа, которые выходят из узла; - расстояние от данного узла до каждого из других; - среднее расстояние от данного узла до других; - эксцентричность (eccentrіcіty) – наибольшее из геодезических расстояний от данного узла к другим; - посредничество (betwetnness), показывающее, сколько кратчайших путей проходит через данный узел; - центральность – общее количество связей данного узла по отношению к другим; - уязвимость, рассматриваемая как уровень спада производительности сети в случае удаления вершины и всех смежных ей ребер. Летняя школа Компьютерной лингвистики 5-11 июля 2011 г.

Общие параметры сети Наиболее часто используются такие параметры: количество узлов, число ребер, расстояние между узлами, среднее расстояние от одного узла к другим, плотность – отношение количества ребер в сети к макс. возможному количеству, количество симметричных, транзитивных и циклических триад, диаметр, уязвимость - максимальная уязвимость всех вершин сети, ассортативность - мера зависимости между узлами с одинаковыми степенями… Существует несколько задач исследования сложных сетей, среди которых можно выделить следующие основные: определение клик, кластеров, в которых узлы связаны между собой сильнее, чем с членами других подобных фрагментов; выделение компонент связности, которые связаны внутри и не связаны между собой; нахождение перемычек, т.е. узлов, при изъятии которых сеть распадается на несвязанные части. Летняя школа Компьютерной лингвистики 5-11 июля 2011 г.

Распределение степеней связности узлов Важной характеристикой сети является функция распределения степеней узлов P(k), которая определяется как вероятность того, что узел i имеет степень k i = k. То есть распределение степеней P(k) отражает долю вершин со степенью k. Для ориентированных сетей существует распределение выходящей полустепени P out (k out ), и полустепени входной P in (k in ), а также распределение общей степени P io (k in,k out ). Последнее задает вероятность нахождения узла с входной полустепенью k in и выходной полустепенью k out. Сети, характеризующиеся разными P(k), демонстрируют весьма разное поведение. P(k) в некоторых случаях может быть распределениями Пуассона (P(k)=e -m m k /k!, где m – математическое ожидание), экспоненциальным (P(k)=e -k/m ) или степенным ( P(k)=1/k γ ). Летняя школа Компьютерной лингвистики 5-11 июля 2011 г.

Путь между узлами Если два узла i и j можно соединить с помощью последовательности из m ребер, то такую последовательность называют маршрутом (walk) между узлами i и j, а m называю длиной маршрута. Расстояние между узлами определяется как длина маршрута от одного узла до другого. Естественно, узлы могут быть соединены прямо или опосредованно. Путем между узлами d ij называется кратчайшее расстояние между ними. Для всей сети можно ввести понятие среднего пути, как среднее по всем парам узлов кратчайшего расстояния между ними: Летняя школа Компьютерной лингвистики 5-11 июля 2011 г.

Глобальная эффективность Некоторые сети могут оказаться несвязными. Соответственно, средний путь может оказаться также равным бесконечности. Для таких случаев вводится понятие глобальной эффективности сети, рассчитываемое по формуле: где сумма учитывает все пары узлов. Эта характеристика отражает эффективность сети при пересылке информации между узлами (предполагается, что эффективность в пересылке информации между двумя узлами и обратно пропорциональна расстоянию между ними). Обратная величина глобальной эффективности – среднее гармоническое геодезических расстояний: h=1/E.. Летняя школа Компьютерной лингвистики 5-11 июля 2011 г.

Коэффициент кластеризации Дункан Уаттс и Стив Строгатц определили коэффициент кластерности, который Данный Коэффициент характеризует тенденцию к образованию групп взаимосвязанных узлов, так называемых клик (clіque). Пусть из узла выходит k ребер, которые соединяют его с k другими узлами, ближайшими соседями. Если предположить, что все ближайшие соседи соединены непосредственно друг с другом, то количество ребер между ними составляло бы k(k-1)/2. Т.е. это число, которое соответствует максимально возможному количеству ребер, которыми могли бы соединяться ближайшие соседи выбранного узла. Отношение реального количества ребер, которые соединяют ближайших соседей данного узла к максимально возможному (такому, при котором все ближайшие соседи данного узла были бы соединены непосредственно друг с другом) называется коэффициентом кластеризации узла. Летняя школа Компьютерной лингвистики 5-11 июля 2011 г. Watts

Посредничество Значение узла для сети тем больше, чем в большем количестве путей он задействован. Поэтому, полагая, что обмен данными происходит по кратчайшим путям между двумя вершинами, можно измерить количественно значение узла с точки зрения посредничества (betweenness), определяемого количеством кратчайших путей проходящих через узел. Эта характеристика отражает роль данного узла в установлении связей в сети. Узлы с наибольшим посредничеством играют главную роль в установлении связей между другими узлами в сети. Посредничество узла определяется по формуле: где B(i,j) – общее количество кратчайших путей между узлами i и j, B(i,m,j) – количество кратчайших путей между узлами i и j, проходящих через узел m. Летняя школа Компьютерной лингвистики 5-11 июля 2011 г.

Эластичность Р. Альберт из университета штата Пенсильвания (США) при исследовании атак на интернет-серверы изучала эффекты, возникающие при изъятии узла из WWW. Среднее расстояние между двумя узлами, как функция от количества изъятых узлов, почти не изменилось при случайном удалении узлов (высокая эластичность). Вместе с тем целенаправленное удаление узлов с наибольшим количеством связей приводит к разрушению сети. Интернет является высоко эластичной сетью по отношению к случайному отказу узла, но высокочувствительной к намеренной атаке. Летняя школа Компьютерной лингвистики 5-11 июля 2011 г. Противоположные свойства эластичности и уязвимости сетей относятся к распределению расстояний между узлами при изъятии отдельных узлов. Эластичность сети зависит от ее связности, т.е. существовании путей между парами узлов. Réka Albert

Уязвимость где E – глобальная эффективность исходной сети, а E i – глобальная эффективность после удаления узла i и всех смежных ему ребер. Упорядоченное распределение узлов относительно их уязвимостей связано со структурой всей сети, таким образом, наиболее уязвимый узел занимает наивысшую позицию в сетевой иерархии. Мера уязвимости сети – максимальная уязвимость среди всех ее узлов: V=maxV i. Летняя школа Компьютерной лингвистики 5-11 июля 2011 г. Один из способов найти критичные компоненты сети – поиск самых уязвимых узлов. Если производительность сети связана с ее глобальной эффективностью, уязвимость узла может быть определена как спад производительности в случае удаления узла и всех смежных емк ребер из сети: V i =(E-E i )/E,

Коэффициент элитарности Летняя школа Компьютерной лингвистики 5-11 июля 2011 г. Влиятельные исследователи определенных областей формируют сообщества сетевого типа, выражающиеся, в публикации совместных работ. Такая закономерность наблюдается также в других реальных сетях - явление, известное под названием элитарность (rіch-club phenomenon), может быть охарактеризовано коэффициентом элитарности. Элитарность степени k у сети G – это некое множество узлов со степенью, большей k, R(k)={VєN(G)|k v >k}. Коэффициент элитарности степени k выражается следующим образом: где сумма соответствует удвоенному количеству ребер между вершинами в «элите».

Корреляция степеней связанных вершин Летняя школа Компьютерной лингвистики 5-11 июля 2011 г. Корреляции между степенями соседних узлов может быть выражена через совокупное распределение P(k,k), т.е. как вероятность того, что произвольно выбранное ребро соединяет узел степени с узлом k степени k. Зависимость между степенями вершин можно выразить в терминах условной вероятности того, что произвольно выбранный сосед вершины степени k имеет степень k: При этом В случае неориентированных сетей и

Ассортативность Летняя школа Компьютерной лингвистики 5-11 июля 2011 г. Значения P(k,k) и P(k|k) формально описывают корреляции степеней узлов, однако их сложно вычислять экспериментальным путем, что связано с размером сети и малой мощностью выборки узлов с высокими степенями. Эту проблему можно решить, вычислив среднюю степень ближайших соседей узлов с заданной степенью k по формуле: Показатель корреляции степеней связности позволяет выделить отдельные классы сетей. Если корреляция отсутствует, то S(k) не зависит от значений k, S(k)= /. Если S(k) возрастает при увеличении k, то узлы больших степеней тяготеют к соединениям с узлам больших степеней, и сеть относят к ассортативным (отсюда и феномен «клуба богатых»).

Модель слабых связей Летняя школа Компьютерной лингвистики 5-11 июля 2011 г. Существует класс сложных сетей, которым присущи так называемые «слабые» связи. В некоторых случаях эти связи оказываются более эффективными, чем связи «сильные». Для исследова- Ния были проанализированы звонки 4.6 млн. абонентов мобильной связи - около 20% населения одной европейской страны. Было выявлено, что именно слабые социальные связи (один-два обратных звонка за 18 недель) связывают воедино большую социальную сеть. Если эти связи проигнорировать, то сеть распадется на отдельные фрагменты.

Модель малых миров Летняя школа Компьютерной лингвистики 5-11 июля 2011 г. Д. Уаттс и С. Строгатц обнаружили феномен, характерный для многих реальных сетей – эффект малых миров (Small Worlds). Сетевые структуры, соответствующие свойствам малых миров обладают следующими свойствами: малая средняя длина пути относительно диаметра сети и большой коэффициент кластеризации (что присуще сетям с регулярной структурой). Предложена процедура построения наглядной модели сети, которой присущ этот феномен.

Модель случайной сети Эрдоша-Рени Летняя школа Компьютерной лингвистики 5-11 июля 2011 г. Существует две модели классического случайного графа: в первой считается, что M ребер распределены произвольно и независимо между парами из N вершин графа; во второй модели фиксируется вероятность m, с которой может объединяться каждая из пар врешин. При m -> и N -> для обоих вариантов распределение степеней узлов k определяется формулой Пуассона: где среднее значение степени узла: =2M/N для первой модели и =mN для второй. При этом средняя длина кратчайшего пути для сети Эрдоша-Рени составляет =ln(N)/ln( ), а коэффициент кластерности: C~ /N.

Модель случайной сети Барабаши-Альберта Летняя школа Компьютерной лингвистики 5-11 июля 2011 г. Сценарий базируется на двух механизмах – росте и преимущественном присоединении (preferentіal attachment). Mодель использует алгоритм: рост сети происходит начиная с небольшого количества узлов n 0, к которым на каждом временном шагу добавляется новый узел с n< n 0 связями, которые присоединяются к уже существующим узлам; преимущественное присоединение состоит в том, что вероятность присоединения P(k i ) нового узла к уже существующему узлу i зависти от степени k i узла i: В знаменателе суммирование ведется по всем узлам. Как компьютерные модели, так и аналитические решения дают степенную асимптотику распределения степеней узлов с показателем γ=3.

Сложные сети и задачи компьютерной лингвистики Летняя школа Компьютерной лингвистики 5-11 июля 2011 г. Первым шагом при применении теории сложных сетей к анализу текста является представление этого текста в виде совокупностиузлов и связей, построение сети языка (language network). Существуют различные способы интерпретации узлов и связей, что приводит, соответственно, к различным представлениям сети языка. Узлы могут быть соединенны меду собой, если соответствующие им слова стоят рядом в тексте, принадлежат одному предложению, соединены синтаксически или семантически. Сохранение синтаксических связей между словами приводит к изображению текста в виде направленной сети (dіrected network), где направление связи соответствует подчинению слова.

Простейшие типы сетей в лингвистике Летняя школа Компьютерной лингвистики 5-11 июля 2011 г. L-пространство. Связываются соседние слова, которые принадлежат одному предложению. Количество соседей для каждого слова (окно слова) определяется радиусом взаимодействия R, чаще всего рассматривается случай R = 1. B-пространство. Рассматриваются узлы двух видов, соответствующие предложениям и словам, которые им принадлежат. P-пространство. Все слова, которые принадлежат одному предложению, связываются между собой. C-пространство. Предложения связываются между собой, если в них употреблены одинаковые слова.

Экспериментальные данные Летняя школа Компьютерной лингвистики 5-11 июля 2011 г. В случае рассмотрения L-пространства языка количество соседних слов, между которыми строятся связи, определяется параметром R: при R= 1 связаны между собой лишь ближайшие соседи, при R= 2 связи строятся между узлом-словом, его ближайшими и предшествующими близкими соседями и т. д. Для сети, построенной на основании Британского национального корпуса, оказалось, что данная сеть английского языка безмасштабна, а поведение степени P(k) характеризуется двумя режимами степенного распределения со значением степенного показателя γ=1.5 для k 2000 соответственно. Согласно определению, если средняя длина кратчайшего пути растет количеством узло в сети медленнее любой функции степени, то сеть является «малым миром». Данная сеть оказалась именно такой.

СПАСИБО ЗА ВНИМАНИЕ! Ландэ Д.В., Летняя школа Компьютерной лингвистики 5-11 июля 2011 г.