Первая страница / Теория / Графы. Основные алгоритмы /

Случайные графы

Голосование: 17, 0

Введение

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

Эти системы представляют только малую часть примеров, которые не так давно подсказали ученым о надобности исследовать механизмы, которые определяют топологию сложных сетей. Исторически изучением сложных сетей занимается теория графов. В то время как теория графов изначально описывала регулярные графы, начиная с 1950-го года, сложные сети, не имевшие очевидных принципов построения, стали описывать с помощью теории случайных графов, предложенных в качестве наиболее подходящей модели сложных сетей. Впервые случайные графы были изучены венгерскими математиками Полом Эрдёшем (Paul Erdős) и Альфредом Реньи (Alfred Rényi). Согласно модели Эрдёша-Реньи, имеем N вершин и, соединяя каждую пару вершин с вероятностью p, создаем граф с приблизительно случайно распределенными ребрами.

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

Основные концепции моделирования

Малые миры. Концепция малых миров довольно просто описывает тот факт, что, несмотря на их огромные размеры, в большинстве сетей существует сравнительно короткий путь между двумя любыми вершинами. Расстояние между двумя вершинами определяется как число ребер наикратчайшего пути, их соединяющего. Но, принцип «малых миров», хотя и интригует, не является специальным принципом организации. Наконец, Эрдёшем и Реньи показано, что среднее расстояние между двумя вершинами в случайном графе растет как логарифм от числа вершин. Тем не менее, случайные графы являются малыми мирами.

Кластерность. Общее свойство социальных сетей состоит в том, чем является клика графа, представляя собой круг друзей и знакомых, в котором каждый участник знаком друг с другом. Эта тенденция к разбиению на кластеры определяется коэффициентом кластерности (Watts, Strogats 1998). Сначала выберем в сети некоторую вершину i, имеющую Ki ребер, которые соединяют ее с Ki другими вершинами. Если первые ближние соседи этой вершины являются частью клики, между ними существует ребер. Отношение между числом Ei ребер, действительно существующих между Ki вершинами, и общим числом ребер является значением коэффициента кластерности вершины i: . Общий коэффициент кластерности сети находится как сумма коэффициентов отдельных вершин. В случайном графе, поскольку ребра распределяются случайным образом, коэффициент кластерности составляет C = p. Правда, Ватс и Строгатс первыми указали на факт, что во многих, если не во всех, реальных сетях коэффициент кластерности обычно значительно больше, чем в случайных сетях с таким же количеством ребер и вершин.

Распределение степеней. Не все вершины сети имеют одинаковое количество ребер. Распределение количества ребер вершины, то есть степень вершины, характеризуется функцией P(k), которая определяет вероятность того, что случайно выбранная вершина будет иметь ровно k ребер. Поскольку в случайном графе ребра распределяются случайным образом, большая часть вершин имеет приблизительно одинаковую степень, близкую к средней степени <k> сети. Распределение степеней вершин случайного графа является распределением Пуассона с пиком в P(<k>). С другой стороны, последние эмпирические результаты говорят о том, что для большинства сетей распределение степеней значительно отличается от распределения Пуассона. В частности, для многих сетей, включая Всемирную паутину (Albert, Jeong, Barabasi 1999), Интернет (Falautsos 1999), распределение степеней вершин является степенным: P(k) ≈ k−π. Такие сети называют сетями без масштабирования (Barabasi, Albert 1999). В то время как некоторые сети имеют экспоненциальное распределение, часто форма функции P(k) значительно отличается от распределения Пуассона, ожидаемого для случайного графа.

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

Как говорилось ранее, в данной статье рассмотрены случайные графы так, как они изначально были введены Эрдёшем и Реньи.

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

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

Модель Эрдёша-Реньи

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

Другое определение случайного графа называют также биноминальной моделью. В этом случае, имея N вершин, соединяем каждые 2 из них с вероятностью p. В конечном итоге, полученное количество ребер будет случайной величиной с ожидаемым значением N → ∞. Если G0 — граф с вершинами P1, P2, …, PN и n ребрами, вероятность получить его с помощью этого процесса составит .

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

Процесс создания случайного графа в литературе часто называют эволюцией: начиная с N изолированных вершин, граф последовательно развивается благодаря добавлению новых случайных ребер. Графы, полученные на разных стадиях этого процесса, соответствуют все большим и большим вероятностям p, в конце концов, получаем полный граф (имеющий максимальное количество ребер ) при p = 1.

Чтобы лучше понять, о чем идет речь, можете ознакомиться с визуализатором.

Основная идея теории случайных графов состоит в том, чтобы определить при какой вероятности p будет проявлено некоторое свойство. Наибольшее открытие Эрдёша и Реньи в том, что многие важные свойства случайных графов начинают проявляться довольно внезапно. То есть, при заданной вероятности, либо практически каждый граф обладает свойством Q (состоящем, например, в том, что каждая пара вершин соединена последовательными ребрами), либо практически ни один граф им не обладает. Переход от вероятного к маловероятному событию происходит при этом очень резко. Для многих из таких свойств существует критическая вероятность pc(N). Если p(N) возрастает медленнее, чем pc(N) при N → ∞, то практически ни один граф не будет обладать свойством Q. Если p(N) возрастает несколько быстрее, чем pc(N), практически любой граф будет обладать свойством Q. Таким образом, вероятность того, что граф с N вершинами и функцией распределения ребер p = p(N) обладает свойством Q, задается таким образом:

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

Подграфы

