नेटवर्कएक्स का उपयोग कर सिम्रैंक की गणना करना?

Question

मैं सोच रहा था कि 212 नोड्स की समानता की तुलना करने के लिए SimRank को लागू करने के लिए हम पाइथन मॉड्यूल networkX का उपयोग कैसे कर सकते हैं? मैं समझता हूं कि networkX पड़ोसियों को देखने के लिए विधियों और पेजरैंक और एचआईटीएस जैसे विश्लेषण विश्लेषण एल्गोरिदम प्रदान करता है, लेकिन क्या सिमरैंक के लिए कोई है?

उदाहरण, ट्यूटोरियल का भी स्वागत है!

Answer 1

अद्यतन मैंने एक नेटवर्क x_addon लाइब्रेरी लागू की। पुस्तकालय में सिमरेक शामिल है। विवरण के लिए देखें: 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 कर रहा है:

नमूना प्रयोग vertex समानता उपाय। यह टोपोलॉजी, यानी, नोड्स और ग्राफ के लिंक के आधार पर ग्राफ पर दो नोड्स के बीच समानता की गणना करता है। SimRank समझने के लिए, निम्नलिखित ग्राफ, जिसमें एक, ख, ग एक दूसरे से कनेक्ट पर विचार करते हैं, और घ को घ जुड़ा हुआ है। कैसे एक नोड एक एक नोड घ के समान है, पर आधारित है कैसे एक के पड़ोसी नोड्स, ख और ग, घ के लिए इसी तरह के पड़ोसियों, ग।

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

के रूप में देखा है, यह एक पुनरावर्ती परिभाषा है। इस प्रकार, समानता मूल्यों को एकत्रित होने तक सिमरैंक को फिर से गणना की जाती है। ध्यान दें कि सिम्रैंक प्रत्यक्ष-पड़ोसियों और प्रत्यक्ष पड़ोसियों के बीच सापेक्ष महत्व का प्रतिनिधित्व करने के लिए स्थिर r प्रस्तुत करता है। सिमरैंक का औपचारिक समीकरण here पाया जा सकता है।

निम्नलिखित समारोह एक networkx ग्राफ $ जी $ और रिश्तेदार imporance पैरामीटर आर लेता इनपुट के रूप में, और simrank समानता मूल्य सिम में किसी भी दो नोड्स के बीच जी देता है। वापसी मूल्य सिम फ्लोट के शब्दकोश का एक शब्दकोश है। ग्राफ़ जी में नोड और नोड बी के बीच समानता तक पहुंचने के लिए, कोई आसानी से सिम [ए] [बी] तक पहुंच सकता है।

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

के बीच, कहते हैं, नोड एक और नोड ख समानता की गणना के द्वारा परिणाम की पुष्टि, एस (ए, बी) से दर्शाया जाता है चलो मिल जाएगा।

एस (ए, बी) = आर * (एस (बी, ए) + एस (बी, सी) + एस (सी, ए) + एस (सी, सी))/(2 * 2) = 0.9 * (0.6538 + 0.6261 + 0.6261 + 1)/4 = 0.6538,

जो हमारे गणना एस (ए, बी) जैसा ही है।

जी जे और जे Widom:

अधिक जानकारी के लिए, आप निम्न कागज चेकआउट कर सकते हैं। सिमरैंक: संरचनात्मक संदर्भ समानता का एक उपाय। केडीडी 02 पेज 538-543 में। एसीएम प्रेस, 2002.

Answer 2

नहीं, सिमक्रैंक नेटवर्कक्स में लागू नहीं किया गया है।

आप इस जोड़ने के लिए networkx के लिए गए थे, तो आप numpy और itertools का उपयोग करके user1036719 द्वारा दिए गए कोड को छोटा कर सकते हैं:

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 कागज से खिलौना उदाहरण ले, reproduces कागज परिणाम:

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