zaeto.ru

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

Другое
Экономика
Финансы
Маркетинг
Астрономия
География
Туризм
Биология
История
Информатика
Культура
Математика
Физика
Философия
Химия
Банк
Право
Военное дело
Бухгалтерия
Журналистика
Спорт
Психология
Литература
Музыка
Медицина
добавить свой файл
 

 
страница 1 страница 2 страница 3 ... страница 5 страница 6



III. Теория случайных графов.

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



Рисунок 4. Иллюстрация графа с вершинами и ребрами. Множество вершин: . Множество ребер: .

Графы обычно представляются как множество точек, каждая из которых соответствует вершине. Две такие точки соединены линией, если соединены соответствующие вершины (см. рисунок 4).

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

Теория случайных графов была представлена Полом Эрдосом и Альфредом Ренйи (195 1960, 1961) после того, как Эрдос открыл, что вероятностные методы часто оказываются полезными в проблемах со средствами в теории графов. Детальное обсуждение данной области доступно в классической книге Боллобаса (1985), дополненной обозрением Коэна (1988) параллелей между фазовыми переходами и случайными графами, а также путеводителем истории подхода Эрдоса и Ренйи, написанным Каронским и Русинским (1997). Здесь мы кратко описываем важнейшие результаты теории графов, обращая особое внимание на те аспекты, которые имеют прямое отношение к сложным сетям.



  1. Модель Эрдоса-Ренйи.

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

Альтернативным и эквивалентным определением случайного графа является биномиальная модель. Здесь в начале имеется вершин. Каждая пара вершин соединяется с вероятностью (см. рисунок 5). Следовательно общее количество ребер _ случайная величина с ожидаемым значением . Если _ граф с вершинами и с ребрами, то вероятность получения этого графа в процессе построения есть .

Рисунок 5. Иллюстрация процесса изменения графа в модели Эрдоса-Ренйи. В начале имеем отдельных вершин (верхняя часть рисунка), затем каждая пара вершин соединяется с вероятностью . Нижняя часть рисунка показывает два различных этапа формирования графа, соответствующих значениям и . Мы можем увидеть появление деревьев (дерево порядка 3, нарисованное длинными пунктирными линиями) и циклов (цикл порядка 3, нарисованный короткими пунктирными линиями), а также соединенный кластер, который объединяет половину вершин в .



Теория случайных графов изучает свойства вероятностного пространства, связанного с графами с вершинами, при . Многие свойства таких случайных графов могут быть определены с использованием вероятностных доводов. В этом отношении Эрдос и Ренйи использовали определение, что почти каждый граф обладает свойством , если вероятность обладания свойством приближается к 1 при . Среди вопросов, поставленных Эрдосом и Ренйи, есть такие, которые имеют непосредственную значимость в понимании сложных сетей, например: Является ли типичный граф связным? Содержит ли он треугольник соединенных вершин? Каким образом его диаметр зависит от его размера?

В математической литературе конструирование случайного графа часто называется эволюцией: вначале имея множество из отдельных вершин, граф развивается с последовательным добавлением случайных ребер. Графы, полученные на разных этапах этого процесса, соответствуют все большим и большим вероятностям соединения , и наконец, при , получается полный граф [имеющий максимальное количество ребер ]. Основной целью теории случайных графов является выяснение при какой вероятности соединения некоторое фиксированное скорей всего свойство появится. Самым большим открытием Эрдоса и Ренйи было то, что многие важные свойства случайных графов появляются довольно неожиданно. Т. е. при заданной вероятности либо почти все графы обладают некоторым свойством (например, все пары вершин соединены путем из последовательных ребер), либо наоборот почти все графы этим свойством не обладают. Переход между тем, что свойство скорей всего будет или не будет выполняться, обычно происходит очень быстро. Для многих таких свойств есть критическая вероятность . Если растет медленней чем при , то почти каждый граф с вероятностью соединения не будет обладать свойством . Если же растет слегка быстрее чем , то почти каждый граф будет обладать свойством . Таким образом, вероятность того, что граф с вершинами и с вероятностью соединения имеет свойство , удовлетворяет следующей системе:

(4)

