如何在python中实现带重启的随机游动

Question

我使用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中找不到它的实现

请告诉我是否有用于random walk with restarts执行此操作的python库/代码

如果需要，我很乐意提供更多细节

编辑

如果我的现有网络按如下方式加权，我是否仍会按如下方式计算重新启动时的随机游动：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),
])

Answer 1

个性化PageRank-implemented in networkx-本质上是一个随机游动，如果个性化向量的起始节点为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参数，您可以在其中设置要使用的边数据键。当使用^{}添加边时，此数据键称为"weight"，因此代码如下所示

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