zaeto.ru

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

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

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


Аелло, Чанг и Лу (2000) представляют модель графа с двумя параметрами , который определяется следующим образом: Пусть _ количество вершин со степенью . определяет одинаковую вероятность для всех графов с . Таким образом, в этой модели определено не общее количество вершин _ вместе с показателем _ в самом начале, а количество вершин со степенью 1. Тем не менее, количество вершин и ребер в графе может быть выведено, учитывая, что максимальная степень в графе . Для нахождения условия появления гигантского кластера в этой модели подставим в равенство , получая в качестве решения . Таким образом, при случайный граф почти наверняка не содержит бесконечный кластер. С другой стороны, при почти наверняка присутствует единственный бесконечный кластер.

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

B. Формализм функции генерации.

Общий подход к случайным графам с заданным распределением степеней был разработан Ньюманом, Строгатзом и Уоттсом (2001) с использованием формализм функции генерации (Уилф, 1990). Функция генерации распределения степеней,



инкапсулирует всю информацию, содержащуюся в , т.к.



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



Среднее количество первых соседей равна средней степени графа,







  1. Размеры компонент и фазовые переходы.

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

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



Когда в графе нет гигантского кластера, средний размер кластеров представляется следующим образом:



Это выражение расходится при , отмечая появление гигантского кластера. Подставляя значение , условие появления гигантского кластера можно записать так:



что идентично с равенством (45), выведенным Моллоем и Ридом (1995). Равенство (53) дает неявную зависимость для критического распределения степеней случайного графа: Для любого распределения степеней, для которого сумма левой части отрицательна, в графе не присутствует гигантский кластер, а распределения степеней с положительной суммой ведут к появлению гигантского кластера.

Когда гигантский кластер присутствует, генерирует распределение вероятностей конечных кластеров. Это означает, что больше не равно 1, а принимает значение , где _ относительное количество вершин в гигантском кластере. Этот факт может быть использован для вычисления значения размера гигантского кластера (Моллой и Рид, 1998):

где _ наименьшее неотрицательное действительное решение равенства .

Т.к. мы имеем дело со случайными графами (несмотря на то, что распределение степеней), теория перколяции (см. раздел IV) отмечает, что в близи перехода фаз хвост распределения размера кластера,, ведет себя следующим образом:

Характерный размер кластера может быть связан с первой особой точкой , , переходом фаз и . Используя разложение в ряд Тейлора в окрестности критической точки, мы видим, что измеряется как



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





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

Расширяя метод вычисления среднего количества ближайших соседей, мы находим среднее количество -тых соседей,

где и _ количество ближайших и вторых по близости соседей. Используя это выражение, мы можем вывести приблизительное соотношение для средней длины пути в графе. Пусть имеется некоторая вершина. Найдем количество ее ближайших, вторых ближайших, …, -тых соседей. Предполагая, что все вершины графа могут быть достигнуты через шагов, получим



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



Для большинства графов с , получим



В случае связных деревьев существует более точный метод (Амбъорн, Дуруус и Джонсон, 1990; Бурда, Коррея и Крзивики, 2001), согласно которому средняя длина связных деревьев с распределением степеней по степенному закону оценивается как , где _ показатель степени. Ни смотря на то, что данная оценка имеет другой функциональный вид, при приближении к зависимость от размера системы становится очень слабой и практически не отличается от логарифмической зависимости.

C. Случайные графы с распределением степеней по степенному закону.

В качестве применения формализма функции генерации Ньюман, Строгатс и Уоттс (2001) рассматривают случай распределения степеней типа



где , и к _ константы. Экспоненциальный остаток, который присутствует в некоторых социальных и биологических (см. Амараль и др., 2000; Йонг, Мейсон и др., 2001; Ньюман, 2001a), обладает техническим преимуществом, давая возможность нормализировать распределения для всех , а не только , как в случае исключительно степенного закона. Константа фиксируется нормализацией, получая значение , где _ -тый полилогарифм . Таким образом, распределение степеней характеризуется двумя независимыми параметрами: показателем и остатком к. Следуя выше описанному формализму, мы получаем, что размер бесконечного кластера равен



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

Средняя длина пути следующая:

где в пределе к имеем





Заметим, что данное выражение не имеет конечного положительного действительного значения для любого , обозначая, что для получения определенной средней длины пути необходимо определить конечный остаток к для распределения степеней.
страница 1 ... страница 3 страница 4 страница 5 страница 6


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





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

скачать файл




 



 

 
 

 

 
   E-mail:
   © zaeto.ru, 2021