python - 使用 NetworkX 计算 SimRank？

Question

我想知道我们如何使用 python 模块 networkX 来实现 SimRank比较2个节点的相似度？我知道 networkX 提供了查看邻居的方法，以及链接分析算法(例如 PageRank 和 HITS)，但是有用于 SimRank 的方法吗？

示例，教程也欢迎!

Answer 1

更新我实现了一个 networkx_addon 库。 SimRank 包含在库中。查看:https://github.com/hhchen1105/networkx_addon了解详情。

示例用法:

    >>> import networkx
    >>> import networkx_addon
    >>> G = networkx.Graph()
    >>> G.add_edges_from([('a','b'), ('b','c'), ('a','c'), ('c','d')])
    >>> s = networkx_addon.similarity.simrank(G)

您可以通过以下方式获得两个节点(例如，节点“a”和节点“b”)之间的相似度得分

    >>> print s['a']['b']

---

SimRank 是一种顶点相似性度量。它基于拓扑计算图上两个节点之间的相似度，即图的节点和链接。为了说明 SimRank，让我们考虑下图，其中 a、b、c 相互连接，d 连接到 d。节点a与节点d的相似程度取决于a的邻居节点b和c，类似于d的邻居c。

    +-------+
    |       |
    a---b---c---d

正如所见，这是一个递归定义。因此，递归计算 SimRank，直到相似度值收敛。请注意，SimRank 引入了一个常量 r 来表示间接邻居和直接邻居之间的相对重要性。可以找到 SimRank 的形式方程 here .

以下函数以networkx图$G$和相对重要性参数r为输入，返回中任意两个节点之间的simrank相似度值sim>G。返回值sim 是一个float 字典的字典。要访问图 G 中节点 a 和节点 b 之间的相似性，可以简单地访问 sim[a][b]。

    def simrank(G, r=0.9, max_iter=100):
      # init. vars
      sim_old = defaultdict(list)
      sim = defaultdict(list)
      for n in G.nodes():
        sim[n] = defaultdict(int)
        sim[n][n] = 1
        sim_old[n] = defaultdict(int)
        sim_old[n][n] = 0

      # recursively calculate simrank
      for iter_ctr in range(max_iter):
        if _is_converge(sim, sim_old):
          break
        sim_old = copy.deepcopy(sim)
        for u in G.nodes():
          for v in G.nodes():
            if u == v:
              continue
            s_uv = 0.0
            for n_u in G.neighbors(u):
              for n_v in G.neighbors(v):
                s_uv += sim_old[n_u][n_v]
            sim[u][v] = (r * s_uv / (len(G.neighbors(u)) * len(G.neighbors(v))))
      return sim

    def _is_converge(s1, s2, eps=1e-4):
      for i in s1.keys():
        for j in s1[i].keys():
          if abs(s1[i][j] - s2[i][j]) >= eps:
            return False
      return True

要计算上图中节点之间的相似度值，你可以试试这个。

    >> G = networkx.Graph()
    >> G.add_edges_from([('a','b'), ('b', 'c'), ('c','a'), ('c','d')])
    >> simrank(G)

你会得到

    defaultdict(<type 'list'>, {'a': defaultdict(<type 'int'>, {'a': 0, 'c': 0.62607626807407868, 'b': 0.65379221101693585, 'd': 0.7317028881451203}), 'c': defaultdict(<type 'int'>, {'a': 0.62607626807407868, 'c': 0, 'b': 0.62607626807407868, 'd': 0.53653543888775579}), 'b': defaultdict(<type 'int'>, {'a': 0.65379221101693585, 'c': 0.62607626807407868, 'b': 0, 'd': 0.73170288814512019}), 'd': defaultdict(<type 'int'>, {'a': 0.73170288814512019, 'c': 0.53653543888775579, 'b': 0.73170288814512019, 'd': 0})})

让我们通过计算节点 a 和节点 b 之间的相似性来验证结果，用 S(a,b) 表示。

S(a,b) = r * (S(b,a)+S(b,c)+S(c,a)+S(c,c))/(2*2) = 0.9 * (0.6538+0.6261+0.6261+1)/4 = 0.6538,

这与我们上面计算的 S(a,b) 相同。

有关更多详细信息，您可能需要查看以下论文:

G. Jeh 和 J. Widom。 SimRank:结构上下文相似性的度量。在 KDD'02 第 538-543 页。 ACM 出版社, 2002.