Часть 2.1 Мосты Кёнигсберга

Теория графов - наука, которая, одна из немногих, может похвастаться точно известным местом и временем зарождения. Ее корни ведут в Кёнигсберг 1735 года, столицу Западной Пруссии, одного из богатейших торговых городов своего времени (современный Калининград, Россия). Активная торговля, обеспечиваемая целой флотилией кораблей, позволила властям города построить целых семь мостов через реку Преголю, окружающую город. Пять мостов соединяли основной город с небольшим островом Кнайпхофом, расположившийся между двумя устьями реки. Оставшиеся два моста соединяли между собой берега реки (см. изображение 2.1). Такая необычная композиция и послужила основной для головоломки: Можно ли посетить все семь мостов, не проходя ни один из них дважды. Несмотря на многочисленные попытки, ни одного решения так и не было найдено вплоть до 1735 года, когда Леонард Эйлер, математик швейцарского происхождения, предложил точное математическое доказательство того, что решения у задачи не существует в принципе [6, 7].

Эйлер представил каждую часть города, разделенного рекой, буквами A, B, C и D ( изображение 2.1 ). После этого он изобразил каждый мост прямой линией. Таким образом, он построить граф, чьи узлы представляли части города, а ребра - мосты. На следующем этапе Эйлер произвел простое наблюдение: если бы путь, позволяющий пройти по всем мостам всего один раз, существовал, любой узел с нечетным количеством ребер должен был бы быть или началом, или же концом такого путешествия. Действительно, если вы переходите в узел с нечетным количеством связей, в какой-то момент вы можете обнаружить, что неиспользованных путей выхода из этого узла уже не остается.

Любой маршрут, разумеется, имеет только одну точку старта, и только один финиш. Соответственно, для любого графа, имеющего более двух узлов с нечетным количеством исходящих ребер такой маршрут не возможен. На графе Кёнигсберга целых 4 узла с нечетным количеством ребер - A, B, C, и D, а значит, подходящего маршрута просто не существует.

Решение Эйлера было первым в истории решением математической проблемы с использованием графа. Для нас этот пример важен по двум причинам: во-первых, он показывает, что некоторые проблемы становятся проще и понятнее, если представлены в виде графа. Во-вторых, то что существование того или иного маршрута не зависит от нашего желания его найти; Существование такого маршрута - свойство графа. Действительно, имея граф, подобный графу Кёнигсберга, мы не сможем найти искомый маршрут, как бы мы не старались. Другими словами, свойства сетей определяются их структурой.

Чтобы понять все многообразие путей, которыми сети могут определять свойства системы, мы должны познакомиться поближе с теорией графов, — частью математики, выросшей из доказательства Эйлера. В этой главе мы узнаем, как представить сеть в виде графа, какие элементарные характеристики сетей бывают, — включая степени, распределение степеней, пути и дистанции, - научимся определять взвешенные, направленные и бимодальные сети. Таким образом, мы дадим определения основные понятиям, и терминам, который в дальнейшем будем использовать в этой книге.

Часть 2.2 Сети и Графы

Чтобы понять, как работает сложная система, следует для начала понять как взаимодействуют её элементы друг с другом по отдельности. Другими словами, нам нужна схема. Сеть представляет собой каталог элементов системы, обычно называемых узлами, и взаимодействий между ними, часто называемыми связями, или ребрами графа (Памятка 2.1). Такое представление сети позволяет иметь общий “язык” для изучения систем, которые могут различаться по своей природе, внешнему виду или масштабу. Действительно, как показано на изображении 2.2, три совершенно разные системы могут иметь идентичное представление в качестве графа.

Изображение 2.2 представляет два основных параметра графа:

Количество узлов, N, определяет количество элементов системы. Часто мы определяем N как размер графа. Чтобы различать графы между собой, мы определяем для каждого его индекс: i=1,2, …, N.

Количество связей, — L, — представляет общее количество связей между узлами. Связи обычно не имеют особых индексов, так как могут быть идентифицированы через соединяемые узлы. Например, ребро (2, 4) в этом случае соединяет узлы 2 и 4.

Граф на рисунке 2.2 имеет N = 4 и L = 4.

Связи сети могут быть направлены (ориентированы) или ненаправлены (не ориентированы). Некоторые системы имеют направленные связи, как, например, WWW, где ссылки (URL) переадресуют нас от одного документа к другому, или телефонные звонки, когда один человек звонит другому. Другие системы характеризуются ненаправленными связями, — например, романтическими отношениями: если я встречаюсь с Анной, то и Анна встречается со мной, или как провода в электроцепи, позволяющие току течь в обоих направлениях.

