Memory efficient DevRank using scipy.sparse
(G, count_self=False, alpha=0.85, epsilon=1e-5, max_iters=300)
| 4 | |
| 5 | |
| 6 | def devrank(G, count_self=False, alpha=0.85, epsilon=1e-5, max_iters=300): |
| 7 | """Memory efficient DevRank using scipy.sparse""" |
| 8 | ni = {} |
| 9 | for i, u in enumerate(G): |
| 10 | ni[u] = i |
| 11 | |
| 12 | def sizeof(u): |
| 13 | return G.node[u]['num_lines'] |
| 14 | |
| 15 | num_nodes = len(G.nodes()) |
| 16 | row, col, data = [], [], [] |
| 17 | for u in G: |
| 18 | num_out_edges = len(G[u]) |
| 19 | if num_out_edges > 0: |
| 20 | total_out_sizes = 0 |
| 21 | for v in G[u]: |
| 22 | total_out_sizes += sizeof(v) |
| 23 | if count_self: |
| 24 | total_out_sizes += sizeof(u) |
| 25 | row.append(ni[u]) |
| 26 | col.append(ni[u]) |
| 27 | data.append(sizeof(u) / total_out_sizes) |
| 28 | for v in G[u]: |
| 29 | row.append(ni[v]) |
| 30 | col.append(ni[u]) |
| 31 | data.append(sizeof(v) / total_out_sizes) |
| 32 | |
| 33 | P = coo_matrix((data, (row, col)), shape=(num_nodes, num_nodes)).tocsr() |
| 34 | |
| 35 | universe_size = 0 |
| 36 | for u in G: |
| 37 | universe_size += sizeof(u) |
| 38 | |
| 39 | p = np.empty(num_nodes) |
| 40 | for u in G: |
| 41 | p[ni[u]] = sizeof(u) / universe_size |
| 42 | |
| 43 | v = np.ones(num_nodes) / num_nodes |
| 44 | |
| 45 | for i in range(max_iters): |
| 46 | new_v = alpha * P.dot(v) |
| 47 | gamma = LA.norm(v, 1) - LA.norm(new_v, 1) |
| 48 | new_v += gamma * p |
| 49 | delta = LA.norm(new_v - v, 1) |
| 50 | if delta < epsilon: |
| 51 | break |
| 52 | v = new_v |
| 53 | |
| 54 | pr = {} |
| 55 | for u in G: |
| 56 | pr[u] = v[ni[u]] |
| 57 | |
| 58 | return pr |