simrank_similarity#

simrank_similarity(G, source=None, target=None, importance_factor=0.9, max_iterations=1000, tolerance=0.0001)[source]#

返回图 G 中节点的 SimRank 相似度。

SimRank 是一种相似度度量，它指出“如果两个对象被相似的对象引用，则认为它们是相似的。” [1]。

论文中的伪代码定义为

def simrank(G, u, v):
    in_neighbors_u = G.predecessors(u)
    in_neighbors_v = G.predecessors(v)
    scale = C / (len(in_neighbors_u) * len(in_neighbors_v))
    return scale * sum(
        simrank(G, w, x) for w, x in product(in_neighbors_u, in_neighbors_v)
    )

其中 G 是图，u 是源节点，v 是目标节点，C 是介于 0 和 1 之间的浮点衰减因子或重要性因子。

用于确定节点相似度的 SimRank 算法定义在 [2] 中。

参数:
GNetworkX 图

一个 NetworkX 图

source节点

如果指定此参数，返回的字典会将图中的每个节点 v 映射到 source 与 v 之间的相似度。

target节点

如果同时指定了 source 和 target，则返回 source 与 target 之间的相似度值。如果指定了 target 但未指定 source，则忽略此参数。

importance_factor浮点数

间接邻居相对于直接邻居的相对重要性。

max_iterations整数

最大迭代次数。

tolerance浮点数

用于检查收敛性的误差容忍度。当算法的一次迭代发现没有相似度值变化超过此量时，算法停止。

返回:
similarity字典或浮点数

如果 source 和 target 都为 None，则返回一个字典的字典，其中键是节点对，值是该节点对的相似度。

如果 source 不为 None 但 target 为 None，则返回一个字典，将节点映射到 source 与该节点之间的相似度。

如果 source 和 target 都不为 None，则返回给定节点对的相似度值。

引发:
ExceededMaxIterations

如果算法在 max_iterations 次迭代内未收敛。

NodeNotFound

如果 source 或 target 不在 G 中。

参考文献

[2]

G. Jeh 和 J. Widom。“SimRank: 一种结构上下文相似度度量”，载于 KDD’02：第八届 ACM SIGKDD 国际知识发现与数据挖掘会议论文集，第 538–543 页。ACM Press，2002 年。

示例

>>> G = nx.cycle_graph(2)
>>> nx.simrank_similarity(G)
{0: {0: 1.0, 1: 0.0}, 1: {0: 0.0, 1: 1.0}}
>>> nx.simrank_similarity(G, source=0)
{0: 1.0, 1: 0.0}
>>> nx.simrank_similarity(G, source=0, target=0)
1.0

此函数的结果可以通过使用图的节点顺序来确定每行和每列代表哪个节点，从而转换为表示 SimRank 矩阵的 numpy 数组。其他节点排序也是可能的。

>>> import numpy as np
>>> sim = nx.simrank_similarity(G)
>>> np.array([[sim[u][v] for v in G] for u in G])
array([[1., 0.],
       [0., 1.]])
>>> sim_1d = nx.simrank_similarity(G, source=0)
>>> np.array([sim[0][v] for v in G])
array([1., 0.])
在本页上