Как реализовать случайные прогулки с перезапусками в python - PullRequest
Новая
       65

Как реализовать случайные прогулки с перезапусками в python

1 голос
/ 21 апреля 2020

У меня есть следующий график, который я создал с помощью networkx. 

import networkx as nx

G = nx.Graph()

G.add_nodes_from(["John", "Mary", "Jill", "Todd",
                  "iPhone5", "Kindle Fire", "Fitbit Flex Wireless", "Harry Potter", "Hobbit"])

G.add_edges_from([
    ("John", "iPhone5"),
    ("John", "Kindle Fire"),
    ("Mary", "iPhone5"),
    ("Mary", "Kindle Fire"),
    ("Mary", "Fitbit Flex Wireless"),
    ("Jill", "iPhone5"),
    ("Jill", "Kindle Fire"),
    ("Jill", "Fitbit Flex Wireless"),
    ("Todd", "Fitbit Flex Wireless"),
    ("Todd", "Harry Potter"),
    ("Todd", "Hobbit"),
])

Теперь я хочу выполнить random walk with restarts, чтобы определить наиболее похожих пользователей на John. Я искал документацию в networkx и не смог найти ее реализацию в networkx.

Пожалуйста, дайте мне знать, если есть python библиотека / код для random walk with restarts, чтобы сделать это.

Я с радостью предоставлю более подробную информацию, если это необходимо.

РЕДАКТИРОВАТЬ

Если моя существующая сеть будет иметь такой вес, как показано ниже, я все равно рассчитываю случайные обходы с перезапусками следующим образом: nx.pagerank_numpy(G, personalization={"John": 1})? 

import networkx as nx

G = nx.Graph()

G.add_nodes_from(["John", "Mary", "Jill", "Todd",
                  "iPhone5", "Kindle Fire", "Fitbit Flex Wireless", "Harry Potter", "Hobbit"])

G.add_weighted_edges_from([
    ("John", "iPhone5", 0.1),
    ("John", "Kindle Fire", 0.2),
    ("Mary", "iPhone5", 0.3),
    ("Mary", "Kindle Fire", 0.4),
    ("Mary", "Fitbit Flex Wireless", 0.5),
    ("Jill", "iPhone5", 0.9),
    ("Jill", "Kindle Fire", 0.1),
    ("Jill", "Fitbit Flex Wireless", 0.1),
    ("Todd", "Fitbit Flex Wireless", 0.1),
    ("Todd", "Harry Potter", 0.1),
    ("Todd", "Hobbit", 0.1),
])

1 Ответ

2 голосов
/ 22 апреля 2020

Персонализированный PageRank - реализован в сети x - это, по сути, случайный обход с перезапусками, если вектор персонализации имеет 1 для начального узла и 0 везде.

Следующий код 

nx.pagerank_numpy(G, personalization={"John": 1})

затем выдает словарь с вероятностями попадания в каждый узел 

{'John': 0.24958826532666656,
 'Mary': 0.1229452674202248,
 'Jill': 0.12294526742022475,
 'Todd': 0.04506174037342413,
 'iPhone5': 0.17574399763529416,
 'Kindle Fire': 0.17574399763529416,
 'Fitbit Flex Wireless': 0.08243647797726429,
 'Harry Potter': 0.012767493105803515,
 'Hobbit': 0.012767493105803515}

Из этого словаря вы можете выбрать пользователя с наибольшей вероятностью.

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

nx.pagerank_numpy(G, personalization={"John": 1}, weight="weight")
...