我想知道如何使用python模块networkX来实现SimRank来比较2个节点的相似性？我知道networkX提供了查看邻居的方法以及链接分析算法(例如PageRank和HITS)，但是SimRank是否有一种？
例子，教程也欢迎!
最佳答案
更新
我实现了networkx_addon库。 SimRank包含在库中。退房:https://github.com/hhchen1105/networkx_addon了解详细信息。
sample 用法:
>>> 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作为输入，并返回G中任意两个节点之间的simrank相似值sim。返回值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年。
关于python - 使用NetworkX计算SimRank？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9767773/