Сеть называется направленной, если направлены все ее связи. Аналогично, если все связи сети ненаправлены, то и сеть называют ненаправленной. Некоторые сети могут иметь как направленные, так и ненаправленные связи. Например, в метаболической сети некоторые реакции могут быть повернуты вспять (т.е, в терминологии сетей, ненаправлены), в то время как другие являются необратимыми, и, таким образом, могут быть представлены направленной связью.

Правильный выбор типа ребер при представлении системы как сети может определить успешность наших попыток решить задачу методами науки о сетях. Так, например, то, как мы определим связь между двумя людьми определит природу вопросов, на которые мы сможем отвечать:

• Определяя связи между людьми, общающимся между собой в профессиональной среде, мы создадим организационную или профессиональную сеть, которая может играть ключевую роль в работе компании или организации и является главным предметом интереса организационных исследований (рис 1.7)
• Определяя связи между друзьями, мы получим сеть дружбы, которая играет важную роль в распространении идей, продуктов и привычек, и является предметом интереса социологов, маркетологов и медиков.
• Определяя сеть интимных взаимоотношений, мы получим сеть половых связей, играющую ключевую роль для распространения заболеваний, передающихся половым путем, в том числе СПИД, и представляющую большой интерес для эпидемиологов.
• Используя в качестве связей записи электронной почты и телефонные звонки, мы можем получить сеть знакомств, представляющую собой смесь профессиональных, дружеских и интимных связей, и важную для специалистов по коммуникациям и маркетингу.
  

Хотя многие связи в этих четырех сетях будут пересекаться (некоторые коллеги наверняка окажутся друзьями или даже любовниками), сети будут иметь разное значение и служить разным задачам.

Мы также можем представить себе сети, которые будут корректны с точки зрения требований теории, но нести мало практической пользы. Например, если мы объединим всех участников сети с одинаковыми именами, — Ивана с Иваном, а Марию с Марией, — мы тоже получим правильную сеть, свойства которой можно анализировать методами науки о сетях. Однако из такого анализа, скорее всего, никаких значимых результатов мы не получим. Другими словами, в ходе моделирования сети на основе любой системы стоит тщательно продумать выбор узлов и ребер, и удостоверится, что наш выбор соответствуют теме, которую вы хотите изучить.

На протяжении всей книги мы будем использовать 10 сетей для иллюстрации инструментария науки о сетях. Эти сети описаны в таблице 2.1 и покрывают диапазон тем от социальных сетей (графы мобильной сети и электронной почты), сотрудничества ( сети научного сотрудничества, Голливудских актеров) , информационные системы (WWW), технические и инфраструктурные системы (интернет, электросети), а также биологические системы (взаимодействие протеинов и метаболические сети), сети цитирования.

Все они отличаются по размеру, от N=1039 узлов в системе метаболизма палочки Коха, и почти до полумиллиона узлов в сети цитирования. Они служат иллюстрациями для нескольких предметных областей, где сети активно используются, представляя собой “канонические” наборы данных, часто используемые исследователями для иллюстрации ключевых особенностей сетей. Как мы указываем в таблице 2.1, некоторые из них являются направленными, в то время как другие - нет. В последующих частях мы детально обсудим природу и характеристики каждого из этих наборов данных, используя их в качестве “подопытных кроликов” для наглядного представления свойств сложных сетей.

Часть 2.3 Степени, Средняя степень графа, распределение степеней

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

Степень

Определим ki как степень i-того узла сети. К примеру, для ненаправленной сети, показанной на изображении 2.2 k1=2, k2=3, k3=2, k4=1. В ненаправленных сетях общее количество связей, L, может быть представлено как сумма степеней всех узлов:

Деление на два в данном случае учитывает тот факт, что в сумме степеней (2.1) каждое ребро получается посчитанны два раза. Например, ребро, соединяющее узлы 2 и 4 на изображении 2.2 будет посчитано дважды - один раз для узла 2 и второй - для узла 4.

Средняя степень

Важная характеристика сети - её средняя степень (Памятка 2.2), которая для ненаправленной сети равна

Для направленной сети мы разделяем степень входящих k_i_in, соответствующую количеству входящих в узел i ребер, и исходящих, k_i_out, соответствующую количеству ребер, ведущих из узла i к другим узлам. Наконец, общая степень узла равна сумме входящей и исходящей степеней.

К примеру, для WWW количество страниц, на которые ссылается документ, будет определять исходящую степень узла, а количество страниц, которые, в свою очередь, ссылаются на этот документ, определят его входящую степень. Сумма входящих и исходящих степеней узлов в таком случае будет одинаковой

Одна вторая, которую мы применили в (2.1), в этом случае не применяется, так как две суммы считают входящие и исходящие ребра отдельно. Средняя степень направленной сети определяется по формуле

Распределение степеней

Распределение степеней pk, определяется как вероятность того, что случайно выбранный узел сети i имеет степень k. Так как pk - это вероятность, она всегда нормализована.

