Смещенное случайное блуждание по графу

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

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

Модель

Было написано много различных представлений смещенных случайных блужданий на графах, основанных на конкретной цели анализа. Общее представление механизма неориентированных графов выглядит следующим образом: ^[2]

В неориентированном графе ходок делает шаг от текущего узла, $j,$ узел $i.$ Предполагая, что каждый узел имеет атрибут $\alpha _{i},$ вероятность прыжка с узла $j$ к $i$ дается:

T_{ij}^{\alpha }={\frac {\alpha _{i}A_{ij}}{\sum _{k}\alpha _{k}A_{kj}}},

где $A_{ij}$ представляет топологический вес ребра, идущего от $j$ к $i.$

Фактически, шаги ходока смещаются под действием фактора $\alpha$ которые могут отличаться от одного узла к другому. ^[3]

В зависимости от сети атрибут $\alpha$ можно интерпретировать по-разному. Это может подразумеваться как притяжение человека в социальной сети , это может быть центральность посредничества или даже может быть объяснено как внутренняя характеристика узла. В случае справедливого случайного блуждания по графу $\alpha$ один для всех узлов.

В случае кратчайших путей случайные блуждания ^[4] $\alpha _{i}$ общее количество кратчайших путей между всеми парами узлов, проходящих через узел $i$ . Фактически, ходок предпочитает узлы с более высокой центральностью посредничества , которая определяется следующим образом:

C(i)={\tfrac {{\text{Total number of shortest paths through }}i}{\text{Total number of shortest paths}}}

На основе приведенного выше уравнения время возврата к узлу смещенного обхода определяется выражением: ^[5]

r_{i}={\frac {1}{C(i)}}

Приложения

Существует множество приложений, использующих смещенные случайные блуждания по графам. Такие приложения включают контроль диффузии, ^[6] реклама продукции в социальных сетях , ^[7] объясняющие расселение и перераспределение популяций животных и микроорганизмов, ^[8] обнаружение сообщества, ^[9] беспроводные сети, ^[10] и поисковые системы. ^[11]

См. также

Ссылки

^ Роберта Синатра ; Хесус Гомес-Гарденьес ; Рено Ламбьотт; Винченцо Никосия; Вито Латора (март 2011 г.). «Случайные блуждания с максимальной энтропией в сложных сетях с ограниченной информацией». Физический обзор E . 83 (3): 030103. arXiv : 1007.4936 . Бибкод : 2011PhRvE..83c0103S . дои : 10.1103/PhysRevE.83.030103 . ПМИД 21517435 . S2CID 6984660 .
^ Х. Гомес-Гарденьес; В. Латора (декабрь 2008 г.). «Скорость энтропии диффузионных процессов в сложных сетях». Физический обзор E . 78 (6): 065102. arXiv : 0712.0278 . Бибкод : 2008PhRvE..78f5102G . дои : 10.1103/PhysRevE.78.065102 . ПМИД 19256892 . S2CID 14100937 .
^ Р. Ламбьотт; Р. Синатра; Ж.-К. Дельвенн; Т.С. Эванс; М. Бараона; В. Латора (декабрь 2010 г.). «Потоковые графики: переплетение динамики и структуры». Физический обзор E . 84 (1): 017102. arXiv : 1012.1211 . Бибкод : 2011PhRvE..84a7102L . дои : 10.1103/PhysRevE.84.017102 . ПМИД 21867345 . S2CID 2286264 .
^ Бланшар, П; Волченков, Д (2008). Математический анализ городских пространственных сетей . Спрингер. дои : 10.1007/978-3-540-87829-2 . ISBN 978-3-540-87828-5 – через ResearchGate.
^ Волченков Д; Бланшар П. (2011). Честные и предвзятые случайные блуждания по неориентированным графам и связанные с ними энтропии . Биркхойзер. п. 380. ИСБН 978-0-8176-4903-6 .
^ Чунг, Чжао, Фань, Вэньбо (2010). «PageRank и случайные блуждания по графикам». Праздник комбинаторики и информатики . Общество математических исследований Боляи. Том. 20. стр. 43–62. CiteSeerX 10.1.1.157.7116 . дои : 10.1007/978-3-642-13580-4_3 . ISBN 978-3-642-13579-8 . S2CID 3207094 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Адал, К.М. (июнь 2010 г.). «Маршрутизация на основе смещенного случайного блуждания для одноранговых мобильных сетей». 2010 Международная конференция по интеллектуальным и передовым системам . стр. 1–6. дои : 10.1109/ICIAS.2010.5716181 . ISBN 978-1-4244-6623-8 . S2CID 16113377 .
^ Какаджан Комуров; Майкл А. Уайт; Прахлад Т. Рам (август 2010 г.). «Использование случайных блужданий по графам, основанных на данных, для извлечения контекстно-зависимых сетей из геномных данных» . ПЛОС Компьютерная Биол . 6 (8): e1000889. Бибкод : 2010PLSCB...6E0889K . дои : 10.1371/journal.pcbi.1000889 . ПМЦ 2924243 . ПМИД 20808879 .
^ Дж. К. Охаб; З. Бурда (январь 2013 г.). «Случайное блуждание с максимальной энтропией при обнаружении сообществ». Специальные темы Европейского физического журнала . 216 : 73–81. arXiv : 1208.3688 . Бибкод : 2013EPJST.216...73O . doi : 10.1140/epjst/e2013-01730-6 . S2CID 56409069 .
^ Беральди, Роберто (апрель 2009 г.). «Смещенные случайные блуждания в однородных беспроводных сетях». Транзакции IEEE на мобильных компьютерах . 8 (4): 500–513. дои : 10.1109/TMC.2008.151 . S2CID 13521325 .
^ Да-Чэн Не; Цзы-Ке Чжан; Цян Донг; Чунцзин Сунь; Ян Фу (июль 2014 г.). «Фильтрация информации посредством смещенного случайного блуждания в связанной социальной сети» . Научный мировой журнал . 2014 : 829137. doi : 10.1155/2014/829137 . ПМЦ 4132410 . ПМИД 25147867 .

