Calculando SimRank usando NetworkX?

Question

Me preguntaba cómo podemos usar el módulo python networkX para implementar SimRank para comparar la similitud de 2 nodos? Entiendo que networkX proporciona métodos para buscar vecinos y algoritmos de análisis de enlaces como PageRank y HITS, pero ¿hay uno para SimRank?

¡Ejemplos, tutoriales también son bienvenidos!

Answer 1

Actualización Implementé una biblioteca networkx_addon. SimRank está incluido en la biblioteca. Consulte: https://github.com/hhchen1105/networkx_addon para más detalles.

Uso de la muestra:

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

Usted puede obtener la puntuación de similitud entre dos nodos (por ejemplo, nodo 'a' y el nodo 'b') por

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

---

SimRank es una medida de similitud de vértice. Calcula la similitud entre dos nodos en un gráfico basado en la topología, es decir, los nodos y los enlaces del gráfico. Para ilustrar SimRank, consideremos el siguiente gráfico, en el que un, b, c se conectan entre sí, y d está conectado a d. ¿Cómo un nodo un es similar a un nodo d, se basa en la forma de un 's nodos vecinos, b y c , similar a d' s vecinos, c.

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

Como se ve, esta es una definición recursiva. Por lo tanto, SimRank se calcula recursivamente hasta que converjan los valores de similitud. Tenga en cuenta que SimRank introduce una constante r para representar la importancia relativa entre vecinos directos y vecinos directos. La ecuación formal de SimRank se puede encontrar here.

La siguiente función toma un NetworkX gráfico $ G $ y el parámetro imporance relativa r como entrada, y devuelve el valor de similitud simrank sim entre dos nodos en G. El valor de retorno sim es un diccionario del diccionario de flotación. Para acceder a la similitud entre el nodo a y el nodo b en el gráfico G, se puede acceder simplemente a 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 

Para calcular los valores de similitud entre los nodos en el gráfico anterior, puede intentarlo.

>> G = networkx.Graph() 
    >> G.add_edges_from([('a','b'), ('b', 'c'), ('c','a'), ('c','d')]) 
    >> simrank(G) 

Usted obtendrá

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})}) 

Vamos a verificar el resultado mediante el cálculo de similitud entre, por ejemplo, el nodo un y el nodo b, denotado por 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,

que es lo mismo que nuestro calculado S (a, b) anterior.

Para más detalles, es posible que quieres descargar el siguiente documento:

G. y J. Jeh Widom. SimRank: una medida de similitud de contexto estructural. En KDD'02 páginas 538-543. ACM Press, 2002.

Answer 2

No, simrank no está implementado en networkx.

Si se va a añadir esto a NetworkX, se podría acortar el código dado por user1036719 utilizando numpy y 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 

Entonces, tomando el ejemplo de juguete del papel SimRank (gráfico de la Universidad), se reproduce los resultados de papel:

G = networkx.DiGraph() 
G.add_edges_from([('1','2'), ('1', '4'), ('2','3'), ('3','1'), ('4', '5'), ('5', '4')]) 
pprint(simrank(G).round(3)) 

que da salida:

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