Обзоры современной физики, том 74, январь 2002 Статистическая механика сложных сетей

ОБЗОРЫ СОВРЕМЕННОЙ ФИЗИКИ, ТОМ 74, ЯНВАРЬ 2002

Статистическая механика сложных сетей.

Réka Albert* и Albert-Lászlό Barabási

Отдел физики, университет , Notre Dame, Notre Dame, Indiana 46556

(опубликовано 30 января, 2002)

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

После просмотра эмпирических данных, которые мотивировали недавний интерес к сетям, авторы обсуждают основные модели и аналитические средства, покрывающие случайные графы, сети, без окалины и small-world сети, возникающую теорию развивающихся сетей, и взаимодействие между топологией и устойчивость сетей к сбоям и атакам.

I. Введение.

Сложные сетевые структуры описывают широкий спектр систем высокотехнологической и интеллектуальной важности. Например, клетка наилучше описывается как сложная сеть химических элементов, связанных химическими реакциями; интернет _ сложная сеть маршрутизаторов и компьютеров, соединенных различными физическими и беспроводными связями; причуды и идеи, распространенные в социальных системах, узлами которых являются люди, а ребра представляют различные социальные связи; всемирная паутина есть огромная сеть веб-страниц, связанных гиперссылками. Эти примеры лишь несколько из того множества, которое подсказало научной общественности исследовать механизмы, которые определяют топологию сложных сетей. Желание понять такие переплетенные системы столкнулось со значительными трудностями. В физике разработан целый арсенал успешных средств для предсказания поведения системы в целом исходя из свойств ее составляющих. Мы теперь понимаем, как магнетизм возникает из коллективного поведения миллионов частиц, или как квантовые частицы приводят к такой выдающейся феномене как конденсация Бозе-Эйнштейна или сверхтекучести. Успех таких попыток моделирования основан на простоте взаимодействий между элементами; нет никаких неясностей о том, какой элемент с каким взаимодействует, а сила взаимодействия одинаково определяется исходя из физического расстояния. Тем не менее, для нас затруднительно описать системы, для которых физическое расстояние неуместно или неясно, взаимодействуют ли два компонента. В то время как для сложных с нетривиальными топологиями сетей такая неясность естественно присутствует, в последние несколько лет мы осознали, что средства статистической механики предлагают идеальный каркас для описания таких переплетенных систем. Такие развития представили новые проблемы для статистической физики и неожиданные связи с главными темами в физике конденсированных сред, от процеживания до конденсации Бозе-Эйнштейна. Традиционно изучение сложных сетей являлось делом теории графов. В то время как теория графов изначально специализировалась на регулярных графах, с 1950-х обширные сети с отсутствием явных принципов построения были описаны как случайные графы, которые предлагались как самая простая и непосредственная реализация сложных сетей. Случайные графы были впервые изучены венгерскими математиками Полом Эрдосом и Алфредом Ренйи. Согласно модели Эрдоса-Ренйи, мы начинаем с N вершин и соединяя каждую пару вершин с вероятностью

, создавая граф приблизительно с

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

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

Маленькие миры: Концепция маленьких миров, в простых терминах, описывает тот факт, что, несмотря на частые большие размеры, в большинстве сетей путь от одного узла к другому сравнительно небольшой. Расстояние между узлами определяется как количество ребер в наикратчайшем пути, соединяющем их. Самым распространенным примером маленького мира является концепция “шесть градусов разделения”, обнаруженная социальным психологом Стэнли Милграмом (1967). Последний пришел к выводу, что между любыми двумя людьми, живущими в США (Кочен, 1989) есть путь знакомств с типичной длиной примерно в шесть человек. Многие сложные сети характеризуются свойством маленьких миров: актеры в Голливуде находятся друг от друга в среднем в пределах трех человек, или химические элементы в клетке обычно разделены тремя химическими реакциями. Концепция маленьких миров, будучи очень занимательной, не является индикатором определенного принципа организации. В самом деле, как показали Эрдос и Ренйи, типичная дистанция между любыми двумя вершинами в случайном графе оценивается как логарифм количества вершин. Таким образом, случайные графы также являются маленькими мирами.