Внешние ссылки

Габор Симони, «Энтропия графа: исследование» . В книге «Комбинаторная оптимизация» (под ред. У. Кука, Л. Ловаша и П. Сеймура). Провиденс, Род-Айленд: Амер. Математика. Соц., стр. 399–441, 1995.
Анн-Мари Кермаррек, Эрван Ле Меррер, Бруно Серикола, Жиль Тредан, «Оценка качества топологии сети посредством случайных блужданий» в книге Гади Таубенфельда (ред.) Распределенные вычисления

[1] Роберта Синатра ; Хесус Гомес-Гарденьес ; Рено Ламбьотт; Винченцо Никосия; Вито Латора (март 2011 г.). «Случайные блуждания с максимальной энтропией в сложных сетях с ограниченной информацией». Физический обзор E . 83 (3): 030103. arXiv : 1007.4936 . Бибкод : 2011PhRvE..83c0103S . дои : 10.1103/PhysRevE.83.030103 . ПМИД 21517435 . S2CID 6984660 .

[2] Х. Гомес-Гарденьес; В. Латора (декабрь 2008 г.). «Скорость энтропии диффузионных процессов в сложных сетях». Физический обзор E . 78 (6): 065102. arXiv : 0712.0278 . Бибкод : 2008PhRvE..78f5102G . дои : 10.1103/PhysRevE.78.065102 . ПМИД 19256892 . S2CID 14100937 .

[3] Р. Ламбьотт; Р. Синатра; Ж.-К. Дельвенн; Т.С. Эванс; М. Бараона; В. Латора (декабрь 2010 г.). «Потоковые графики: переплетение динамики и структуры». Физический обзор E . 84 (1): 017102. arXiv : 1012.1211 . Бибкод : 2011PhRvE..84a7102L . дои : 10.1103/PhysRevE.84.017102 . ПМИД 21867345 . S2CID 2286264 .

[4] Бланшар, П; Волченков, Д (2008). Математический анализ городских пространственных сетей . Спрингер. дои : 10.1007/978-3-540-87829-2 . ISBN 978-3-540-87828-5 – через ResearchGate.

[5] Волченков Д; Бланшар П. (2011). Честные и предвзятые случайные блуждания по неориентированным графам и связанные с ними энтропии . Биркхойзер. п. 380. ИСБН 978-0-8176-4903-6 .

[6] Чунг, Чжао, Фань, Вэньбо (2010). «PageRank и случайные блуждания по графикам». Праздник комбинаторики и информатики . Общество математических исследований Боляи. Том. 20. стр. 43–62. CiteSeerX 10.1.1.157.7116 . дои : 10.1007/978-3-642-13580-4_3 . ISBN 978-3-642-13579-8 . S2CID 3207094 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )

[7] Адал, К.М. (июнь 2010 г.). «Маршрутизация на основе смещенного случайного блуждания для одноранговых мобильных сетей». 2010 Международная конференция по интеллектуальным и передовым системам . стр. 1–6. дои : 10.1109/ICIAS.2010.5716181 . ISBN 978-1-4244-6623-8 . S2CID 16113377 .

[8] Какаджан Комуров; Майкл А. Уайт; Прахлад Т. Рам (август 2010 г.). «Использование случайных блужданий по графам, основанных на данных, для извлечения контекстно-зависимых сетей из геномных данных» . ПЛОС Компьютерная Биол . 6 (8): e1000889. Бибкод : 2010PLSCB...6E0889K . дои : 10.1371/journal.pcbi.1000889 . ПМЦ 2924243 . ПМИД 20808879 .

[9] Дж. К. Охаб; З. Бурда (январь 2013 г.). «Случайное блуждание с максимальной энтропией при обнаружении сообществ». Специальные темы Европейского физического журнала . 216 : 73–81. arXiv : 1208.3688 . Бибкод : 2013EPJST.216...73O . doi : 10.1140/epjst/e2013-01730-6 . S2CID 56409069 .

[10] Беральди, Роберто (апрель 2009 г.). «Смещенные случайные блуждания в однородных беспроводных сетях». Транзакции IEEE на мобильных компьютерах . 8 (4): 500–513. дои : 10.1109/TMC.2008.151 . S2CID 13521325 .

[11] Да-Чэн Не; Цзы-Ке Чжан; Цян Донг; Чунцзин Сунь; Ян Фу (июль 2014 г.). «Фильтрация информации посредством смещенного случайного блуждания в связанной социальной сети» . Научный мировой журнал . 2014 : 829137. doi : 10.1155/2014/829137 . ПМЦ 4132410 . ПМИД 25147867 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]