Модели случайных графов, для реальных компьютерных сетей

19

Меня интересуют модели случайных графов, которые похожи на графы реальных компьютерных сетей. Я не уверен, что общая хорошо изученная модель ( n вершин, каждое возможное ребро выбрано с вероятностью p ) подходит для изучения реальных компьютерных сетей (не так ли?).G(n,p)np

Какие модели случайных графов полезны для понимания создания компьютерных сетей на практике?

В более общем смысле, какие другие модели конечных случайных графов (кроме тех, которые эквивалентны модели ) были изучены в литературе? (Идеальным ответом будет указатель на опрос для изученных моделей конечных случайных графов.)G(n,p)

Кава
источник
2
Где вам нужны такие модели - это просто для генерирования некоторых тестовых входов для алгоритмов, или вы хотите проанализировать модели, чтобы узнать что-то о компьютерных сетях? Какие компьютерные сети вас интересуют; Каков ваш масштаб (LAN против Интернета)? Почему вы предполагаете, что реальные компьютерные сети генерируются случайным процессом - на удивление часто реальные сети на самом деле разрабатываются инженером с довольно небольшим бросанием монет?
Юкка Суомела
@Jukka, я пытаюсь понять, могу ли я применить методы, разработанные для к таким случайным моделям, чтобы получить информацию о реальных сетях, сейчас я не хочу быть более конкретным, потому что это может дать прочь проблема, о которой я думаю :). Я в основном заинтересован в IP-уровне Интернета. Я видел, как люди использовали случайные графики для анализа графиков, возникающих в социальных сетях. Я не уверен, почему эти реальные сети имеют общие свойства со случайными графами, может быть скрытый случайный процесс за поверхностью работы (кажется интересным задавать вопрос :). G(n,p)
Каве
Я предполагаю, что отчасти интерес к использованию случайных моделей заключается в том, что анализировать их легче, чем анализировать реальные сети, поэтому разумно рассмотреть их, если они достаточно хорошо приближаются к реальной.
Каве
Спасибо всем за хорошие ответы. (Теперь я должен был потратить некоторое время на чтение этих статей. :)
Каве

Ответы:

10

В последние несколько лет изучение случайных графов с «естественными» структурными ограничениями набирает обороты. Например, можно рассмотреть планарный граф, построенный из класса всех плоских графов с вершинами, и изучить его поведение при n . В отличие от случайных графов Эрдеша-Реньи или других подобных моделей, ребра в этих графах сильно зависимы, поэтому одной из псевдомотиваций для изучения таких распределений является анализ сетевых моделей с очень ограниченной независимостью между ребрами.nn

Однако, возможно, в настоящее время эта цель кажется довольно далекой, поскольку ограниченная независимость значительно усложняет анализ свойств таких графов. Фактически, несколько основных вопросов, на которые очень легко получить ответ для , таких как распределение последовательности степеней, были решены только для случайных плоских графов совсем недавно.G(n,p)

Точную ссылку см. В работах Константиноса Панайоту и цитатах из них. Для удобства приведу небольшой образец некоторых соответствующих работ:

  • О степенном распределении случайных плоских графов . Константинос Панайоту и Анжелика Стегер . Появиться в материалах 22-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '11).
  • О свойствах случайных диссекций и триангуляций . Никла Бернаскони, Константинос Панайоту и Анжелика Стегер . В материалах 19-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '08), с. 132-141. [http://www.mpi-inf.mpg.de/~kpanagio/Dissections.pdf]
  • О степенных последовательностях случайных внешнепланарных и последовательно-параллельных графов . Никла Бернаскони, Константинос Панайоту и Анжелика Стегер . В материалах 12-го Международного семинара по рандомизированным методам вычислений (RANDOM'08), с. 303-316. [http://www.mpi-inf.mpg.de/~kpanagio/OPSP.pdf]
Максимум
источник
1
Дополнительный комментарий: это направление исследований на самом деле восходит к 15 годам, по крайней мере, к работе Дениз, Васконселлос и Уэлш (1996), и одна из причин, по которой он «набрал обороты», - это большой успех применения аналитическая комбинаторика и асимптотическое перечисление здесь, например, Gimenez and Noy (2009).
RJK
10

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

Ссылки:

1) Случайные графы как модели сетей, MEJ Newman, в Handbook of Graphs and Networks, S. Bornholdt и HG Schuster (eds.), Wiley-VCH, Berlin (2003).