Кластерация: Клики, представляющие круг друзей или знакомых, в котором каждый член знает любого другого, являются распространенным свойством социальных сетей. Эта неотъемлемая тенденция образовывать группы измеряется коэффициентом кластерации (Уоттс и Строгатс, 1998). Данная концепция исходит из социологии, где имеет название “разрыв транзитивных троек” (“fraction of transitive triples”) (Вассерманн и Фауст, 1994). Рассмотрим фиксированную вершину

, имеющую

ребер, которые соединяют ее с

вершинами. Если ближайшие соседи этой вершины были бы частью клики, то между ними было бы

ребер. Соотношение между количеством ребер

, которые реально существуют между этими

вершинами и общее число

дает нам значение коэффициента кластерации вершины

Коэффициент группирования всей сети есть среднее всех отдельных . Альтернативное определение коэффициента кластерации, которое часто используется в литературе, обсуждено в Sec. VI.B.2 (Баррат и Уэйт, 2000; Ньюман, Строгатс и Уоттс, 2000).

В случайном графе, т. к. ребра распределены случайным образом, коэффициент кластерации имеет величину (Sec. III.F). Тем не менее, в большинстве, если не во всех, реальных сетях коэффициент кластерации намного больше чем в соизмеримой случайной сети (т. е. имеющей то же количество вершин и ребер, что и реальная сеть).
Распределение степеней: Не все узлы в сети имеют то же самое число ребер (степень узла). Разброс степеней узлов характеризуется функцией распределения , которая дает вероятность того, что случайно выбранный узел имеет ровно ребер. Т. к. в случайном графе ребра распределяются случайным образом, большинство узлов имеет приблизительно ту же степень, которая близка к средней для всей сети степени . Распределение степеней случайного графа является распределением Пуассона с пиком . Одним из самых интересных развитий нашего понимания сложных сетей является открытие того, что для доминирующей части больших сетей распределение степеней значительно отступает от пуассоновского. В частности, для большого количества сетей, в том числе и всемирной сети (Альберт, Йонг и Барабаси, 1999), интернета (Фалоутсос, 1999), или метаболических сетей (Йонг и другие, 2000) распределение степеней имеет хвост со степенным законом,

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

II. Топология реальных сетей: эмпирические результаты.

Изучение большинства сложных сетей было вызвано желанием понять различные реальные системы, от коммуникационных сетей до экологических. Таким образом, доступные для исследования базы данных обхватывали несколько дисциплин. В этой части мы кратко обозрим те сети, которые были изучены исследователями с целью раскрыть общие свойства сложных сетей. Помимо описания баз данных, мы также обратим внимание на три сильные меры топологии сети: средняя длина пути, коэффициент кластерации, и распределение степеней. Другие числовые значения, как обсуждено в последующих частях, будут также тестированы на этих базах данных. Свойства исследуемых баз данных, а также применяемых образцов, подытожены в таблицах I и II.

Таблица I. Общие характеристики некоторых реальных сетей. Для каждой сети мы отметили количество узлов, среднюю степень

, среднюю длину пути

и коэффициент кластерации

. Для сравнения мы включили среднюю длину пути

и коэффициент кластерации

случайного графа той же величины и с той же средней степенью. Числа в последнем столбце закреплены с символами на рисунках 8 и 9.

A. Всемирная сеть.

Всемирная сеть представляет собой самую крупную сеть, для которой информация о топологии в данное время доступна. Узлами сети являются документы (веб-страницы), а ребра _ гиперссылки (URL-ы), которые ведут от одного документа к другому (смотри рис.1). Размер этой сети в конце 1999-го года составлял примерно один миллиард (Лоуренс и Гилс, 1999). Интерес к всемирной сети во многом возрос после того, как было открыто, что распределение степеней веб-страниц подчиняется степенному закону над несколькими порядками величин (Альбер, Йонг и Барабаси, 1999; Кумар и др., 1999). Т. к. ребра во всемирной сети имеют направление, сеть характеризуется двумя распределениями степеней: распределение выходящих ребер, , обозначает вероятность того, что у документа есть гиперссылок, и распределение входящих ребер, , есть вероятность того, что гиперссылок указывают на конкретный документ. Несколько исследований показали, что и у, и у хвосты подчиняются степенному закону:

. (3)

