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] 中定义。

Parameters:
GNetworkX 图

一个 NetworkX 图

source节点

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

target节点

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

importance_factor浮点数

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

max_iterations整数

最大迭代次数。

tolerance浮点数

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

Returns:
similarity字典或浮点数

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

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

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

Raises:
ExceededMaxIterations

如果算法在 max_iterations 内未收敛。

NodeNotFound

如果 source 或 target 不在 G 中。

References

[2]

G. Jeh 和 J. Widom. “SimRank: a measure of structural-context similarity”, In KDD’02: Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 538–543. ACM Press, 2002.

Examples

>>> 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.])
On this page