Для сети с N узлами распределение степеней представляется нормализованной гистограммой (изображение 2.3), определяемой как

Где Nk - количество узлов со степенью k. Таким образом, количество узлов с определенной степенью могут быть получено из распределения как Nk = Npk.

Распределение Степеней - центральная концепция теории сетей, ставшая таковой после открытия безмасштабных (scale-free) сетей 8. Одной из причин является тот факт, что из распределения степеней можно получить большинство свойств сети. Например, средняя степень сети может быть определена как

Другая причина - то, что точная форма распределения определяет многие свойства сети, от устойчивости сети до распространения вирусов в ней.

Часть 2.4 Матрица смежности

Для полного описания сети необходимо хранить информацию обо всех ребрах. Простейшее решение этой проблемы - просто хранить список всех ребер. Так, сеть на изображении 2.2 может быть описана как список ребер: {(1, 2), (1, 3), (2, 3), (2, 4)}. Однако, для математических преобразований граф часто представляют в виде “Матрицы смежности”. Такая матрица для направленной сети с N узлами будет иметь N рядов и N колонок, а ее значения будут равны:

Aij = 1 если существует ребро между узлами j и i

Aij = 0 если узлы j и i не соединены прямым ребром

Матрица смежности ненаправленной сети строится аналогично, но, так как в этом случае связь считается в обе стороны, то матрица становится симметричной (Изображение 2.5b)

Из матрицы легко получить степень ki для любого узла i. Для ненаправленного графов степень будет равна сумме элементов соответствующей строки или столбца:

Для направленного графа сумма строки будет соответствовать входящую степень, а колонки - исходящую.

Зная, что в ненаправленной сети количество исходящих ребер всегда равно количеству входящих, получаем:

Количество ненулевых элементов матрицы равно 2L, то есть ровно в два раза больше чем количество ребер. Действительно, в таком случае мы опять считаем каждое ребро два раза: Aij = 1, как ребро из узла j в узел i, и Aji = 1, как ребро из i в j (Изображение 2.5b).

Часть 2.5 В реальном мире сети разряженные

В реальной практике количество узлов (N) и ребер (L) может значительно меняться. Возьмем, к примеру, нейронную сеть круглого червя (C. elegans), единственную полностью определенную нервную систему живого организма. Она насчитывает N = 302 нейрона (узла). Для сравнения, человеческий мозг насчитывает, по примерным оценкам, примерно сто миллиардов (N ≈ 1011) нейронов. Сеть ДНК в человеческой клетке насчитывает 20,000 генов, или узлов; население земли насчитывают семь миллиардов человек(N ≈ 7×109), а всемирная паутина содержит более триллиона документов (N > 1012).

Разницы в масштабе сетей хорошо видны в таблице 2.1, где указаны N и L для нескольких графов. Некоторые графы точно описывают связи систем (как, например, сеть актеров или схема метаболизма палочки Коха), в то время как другие служат лишь примерами, представляющие часть реальной сети (как, например, WWW или сеть мобильной связи).

Таблица 2.1 так же показывает, что количество ребер также меняется. Для сети из N узлов, количество ребер L может быть любым в диапазоне от L = 0 до Lf , где

L_max в данном случае - максимальное возможное количеств ребер в графе. Если число связей максимальное, или, другими словами, каждый узел соединен со всеми другими прямым ребром, граф называется Полным (Изображение 2.6).

Как правило, в реальных сетях L намного меньше его максимального значения L_max , другими словами, большинство сетей являются разреженными. Мы называем сеть разреженной, если ее количество ребер значительно меньше максимального, L ‹‹ L_max . К примеру, граф WWW в Table 2.1 имеет 1.5 миллиона ссылок. При этом если бы этот граф был бы полным, он бы имел L_max ≈ 5x10¹⁰ ссылок, в соответствии (2.12). Другими словами, мы имеем лишь 3x10-5 доли от максимального количества ссылок. То же верно и для любой сети из таблицы 2.1: вы можете проверить, что для каждой количество существующих ссылок — лишь небольшая часть от количества ребер, которые бы потребовались для полноты графа.

Матрица смежности разреженной сети будет также разреженной. Если полная сеть соответствует Aij = 1, для каждой пары (i, j), то есть каждый матричный элемент равен единице, то для разреженной сети ненулевой будет только малая толика матричных элементов. Это проиллюстрировано на рисунке 2.7, представляющей матрицу смежности для графа взаимодействий протеин-протеин, отображенной в таблице 2.1 и показанной на картинке 2.4a. Как вы можете увидеть, матрица в этом случае практически пустая.

Разреженность сетей имеет важные последствия для их исследования и хранения. К примеру, при сохранении больших сетей в виде файла на компьютере, часто лучшим решением оказывается хранить лишь список существующих ребер (т.е. элементов, для которых Aij ≠ 0), не тратя памяти на отсутствующие. Матричное представление такой сети потребовало бы гораздо больше памяти на хранение по сути лишней, нулевой информации (Изображение 2.7).