Альберт, Йонг и Барабаси (1999) изучили подмножество всемирной сети, содержащее 325 729 узлов, и обнаружили, что и . Кумар и др. (1999) использовали кроль Алекса Inc., состоящий из 40 миллионов документов, и получили и (см. также Клейнберг и др., 1999). Последующее рассмотрение топологии всемирной сети Бродером и др. (2000) использовало два 1999 кролей Алтависта, содержащих в общей мере 200 миллиона документов, и обнаружили, что и с масштабом, близким к пяти порякам величин (рис. 2). Адамик и Хьюберман (2000) использовали несколько другое представление всемирной сети, где каждый узел представлял отдельное имя домена и два узла соединялись, если любая страница из одного домена соединялась с любой страницей из другого домена. В то время как данный метод рассматривал страницы из одного домена как целое, представляя нетривиальное скопление узлов, распределение входящих ребер все еще подчинялось степенному закону с .

Обратите внимание на то, что одно и то же для всех измерений на уровне документов, кроме двухгодичного перерыва между первым и последним сетевым кролем, в течение которого всемирная сеть выросла, по крайней мере, в пять раз. Тем не менее, склонно расти с объемом выборки или со временем (см. таблицу 2).

Несмотря на большое число узлов, всемирная сеть обладает свойством маленького мира. Это впервые было отмечено Альбетом, Йонгом и Барабаси (1999). Они открыли, что средняя длина пути в выборке, содержащей 325 729 узлов, есть 11,2 и, используя масштабное преобразование в конечном объеме, предсказали, что для всей всемирной сети из 800 миллиона узлов средняя длина пути будет примерно 19. Дальнейшие измерения Бродера и др. (2000) показали, что средняя длина пути в 50-миллионном образце всемирной сети есть 16, что совпадает с предсказанием для конечного объема для образца такой величины. И наконец, сеть уровня доменов демонстрирует среднюю длину пути 3,1 (Адамик, 1999).

Ориентированность всемирной сети не дает нам возможность измерят коэффициент кластерации, используя равенство (1). Для того чтобы избежать этой трудности, можно избавиться от ориентированности, сделав все ребра двунаправленными. Таким способом воспользовался Адамик (1999), кто изучил всемирную сеть на уровне домена, используя кроль Алекса 1997, состоящий из 50 миллионов веб-страниц, распределенных в 259 794 сайтах. Адамик убрал узлы, имеющие лишь один край, и работал с сетью из 153 127 сайтов. В то время как ожидалось, что такие изменения несколько увеличат коэффициент кластерации, она обнаружила значения , порядок величин выше чем , соответствующий случайному графу такой же величины и средней степени.

B.Интернет.

Интернет _ сеть физических связей между компьютерами и другими телекоммуникационными устройствами (рис. 1). Топология интернета изучена на двух различных уровнях. На уровне маршрутизаторов, где последние являются вершинами, а ребра _ физические соединения между ними. И на внутридоменном уровне (или уровне автономных систем), где каждый домен, состоящий из сотен маршрутизаторов и компьютеров, представляется единственным узлом. Два домена соединены ребром, если есть хотя бы один путь, соединяющий их. Фалоутсос и др. (1999) изучили интернет на обоих уровнях и пришли к выводу, что в каждом случаи распределение степеней подчиняется степенному закону. В результате исследования топологии интернета в трех различных датах между 1997 и концом 1998 были получены значения между = 2,15 и = 2,22. Исследования топологии интернета 1995-го на уровне маршрутизаторов, содержащем 3888 узлов, привело к значению = 2,48 (Фалоутсос и др., 1999).

Таблица II. Масштабные степени, характеризующие распределение степеней некоторых свободных от масштаба сетей, для которых подчиняется степенному закону (2). Мы отмечаем размер сети, ее среднюю степень и границу к для масштабирования по степенному закону. Для ориентированных сетей мы отдельно отмечаем показатели для входящих и для выходящих, а для неориентированных сетей, отмеченных звездочкой , эти величины совпадают. Столбцы , и сравнивают среднюю длину пути реальных сетей с распределением степеней по степенному закону и предсказаниями в теории случайных графов (17) и Ньюмана, Строгатса, и Уоттса (2001) [см. также равенство (63) выше], как это обсуждено в отделе V. Числа в последнем столбце связаны с символами в рисунках 8 и 9.