2) Структура и функции сложных сетей, MEJ Newman, SIAM Review 45, 167-256 (2003)

Мухаммед Аль-Туркистани
источник
1
просто любопытно: это для "социальных" сетей против интернета?
Суреш Венкат
И второе: подходы к социальным сетям должны быть очень полезными, учитывая, что большая часть исследований этих сетей изначально была сосредоточена на «универсальных» свойствах сетей и включала нейронную топологию, электросеть и дорожные сети. Кроме того, сети Барабаси-Альберта и Ваттса-Строгатца, каждая из которых обладает свойствами, которыми обладают реальные сети, и пренебрежением по отношению к Эрдос-Реньи, очень и очень хорошо изучены
Эллиот Дж.Дж.
1
@Suresh, эти сложные сети, описанные в обеих ссылках, включают компьютерные сети, такие как Интернет и социальные сети.
Мохаммед Аль-Туркистани
8

Реальные компьютерные сети на каком уровне? Интернет на уровне AS (возможно, на самом верхнем уровне) - это сеть небольшого мира с некоторыми узлами чрезвычайно высокой степени. По мере того, как слои становятся ближе к фактическим проводам, график становится все более связанным с географией и менее связанным с социальным слоем (социальное - это своего рода неправильное слово - действительно ли это социальная сеть, когда сущности, являющиеся «друзьями», являются многонациональными корпорациями?) , В крайнем случае локальная сеть Ethernet - это логическое дерево, которое (вероятно) является подграфом физического шаблона проводных соединений, и этот шаблон проводных соединений, вероятно, не слишком много проводов, чем дерево.

«Настоящие компьютерные сети» бывают разных вкусов и уровней. Некоторые из них похожи на социальные сети, некоторые нет. Подробнее об этом я нескромно отсылаю вас к главе 2 моей диссертации - http://home.manhattan.edu/~peter.boothe/thesis.pdf

Питер Бут
источник
В основном меня интересуют физические сети (скажем, IP-уровень). Спасибо за ссылку, проверю.
Каве
2
Уровень IP не является физическим уровнем. MPLS и другие технологии коммутации каналов нарушают это предположение. Физический уровень - это провода. У нас даже есть многопроводные соединения, которые выглядят как отдельные переходы Ethernet! Этот вопрос о том, «какой слой» является более глубоким, чем можно предположить при первом осмотре, требует тщательного обдумывания. Я предлагаю вам подумать о свойствах, которые вы, возможно, хотите иметь в сети, найти уровень, на котором анализ топологии поможет вам лучше проанализировать это свойство, и надеяться, что данные будут доступны.
Питер Бут
5

Уолтер Виллингер сделал карьеру на использовании безмасштабных графов для моделирования сетей. Здесь слишком много ссылок, поэтому я укажу на его запись в DBLP . Ключевым моментом в этих моделях является то, что они обладают свойствами, подобными «реальным» сетям, которые не фиксируются G (n, p).

Суреш Венкат
источник
5

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

Sp1:(S)Sp2:εp1,p2

Очевидно, что конкретная грамматика может (и должна!) Использовать знание предметной области. Рассмотрим, например, различные грамматики, используемые для предсказания вторичной структуры РНК в Dowell, Eddy (2004) для вкуса.

Найдите некоторые подробности об этой технике в Weinberg, Nebel (2010) . Я не знаю, как (хорошо) это может быть применено к общим графам, все же.

Если вам нужно больше энергии, вы можете перейти к многомерным (S) CFG (например, Seki, Kato (2008) ) или SCFG, зависящим от длины / позиции ( Weinberg, Nebel (2010) ).

Рафаэль
источник
1
это круто, но разве контекстно-свободный характер SCFG не заставляет вашего ученика пренебрегать определенной глобальной структурой, которую могут иметь сети в вашем учебном наборе?
Артем Казнатчеев
Ну да, неконтекстно-свободные функции теряются. Но обратите внимание, что такие свойства, как (средняя) степень узла могут быть зафиксированы. Для получения дополнительной информации см. Мое редактирование.
Рафаэль
Благодарность! Я посмотрю поближе. Разве скрытые MDP также не могут захватывать свойства, такие как средняя степень? Кажется, что-то, что обычный язык должен уметь воспринимать, или я запутался? (Кроме того, второстепенный момент: ссылка Вайнберг, Небель имеет завершающий символ, который убивает ссылку, очевидно, какую ссылку вы намеревались, но если вы сделаете больше правок, возможно, стоит исправить).
Артем Казнатчеев
Конечно, я просто хотел отметить, что с помощью этой модели вы можете охватить некоторые глобальные характеристики. REG также может охватывать некоторые, но не сможет моделировать по своей природе нерегулярные структуры. (спасибо, исправлено)
Рафаэль
3

