Mi chiedevo come è possibile utilizzare il modulo Python networkX per implementare SimRank per confrontare la somiglianza di 2 nodi? Comprendo che networkX fornisce metodi per esaminare i vicini e collegare algoritmi di analisi come PageRank e HITS, ma ce n'è uno per SimRank?Calcolo di SimRank tramite NetworkX?
Esempi, tutorial sono anche benvenuti!
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.
No, il simrank non è implementato in networkx.
Se si dovesse aggiungere questo per NetworkX, si potrebbe accorciare il codice data dal user1036719 utilizzando numpy e 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
Poi, prendendo l'esempio di giocattoli dalla carta SimRank (grafico University), riproduce i risultati carta:
G = networkx.DiGraph()
G.add_edges_from([('1','2'), ('1', '4'), ('2','3'), ('3','1'), ('4', '5'), ('5', '4')])
pprint(simrank(G).round(3))
quali uscite:
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. ]])
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