Aggiornamento Ho implementato una libreria networkx_addon. SimRank è incluso nella libreria. Check out: https://github.com/hhchen1105/networkx_addon per i dettagli.
campione Uso:
>>> 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)
È possibile ottenere il punteggio di somiglianza tra due nodi (ad esempio, il nodo 'a' e il nodo 'b') di
>>> print s['a']['b']
SimRank è un misura di somiglianza del vertice. Calcola la somiglianza tra due nodi su un grafico basato sulla topologia, cioè i nodi e i collegamenti del grafico. Per illustrare SimRank, consideriamo il grafico seguente, in cui un , b, c si connettono tra loro, e d è collegato ad d. Come un nodo un è simile ad un nodo d, è basato su come un 's nodi vicini, b e c, simile a d' s vicini, c.
+-------+
| |
a---b---c---d
Come si vede, si tratta di un ricorsiva definizione . Pertanto, SimRank viene calcolato in modo ricorsivo finché i valori di similarità non convergono. Si noti che SimRank introduce una costante r per rappresentare l'importanza relativa tra vicini in-direct e vicini diretti. L'equazione formale di SimRank può essere trovata here.
La seguente funzione prende un grafo NetworkX $ G $ e il parametro relativo imporance r come input e restituisce il valore di similarità simrank sim tra due nodi in G. Il valore restituito sim è un dizionario del dizionario di float. Per accedere alla somiglianza tra il nodo a e il nodo b nel grafico G, è sufficiente accedere 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
per calcolare i valori di similarità tra i nodi nel grafico qui sopra, si può provare questo.
>> G = networkx.Graph()
>> G.add_edges_from([('a','b'), ('b', 'c'), ('c','a'), ('c','d')])
>> simrank(G)
Otterrete
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})})
Diamo verificare il risultato calcolando somiglianza tra, ad esempio, il nodo un e il nodo b, indicato con 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,
che è la stessa dei nostri calcolati S (a, b) sopra.
Per maggiori dettagli, si può decidere di checkout il seguente documento:
G. Jeh e J. Widom. SimRank: una misura della somiglianza al contesto strutturale. In KDD'02 pagine 538-543. ACM Press, 2002.
Questa implementazione non è accurata. L'algoritmo SimRank gira su grafici diretti e considera solo i bordi dei nodi precedenti. – yuval
Credo che un grafico non orientato possa essere considerato come un grafico "bi-diretto". :) – user1036719
@ user1036719 per favore potresti spiegare ulteriormente il tuo commento. Penso che il punto sia che SimRank dovrebbe funzionare su grafici diretti e come implementato no. Non credo che sia possibile convertire un grafico diretto in un grafico non orientato ed eseguire correttamente l'algoritmo. – Andrew