PageRank с пользовательскими начальными баллами - PullRequest
Новая
       58

PageRank с пользовательскими начальными баллами

1 голос
/ 20 июня 2019

Я пытаюсь реализовать простой алгоритм, который будет вычислять PageRank в целевой сети, сгенерированной и обработанной с помощью NetworkX. Однако я хотел бы добавить простое изменение: вместо того, чтобы начальный PageRank для каждого узла был равен 1 / n, где n - количество узлов в графе, я хочу, чтобы каждый узел имел ранг 1.

До сих пор я пытался проверить официальную документацию на PageRank, но я не нашел ничего, что могло бы помочь. Видимо, параметр 'personalization' также бесполезен. Я пытался использовать nstart, но безрезультатно. Код в настоящее время выглядит так: 

import networkx as nx

D=nx.DiGraph()
D.add_weighted_edges_from([('1','2',0.5),('1','3',0.5)])
nst = {n: 1 for n in D.nodes}

print(nx.pagerank(D, alpha = 0.95, nstart=nst))

В настоящее время ранги, присвоенные каждому узлу в конце расчета, по-прежнему составляют до 1, в то время как они должны составлять до 3.

Возможно ли с самого начала такое сделать? Должен ли я искать в другом месте для реализации такого алгоритма? Могут ли быть проблемы с конвергенцией, если такое изменение применяется? Заранее спасибо.

1 Ответ

0 голосов
/ 20 июня 2019

PageRank в сети x имеет атрибут nstart :

nstart (словарь, необязательно) - начальное значение итерации PageRank для каждого узла.

Вот исходный код для этого: 

    # Choose fixed starting vector if not given
    if nstart is None:
        x = dict.fromkeys(W, 1.0 / N)
    else:
        # Normalized nstart vector
        s = float(sum(nstart.values()))
        x = dict((k, v / s) for k, v in nstart.items())

Вы можете просто указать nstart в своем коде, например: 

nst = {n: 1 for n in G.nodes}
pr = nx.pagerank(G, nstart=nst)

Редактировать 1: Современный алгоритм PageRank принудительно нормализует начальный вектор (вы можете увидеть это в коде выше). Весь алгоритм основан на нем, и если заставить значения nstart быть 1, а не 1/N, он будет нарушен из-за сходимости:

enter image description here

никогда не предполагается (e увеличивает каждую итерацию). Если вы хотите использовать 1 в качестве начальных значений, как в оригинальном алгоритме PageRank:

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

Вы должны реализовать весь алгоритм вручную, потому что он устарел.

...