$c:\documents and settings\а\рабочий стол\безымянный.bmp$

Рисунок 1. Сетевая структура всемирной сети и интернета. Верхняя панель: узлами всемирной сети являются веб-документы, соединенные гиперссылками (URL-ы). Нижняя панель: в интернете узлами являются маршрутизаторы и компьютеры, а ребра _ провода и кабели, которые их физически соединяют. Рисунок любезно предоставлен Истваном Альбертом.

Рисунок 2. Распределение степеней всемирной сети с точки зрения двух различных измерений: , 325 729-узелный образец Альберта и др. (1999); , измерения более чем 200 миллионов страниц Бродером и др. (2000); (a) степенное распределение выходящих ребер; (b) степенное распределение входящих ребер. Информация представлена логарифмически для уменьшения шума. Любезно предоставлено Алтависта и Эндрю Томкинами. Авторы благодарят Луизу Амараль за исправление ошибки в предыдущей версии рисунка (см. Мосса и др., 2001).

Рисунок 3. Степенное распределение некоторых реальных систем: (a) интернет на уровне маршрутизаторов. Информация любезно предоставлена Рамешом Говинданом; (b) сеть сотрудничества фильмов и актеров. Барабаси и Альберт (1999). Обратите внимание на то, что если добавить также телевизионные сериалы, что включает большое число актеров, то возникает экспоненциальный останов для больших (Амараль и др., 2000); (c) соавторская сеть физиков высокой энергии. Ньюман (2001a, 2001b); (d) соавторская сеть нейробиологов, Барабаси и др. (2001).

Недавно Говиндан и Тангмунарункит (2000) отобразили множество из примерно 150 000 интерфейсов маршрутизаторов и примерно 200 000 смежных маршрутизаторов, подтверждая степенной закон с 2,3 [см. рис. 3(a)].

Интернет как сеть демонстрирует кластерацию и небольшую длину пути. Йук и др. (2001a) и Пастор-Саторрас и др. (2001), изучая интернет на уровне доменов между 1997 и 1999, обнаружили, что коэффициент кластерации менялся между 0,18 и 0,3 в сравнении с 0.001 для случайных графов со сходными параметрами. Средняя длина пути для интернета на уровне доменов менялся от 3,70 до 3,77 (Пастор-Саторрас и др., 2001; Йук и др., 2001a), а на уровне маршрутизаторов он был около 9 (Йук и др., 2001a), указывая на свойство маленького мира.

C. Сеть сотрудничества фильмов и актеров.

Сеть сотрудничества фильмов и актеров немало изучена. Она основана на базе данных о фильмах в интернете, которая содержит все фильмы и их составы актеров с 1890-ых. В этой сети узлы _ актеры, а два узла соединяются ребром, если соответствующие актеры играли вместе в некотором фильме. Эта сеть постоянно увеличивается: в 1998 году было 225 226 узлов (Уоттс и Строгатс, 1998), а к маю 2000 года это число выросло до 449 913 (Ньюман, Строгатс и Уоттс, 2000). Средняя длина пути в сети актеров близка к значению длины для случайного графа той же величины и средней степени _ 3,65 по сравнению с 2,9, но коэффициент кластерации 100 раз превышает значение для случайного графа (Уоттс и Строгатс, 1998). Распределение степеней сети фильмов и актеров имеет хвост со степенным законом для больших значений [см. рис. 3(b)], с где = 2.3 0,1 (Барабаси и Альберт, 1999; Альберт и Барабаси, 2000; Амараль и др., 2000).

D. Сеть научных сотрудничеств.

Аналогичная к сети актеров и фильмов сеть может быть сконструирована и для ученых, где узлы _ ученые, и два узла соединяются, если соответствующие ученые вместе писало статью. Для раскрытия топологии этого сложного графа Ньюман (2001a, 2001b, 2001c) в течение пяти лет (1995-1999) изучал четыре базы данных, охватывающие физику, биомедицинские исследования, физику высокой энергии компьютерную науку. Все эти сети демонстрируют маленькую среднюю длину пути, но большой коэффициент кластерации, это показано в таблице I. Степенное распределение сети сотрудничеств физиков высокой энергии демонстрирует почти идеальный степенной закон с показателем 1,2 [рис. 3(c)], во время как другие базы данных имеют степенной закон с более высоким показателем в хвосте.