Часть 2.6 Сети с весом

До сих пор мы обсуждали лишь сети, для которых все ребра имеют равный вес, т.е, Aij = 1. Однако во многих случаях приходится работать с сетями с весом (взвешенными сетями), для которых каждая связь (i, j) имеет уникальны вес w^ij. В мобильных сетях вес может соответствовать суммарному количеству минут, в течении которых двое говорили по телефону; для электросетей вес может соответствовать величинам напряжения, протекающего по каждому кабелю.

Для сетей с весом элементы матрицы смежности равны величинам веса соответствующих ребер, т.е.

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

Часть 2.7 Бимодальные сети

Бимодальный граф (или биграф) - это сеть, чьи узлы могут быть выделены в два отдельных набора U и V, так, что каждая связь будет соединять узел U и узел V. Другими словами, если раскрасить все узлы U зеленым, а V — фиолетовым, то каждая связь будет соединять узлы разных цветов (Изображение 2.9).

Для каждого бимодального графа можно создать две проекции. Первая будет представлять каждую пару U-узлов как связанную, если они связаны с одним и тем же V-узлом в бимодальной репрезентации. Вторая проекция соединяет аналогичным образом все V-узлы, имеющие общие U-узлы как посредники. (Изображение 2.9).

Существует множество бимодальных сетей. Один из наиболее известных примеров - сеть актеров Голливуда, в котором часть узлов соответствует фильмам (U), а другая часть - актерам (V). Фильм связан с актером, если этот актер в нем играл. В таком случае одна проекция сети будет показывать всех актеров, связывая их по принципу работы над одними и теми же фильмами. Эта сеть представлена в таблице 2.1. Другим примером будет сеть фильмов, связанных, если хотя-бы один актер играл в обоих произведениях.

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

Наконец, могут быть и мультимодальные сети, такие как трехчастная сеть рецепт-ингредиент-вещество, показанная на Изображении 2.11.

Чaсть 2.8 Пути и расстояния

Физическое расстояние играет ключевую роль в степени взаимодействия между двумя компонентами физических систем. Например, расстояние между двумя атомами в кристалле или между двумя галактиками во вселенной определяет силу и тип их взаимодействия.

Дать однозначное определение дистанции в сетях сложно. Действительно, что означает “дистанция” между двумя страницами в интернете, или между двумя людьми, которые знают друг друга? В этом случае физическое расстояние ничего не значит: две страницы могут находиться на компьютерах в разных полушариях, и все же соединяться простой ссылкой. И в то же время, двое могут жить в одном здании, и все же совсем друг друга не знать.

Физическое расстояние в сетях замещается длиной пути. Путь - это маршрут, проходящий вдоль связей сети. Длина пути определяется количеством связей, через которые маршрут проходит (Изображение 2.12a). В некоторых версиях определение требует, чтобы узлы, через которые проходит путь, не повторялись.

В науке о сетях пути играют ключевую роль. Сейчас мы обсудим наиболее важные их свойства, а многие другие вкратце изложены на изображении 2.13.

Кратчайший путь

Кратчайшим путем между узлами i и j называют путь через наименьшее количество связей (Изображение 2.12b). Длину кратчайшего пути между двумя узлами i и j часто называют расстоянием между узлами d^ij , или просто d. Между парой узлов могут быть и несколько кратчайших путей (Изображение 2.12b). Кратчайший путь не имеет самопересечений и колец.

В ненаправленной сети d^ij = d^ji , т.е. расстояние от узла i к узлу j равно расстоянию от узла j к узлу i. В направленной сети, как правило, d ^ij ≠d ^ji . Более того, в направленной сети существование пути из узла i в узел j в принципе не гарантирует существование обратного пути.

В реальной жизни нам часто требуется определить расстояние между двумя узлами. Для небольшой сети, такой как на изображении 2.12, это не сложно. Однако для графа с миллионами узлов поиск кратчайшего пути может быть довольно затратным по времени. Формально, длина кратчайшего пути и количество таких путей может быть получена на основе матрицы смежности (памятка 2.4). Однако на практике мы используем алгоритм “поиска в ширину” (Breadth first search , BFS), который описывается в памятке 2.5.

Свойства Пути

• Путь
  Последовательность узлов, последовательно соединенных между собой связью. Каждый путь состоит из n+1 узлов и n связей. Длина пути определяется как количество связей. К примеру, оранжевая линия 1 → 2 → 5 → 4 → 3 соответствует пути с длиной 4.
