Обновление
Я реализовал библиотеку 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 подключен до д . То, как узел a похож на узел d , основано на том, как соседние узлы a , b и c , аналогично соседям d , c .
+-------+
| |
a---b---c---d
Как видно, это рекурсивное определение. Таким образом, SimRank рекурсивно вычисляется, пока значения сходства не сходятся. Обратите внимание, что SimRank вводит константу r для представления относительной важности между прямыми соседями и прямыми соседями. Формальное уравнение SimRank можно найти здесь .
Следующая функция принимает график networkx $ G $ и параметр относительного значения r в качестве входных данных и возвращает значение сходства simrank sim между любыми двумя узлами в G . Возвращаемое значение sim - словарь словаря с плавающей точкой. Чтобы получить доступ к подобию между узлом a и узлом b в графе G , можно просто получить доступ к 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. Дже и Дж. Видом. SimRank: мера структурно-контекстного сходства. В КДД'02 страницы 538-543. ACM Press, 2002.