Math
Випадкові блукання і PageRank
Слідкуйте за ймовірністю маси через напрямлений графік і порівняйте потужність ітерації з натовпом випадкових ходців. Телепортація може зробити PageRank збігатися до унікального розподілу. Порівняйте періодичний цикл з графіком, в якому відсутні вішаючі вершини витікають з маси.
Що відбувається
Смужки показують розподіл на поточному кроці; тонкі смужки показують ансамблі ходячих. Це не частка часу, витраченого на кожному вузлі одним ходоком. На орієнтованому циклі розподіл, концентрований в одному вузлі, продовжує циркулювати, в той час як довгострокові фракції зайнятості все ще можуть наближатися до однорідного стаціонарного розподілу.
З позитивною ймовірністю телепортації і латованими вішаними рядками, матриця переходу є стохастичної і всі вузли спілкуються: стаціонарний розподіл є унікальним і ітерації збігаються. Якщо залишити вішаний рядок порожнім, буде створено протікаючу, субстохастичну модель. Його посилання на розв’ язання тут вимкнено; це не означає, що кожен суб- стохастичний граф не має стаціонарного розподілу.
Модуль субдомінантного власного значення описує асимптотичну експоненціальну швидкість розпаду, коли відбувається конвергенція. Індивідуальні кроки можуть коливатися, і спеціальні початкові стани можуть пропускати найповільніший режим. Спробуйте використовувати точковий початок, однорідний початок і різні значення пригнічення.
Рівняння модуля
Рівняння блукання: P[i][j] = w[i][j] / (сума по j від w[i][j]); рядок із нулів - це ВИСЯЧИЙ вузол матриця Google: G = d·P + (1 − d)/n, де висячий рядок замінено рівномірним рядком стаціонарний розподіл: pi·G = pi при sum(pi) = 1; досягається степеневими ітераціями й розв'язується напряму для перевірки збіжність: похибка спадає як |lambda_2|^n, тож |lambda_2| і є швидкістю - але розмір кроку відстежує її лише в середньому, бо комплексна субдомінантна пара змушує згасання ОБЕРТАТИСЯ (середнє геометричне відношень кроків відновлює її, середнє арифметичне завищене на 1.5 %) межа згасання: |lambda_2| = d·|mu_2(P)| точно, тож |lambda_2| ≤ d є НЕРІВНІСТЮ - виміряно з точністю 5.0e-16, нещільна на множник 0.667 на малому вебі, щільна на циклі, де |mu_2| = 1 стік рангу: якщо висячий рядок залишити порожнім, повна маса спадає до нуля - ранг повністю витікає із системи періодичний: орієнтований n-цикл має за власні значення корені n-го степеня з одиниці, усі за модулем 1; зі старту в точці він повертається в цю точку кожні n кроків і ніколи не встановлюється неорієнтований: блукання оборотне, і pi - це просто степінь / 2|E| - один рядок арифметики й перевірка того, що ітерація розв'язує те, що заявляє
