Source code for easygraph.functions.structural_holes.ICC

import easygraph as eg

from easygraph.utils import *


__all__ = ["ICC", "BICC", "AP_BICC"]


def inverse_closeness_centrality(G, v):
    c_v = sum(eg.Dijkstra(G, v).values()) / (len(G) - 1)
    return c_v


def bounded_inverse_closeness_centrality(G, v, l):
    queue = []
    queue.append(v)
    seen = set()
    seen.add(v)
    shortest_path = eg.Floyd(G)
    result = 0
    while len(queue) > 0:
        vertex = queue.pop(0)
        if shortest_path[v][vertex] == l + 1:
            break
        nodes = G.neighbors(node=vertex)
        for w in nodes:
            if w not in seen:
                queue.append(w)
                seen.add(w)
                result += shortest_path[v][w]
    return result / (len(G) - 1)


def Modified_DFS(G, u, V, time, n):
    V[u]["color"] = "black"
    time += 1
    n -= 1
    V[u]["discovered"] = time
    V[u]["lowest"] = time
    cc0 = n
    V[u]["descendant"] = 0
    root = u
    for edge in G.edges:
        u, v = edge[:2]
        if V[u]["color"] == "white":
            V[u]["color"] = "grey"
            V[v]["parent"] = u
            V[u]["child"] += 1
            V, time, n = Modified_DFS(G, v, V, time, n)
            V[u]["descendant"] = V[u]["descendant"] + V[v]["descendant"]
            V[u]["lowest"] = min(V[u]["lowest"], V[v]["lowest"])
            if V[v]["lowest"] >= V[u]["discovered"] or root == u and V[u]["child"] > 1:
                V[u]["c"] += V[v]["descendant"] * (n - V[v]["descendant"] - 1)
                cc0 -= V[v]["descendant"]
        elif v != V[u]["parent"]:
            V[u]["lowest"] = min(V[u]["lowest"], V[v]["discovered"])
    V[u]["c"] += cc0 * (n - cc0 - 1)
    return V, time, n


def approximate_inverse_closeness_centrality(G):
    V = {}
    for i in G.nodes:
        V[i] = {}
        V[i]["child"] = 0
        V[i]["color"] = "white"
        V[i]["c"] = 0
        V[i]["parent"] = None
        V[i]["discovered"] = 0
        V[i]["lowest"] = 0
        V[i]["descendant"] = 0
    time = 0
    n = len(G)
    for u in G.nodes:
        if V[u]["color"] == "white":
            V, time, n = Modified_DFS(G, u, V, time, n)
    return V


[docs] @not_implemented_for("multigraph") def ICC(G, k): """an efficient algorithm for structural hole spanners detection. Returns top k nodes as structural hole spanners, Algorithm 1 of [1]_ Parameters ---------- G : easygraph.Graph An unweighted and undirected graph. k : int top - k structural hole spanners Returns ------- V : list The list of top-k structural hole spanners. Examples -------- Returns the top k nodes as structural hole spanners, using **ICC**. >>> ICC(G,k=3) References ---------- .. [1] https://dl.acm.org/doi/10.1145/2806416.2806431 """ Q = [] V = [] for v in G.nodes: i_c = inverse_closeness_centrality(G, v) if len(Q) < k: Q.append([v, i_c]) continue MAX = 0 t = v for i in Q: if MAX < i[1]: MAX = i[1] t = i[0] if i_c < MAX: Q.remove([t, MAX]) Q.append([v, i_c]) for i in Q: V.append(i[0]) return V
[docs] @not_implemented_for("multigraph") def BICC(G, k, K, l): """an efficient algorithm for structural hole spanners detection. Returns top k nodes as structural hole spanners, Algorithm 2 of [1]_ Parameters ---------- G : easygraph.Graph An unweighted and undirected graph. k : int top - k structural hole spanners K : int the number of candidates K for the top-k hole spanners l : int level-l neighbors of nodes Returns ------- V : list The list of top-k structural hole spanners. Examples -------- Returns the top k nodes as structural hole spanners, using **BICC**. >>> BICC(G,k=3,K=5,l=4) References ---------- .. [1] https://dl.acm.org/doi/10.1145/2806416.2806431 """ H = [] V = [] for v in G.nodes: b_i_c = bounded_inverse_closeness_centrality(G, v, l) if len(H) < K: H.append([v, b_i_c]) continue MIN = 10000000 t = v for i in H: if MIN > i[1]: MIN = i[1] t = i[0] if b_i_c > MIN: H.remove([t, MIN]) H.append([v, b_i_c]) for i in H: v = i[0] i_c = inverse_closeness_centrality(G, v) if len(V) < k: V.append([v, i_c]) continue MAX = 0 t = v for i in V: if MAX < i[1]: MAX = i[1] t = i[0] if i_c < MAX: V.remove([t, MAX]) V.append([v, i_c]) VS = [] for i in V: VS.append(i[0]) return VS
[docs] @not_implemented_for("multigraph") def AP_BICC(G, k, K, l): """an efficient algorithm for structural hole spanners detection. Returns top k nodes as structural hole spanners, Algorithm 3 of [1]_ Parameters ---------- G : easygraph.Graph An unweighted and undirected graph. k : int top - k structural hole spanners K : int the number of candidates K for the top-k hole spanners l : int level-l neighbors of nodes Returns ------- V : list The list of top-k structural hole spanners. Examples -------- Returns the top k nodes as structural hole spanners, using **AP_BICC**. >>> AP_BICC(G,k=3,K=5,l=4) References ---------- .. [1] https://dl.acm.org/doi/10.1145/2806416.2806431 """ V = [] T = [] A = {} A = approximate_inverse_closeness_centrality(G) for v in A: if len(T) < k: T.append([v, A[v]["c"]]) continue MIN = 10000000 t = v for i in T: if MIN > i[1]: MIN = i[1] t = i[0] if A[v]["c"] > MIN: T.remove([t, MIN]) T.append([v, A[v]["c"]]) if len(T) < k: U = {} for i in G.nodes: if i not in A: U.append(i) kk = k - len(T) Q = [] for v in U: b_i_c = bounded_inverse_closeness_centrality(G, v, l) if len(Q) < K: Q.append([v, b_i_c]) else: MIN = 10000000 t = v for i in Q: if MIN > i[1]: MIN = i[1] t = i[0] if b_i_c > MIN: Q.remove([t, MIN]) Q.append([v, b_i_c]) while len(T) != k: MAX = 0 t = None for i in Q: if MAX < i[1]: MAX = i[1] t = i[0] T.append([t, A[t]["c"]]) for i in T: V.append(i[0]) return V
if __name__ == "__main__": G = eg.datasets.get_graph_karateclub() print(ICC(G, 3)) print(BICC(G, 3, 5, 3)) print(AP_BICC(G, 3, 5, 3))