• Кратчайший путь (Геодезический путь, d)
  Путь с наименьшим расстоянием d между двумя узлами. Мы так же называем d расстоянием между двумя узлами. Заметьте, что между парой точек может существовать несколько кратчайший путей: между узлами 1 и 4 существует два кратчайших пути — 1→ 2→ 3→ 4 (голубой) и 1→ 2→ 5→ 4 (оранжевый). Длина обоих путей в этом случае равна трем.
• Диаметр (d_max )
  Наиболее длинный кратчайший путь в графе, или расстояние между двумя наиболее удаленными друг от друга узлами. В представленном здесь графе диаметр между узлами 1 и 4, следовательно d_max =3.
• Средняя длина пути (〈d〉)
  Средняя длина кратчайших путей между всеми возможными парами точек. Для представленного слева графа 〈d〉 =1.6. Рядом с изображением представлен расчет.
• Цикл
  Путь, начало и конец которого совпадают. В графе слева существуют только один цикл, представленный оранжевой линией.
• Эйлеров путь
  Путь, который проходит один раз через каждую связь в графе. На изображении указаны два возможных эйлеровых пути, промаркированный оранжевым и голубым цветами.
• Гамильтонов путь
  Путь, который проходит один раз через каждый узел в графе. На изображении указаны два возможных гамильтоновых пути, промаркированный оранжевым и голубым цветами.

Диаметр Сети

Диаметр сети, обозначаемый d_max, соответствует наибольшей длине кратчайшего пути в сети. Другими словами, это наибольшее возможное расстояние в графе. Так, диаметр графа на изображении 2.13 равен d_max = 3. Для больших сетей диаметр может быть определен с помощью алгоритма BFS , описанного в памятке 2.5.

Средняя длина пути

Средняя длина пути, обозначаемая как〈d〉, равна среднему значению расстояния между всеми возможными парами узлов в сети. Для направленной сети с N узлами, 〈d〉 равен

Обратите внимание, что (2.14) определяется только пар, находящихся в одном компоненте (Часть 2.9). Для большой сети мы можем использовать алгоритм BFS для определения среднего пути. Для этого нам потребуется определить расстояние между первым узлом и всеми оставшихся. После этого мы определим расстояние между вторым узлом и всеми оставшимися, кроме первого (если сеть ненаправленная). Далее мы повторим эту процедуру для всех остальных узлов по очереди и подсчитаем среднее значение среди всех массивов.

Чвсть 2.9 Связанность

Ценность телефона весьма условной, если по нему нельзя позвонить. Так же и польза от электронной почты весьма ограничена, если мы сможем писать лишь на несколько адресов. С точки зрения сетей это означает, что между любыми двумя узлами должен быть связный путь. По большему счету в этом и состоит основная задача любой сети - сети определяют связанность объектов. В этой главе мы дадим связанности формальное определение.

В ненаправленной сети узлы i и j связанны, если есть хотя бы один путь между ними. Если такого пути не существует, то они не связаны, а расстояние между ними d_ij = ∞. Пример тому можно найти на изображении 2.15a, демонстрирующем сеть из двух разделенных кластеров. Хотя внутри каждого кластера все узлы связаны, (например, узлы 4 и 6), между узлами из разных кластеров связей не существует (узлы 1 и 6).

Сеть называют связной, если любая пара узлов в сети имеет хотя бы один путь между ними. Если хотя бы для одной пары d_ij = ∞, сеть называют несвязной. Так, сеть на изображении 2.15a несвязная, и мы можем назвать две части компонентами или кластерами. Компонентой называется такая часть сети, что между любой парой узлов внутри компоненты есть путь, однако нельзя добавить ни одного дополнительного узла основной сети, сохранив при этом связность компоненты.

Если сеть состоит из двух компонент, всего одна связь может их соединить, таким образом делая всю сеть связной (изображение 2.15b). В этом случае эта связь будет называться мостом. Мост - любая связь в сети, такая что при её удалении сеть становится несвязанной.

Хотя для небольших сетей определить связность можно визуально, для сетей с несколькими миллионами узлов это становится проблематичным. В определения связности нам может помочь математика и алгоритмы. К примеру, матрицу смежности для любой несвязной сети можно отсортировать таким образом, что она примет форму диагональных блоков, такую что все ненулевые элементы матрицы хранятся в квадратах вдоль диагонали матрицы, а все другие элементы равны нулю (изображение 2.15a). Каждый блок в таком случае соответствует одной компоненте сети. В определения того, можно ли привести матрицу к форме диагональных блоков, нам может помочь линейная алгебра.

Однако, на практике для больших сетей более эффективным способом будет использовать алгоритм BFS (Памятка 2.6).

Часть 2.10 Коэффициент кластеризации

Коэффициент кластеризации определяет частоту, с которой соседние узлы выбранного узла соединены друг с другом. Для узла i со степенью k_i локальный коэффициент кластеризации определяется как [12]