G(n,p)G(n,m)

Как вы, вероятно, знаете, похоже, что существует разница между графиком подключений для Всемирной паутины и противоположностью графиков подключений для инфраструктуры Интернета. Я, конечно, не претендую на звание эксперта, но я видел статью Ли, Олдерсона, Танаки, Дойла и Виллингера «К теории безмасштабных графов: определение, свойства и следствия», в которой вводится метрика «для измерения« свободы от масштаба » графа (с определением безмасштабных графов, насколько я знаю, до сих пор обсуждаемых), которые утверждают, что имеют графовую модель, которая создает графы, похожие на интернет-соединение на маршрутизаторе уровень.

Вот еще несколько генеративных моделей, которые могут представлять интерес:

Статья Бергера, Боргса, Чайеса, Д'Сузы и Кляйнберга "Преференциальный привязанность, вызванная конкуренцией"

Высокооптимизированный допуск Карлсона и Дойла : механизм для степенных законов в проектируемых системах

Критическая точка Моллой и Рида для случайных графов с заданной последовательностью степеней, которая вводит «стертую модель конфигурации»

Кластеризация Ньюмана и преференциальная привязанность в растущих сетях (о которых уже упоминалось)

Можно также явно сгенерировать распределение степеней и создать график таким образом, но мне неясно, насколько близко это моделирует интернет-график на уровне маршрутизатора.

Разумеется, литературы по этому вопросу гораздо больше, и я дал лишь несколько (как мне кажется,) основных моментов.

G(n,p)G(n,m)) не работают именно потому, что степень без масштаба или степенной закон распределены случайными графиками, расходящимися второй момент в распределении степеней. Я не претендую на то, что знаю достаточно о предмете, чтобы категорически утверждать о «большинстве» доказательств, но из того, что я видел, одна из первых нескольких строк доказательств свойств случайных графов Эрдоша-Реньи явно предполагает конечное Второй момент в распределении степеней. С моей точки зрения, это имеет смысл, так как конечный второй момент делает графы Эрдоша-Реньи более локально древовидными (см. Информацию, физику и вычисления Мертенса и Монтанари) который эффективно дает свойства / пути / структуры независимости. Поскольку степенные распределенные случайные графы имеют второй расходящийся момент, эта локальная древовидная структура разрушается (и, следовательно, требует различных методов доказательства?). Я был бы счастлив лишить эту интуицию, если бы кто-то с большим знанием или проницательностью показал, почему это не так.

Надеюсь, это поможет.

user834
источник
3

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

Модель Барабаси-Альберта и другие модели, которые создают безмасштабные графы, были предложены для моделирования Интернета на уровне маршрутизатора и на уровне автономной системы. Хотя изначально такие модели считались точными, оказалось, что у нас нет полного представления о топологии Интернета из-за трудностей с обнаружением всех ссылок. Хотя это, как полагают, тяжелый хвост, это в значительной степени работа в процессе.

Для справки вы можете прочитать: RG Clegg, C Di Cairano-Gilfedder, S Zhou, критический взгляд на степенное моделирование Интернета

Василис
источник
2

Есть несколько книг о случайных графах, как книги Bollobás' и есть несколько моделей случайных графов , как малый мир Википедии ссылки или льготное Attachment ссылки Википедии , модельные сети с малыми расстояниями между компьютерами или те , со степенью распределения следующих степенным закона соответственно.

Я думаю, что не существует простого способа моделирования реальной компьютерной сети, но я уверен, что G (n, p) не очень хорошо смоделирует ее. Если вы не работаете с очень определенной организованной сетью.

dpufrj
источник
2

Моя рекомендация - обзорная статья, написанная изобретателями генератора случайных графов R-MAT. http://portal.acm.org/citation.cfm?id=1132954

Генератор случайных графов R-MAT очень прост и широко используется. Например, этот генератор принят в тесте Graph500 ( http://www.graph500.org/ ).

Snowie
источник