我想知道如何使用Python模块
欢迎提供示例和教程！
networkX来实现SimRank以比较两个节点的相似度？我知道networkX提供了查看邻居和链接分析算法（如PageRank和HITS）的方法，但是否有一种方法可以用于SimRank？欢迎提供示例和教程！
2个回答
16
更新： 我实现了一个名为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']
+-------+
| |
a---b---c---d
如上所述，这是一个递归定义。因此，SimRank将递归计算直到相似度值收敛。注意，SimRank引入了一个常数r来表示间接邻居和直接邻居之间的相对重要性。SimRank的正式方程可以在此处找到。
以下函数接受一个networkx图形$G$和相对重要性参数r作为输入，并返回G中任意两个节点之间的simrank相似度值sim。返回值sim是一个包含浮点数字典的字典。要访问图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 Press，2002年。
- user1036719
4
1这个实现不够准确。SimRank算法在有向图上运行，并且只考虑前驱节点的边。 - Yuval Atzmon
我相信无向图可以被看作是双向图。 :) - user1036719
@user1036719，请您能否进一步解释您的评论。我认为关键在于SimRank应该在有向图上运行，但是当前实现并非如此。我不认为您可以将有向图转换为无向图并正确地运行算法。 - Andrew
明白了。实际上，我们无法将有向图转换为无向图。但是，由于我们可以将无向图视为双向图，因此SimRank可以在无向图上运行。因此，如果您处理的是无向图，则上述脚本可以正常工作。然而，正如@user2476373指出的那样，使用G.predecessors()是更好（更通用）的方法。 - user1036719
8
不，networkx中没有实现simrank。
如果您想将其添加到networkx中，可以使用numpy和itertools缩短user1036719提供的代码：
def simrank(G, r=0.8, max_iter=100, eps=1e-4):
nodes = G.nodes()
nodes_i = {k: v for(k, v) in [(nodes[i], i) for i in range(0, len(nodes))]}
sim_prev = numpy.zeros(len(nodes))
sim = numpy.identity(len(nodes))
for i in range(max_iter):
if numpy.allclose(sim, sim_prev, atol=eps):
break
sim_prev = numpy.copy(sim)
for u, v in itertools.product(nodes, nodes):
if u is v:
continue
u_ns, v_ns = G.predecessors(u), G.predecessors(v)
# evaluating the similarity of current iteration nodes pair
if len(u_ns) == 0 or len(v_ns) == 0:
# if a node has no predecessors then setting similarity to zero
sim[nodes_i[u]][nodes_i[v]] = 0
else:
s_uv = sum([sim_prev[nodes_i[u_n]][nodes_i[v_n]] for u_n, v_n in itertools.product(u_ns, v_ns)])
sim[nodes_i[u]][nodes_i[v]] = (r * s_uv) / (len(u_ns) * len(v_ns))
return sim
然后，以SimRank论文中的玩具示例（大学图）为例，重现了论文结果：
G = networkx.DiGraph()
G.add_edges_from([('1','2'), ('1', '4'), ('2','3'), ('3','1'), ('4', '5'), ('5', '4')])
pprint(simrank(G).round(3))
输出如下：
array([[ 1. , 0. , 0. , 0.034, 0.132],
[ 0. , 1. , 0. , 0.331, 0.042],
[ 0. , 0. , 1. , 0.106, 0.414],
[ 0.034, 0.331, 0.106, 1. , 0.088],
[ 0.132, 0.042, 0.414, 0.088, 1. ]])
- Jon
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接