где L_i соответствует количеству связей между k_i соседей узла i. Коэффициент C _i всегда находится на промежутке от 0 до 1 включительно. (Изображение 2.16a):

• C _i = 0 если ни один из соседних узлов не имеет связи с другим.
• C _i = 1 если соседние узлы формируют полный граф, то есть существует связь для каждого с каждым.
• C _i является вероятностью того, что два соседних i узла связаны друг с другом. Соответственно C = 0.5 означает 50% вероятность что два соседних узла соединены.
  

Таким образом C _i измеряет локальную плотность связей сети: чем более плотно связаны между собой соседи узла, тем выше, локальный коэффициент кластеризации.

Степень кластеризации сети определяется как средний коэффициент кластеризации, 〈C〉, то есть среднее значение C _i всех узлов i = 1, ..., N [12],

В соответствии с вероятностной интерпретацией коэффициента, 〈C〉 соответствует вероятности того, что два соседних узла для любого рассматриваемого узла соединены между собой.

Хотя (2.16) определен для ненаправленных сетей, коэффициент кластеризации может быть обобщен для направленных сетей и сетей с весом [13, 14, 15, 16]. В литературе вы можете также встретить понятие глобального коэффициента кластеризации, описанные в ДОПОЛНИТЕЛЬНЫХ МАТЕРИАЛАХ 2.A.

Часть 2.11 Основные тезисы

В этой главе мы прошли вводный курс по основным понятиям и инструментам науки о сетях. Набор основных характеристик, представленный на изображении 2.17, предоставляет формальный язык, посредством которого мы можем исследовать сети.

Многие из сетей, которые изучает наука о сетях, содержат тысячи и даже миллионы узлов и связей. Чтобы исследовать их, нам придется выйти за пределы простых вычислений, возможных для небольших графов (см. Изображение 2.17). Некоторое представление об уровне сложности дает сеть протеин-протеин взаимодействий в дрожжах (Изображение 2.4a). Сеть настолько сложна, что визуальный анализ не может разобраться в переплетениях и определить какие-то количественные показатели. Таким образом, для оценки характеристик её топологии придется использовать специальный инструментарий сетевого анализа.

Давайте теперь используем вышеописанные понятия для исследования основных характеристик сетей. Ненаправленная сеть, показанная на изображение 2.4a, имеет N = 2,018 протеинов в виде узлов и L=2,930 взаимодействий между ними в виде связей.

Соответственно, средняя степень сети, в соответствии с (2.2), равна 〈k〉 = 2.90, и означает что протеины в сети в среднем взаимодействют с 2-3 другими. В то же время это число может ввести нас в заблуждение: распределение степеней на изображении 2.4b, c, показывает что абсолютное большинство узлов имеют только 1-2 связи. Если быть точным, 69% узлов в сети имеют меньше чем 3 связи, то есть их степень меньше средней, k ‹ 〈k〉 . В то же время, существуют несколько протеинов с очень большим количеством связей, так называемых “центральных узлов (хабов)”, самый большой из которых имеет аж 92 связи. Такое широкое разнообразие в степенях - результат особого свойства сети, называемого безмасштабностью (scale-free), которую мы рассмотрим в ГЛАВЕ 4. Как мы увидим, форма распределения степеней определяет множество свойств сети, -от устойчивости сети и до распространения вирусов.

Алгоритм поиска в ширину (ПАМЯТКА 2.5) позволяет определить диаметр сети, d_max = 14. Хотя на первый взгляд расстояния между узлами должны сильно варьироваться, так как некоторые узлы близки друг к другу, а другие находятся далеко, распределение расстояний (Изображение 2.18a) говорит об обратном: pd имеет пик между 5 и 6, что означает что большинство расстояний достаточно малы и находятся в окрестности 〈d〉 =5.61. Также, вероятность p_d больших расстояний быстро падает, означая что таких путей в графе практически нет. Вариативность распределения σ_d = 1.64, что означает что большинство расстояний практически равны〈d〉 . Это является признаком свойства “тесного мира”, которое мы обсудим в ГЛАВЕ 3.

Алгоритм поиска в ширину (BFS) также указывает, что сеть протеинов не является связной, и состоит из 185 компонент, показанных отдельно на изображении 2.4a. Самая большая, которую обычно называют гигантской компонентой, состоит из 1,647 узлов из 2,018 узлов сети; все остальные компоненты крошечные. Как мы увидим в дальнейшем, такое разделение тоже характерно для сетей в реальном мире.

Средний коэффициент кластеризации сети взаимодействия протеинов равен 〈C〉 =0.12, что, как мы увидим в дальнейшем, означает высокую степень локальной кластеризации. Такой вывод можно сделать, зная зависимость коэффициента кластеризации от степени узла, функции C(k) (Изображение 2.18b). Так как C(k) уменьшается для больших степеней k, то локальный коэффициент кластеризации для небольших узлов значительно выше, чем для хабов. Следовательно, узлы с небольшой степенью расположены в плотных областях сети, в то время как хабы расположены в рассеянных частях сети. Это следствие иерархии, еще одного свойства сети, которое описывается в ГЛАВЕ 9.