Здесь уместно важное замечание. Физики, специализированные в критических явлениях, примут как критическую вероятность, знакомую в протекании. В литературе физики система обычно рассматривается в фиксированном размере , а затем различные режимы в равенстве (4) сводятся к вопросу меньше ли , чем , или наоборот. Подходящее значение , т. е. предел () получается с помощью конечного масштабного преобразования. Базисом данного действия является предположение, что предел существует, отражая тот факт, что в конечном счете предел протекания не зависит от размера системы. Это в основном случай конечномерных систем, который включает большинство систем теории просачивания и критических явлений, представляющих интерес. Сети же, наоборот, по определению являются бесконечномерными: количество возможных соседей узла возрастает вместе с размером системы. Соответственно, в теории случайных графов вероятность соединения определяется как функция от размера: представляет из себя отношение количества существующих ребер и количества всех возможных. Более крупные графы с тем же будут содержать больше ребер, следовательно, такие свойства, как наличие циклов, будут иметь место для относительно маленьких в более крупных графах, нежели в меньших. Это означает, что для многих свойств для случайных графов нет единого независящего от предела, но мы можем определить предельную функцию, которая зависит от размера системы, и . Тем не менее, мы увидим, что средняя степень графа



(5)

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





  1. Подграфы.

Первым свойством случайных графов, изученным Эрдосом и Ренйи (1959), было появление подграфов. Граф , состоящий из вершин и множества ребер , является подграфом графа , если все вершины в содержатся также и в и все ребра из являются также ребрами из . Самыми простыми примерами подграфов являются циклы, деревья и полные подграфы (клики) (см. рисунок 5). Цикл порядка _ это замкнутая петля из ребер такой что каждая пара последовательных ребер, и только она, имеет общую вершину. Таким образом, графически треугольник _ цикл порядка 3, а квадрат _ порядка 4. Средняя степень цикла равняется двум, т.к. у каждой вершины есть два ребра. Противоположностью к циклам являются деревья. Более точно, граф является деревом порядка , если он имеет вершин и ребер, и ни один из его подграфов не является циклом. Средняя степень дерева порядка есть , что приближается к 2 для больших . Полные подграфы (клики) порядка содержат вершин и все возможные ребер, другими словами, они полностью связаны.

Рассмотрим процесс эволюции, описанном на рисунке 5 для графа .

Рисунок 6. Предельные вероятности, при которых в случайных графах появляются различные подграфы. При граф состоит из отдельных вершин и ребер. При появляются деревья порядка 3, а при _ порядка 4. При присутствуют деревья всех порядков, в то же время появляются циклы всех порядков. Вероятность отмечает появление полных подграфов порядка 4, а соответствует наличию кликов порядка 5. При приближении к нулю граф содержит полные подграфы увеличивающегося порядка.c:\documents and settings\а\рабочий стол\новый рисунок.bmp
В начале имеем отдельных вершин, потом соединяем каждую пару вершин с вероятностью . Для маленьких вероятностей соединения вершины изолированы, но с ростом и количества ребер вместе с ним, два ребра могут быть соединены с одной и той же вершиной, формируя деревья порядка 3. В общем случае мы можем спросить есть ли критическая вероятность, которая отмечает наличие произвольных подграфов с вершинами и ребрами.

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

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

Равенство (6) показывает, что если p такое что при , то количество подграфов , т.е. почти ни один случайный граф не содержит подграф . Тем не менее, если , то среднее количество подграфов _ конечное число, которое обозначается через , отмечая, что эта функция может быть критической вероятностью. Достоверность данного результата может быть проверена вычислением распределения количеств подграфов, , получая (Боллобас, 1985)



(7)

Тогда вероятность того, что содержит хотя бы один такой подграф , равняется



(8)

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

Несколько важных особых случая следуют прямо из равенства (8):

(a) Критическая вероятность наличия дерева порядка есть .

(b) Критическая вероятность наличия цикла порядка есть .

(c) Критическая вероятность наличия клики порядка есть .


страница 1 страница 2 страница 3 ... страница 5 страница 6


Смотрите также:





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

скачать файл




 



 

 
 

 

 
   E-mail:
   © zaeto.ru, 2021