import easygraph as eg from easygraph.utils import * __all__ = [ "weakTie", "weakTieLocal", ] def _computeTieStrength(G, node_u, node_v): F_u = set(G.neighbors(node=node_u)) F_u.add(node_u) F_v = set(G.neighbors(node=node_v)) F_v.add(node_v) uni = len(F_u.union(F_v)) inter = len(F_u.intersection(F_v)) S_uv = inter / uni G[node_u][node_v]["strength"] = S_uv def _computeAllTieStrength(G): for edge in G.edges: node_u = edge[0] node_v = edge[1] _computeTieStrength(G, node_u, node_v) # print(G.edges) def _strongly_connected_components(G, threshold): """Generate nodes in strongly connected components of graph with constraint threshold. Parameters ---------- G : easygraph.DiGraph A directed graph. threshold: float the edge whose tie strength is smaller than threshold will be ignored. Returns ------- comp : generator of sets A generator of sets of nodes, one for each strongly connected component of G. Examples -------- # >>> _strongly_connected_components(G, 0.2) Notes ----- Uses Tarjan's algorithm[1]_ with Nuutila's modifications[2]_. Nonrecursive version of algorithm. References ---------- .. [1] Depth-first search and linear graph algorithms, R. Tarjan SIAM Journal of Computing 1(2):146-160, (1972). .. [2] On finding the strongly connected components in a directed graph. E. Nuutila and E. Soisalon-Soinen Information Processing Letters 49(1): 9-14, (1994).. """ preorder = {} lowlink = {} scc_found = set() scc_queue = [] i = 0 # Preorder counter for source in G: if source not in scc_found: queue = [source] while queue: v = queue[-1] if v not in preorder: i = i + 1 preorder[v] = i done = True for w in G[v]: if G[v][w]["strength"] >= threshold: if w not in preorder: queue.append(w) done = False break if done: lowlink[v] = preorder[v] for w in G[v]: if G[v][w]["strength"] >= threshold: if w not in scc_found: if preorder[w] > preorder[v]: lowlink[v] = min([lowlink[v], lowlink[w]]) else: lowlink[v] = min([lowlink[v], preorder[w]]) queue.pop() if lowlink[v] == preorder[v]: scc = {v} while scc_queue and preorder[scc_queue[-1]] > preorder[v]: k = scc_queue.pop() scc.add(k) scc_found.update(scc) yield scc else: scc_queue.append(v) def _computeCloseness(G, c, u, threshold, length): n = 0 strength_sum_u = 0 for v in c: if u in G[v] and v != u: if G[v][u]["strength"] != 0: n += 1 strength_sum_u += G[v][u]["strength"] closeness_c_u = (strength_sum_u - n * threshold) / length return closeness_c_u def _computeScore(G, threshold): score_dict = {} for node in G.nodes: score_dict[node] = 0 for c in _strongly_connected_components(G, threshold): length = len(c) for u in G.nodes: closeness_c_u = _computeCloseness(G, c, u, threshold, length) if closeness_c_u < 0: score_dict[u] += (-1) * closeness_c_u return score_dict @not_implemented_for("multigraph") def weakTie(G, threshold, k): """Return top-k nodes with highest scores which were computed by WeakTie method. Parameters ---------- G: easygraph.DiGraph k: int top - k nodes with highest scores. threshold: float tie strength threshold. Returns ------- SHS_list : list The list of each nodes with highest scores. score_dict: dict The score of each node, can be used for WeakTie-Local and WeakTie-Bi. See Also ------- weakTieLocal Examples -------- # >>> SHS_list,score_dict=weakTie(G, 0.2, 3) References ---------- .. [1] Mining Brokers in Dynamic Social Networks. Chonggang Song, Wynne Hsu, Mong Li Lee. Proc. of ACM CIKM, 2015. """ _computeAllTieStrength(G) score_dict = _computeScore(G, threshold) ordered_set = sorted(score_dict.items(), key=lambda x: x[1], reverse=True) SHS_list = [] for i in range(k): SHS_list.append((ordered_set[i])[0]) print("score dict:", score_dict) print("top-k nodes:", SHS_list) return SHS_list, score_dict @not_implemented_for("multigraph") def _updateScore(u, G, threshold): score_u = 0 for c in _strongly_connected_components(G, threshold): length = len(c) closeness_c_u = _computeCloseness(G, c, u, threshold, length) if closeness_c_u < 0: score_u -= closeness_c_u return score_u def _get2hop(G, node): neighbors = [] firstlevel = {node: 1} seen = {} # level (number of hops) when seen in BFS level = 0 # the current level nextlevel = set(firstlevel) # set of nodes to check at next level n = len(G.adj) while nextlevel and level <= 2: thislevel = nextlevel # advance to next level nextlevel = set() # and start a new set (fringe) found = [] for v in thislevel: if v not in seen: seen[v] = level # set the level of vertex v found.append(v) # yield (v, level) neighbors.append(v) if len(seen) == n: return for v in found: nextlevel.update(G.adj[v]) level += 1 del seen return neighbors def _commonUpdate(G, node_u, node_v, threshold, score_dict): for node_w in G.neighbors(node=node_u): _computeTieStrength(G, node_u, node_w) for node_w in G.predecessors(node=node_u): _computeTieStrength(G, node_w, node_u) G_un = eg.Graph() for node in G.nodes: G_un.add_node(node) for edge in G.edges: if not G_un.has_edge(edge[0], edge[1]): G_un.add_edge(edge[0], edge[1]) u_2hop = _get2hop(G_un, node_u) G_u = G.nodes_subgraph(from_nodes=u_2hop) v_2hop = _get2hop(G_un, node_v) G_v = G.nodes_subgraph(from_nodes=v_2hop) score_u = _updateScore(node_u, G_u, threshold) score_v = _updateScore(node_v, G_v, threshold) score_dict[node_u] = score_u score_dict[node_v] = score_v all_neigh_u = list(set(G.all_neighbors(node=node_u))) # print("all_neigh:",all_neigh_u) all_neigh_v = list(set(G.all_neighbors(node=node_v))) for node_w in all_neigh_u: if node_w in all_neigh_v: w_2hop = _get2hop(G_un, node_w) G_w = G.nodes_subgraph(from_nodes=w_2hop) score_w = _updateScore(node_w, G_w, threshold) else: score_w = 0 w_2hop = _get2hop(G_un, node_w) G_w = G.nodes_subgraph(from_nodes=w_2hop) for c in _strongly_connected_components(G_w, threshold): if node_u in c: length = len(c) closeness_c_w = _computeCloseness(G, c, node_w, threshold, length) if closeness_c_w < 0: score_w -= closeness_c_w score_dict[node_w] = score_w def weakTieLocal(G, edges_plus, edges_delete, threshold, score_dict, k): """Find brokers in evolving social networks, utilize the 2-hop neighborhood of an affected node to identify brokers. Parameters ---------- G: easygraph.DiGraph edges_plus: list of list set of edges to be added edges_delete: list of list set of edges to be removed threshold: float tie strength threshold. score_dict: dict The score of each node computed before. k: int top - k nodes with highest scores. Returns ------- SHS_list : list The list of each nodes with highest scores. See Also ------- weakTie Examples -------- # >>> SHS_list=weakTieLocal(G, [[2, 7]], [[1,3]], 0.2, score_dict, 3) References ---------- .. [1] Mining Brokers in Dynamic Social Networks. Chonggang Song, Wynne Hsu, Mong Li Lee. Proc. of ACM CIKM, 2015. """ for edge in edges_plus: G.add_edge(edge[0], edge[1]) _computeTieStrength(G, edge[0], edge[1]) _commonUpdate(G, edge[0], edge[1], threshold, score_dict) for edge in edges_delete: G.remove_edge(edge[0], edge[1]) _commonUpdate(G, edge[0], edge[1], threshold, score_dict) ordered_set = sorted(score_dict.items(), key=lambda x: x[1], reverse=True) SHS_list = [] for i in range(k): SHS_list.append((ordered_set[i])[0]) print("updated score:", score_dict) print("top-k nodes:", SHS_list) return SHS_list if __name__ == "__main__": G = eg.DiGraph() G.add_edge(1, 5) G.add_edge(1, 4) G.add_edge(2, 1) G.add_edge(2, 6) G.add_edge(2, 9) G.add_edge(3, 4) G.add_edge(3, 1) G.add_edge(4, 3) G.add_edge(4, 1) G.add_edge(4, 5) G.add_edge(5, 4) G.add_edge(5, 8) G.add_edge(6, 1) G.add_edge(6, 2) G.add_edge(7, 2) G.add_edge(7, 3) G.add_edge(7, 10) G.add_edge(8, 4) G.add_edge(8, 5) G.add_edge(9, 6) G.add_edge(9, 10) G.add_edge(10, 7) G.add_edge(10, 9) SHS_list, score_dict = weakTie(G, 0.2, 3) SHS_list = weakTieLocal(G, [[2, 7]], [[2, 7]], 0.2, score_dict, 3)