Наконец, мы можем заметить интересную закономерность: центральные узлы имеют тенденцию соединяться с небольшими узлами, создавая визуальный центр и определяя характер всей сети (Изображение 2.4a). Эта черта является результатом зависимости степеней, которую мы обсудим в ГЛАВЕ 7. Эта зависимость влияет на целый ряд сетевых процессов, такие как феномен распространения и определение ключевых узлов сети.

Изображения 2.4 и 2.18 иллюстрируют, как метрики, описанные в данной главе могут помочь с определением нескольких ключевых свойств настоящих сетей. На протяжении последующих частей мы изучим эти свойства сети и постараемся понять, что они могут сказать о свойствах конкретной сложной системы.

Часть 2.12. Домашнее задание

• Задача мостов Кёнигсберга
  Какая схема на Изображении 2.19 может быть нарисована, не отрывая карандаш от бумаги и без повторения линий? Почему
• Матрицы
  Пусть A будет матрицей смежности NxN ненаправленной сети без весов и автовзаимодействий. Пусть l будет колонкой из N элементов, все элементы которой равны 1. Другими словами l = (1, 1, ..., 1)T , где T указывает на транспозицию матрицы. Используя матричные выражения (мультипликативные константы, умножение ряда на колонку, матричные выражения типа транспозиции и следа, но без использования знака суммы Σ) напишите выражения для:
  • Вектора k, чьи элементы являются степенями k _i всех узлов i = 1, 2,..., N.
  • Общей суммы связей в сети, L.
  • Количества треугольников T в сети, где треугольником является три узла, каждый из которых соединен с двумя другими (Подсказка: используйте след матрицы).
  • Вектор k _nn чьи элементы i являются суммами степеней соседей узла i’.
  • Вектор k _nnn чьи элементы i являются суммами степеней всех соседей для узлов-соседей узла i’ (соседей второго уровня).
• Графы
  Матрица смежности является удобным представлением графа для многих вычислений. Тем не менее, для экономии места в памяти компьютера стоит хранить лишь список связей в виде матрицы Lx2, в которой каждая строка хранит индексы начала и конца связи. Выпишите для графов (a) и (b) на изображении 2.20:

• Соответствующие матрицы смежности.
  • Список связей.
  • Определите средний коэффициент кластеризации для сети на Изображении 2.20a
  • Если вы поменяете местами индексы узлов 5 и 6 на Изображении 2.20a, как изменится матрица смежности? Список узлов?
  • Какую информацию мы не можем получить из списка связей, но можем из матрицы смежности?
  • Для сети (a) сколько всего существует путей, начинающихся из узла 1 и заканчивающихся в узле 3 (в том числе с повторением связей и узлов) и имеющих длину 3? А в (b)?
  • С помощью компьютера, посчитайте количество циклов (путей, чьи начало и конец совпадают) с длиной 4 в обеих сетях.
    
• Степень, Коэффициент кластеризации и компоненты
  • Возьмем ненаправленную сеть размера N, в которой степень каждого узла k = 1. Каким условиям должно соответствовать число N? Каково будет распределение степеней такой сети? Сколько компонент будет иметь такая система?
  • Рассмотрим сеть, для которой каждый узел имеет степень k = 2 и коэффициент кластеризации C = 1. Как будет выглядеть такая сеть? Каким условиям будет соответствовать N в этом случае?
• Бимодальные сети
  • Рассмотрим бимодальную сеть, изображенную на Изображение 2.21.
  • Постройте для нее матрицу смежности. Почему матрица получилось блок-диагональной?
  • Теперь постройте матрицы смежности для двух проекций, то есть зеленых узлов и фиолетовых узлов, отдельно.
  • Рассчитайте среднее значение степени для фиолетовых и зеленых узлов.
  • Рассчитайте среднее значение степени для отдельных проекций. Почему значения в этом случае получились другими?
    

• Бимодальные сети - общие соображения
  Представьте бимодальную сеть из N1 и N2 узлов каждого типа.
  • Какое максимальное количество связей Lmax может иметь такая сеть?
  • Сколько связей в этом случае не могут быть проведены по сравнению с обычной (не бимодальной) сетью размером N = N1 + N2 ?
  • Если N1‹‹N2 , что можно сказать о плотности сети, то есть отношении общего количества связей к максимальному, Lmax?
  • Сформулируйте зависимость между N1, N2 и средней степенью для двух типов узлов в бимодальной сети,〈k1〉 и〈k2〉.
    

Часть 2.13 Дополнительный материал 2.A

