Меня интересуют модели случайных графов, которые похожи на графы реальных компьютерных сетей. Я не уверен, что общая хорошо изученная модель ( n вершин, каждое возможное ребро выбрано с вероятностью p ) подходит для изучения реальных компьютерных сетей (не так ли?).
Какие модели случайных графов полезны для понимания создания компьютерных сетей на практике?
В более общем смысле, какие другие модели конечных случайных графов (кроме тех, которые эквивалентны модели ) были изучены в литературе? (Идеальным ответом будет указатель на опрос для изученных моделей конечных случайных графов.)
Ответы:
В последние несколько лет изучение случайных графов с «естественными» структурными ограничениями набирает обороты. Например, можно рассмотреть планарный граф, построенный из класса всех плоских графов с вершинами, и изучить его поведение при n → ∞ . В отличие от случайных графов Эрдеша-Реньи или других подобных моделей, ребра в этих графах сильно зависимы, поэтому одной из псевдомотиваций для изучения таких распределений является анализ сетевых моделей с очень ограниченной независимостью между ребрами.N n → ∞
Однако, возможно, в настоящее время эта цель кажется довольно далекой, поскольку ограниченная независимость значительно усложняет анализ свойств таких графов. Фактически, несколько основных вопросов, на которые очень легко получить ответ для , таких как распределение последовательности степеней, были решены только для случайных плоских графов совсем недавно.G(n,p)
Точную ссылку см. В работах Константиноса Панайоту и цитатах из них. Для удобства приведу небольшой образец некоторых соответствующих работ:
источник
В этом обзоре «Структура и функции сложных сетей», подготовленном 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)
источник
Реальные компьютерные сети на каком уровне? Интернет на уровне AS (возможно, на самом верхнем уровне) - это сеть небольшого мира с некоторыми узлами чрезвычайно высокой степени. По мере того, как слои становятся ближе к фактическим проводам, график становится все более связанным с географией и менее связанным с социальным слоем (социальное - это своего рода неправильное слово - действительно ли это социальная сеть, когда сущности, являющиеся «друзьями», являются многонациональными корпорациями?) , В крайнем случае локальная сеть Ethernet - это логическое дерево, которое (вероятно) является подграфом физического шаблона проводных соединений, и этот шаблон проводных соединений, вероятно, не слишком много проводов, чем дерево.
«Настоящие компьютерные сети» бывают разных вкусов и уровней. Некоторые из них похожи на социальные сети, некоторые нет. Подробнее об этом я нескромно отсылаю вас к главе 2 моей диссертации - http://home.manhattan.edu/~peter.boothe/thesis.pdf
источник
Waxman, Маршрутизация многоточечных соединений , IEEE J. Select. Области Сообщество. 6 (9), 1617-1622, 1988. Зегура, Калверт, Бхаттачарджи, Как смоделировать межсетевое взаимодействие , Учеб. IEEE INFOCOM '96, 1996.
источник
Уолтер Виллингер сделал карьеру на использовании безмасштабных графов для моделирования сетей. Здесь слишком много ссылок, поэтому я укажу на его запись в DBLP . Ключевым моментом в этих моделях является то, что они обладают свойствами, подобными «реальным» сетям, которые не фиксируются G (n, p).
источник
Возможно, вы захотите проверить книгу Дарретта . Я полагаю, у вас есть много чтения, чтобы сделать.
источник
Вместо того, чтобы кропотливо находить, обосновывать и анализировать конкретную модель, вы, возможно, захотите использовать имеющиеся у вас реальные данные (если они у вас есть). Это означает определение общей вероятностной модели и обучение ее параметров с учетом ваших данных (например, путем оценки максимального правдоподобия).
Очевидно, что конкретная грамматика может (и должна!) Использовать знание предметной области. Рассмотрим, например, различные грамматики, используемые для предсказания вторичной структуры РНК в Dowell, Eddy (2004) для вкуса.
Найдите некоторые подробности об этой технике в Weinberg, Nebel (2010) . Я не знаю, как (хорошо) это может быть применено к общим графам, все же.
Если вам нужно больше энергии, вы можете перейти к многомерным (S) CFG (например, Seki, Kato (2008) ) или SCFG, зависящим от длины / позиции ( Weinberg, Nebel (2010) ).
источник
Как вы, вероятно, знаете, похоже, что существует разница между графиком подключений для Всемирной паутины и противоположностью графиков подключений для инфраструктуры Интернета. Я, конечно, не претендую на звание эксперта, но я видел статью Ли, Олдерсона, Танаки, Дойла и Виллингера «К теории безмасштабных графов: определение, свойства и следствия», в которой вводится метрика «для измерения« свободы от масштаба » графа (с определением безмасштабных графов, насколько я знаю, до сих пор обсуждаемых), которые утверждают, что имеют графовую модель, которая создает графы, похожие на интернет-соединение на маршрутизаторе уровень.
Вот еще несколько генеративных моделей, которые могут представлять интерес:
Статья Бергера, Боргса, Чайеса, Д'Сузы и Кляйнберга "Преференциальный привязанность, вызванная конкуренцией"
Высокооптимизированный допуск Карлсона и Дойла : механизм для степенных законов в проектируемых системах
Критическая точка Моллой и Рида для случайных графов с заданной последовательностью степеней, которая вводит «стертую модель конфигурации»
Кластеризация Ньюмана и преференциальная привязанность в растущих сетях (о которых уже упоминалось)
Можно также явно сгенерировать распределение степеней и создать график таким образом, но мне неясно, насколько близко это моделирует интернет-график на уровне маршрутизатора.
Разумеется, литературы по этому вопросу гораздо больше, и я дал лишь несколько (как мне кажется,) основных моментов.
Надеюсь, это поможет.
источник
Хотя это старая тема, на которую я отвечаю, поскольку многие люди до сих пор посещают такие посты. Я мотивирован из комментария в другом ответе.
Модель Барабаси-Альберта и другие модели, которые создают безмасштабные графы, были предложены для моделирования Интернета на уровне маршрутизатора и на уровне автономной системы. Хотя изначально такие модели считались точными, оказалось, что у нас нет полного представления о топологии Интернета из-за трудностей с обнаружением всех ссылок. Хотя это, как полагают, тяжелый хвост, это в значительной степени работа в процессе.
Для справки вы можете прочитать: RG Clegg, C Di Cairano-Gilfedder, S Zhou, критический взгляд на степенное моделирование Интернета
источник
Есть несколько книг о случайных графах, как книги Bollobás' и есть несколько моделей случайных графов , как малый мир Википедии ссылки или льготное Attachment ссылки Википедии , модельные сети с малыми расстояниями между компьютерами или те , со степенью распределения следующих степенным закона соответственно.
Я думаю, что не существует простого способа моделирования реальной компьютерной сети, но я уверен, что G (n, p) не очень хорошо смоделирует ее. Если вы не работаете с очень определенной организованной сетью.
источник
Моя рекомендация - обзорная статья, написанная изобретателями генератора случайных графов R-MAT. http://portal.acm.org/citation.cfm?id=1132954
Генератор случайных графов R-MAT очень прост и широко используется. Например, этот генератор принят в тесте Graph500 ( http://www.graph500.org/ ).
источник