Барабаси и др. (2001) изучили граф сотрудничества математиков и неврологов, публикации между 1991 и 1998. Средняя длина пути в этих сетях составляет примерно = 9.5 и = 6, коэффициенты кластерации = 0.59 и = 0,76. Степенные распределения данных сетей сотрудничеств стойкие со степенными законами с показателями 2,1 и 2,5, соответственно [см. рис. 3(d)].

E. Сеть половых контактов человека.

Многие болезни, передаваемые половым путем, включая СПИД, распространяются на сеть сексуальных отношений. Лильерос и др. (2001) изучили сеть, составленную из сексуальных отношений 2810 людей и основанную на широком исследовании, проведенной в Швеции в 1996. Т.к. ребра в этой сети существуют относительно недолго, они анализировали распределение партнеров в течение одного года, и выяснили, что и для мужчин, и для женщин распределение имеет степенной закон с показателями = 3,5 0,2 и = 3,3 0,2, соответственно.

F. Клеточные сети.

Йонг и др. (2000) изучали обмен веществ 43 организмов, представляющих все три среды жизни, объединяя их в сеть, где узлы _ субстраты (такие как ATP, ADP, H2O), а ребра представляют преимущественно ориентированные химические реакции, в которых эти субстраты могут участвовать. Оказалось, что для всех организмов распределение входящих и выходящих ребер подчиняется степенному закону с показателями между 2,0 и 2,4. В силу ориентированности сетей коэффициент кластерации не определен. Средняя длина пути приблизительно одна и та же для всех организмов, со значением 3,3.

Коэффициент кластерации был изучен Уонгером и Феллем (2000; см. также Фелл и Уонгер, 2000), обращая внимание на энергетический и биосинтетический обмен веществ бактерии Escherichia coli. Они открыли, что , вдобавок к степенному закону распределения степеней, неориентированная версия этого графа обладает маленькой средней длиной пути и большим коэффициентом кластерации (см. таблицу I).

Еще одна сеть, характеризующая клетку, описывает взаимодействия между протеинами, где узлы _ протеины, которые соединяются ребром, если экспериментальным путем показано, что они связаны вместе. Изучение этих физических взаимодействий показало, что распределение степеней в карте физических взаимодействий протеинов дрожжах подчиняется степенному закону с показателем в хвосте , где , и (Йонг, Мейсон и др., 2001).

G. Экологические сети.

Пищевые сети очень часто используются экологами для численной оценки взаимодействий между различными видами (Пим, 1991). В пищевой сети узлами являются виды, а ребра представляют отношения хищник-добыча. В недавнем исследовании, Уиллиамс и др. (2000) изучили топологию семи наиболее документированных и больших пищевых цепей: Skipwith Pond, Little Rock Lake, Bridge Brook Lake, Chesapeake Bay, Ythan Estuary, Coachella Valley и St. Martin Island. В то время как эти сети широко различаются в количестве видов или средней степени, в каждом из них виды находятся в трех или меньше ребрах друг от друга. Этот результат был подтвержден независимым исследованием Монтоя и Сола (2000) и Камачо и др. (2001a). Они также показали, что пищевые сети обладают высокой кластерацией. Степенное распределение было вначале исследовано Монтоя и Сола (2000). Они сфокусировались на сетях Ythan Estuary,

Silwood Park и Little Rock Lake, считая их неориентированными. Несмотря на маленький размер этих сетей (самый большой из них имеет 186 узлов), они разделяют свойства их бо'льших аналогов, присущие неслучайным графам. В частности, Монтоя и Соле (2000) пришли к выводу о том, что распределение степеней стойко со степенным законом с необычно маленьким показателем 1,1. Тем не менее, маленький размер этих сетей оставляет место для некоторой неопределенности . Камачо и др. (2001a, 2001b) считают, что для некоторых пищевых цепей экспоненциальный fit очень подходящий. Подтвердившееся существование ключевых видов, которые играют важную роль в топологии пищевой сети, указывает существование узлов (распространенное свойство сетей, не обладающих масштабом), однозначное определение топологи сети может улучшиться благодаря более крупным сетям данных.