В литературе по сетям вы можете встретить определение глобального коэффициента кластеризации, измеряющего общее количество замкнутых треугольников в сети. Действительно, в (2.15) L _iравен числу треугольников, в которых участвует узел i, так как каждая связь между его соседей и замыкает такой треугольник (Изображение 2.17). Следовательно, степень глобального коэффициента кластеризации сети может быть также определена как глобальный коэффициент кластеризации, т.е.

где соединенным триплетом называется набор из трех узлов ABC, такой что A соединяется с B а B соединяется с C. К примеру, треугольник A, B, C содержит три триплета, ABC, BCA и CAB. В то же время цепь из соединенных узлов A, B, C, где B соединен с A и C, но связь между A и C отсутствует, формируется лишь один триплет ABC. Мультипликатор 3 в начале формулы (2.17) следует из факта что каждый треугольник посчитан три раза в подсчете триплетов.

Корни глобального коэффициента кластеризации восходят к литературе по социальным сетям 1940-х [17, 18], где C _Δ часто называют долей транзитивных триплетов (the ratio of transitive triplets).

Заметьте, что средний коэффициент кластеризации ‹C›, определенный в (2.16) не равен глобальному коэффициенту кластеризации (2.17). К примеру возьмем сеть в виде двойной звезды с N узлами, где узлы 1 и 2 соединены друг с другом и со всеми другими узлами, а больше связей нет. В таком случае локальный коэффициент кластеризации C _i равен 1 для $i ≥ 3$ и $<em>2/(_N_ − 1)$ для $</em>i = 1, 2$. Средний локальный коэффициент кластеризации следовательно равен ‹C› = 1−O(1), в то время как глобальный примерно равен CΔ \~ 1/N. В большинстве сетей два коэффициента различаются не так сильно, однако все же отличаются друг от друга [19]. К примеру, для сети на Изображении 2.16b ‹C› = 0.31 , в то время как C_Δ = 0.375.

Часть 2.14 Литература

[1] K.-I. Goh, M. E. Cusick, D. Valle, B. Childs, M. Vidal, and A.-L. Barabási. The human disease network. PNAS, 104:8685–8690, 2007.

[2] H.U. Obrist. Mapping it out: An alternative atlas of contemporary cartographies. Thames and Hudson, London, 2014.

[3] I. Meirelles. Design for Information. Rockport, 2013.

[4] K. Börner. Atlas of Science: Visualizing What We Know. The MIT Press, 2010.

[5] L. B. Larsen. Networks: Documents of Contemporary Art. MIT Press. 2014.

[6] L. Euler, Solutio Problemat is ad Geometriam Situs Pertinentis. Commentarii Academiae Scientiarum Imperialis Petropolitanae 8:128-140, 1741.

[7] G. Alexanderson. Euler and Königsberg’s bridges: a historical view. Bulletin of the American Mathematical Society 43: 567, 2006.

[8] A.-L. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286:509–512, 1999.

[9] G. Gilder. Metcalfe’s law and legacy. Forbes ASAP, 1993.

[10] B. Briscoe, A. Odlyzko, and B. Tilly. Metcalfe’s law is wrong. IEEE Spectrum, 43:34–39, 2006.

[11] Y.-Y. Ahn, S. E. Ahnert, J. P. Bagrow, A.-L. Barabási. Flavor network and the principles of food pairing, Scientific Reports, 196, 2011.

[12] D. J. Watts and S. H. Strogatz. Collective dynamics of ‘small-world’ networks. Nature, 393:440–442, 1998.

[13] A. Barrat, M. Barthélemy, R. Pastor-Satorras, and A. Vespignani. The architecture of complex weighted networks. PNAS, 101:3747–3752, 2004.

[14] J. P. Onnela, J. Saramäki, J. Kertész, and K. Kaski. Intensity and coherence of motifs in weighted complex networks. Physical Review E, 71:065103, 2005.

[15] B. Zhang and S. Horvath. A general framework for weighted gene coexpression network analysis. Statistical Applications in Genetics and Molecular Biology, 4:17, 2005.

[16] P. Holme, S. M. Park, J. B. Kim, and C. R. Edling. Korean university life in a network perspective: Dynamics of a large affiliation network. Physica A, 373:821–830, 2007.

[17] R. D. Luce and A. D. Perry. A method of matrix analysis of group structure. Psychometrika, 14:95–116, 1949.

[18] S. Wasserman and K Faust. Social Network Analysis: Methods and Applications. Cambridge University Press, 1994.

[19] B. Bollobás and O. M. Riordan. Mathematical results on scale-free random graphs, in Stefan Bornholdt, Hans Georg Schuster, Handbook of Graphs and Networks: From the Genome to the Internet(2003 Wiley-VCH Verlag GmbH & Co. KGaA).