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

22

Время коммутирования в связанном графе определяется как ожидаемое количество шагов в случайном блуждании, начиная с , до посещения узла и затем достижения узла снова. В основном это сумма двух времен удара и .гзнак равно(В,Е)яJяЧАС(я,J)ЧАС(J,я)

Есть ли что-то похожее на время в пути (не совсем то же самое), но определенное в терминах узлов? Другими словами, каково ожидаемое количество отдельных узлов, которые будут посещать случайные блуждания, начиная с и заканчивая ?яя

Обновление (30 сентября 2012 г.). Существует ряд работ, посвященных количеству различных сайтов, посещаемых случайным посетителем на решетке (т. ). Например, см .: http://jmp.aip.org/resource/1/jmapaq/v4/i9/p1191_s1?isAuthorized=noZN

Кто-нибудь когда-нибудь читал что-нибудь об этом?

Фабрицио Сильвестри
источник
В чем проблема со следующим аргументом? Случайное блуждание на графе может быть описано цепью Маркова, где состояния являются узлами. Точно так же можно представить ту же прогулку цепью Маркова, где состояния могут быть ребрами. (Каждое ребро также содержит информацию о текущем посещенном узле.) Как только цепь Маркова получена, вы можете использовать любое определение / результат цепей Маркова.
Абузер Якарылмаз
Спасибо за комментарий. Я на самом деле забыл сказать отдельные узлы. Я собираюсь изменить вопрос прямо сейчас.
Фабрицио Сильвестри
Возможно я пропустил это (извините, если так), но каков URL к сообщению SE?
Я удалил сообщение SE ... Запрещено размещать один и тот же вопрос в двух разных местах.
Фабрицио Сильвестри
это зависит от конкретного графика, верно? Можете ли вы набросать что-нибудь известное о подобных проблемах?
vzn

Ответы:

4

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

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

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

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

(может быть, он имеет небольшую мировую структуру ?, что довольно широко распространено в реальных данных)

ВЗН
источник
Хорошо поймал. Действительно, он имеет небольшую мировую структуру. Фактически, в приложении, которое я имею в виду, распределение степеней следует степенному закону. Теперь это может помочь ... Тем не менее, мы не нашли хороший способ пойти :)
Фабрицио Сильвестри
Спасибо. какой параметр кэширования вы пытаетесь оптимизировать? Кажется, это может как-то напрямую соотноситься с показателем степенного закона ....? Подозреваю, что простые подходы Монте-Карло могут показать, что расстояние в стеке связано с показателем степенного закона и т. д.
vzn
ααзнак равно1,<1,>1
Кажется, что расстояние в стеке не изучалось непосредственно в теории графов, но это обширная область. обратите внимание, что модель Ватт / Строгатц хороша для подходов Монте-Карло, генерирующих маленькие графы мира. Также случайные блуждания по графу Ловаша - хороший обзор теории блужданий по случайным графам.
2012 года
4

Комментарий: Недавно я присутствовал на выступлении Брюса Рида под названием « Поймать пьяницу» , которое было совместной работой с Наташей Коморовой и Питером Винклером. Если вы сможете получить результаты этой работы, возможно, это поможет вам в каком-то направлении.

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

Пол Г.Д.
источник
Есть ли возможность иметь черновик или копию слайдов?
Фабрицио Сильвестри
2
Извините, мне больше нечего дать, но, может быть, эта ветка МО поможет: копам и пьяным грабителям .
Пол GD
Спасибо, Пол ... Я смотрю на документ, связанный из темы МО.
Фабрицио Сильвестри
3

Это не совсем правильный ответ на ваш вопрос, но это слишком долго для комментария.

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

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

N1NN+1

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

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

Конечно, эти комментарии больше не действуют в случае квантовых случайных блужданий, но я думаю, что вы заботитесь только о классическом случае.

Джо Фитцсимонс
источник