NetworkXを使用してSimRankを計算しますか？

Question

私はnetworkXを実装して、2ノードの類似性を比較するためにSimRankを実装するにはどうすればいいですか？私は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) 

あなたは2つのノード間の類似度スコアを得ることができる（例えば、 '' とノード 'B' ノード）

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

---

SimRankによってです頂点類似性測度。これは、トポロジー、すなわちグラフのノードおよびリンクに基づいて、グラフ上の2つのノード間の類似性を計算する。 SimRankを説明するために、のは、B、Cが互いに接続された次のグラフを考えると、DはDに接続されています。ノードはノードDに似ている方法に基づいており、どのようの隣接ノード、Dに似BとC、隣人、C。見られるように

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

、これは再帰的定義です。したがって、SimRankは類似値が収束するまで再帰的に計算される。 SimRankは、直接的な近隣者と直接的な近隣者との間の相対的な重要性を表す定数rを導入することに留意されたい。 SimRankの形式式はhereです。

次の関数は、入力としてR networkxグラフ$ G $と相対imporanceパラメータを受け取り、Gにおける任意の2つのノード間simrank類似値シムを返します。戻り値simはfloatの辞書です。ノードとノード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（a、b）はで示される、ノードとノードB、たとえば、間の類似度を計算して、結果を検証してみましょう取得します。 （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.

Answer 2

いいえ、simrankはnetworkxに実装されていません。

あなたはnetworkxにこれを追加した場合、あなたはnumpyとitertoolsを使用してuser1036719によって与えられたコード短縮できますSimRank紙（大学グラフ）からおもちゃの例を取っ​​て、その後

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 

を再生紙の結果：

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