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

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

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

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

• 1 Модель
• 2 Приложения
• 3 См. Также
• 4 Ссылки
• 5 Внешние ссылки

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

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

$T\; ij\; \alpha \; =\; \alpha \; i\; A\; ij\; \sum \; k\; \alpha \; k\; A\; kj,\; \{\backslash \; displaystyle\; T\_\; \{ij\}\; ^\; \{\backslash \; alpha\}\; =\; \{\backslash \; frac\; \{\backslash \; alpha\; \_\; \{i\}\; A\_\; \{ij\}\}\; \{\backslash \; sum\; \_\; \{k\}\; \backslash \; alpha\; \_\; \{k\}\; A\_\; \{kj\}\}\},\}$

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

Фактически, шаги пешехода смещены на коэффициент $\alpha \; \{\backslash \; displaystyle\; \backslash \; alpha\}$, который может отличаться от одного узла к другому.

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

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

$C\; (i)\; =\; Общее\; количество\; кратчайших\; путей\; через\; i\; Общее\; количество\; кратчайших\; путей\; \{\backslash \; displaystyle\; C\; (i)\; =\; \{\backslash \; tfrac\; \{\{\backslash \; text\; \{Общее\; количество\; кратчайших\; путей\; через\}\}\; i\}\; \{\backslash \; text\; \{Общее\; количество\; кратчайших\; путей\}\}\}\}$

Основываясь на приведенном выше уравнении, время повторения до узла в смещенной прогулка определяется следующим образом:

$ri\; =\; 1\; C\; (i)\; \{\backslash \; displaystyle\; r\_\; \{i\}\; =\; \{\backslash \; frac\; \{1\}\; \{C\; (i)\}\}\}$

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

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

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