Efficient рagerank tracking in evolving networks

1.

Efficient PageRank Tracking in
Evolving Networks
Алмаз Насибуллин

2.

План
Задача
Предложенный алгоритм
Сравнительный анализ
–
Теоретическое сравнение
–
Эксперимент
Алмаз Насибуллин

3.

Задача
Подсчет важности каждой вершины в
режиме реального времени
Personalized PageRank
Алмаз Насибуллин

4.

Метрики качества
Время работы алгоритма
Точность решения
Пространственная сложность
Алмаз Насибуллин

5.

Актуальность задачи
Громадные сети
Быстрое развитие сетей
Таблица 1: Развитие крупных сетей Интернет, 1.11.2014.
Алмаз Насибуллин

6.

Personalized PageRank(PPR)
- не взвешенный ориентированный граф
- матрица переходов
- вектор предпочтений, причем
- фактор ослабления(
и
)
Алмаз Насибуллин

7.

Метод Gauss–Southwell
✔
✔
-?
,
➔
Алмаз Насибуллин

8.

Метод Gauss–Southwell
Алмаз Насибуллин

9.

Алмаз Насибуллин

10.

Алмаз Насибуллин