Первым свойством случайных графов, изученным Эрдёшем и Реньи (1959), было появление подграфов. Граф G1, состоящий из множества P1 вершин и множества E1 ребер, является подграфом графа G = {PE}, если все вершины E1 также являются вершинами E. Простейшими примерами подграфов являются циклы, деревья и полные подграфы. Цикл порядка k — это замкнутый путь из k ребер, в котором только два последовательных ребра имеют общую вершину. Таким образом, треугольник — это цикл 3-го порядка, а четырехугольник — 4-го. Средняя степень цикла равна 2, поскольку каждая вершина имеет 2 ребра. Противоположность циклам составляют деревья, которые не могут образовывать замкнутый контур. Точнее, деревом порядка k является граф, не имеющий циклов, у которого k вершин и k−1 ребер. Средняя степень дерева порядка k составляет <k> = 2 − k ⁄ 2 и стремится к 2 для больших деревьев. Полные подграфы порядка k содержат k вершин и все из возможных ребер, другими словами, все их вершины соединены.

В теории случайных графов имеется точный ответ на этот вопрос (Bollobas 1985). Рассмотрим случайный граф G = G(Np). Дополнительно рассмотрим небольшой граф F, состоящий из k вершин и l ребер. В принципе, случайный граф G может содержать несколько таких подграфов. Во-первых, определим, сколько таких подграфов существует. k вершин могут быть выбраны из общего числа N вершин способами, а l ребер могут быть образованы с вероятностью pl. К тому же, мы можем переставлять k вершин и в итоге получить k! новых графов (точное значение равно , где a — количество взаимно изоморфных графов). Таким образом, ожидаемое количество подграфов F графа G составит Подразумеваем, что реальное число таких подграфов может отличаться от E(X), но в большинстве случаев оно будет соответствовать данному выражению. Заметим, что подграфы не должны быть изолированными, то есть могут существовать вершины, имеющие свое начало в подграфе, а конец — вне его. Уравнение показывает, что если p(N) таково, что при N → ∞, ожидаемое количество подграфов E(X) → 0, то есть, практически ни один из случайных графов не содержит подграфа F. С другой стороны, если , количество подграфов будет конечным числом, определяемым , что говорит о том, что эта функция может быть критической вероятностью. Правильность этого утверждения может быть проверена расчетами распределения количества подграфов Pp(X = r), что дает (согласно Боллобасу 1995):

Вероятность того, что граф G содержит, по крайней мере, один подграф F, составляет в таком случае

что стремится к 1 при увеличении c. Для значений p, удовлетворяющих вероятность стремится к 1, тем не менее, критическая вероятность того, что практически каждый граф содержит подграф с k вершинами и l ребрами, составляет Pp(X = r)

Некоторые важные свойства:

  1. Критическая вероятность наличия дерева порядка k составляет
  2. Критическая вероятность наличия цикла порядка k составляет
  3. Критическая вероятность наличия полного подграфа порядка k составляет

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

Эрдёш и Реньи (1959) были первыми, кто изучил распределение максимальных и минимальных степеней в случайном графе, полное распределение степеней было получено позднее Боллобасом (1981). В случайном графе с вероятностью связности p степень ki вершины i следует биномиальному распределению с параметрами N−1 и p:

Эта вероятность представляет количество способов, которыми k ребер могут быть проведены из определенной вершины: вероятность для k ребер составляет pk, вероятность отсутствия дополнительных ребер составляет (1−p)N−1−k и существует эквивалентных способов выбора k конечных точек для этих ребер. Тем более, если вершины i и j являются различными, P(ki = k) и P(kj = k) близки к тому, чтобы быть независимыми случайными переменными. Для нахождения распределения степеней графа, необходимо изучить количество вершин со степенью k (обозначим Xk). Нашей основной целью будет определить вероятность того, что Xk принимает заданное значение P(Xk = r)

Согласно (*), ожидаемое количество вершин со cтепенью k составит , где . C хорошим приближением для распределения степеней в случайном графе подходит биномиальное распределение , которое для больших N может быть заменено распределением Пуассона:

Связность и диаметр

Диаметр графа — наибольшее расстояние между двумя любыми его вершинами. Точно выражаясь, диаметр несвязного графа (например, образованного несколькими изолированными кластерами) бесконечен, но может быть определен, как максимальный из диаметров его кластеров. Случайные графы имеют малый диаметр, при условии, что p мало. Причина этого в том, что случайный граф кажется расширяющимся: с большой вероятностью количество вершин с расстоянием l от выбранной вершины пропорционально ln(N) ⁄ ln(<k>), то есть, оно логарифмически зависит только от количества вершин. Диаметр случайных графов изучался многими людьми (Chang, Lu 2001). Общий вывод состоит в том, что для большинства значений p, практически все графы имеют один и тот же диаметр. Это значит, что, когда мы рассматриваем все графы с N вершинами и вероятностью связности p, диаметры могут лишь незначительно отличаться, обычно находясь около значения

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

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

Заключение

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

Литература

  1. Колчин В. Ф. Случайные графы. 2-е изд. — М.: ФИЗМАТЛИТ, 2004.

Сергей Косухин


Очень хорошее введение в предмет! Спасибо

татьяна / 2015-05-28 13:01:22

А как подсчитать а - количество взаимно изоморфных графов?

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

Татьяна / 2015-05-28 16:23:34

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

Увы, с такой постановкой задачи сталкиваться не приходилось. Собственно, тематика СЛУЧАЙНЫХ графов на нашем сайте достаточна СЛУЧАЙНА.

Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий