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))