Расчет SimRank с помощью NetworkX?

Question

Мне было интересно, как мы можем использовать модуль python networkX для реализации SimRank для сравнения подобия 2 узлов? Я понимаю, что networkX предоставляет методы поиска соседей и алгоритмы анализа ссылок, такие как PageRank и HITS, но есть ли для SimRank?

Примеры, учебные пособия тоже приветствуются!

Answer 1

Обновление Я реализовал библиотеку 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) 

Вы можете получить счет сходства между двумя узлами (например, узел 'а' и узел 'б') по

>>> print s['a']['b'] 

---

SimRank является мера подобия вершин. Он вычисляет сходство между двумя узлами на графике на основе топологии, то есть узлов и связей графика. Чтобы проиллюстрировать SimRank, давайте рассмотрим следующий граф, в котором , б, с соединяются друг с другом, и д подключен к д. Как узел аналогичен узлу г, основан на том, как «с соседними узлами, б и с, похожий на д» с соседями, с.

+-------+ 
    |  | 
    a---b---c---d 

Как видно, это рекурсивный определение. Таким образом, SimRank рекурсивно вычисляется до тех пор, пока значения сходства не сходятся. Обратите внимание, что SimRank вводит константу r и представляет собой относительную важность между соседними соседями и непосредственными соседями. Формальное уравнение SimRank можно найти here.

Следующая функция принимает NetworkX граф $ G $ и относительный параметр imporance г в качестве входных данных, и возвращает значение подобия simrank сим между любыми двумя узлами в G. Возвращаемое значение sim - словарь словаря float. Чтобы получить доступ к сходству между узлом 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})}) 

Давайте проверим результат путем вычисления подобия между, скажем, узел и узел б, обозначаемый S (а, б).

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) выше.

Для получения более подробной информации, Вы можете оформить следующие бумаги:

Г. JEH и J. Видомом. SimRank: мера структурно-контекстного сходства. На KDD'02 стр. 538-543. ACM Press, 2002.

Answer 2

Нет, simrank не реализован в сетиx.

Если бы вы были, чтобы добавить это NetworkX, вы могли бы сократить код, данное user1036719 с помощью numpy и itertools:

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. ]])