H. Сети телефонных звонков.

Из модели звонков дальней дистанции сконструирован большой ориентированный граф, где узлы _ телефонные номера, а каждый звонок есть ребро, направленное от звонившего к принявшему звонок. Абелло, Пардалос и Ресенд (1999) и Айелло, Чанг и Лу (2000) изучили граф телефонных звонков дальней дистанции, сделанных за один день, и обнаружили, что распределение выходящих и входящих ребер подчиняется степенному закону с показателем .

I. Сети цитат.

Из модели цитат научных публикаций сформирована достаточная сложная сеть, где узлами являются статьи, а ориентированные ребра _ ссылка на ранее опубликованную статью. Рендер (1998), изучая распределение 783 339 газет, каталогизированный Институтом Научной Информации, и 24 296 газет, опубликованных в Физическом Обзоре между 1975 и 1994, обнаружил, что вероятность того, что газета была процитирована раз, подчиняется степенному закону с показателем , указывая на то, что распределение входящих ребер в сети подчиняется степенному закону. Недавнее исследование Вазкуезом (2001) распространило эти исследования также на распределение степеней выходящих ребер, обнаружив, что оно имеет экспоненциальный хвост.
J. Лингвистические сети.

Запутанность человеческих языков предлагает несколько возможных способов для определения и изучения сложных сетей. Недавно Феррер и Канчо и Соле (2001) сконструировали такую сеть для английского языка, основанной на Британском Национальном Собрании, где узлы _ это слова; эти узлы соединены, если в предложениях они либо расположены друг за другом, либо между ними есть одно слово. Они обнаружили, что полученная сеть из 440 902 слов имеет маленькую среднюю длину пути , высокий коэффициент кластерации и двурежимное распределение степеней со степенным законом. Слова со степенью разлагаются с показателем степени , в то время как слова с подчинаются степенному закону с .

Другое исследование (Йук, Йонг и Барабаси, 2001b) соединяло слова в зависимости от их значений, т. е. два слова соединялись друг с другом, если они являлись синонимами согласно словарю Мерриам-Уебстер. Результат указывает на существование гигантского кластера из 22 311 слов из 23 279, имеющих синонимы, со средней длиной пути и с более высоким коэффициентом кластерации в сравнении с для эквивалентной случайной сети. Вдобавок, распределение степеней имело хвост, подчиняющийся степенному закону с . Эти результаты показывают, что во многих отношениях язык также образует сложную сеть с принципами организации, которые мало отличаются от примеров, рассмотренных выше (см. также Стейверс и Тененбаум, 2001).

К. Энергетические и нервные системы.

Энергетическая система западной части Соединенных Штатов описывается сложной сетью, узлы в которой _ это генераторы, трансформаторы и подстанции, а ребра _ высоковольтные линии передачи. Количество узлов в энергетической системе есть , а . В крошечной () нервной сети черви нематода узлами являются нейроны, а ребро соединяет два нейрона, если они связаны либо синапсом, либо щелевым контактом. Уоттс и Строгатс (1998) обнаружили, что в то время как средняя длина пути приблизительно равнялась длине для случайного графа того же размера и средней степени, их коэффициент кластерации был намного выше (таблица I). Распределение степеней энергетической системы сопоставимо с экспоненциальной, а для нервной сети оно имеет пик в промежуточном , после чего оно разрушается по экспоненте (Амараль и др., 2000).
L. Белковое свертывание.

Во время свертывания белок принимает последовательные структуры. Каждый узел представляет отдельное состояние. Две структуры соединяются, если они могут быть получены друг из друга с помощью элементарного изменения. Скала, Амараль и Бартелеми (2001) изучили сеть, сформированную из структур двумерного (2D) сетчатого полимера, и обнаружили, что она обладает свойством маленьких миров. В особенности, средняя длина пути увеличивается логарифмически с увеличением размера полимера (и размера сети, соответственно), что соответствует поведение случайного графа. Тем не менее, коэффициент кластерации намного превосходит , и эта разница увеличивается вместе с размером сети. Распределение степеней сети структур сопоставимо с Гауссовским (Амараль и др., 2000).

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

следующая страница >>