zaeto.ru

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

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

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




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




  1. Масштабирование в критических областях.

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

Здесь и _ критические степени, численные значения которых должно быть определено, и _ гладкие функции на и . Результаты раздела IV.B подсказывают, что и для . Этот анзатс показывает, что значение как хвоста та же, что и для дерева Кэли. Общее выражение (37) в качестве частного случая содержит дерево Кэли с , и .

Еще одним элементом масштабной гипотезы является тот факт, что корреляционная длина расходится в окрестности пределе протекания, следую степенному закону:

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



Что расходится при . Показатели и называются критическими степенями для вероятности протекания и среднего размера кластеров, соответственно.





  1. Структура кластера.

До сих пор мы обсуждали размеры и радиусы кластеров, не обращая внимания на их внутреннюю структуру. Будем теперь считать, что периметром кластера называется количество вершин на внешних ребрах (листья). Периметр очень большого, но конечного кластера размера равен следующему (Леат, 1976)

где для и при . Таким образом, ниже периметр кластера пропорционален его объему. Это свойство _ очень неправильное свойство, которое, тем не менее, верно для деревьев, включая дерево Кэли.

Другом способом понимания непривычной структуры конечных кластеров _ оценивание соотношения между их радиусами и объемом. Корреляционная длина _ мера среднего радиуса кластеров, и мы знаем, что соотносится с размером хвоста кластера как . Отсюда, конечные кластеры являются фракталами (см. Манделброт, 1982), т.к. их размер измеряется не как -ая степень радиуса, а как

Где . Можно также показать, что в пределе протекания бесконечный кластер все еще является фракталом, но для он превращается в нормальный -мерный объект.

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

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





  1. Бесконечномерное протекание.

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

  • при ;





  • .

Следовательно, критическими для бесконечномерного протекания являются показатели , и . Фрактальная размерность бесконечного кластера в пределе протекания равна , а размерность графа (Бунд и Халвин, 1996). Таким образом, характеристическое химическое расстояние в конечном или бесконечном кластере при пределе протекания соотносится с его размером как

G. Параллели между теорией случайных графов и протеканием.

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

В разделе IV.C мы увидели, что бесконечномерное протекание подобно протеканию в дереве Кэли. Предел перколяции для дерева Кэли есть , где _ число координации дерева. В случайном графе из ребер число координации есть ; следовательно, “предел протекания”, который показывает вероятность соединения, при которой появляется гигантский кластер, должен быть . И в самом деле, это ровно та вероятность, при которой фазовый переход, ведущий к наличию гигантского компонента, появляется в случайном графе, как это показали Эрдос и Ренйи (см. раздел III.C).

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


  1. Для .

  • Вероятность наличия гигантского кластера в графе и бесконечного кластера в протекании равна 0.

  • Кластеры в случайных графах являются деревьями, а в протекании кластеры имеют фрактальную структуру и периметр, пропорциональный их объему.

  • Самый большой кластер в случайном графе _ это дерево с вершинами, а в протекании в общем случае [см. равенство (28) в разделе IV.B], что подсказывает, что размер наибольшего кластера измеряется как .

  1. Для .

  • Появляется единственный гигантский кластер или бесконечный кластер.

  • Размер гигантского кластера _ , а для бесконечномерного протекания _ , поэтому размер наибольшего кластера измеряется как .

  1. Для .

  • Размер гигантского кластера составляет , где _ экспоненциально возрастающая функция с . Размер бесконечного кластера составляет .

  • Гигантский кластер имеет сложную структуру, содержащую циклы, а бесконечный кластер является не фрактальным, а компактным.

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

В некоторых случаях между предсказаниями теории случайных графов и теорией перколяции есть видимое различие. Например, теория перколяции предсказывает, что химическое расстояние между двумя узлами в бесконечном кластере измеряется как степень размера кластера [см. равенство (44)]. А теория случайных графов предсказывает [см. равенство (16)], что диаметр бесконечного кластера измеряется логарифмически вместе с размером (см. Чанг и Лу, 2001). Причиной этого явного различия является то, что два этих предсказания относятся к различным системам. Тогда как равенство (44) справедливо только тогда, когда бесконечный кластер только что образовался [например, и ] и все еще является фракталом, предсказание теории случайных графов выполняется после перколяционного перехода при . Следовательно, используя эти два предела мы можем обращаться к эволюции химического расстояния в бесконечном кластере (см. Кохен и др., 2001). Таким образом, для того, чтобы полностью охарактеризовать случайные сети, нам необходимо быть знакомыми с этими двумя взаимодополняющими подходами.

V. Обобщенные случайные графы.

В разделе II мы увидели, что реальные сети отличаются от случайных графов в том, что их степенное распределение часто подчиняется степенному закону . Т.к. степенные законы не обладают характерного масштаба, эти сети называются “сетями без масштаба” (Барабаси и Альберт, 1999; Барабаси, Альберт и Йонг, 1999). Из-за того, что случайные графы не обладают свойством независимости от масштаба реальных сетей, нам нужна другая модель для описания этих систем. Одним из подходов является обобщение случайных графов, сконструировав модель, которая в качестве входных данных получает степенное распределение и является случайным по всем другим параметрам. Другими словами, ребра соединяют случайно выбранные вершины с ограничением, что степенное распределение подчиняется степенному закону. Теория таких полу-случайных графов должна ответить на вопросы, подобные тем, что поставили Эрдос и Ренйи и теория перколяции (см. разделы III, IV): Существует ли граница, при которой появляется гигантский кластер? Как развиваются размер и топология кластеров? Когда граф становится связным? Кроме того, необходимо определить среднюю длину пути и коэффициент кластерации такого графа.

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

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

Теория случайных графов с заданной степенной последовательностью возникла сравнительно недавно. Один из первых результатов был достигнут благодаря Луцзаку (1992), кто показал, что почти все случайные графы с фиксированным распределением степеней и со степенями вершин не меньше 2, имеют единственный гигантский кластер. Моллой и Рид (1995, 1998) доказали, что для случайных графов с распределением степеней бесконечный кластер появляется почти наверняка при



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


A. Предел в случайных графах, не зависящих от масштаба.


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


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





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

скачать файл




 



 

 
 

 

 
   E-mail:
   © zaeto.ru, 2021