Tính SimRank bằng NetworkX?

Question

Tôi đã tự hỏi làm thế nào chúng ta có thể sử dụng mô-đun python networkX để thực hiện SimRank để so sánh sự giống nhau của 2 nút? Tôi hiểu rằng networkX cung cấp các phương pháp để xem hàng xóm và các thuật toán phân tích liên kết như PageRank và HITS, nhưng có một phương pháp cho SimRank không?

Ví dụ, hướng dẫn cũng được hoan nghênh!

Answer 1

Cập nhật Tôi đã triển khai thư viện networkx_addon. SimRank được đưa vào thư viện. Kiểm tra: https://github.com/hhchen1105/networkx_addon để biết chi tiết.

Sample Cách sử dụng:

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

Bạn có thể có được số điểm tương đồng giữa hai nút (ví dụ nút 'a' và nút 'b') bởi

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

---

SimRank là một biện pháp tương tự đỉnh. Nó tính toán sự giống nhau giữa hai nút trên biểu đồ dựa trên cấu trúc liên kết, tức là các nút và các liên kết của biểu đồ. Để minh họa SimRank, chúng ta hãy xem xét đồ thị dưới đây, trong đó một, b, c kết nối với nhau, và d được kết nối với d. Làm thế nào một nút một cũng tương tự như một nút d, được dựa trên cách một 's nút hàng xóm, b và c, tương tự như d' s xóm, c.

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

Như đã thấy, đây là một đệ quy nét . Do đó, SimRank được tính toán đệ quy cho đến khi các giá trị tương đồng hội tụ. Lưu ý rằng SimRank giới thiệu một hằng số r để thể hiện tầm quan trọng tương đối giữa những người hàng xóm trực tiếp và hàng xóm trực tiếp. Phương trình chính thức của SimRank có thể được tìm thấy here.

Hàm ở phía dưới có một đồ thị $ networkx G và tham số imporance tương r $ như đầu vào, và trả về giá trị tương đồng simrank sim giữa bất kỳ hai nút trong G. Giá trị trả về sim là từ điển của từ điển nổi. Để truy cập điểm giống nhau giữa nút a và nút b trong biểu đồ G, bạn chỉ cần truy cập vào 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 

Để tính giá trị tương tự giữa các nút trong biểu đồ trên, bạn có thể thử điều này.

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

Bạn sẽ nhận được

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

Hãy kiểm tra kết quả bằng cách tính toán sự tương đồng giữa, nói rằng, nút một và nút b, biểu hiện bằng 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,

giống như được tính S (a, b) ở trên.

Để biết thêm chi tiết, bạn có thể muốn kiểm tra giấy sau:

G. Jeh và J. Widom. SimRank: một thước đo về sự tương đồng về cấu trúc-bối cảnh. Trong KDD'02 trang 538-543. Báo chí ACM, 2002.

Answer 2

Không, simrank không được triển khai trong networkx.

Nếu bạn đã thêm video này vào networkx, bạn có thể rút ngắn mã do user1036719 bằng cách sử dụng numpy và 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 

Sau đó, lấy ví dụ đồ chơi từ giấy SimRank (ĐH graph), Tái tạo kết quả giấy:

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

những kết quả đầu ra:

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