Предвзятое случайное блуждание по графику - Biased random walk on a graph

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

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

Модель

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

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

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

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

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

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

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

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

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

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

Приложения

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

Смотрите также

• Центральность посредничества
• Структура сообщества
• Дивергенция Кульбака – Лейблера
• Цепь Маркова
• Случайное блуждание с максимальной энтропией
• Центральность близости случайного блуждания
• Анализ социальных сетей
• Проблема коммивояжера

Рекомендации

1. Роберта Синатра, Хесус Гомес-Гарденьес, Рено Ламбьот, Винченцо Никосия и Вито Латора (март 2011 г.). «Максимально-энтропийные случайные блуждания в сложных сетях с ограниченной информацией». Физический обзор E. 83 (3): 030103. arXiv:1007.4936. Bibcode:2011PhRvE..83c0103S. Дои:10.1103 / PhysRevE.83.030103. PMID  21517435.
2. Х. Гомес-Гарденьес; В. Латора (декабрь 2008 г.). «Скорость энтропии диффузионных процессов на сложных сетях». Физический обзор E. 78 (6): 065102. arXiv:0712.0278. Bibcode:2008PhRvE..78f5102G. Дои:10.1103 / PhysRevE.78.065102. PMID  19256892.
3. Р. Ламбьотт, Р. Синатра, Ж.-К. Дельвенн, Т. Эванс, М. Бараона, В. Латора (декабрь 2010 г.). «Потоковые графы: динамика и структура переплетения». Физический обзор E. 84 (1): 017102. arXiv:1012.1211. Bibcode:2011PhRvE..84a7102L. Дои:10.1103 / PhysRevE.84.017102. PMID  21867345.
4. Бланшар, Волченков, Д (2008). Математический анализ городских пространственных сетей. Понимание сложных систем. Дои:10.1007/978-3-540-87829-2. ISBN  978-3-540-87828-5.
5. Волченков Д; Бланшар П. (2011). Справедливые и необъективные случайные блуждания по неориентированным графам и родственным энтропиям. Birkhäuser. п. 380. ISBN  9780817649036.
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.
7. Адал, К.М. (июнь 2010 г.). «Маршрутизация на основе предвзятого случайного блуждания для мобильных одноранговых сетей». 2010 Международная конференция по интеллектуальным и перспективным системам. С. 1–6. Дои:10.1109 / ICIAS.2010.5716181. ISBN  978-1-4244-6623-8.
8. Какаджан Комуров, Майкл А. Уайт, Прахлад Т. Рам (август 2010 г.). «Использование случайных блужданий на основе данных на графах для извлечения контекстно-зависимых сетей из геномных данных». PLOS Comput Biol. 6 (8): e1000889. Bibcode:2010PLSCB ... 6E0889K. Дои:10.1371 / journal.pcbi.1000889. ЧВК  2924243. PMID  20808879.
9. J.K. Охаб; З. Бурда (январь 2013 г.). «Максимальное случайное блуждание энтропии в обнаружении сообщества». Специальные темы Европейского физического журнала. 216: 73–81. arXiv:1208.3688. Bibcode:2013EPJST.216 ... 73O. Дои:10.1140 / epjst / e2013-01730-6.
10. Беральди, Роберто (апрель 2009 г.). «Предвзятые случайные блуждания в однородных беспроводных сетях». IEEE Transactions по мобильным вычислениям. 8 (4): 500–513. Дои:10.1109 / TMC.2008.151.
11. Да-Ченг Не, Цзы-Кэ Чжан, Цян Донг, Чунцзин Сунь, Ян Фу (июль 2014 г.). «Фильтрация информации с помощью предвзятого случайного блуждания в связанной социальной сети». Научный мировой журнал. 2014: 829137. Дои:10.1155/2014/829137. ЧВК  4132410. PMID  25147867.

внешняя ссылка

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