wehub-resource-sync
612 lines
18 KiB
Python
612 lines
18 KiB
Python
import math
|
|
import random
|
|
import sys
|
|
|
|
import easygraph as eg
|
|
|
|
from easygraph.functions.components.strongly_connected import condensation
|
|
from easygraph.functions.components.strongly_connected import (
|
|
number_strongly_connected_components,
|
|
)
|
|
from easygraph.utils import *
|
|
|
|
|
|
__all__ = [
|
|
"maxBlock",
|
|
"maxBlockFast",
|
|
]
|
|
tim = 0
|
|
sys.setrecursionlimit(9000000)
|
|
|
|
|
|
class dom_g:
|
|
def __init__(self, N, M):
|
|
self.tot = 0
|
|
self.h = []
|
|
self.ne = []
|
|
self.to = []
|
|
for i in range(N + 1):
|
|
self.h.append(0)
|
|
for i in range(max(N + 1, M + 1)):
|
|
self.ne.append(0)
|
|
self.to.append(0)
|
|
|
|
def add(self, x, y):
|
|
self.tot += 1
|
|
self.to[self.tot] = y
|
|
self.ne[self.tot] = self.h[x]
|
|
self.h[x] = self.tot
|
|
|
|
|
|
def _tarjan(x, dfn, repos, g, fa):
|
|
global tim
|
|
tim += 1
|
|
dfn[x] = tim
|
|
repos[tim] = x
|
|
i = g.h[x]
|
|
while i:
|
|
if dfn[g.to[i]] == 0:
|
|
fa[g.to[i]] = x
|
|
_tarjan(g.to[i], dfn, repos, g, fa)
|
|
i = g.ne[i]
|
|
|
|
|
|
def _find(x, f, dfn, semi, mi):
|
|
if x == f[x]:
|
|
return x
|
|
tmp = f[x]
|
|
f[x] = _find(f[x], f, dfn, semi, mi)
|
|
if dfn[semi[mi[tmp]]] < dfn[semi[mi[x]]]:
|
|
mi[x] = mi[tmp]
|
|
return f[x]
|
|
|
|
|
|
def _dfs(x, tr, ans, desc_set):
|
|
ans[x] += 1
|
|
i = tr.h[x]
|
|
|
|
while i:
|
|
y = tr.to[i]
|
|
desc_set[x].add(y)
|
|
_dfs(y, tr, ans, desc_set)
|
|
ans[x] += ans[y]
|
|
for n in desc_set[y]:
|
|
desc_set[x].add(n)
|
|
i = tr.ne[i]
|
|
|
|
|
|
def _get_idom(G, G_tr, node_s, ans_real, desc_set_real):
|
|
"""Find the immediate dominator of each node and construct an s-rooted dominator tree.
|
|
|
|
Parameters
|
|
----------
|
|
G: easygraph.DiGraph
|
|
|
|
G_tr: easygraph.DiGraph
|
|
an s-rooted dominator tree to be constructed.
|
|
|
|
node_s: int
|
|
the node s
|
|
|
|
ans_real: dict
|
|
denotes the number of proper descendants nu of each node u in the dominator tree.
|
|
a result to be calculated
|
|
|
|
desc_set_real: dict
|
|
denotes the set of proper descendants of node u in the dominator tree.
|
|
a result to be calculated
|
|
|
|
Examples
|
|
--------
|
|
# >>> G_tr = eg.DiGraph()
|
|
# >>> n_set = {}
|
|
# >>> desc_set = {}
|
|
# >>> _get_idom(G, G_tr, node_s, n_set, desc_set)
|
|
|
|
References
|
|
----------
|
|
.. [1] http://keyblog.cn/article-173.html
|
|
|
|
"""
|
|
|
|
global tim
|
|
tim = 0
|
|
n_dom = G.number_of_nodes()
|
|
m_dom = G.number_of_edges()
|
|
g = dom_g(n_dom + 1, m_dom + 1)
|
|
rg = dom_g(n_dom + 1, m_dom + 1)
|
|
ng = dom_g(n_dom + 1, m_dom + 1)
|
|
tr = dom_g(n_dom + 1, m_dom + 1)
|
|
|
|
dfn = [0 for i in range(n_dom + 1)]
|
|
repos = [0 for i in range(n_dom + 1)]
|
|
mi = [i for i in range(n_dom + 1)]
|
|
fa = [0 for i in range(n_dom + 1)]
|
|
f = [i for i in range(n_dom + 1)]
|
|
semi = [i for i in range(n_dom + 1)]
|
|
idom = [0 for i in range(n_dom + 1)]
|
|
|
|
# init
|
|
j = 0
|
|
node_map = {}
|
|
index_map = {}
|
|
for node in G.nodes:
|
|
j += 1
|
|
node_map[node] = j
|
|
index_map[j] = node
|
|
|
|
for edge in G.edges:
|
|
g.add(node_map[edge[0]], node_map[edge[1]])
|
|
rg.add(node_map[edge[1]], node_map[edge[0]])
|
|
|
|
# tarjan
|
|
_tarjan(node_map[node_s], dfn, repos, g, fa)
|
|
# work
|
|
i = n_dom
|
|
while i >= 2:
|
|
x = repos[i]
|
|
tmp = n_dom
|
|
j = rg.h[x]
|
|
while j:
|
|
if dfn[rg.to[j]] == 0:
|
|
j = rg.ne[j]
|
|
continue
|
|
if dfn[rg.to[j]] < dfn[x]:
|
|
tmp = min(tmp, dfn[rg.to[j]])
|
|
else:
|
|
_find(rg.to[j], f, dfn, semi, mi)
|
|
tmp = min(tmp, dfn[semi[mi[rg.to[j]]]])
|
|
j = rg.ne[j]
|
|
|
|
semi[x] = repos[tmp]
|
|
f[x] = fa[x]
|
|
ng.add(semi[x], x)
|
|
x = repos[i - 1]
|
|
j = ng.h[x]
|
|
while j:
|
|
y = ng.to[j]
|
|
_find(y, f, dfn, semi, mi)
|
|
if semi[mi[y]] == semi[y]:
|
|
idom[y] = semi[y]
|
|
else:
|
|
idom[y] = mi[y]
|
|
j = ng.ne[j]
|
|
i -= 1
|
|
|
|
i = 2
|
|
while i <= n_dom:
|
|
x = repos[i]
|
|
if x != 0:
|
|
if idom[x] != semi[x]:
|
|
idom[x] = idom[idom[x]]
|
|
tr.add(idom[x], x)
|
|
if x != node_map[node_s]:
|
|
G_tr.add_edge(index_map[idom[x]], index_map[x])
|
|
i += 1
|
|
G_tr.add_node(node_s)
|
|
ans = {}
|
|
desc_set = {}
|
|
for node in G_tr.nodes:
|
|
ans[node_map[node]] = 0
|
|
desc_set[node_map[node]] = set()
|
|
|
|
_dfs(node_map[node_s], tr, ans, desc_set)
|
|
for key in ans.keys():
|
|
ans[key] -= 1
|
|
ans_real[index_map[key]] = ans[key]
|
|
for key in desc_set.keys():
|
|
desc_set_real[index_map[key]] = set()
|
|
for value in desc_set[key]:
|
|
desc_set_real[index_map[key]].add(index_map[value])
|
|
|
|
|
|
def _find_topk_shs_under_l(G, f_set, k, L):
|
|
"""Find the top-k structural hole spanners under L simulations.
|
|
|
|
Parameters
|
|
----------
|
|
G: easygraph.DiGraph
|
|
|
|
f_set: dict
|
|
user vi shares his/her information on network G at a rate fi.
|
|
|
|
k: int
|
|
top - k structural hole spanners.
|
|
|
|
L: int
|
|
the number of simulations.
|
|
|
|
Returns
|
|
-------
|
|
S_list : list
|
|
A set S of k nodes that block the maximum number of information propagations within L simulations.
|
|
|
|
ave_H_Lt_S: float
|
|
the average number of blocked information propagations by the nodes in set S with L t simulations.
|
|
|
|
"""
|
|
h_set = {}
|
|
n = G.number_of_nodes()
|
|
for node in G.nodes:
|
|
h_set[node] = 0
|
|
for l in range(L):
|
|
if l % 100000 == 0:
|
|
print("[", l, "/", L, "] find topk shs under L")
|
|
# Choose a node s from the n nodes in G randomly
|
|
node_s = random.choice(list(G.nodes))
|
|
# Generate a graph G & = (V, E & ) from G under the live-edge graph model
|
|
G_live = G.copy()
|
|
for edge in G_live.edges:
|
|
wij = G_live[edge[0]][edge[1]]["weight"]
|
|
toss = random.random() + 0.1
|
|
if toss >= wij:
|
|
G_live.remove_edge(edge[0], edge[1])
|
|
# Obtain the induced subgraph by the set R G & (s ) of reachable nodes from s
|
|
R_set = eg.connected_component_of_node(G_live, node_s)
|
|
G_subgraph = eg.DiGraph()
|
|
for node in R_set:
|
|
G_subgraph.add_node(node)
|
|
for edge in G_live.edges:
|
|
if edge[0] in G_subgraph.nodes and edge[1] in G_subgraph.nodes:
|
|
G_subgraph.add_edge(edge[0], edge[1])
|
|
# Find the immediate dominator idom (v ) of each node v $ V && \ { s } in G
|
|
# Construct an s -rooted dominator tree
|
|
# Calculate the number of proper descendants n u of each node u $ V &&
|
|
G_tr = eg.DiGraph()
|
|
n_set = {}
|
|
desc_set = {}
|
|
_get_idom(G_subgraph, G_tr, node_s, n_set, desc_set)
|
|
for node_u in G_tr.nodes:
|
|
if node_u != node_s:
|
|
# the number of blocked information propagations by node u
|
|
h_set[node_u] += n_set[node_u] * f_set[node_s]
|
|
ave_H_set = {}
|
|
for node in G.nodes:
|
|
ave_H_set[node] = h_set[node] * n / L
|
|
ordered_set = sorted(ave_H_set.items(), key=lambda x: x[1], reverse=True)
|
|
S_list = []
|
|
ave_H_Lt_S = 0
|
|
for i in range(k):
|
|
S_list.append((ordered_set[i])[0])
|
|
ave_H_Lt_S += (ordered_set[i])[1]
|
|
return S_list, ave_H_Lt_S
|
|
|
|
|
|
def _get_estimated_opt(G, f_set, k, c, delta):
|
|
"""Estimation of the optimal value OPT.
|
|
|
|
Parameters
|
|
----------
|
|
G: easygraph.DiGraph
|
|
|
|
f_set: dict
|
|
user vi shares his/her information on network G at a rate fi.
|
|
|
|
k: int
|
|
top - k structural hole spanners.
|
|
|
|
c: int
|
|
Success probability 1-n^-c of maxBlock.
|
|
|
|
delta: float
|
|
a small value delta > 0.
|
|
|
|
Returns
|
|
-------
|
|
res_opt : float
|
|
An approximate value OPT.
|
|
|
|
"""
|
|
print("Estimating the optimal value OPT...")
|
|
n = G.number_of_nodes()
|
|
opt_ub = 0
|
|
for f_key in f_set.keys():
|
|
opt_ub = opt_ub + f_set[f_key]
|
|
opt_ub = opt_ub * k * (n - 1)
|
|
T = math.log((opt_ub / (delta / 2)), 2)
|
|
T = math.ceil(T)
|
|
lamda = 4 * (c * math.log(n, 2) + math.log(k * T, 2)) * (2 * k + 1) * k * n * n
|
|
for t in range(T):
|
|
opt_g = opt_ub / math.pow(2, t + 1)
|
|
L_t = math.ceil(lamda / opt_g)
|
|
print("[", t, "/", T, "] Estimating OPT: L=", L_t)
|
|
S_list, ave_H_Lt_S = _find_topk_shs_under_l(G, f_set, k, L_t)
|
|
if ave_H_Lt_S >= opt_g:
|
|
res_opt = opt_g / 2
|
|
return res_opt
|
|
print("[Warning] OPT is not greater that delta")
|
|
return -1
|
|
|
|
|
|
def _find_separation_nodes(G):
|
|
G_s = condensation(G)
|
|
SCC_mapping = {}
|
|
incoming_info = G_s.graph["incoming_info"]
|
|
G_s_undirected = eg.Graph()
|
|
sep_nodes = set()
|
|
for node in (G_s.nodes).keys():
|
|
SCC_mapping[node] = G_s.nodes[node]["member"]
|
|
if len(G_s.nodes[node]["member"]) == 1:
|
|
sep_nodes.add(node)
|
|
G_s_undirected.add_node(node, member=G_s.nodes[node]["member"])
|
|
for edge in G_s.edges:
|
|
G_s_undirected.add_edge(edge[0], edge[1])
|
|
cut_nodes = eg.generator_articulation_points(G_s_undirected)
|
|
out_degree = G_s.out_degree()
|
|
in_degree = G_s.in_degree()
|
|
separations = set()
|
|
for cut_node in cut_nodes:
|
|
if cut_node in sep_nodes:
|
|
if out_degree[cut_node] >= 1 and in_degree[cut_node] >= 1:
|
|
CC_u = eg.connected_component_of_node(G_s_undirected, node=cut_node)
|
|
G_CC = G_s_undirected.nodes_subgraph(list(CC_u))
|
|
G_CC.remove_node(cut_node)
|
|
successors = G_s.neighbors(node=cut_node)
|
|
predecessors = G_s.predecessors(node=cut_node)
|
|
CC_removal = eg.connected_components(G_CC)
|
|
flag = True
|
|
for group in CC_removal:
|
|
flag_succ = False
|
|
flag_pred = False
|
|
for node in group:
|
|
if node in successors:
|
|
flag_succ = True
|
|
if flag_pred:
|
|
flag = False
|
|
break
|
|
elif node in predecessors:
|
|
flag_pred = True
|
|
if flag_succ:
|
|
flag = False
|
|
break
|
|
if not flag:
|
|
break
|
|
if flag:
|
|
separations.add(list(SCC_mapping[cut_node])[0])
|
|
return separations, SCC_mapping, incoming_info
|
|
|
|
|
|
def _find_ancestors_of_node(G, node_t):
|
|
G_reverse = eg.DiGraph()
|
|
for node in G.nodes:
|
|
G_reverse.add_node(node)
|
|
for edge in G.edges:
|
|
G_reverse.add_edge(edge[1], edge[0])
|
|
node_dict = eg.Dijkstra(G_reverse, node=node_t)
|
|
ancestors = []
|
|
for node in G.nodes:
|
|
if node_dict[node] < float("inf") and node != node_t:
|
|
ancestors.append(node)
|
|
return ancestors
|
|
|
|
|
|
@not_implemented_for("multigraph")
|
|
def maxBlock(G, k, f_set=None, delta=1, eps=0.5, c=1, flag_weight=False):
|
|
"""Structural hole spanners detection via maxBlock method.
|
|
|
|
Parameters
|
|
----------
|
|
G: easygraph.DiGraph
|
|
|
|
k: int
|
|
top - k structural hole spanners.
|
|
|
|
f_set: dict, optional
|
|
user vi shares his/her information on network G at a rate fi.
|
|
default is a random [0,1) integer for each node
|
|
|
|
delta: float, optional (default: 1)
|
|
a small value delta > 0.
|
|
|
|
eps: float, optional (default: 0.5)
|
|
an error ratio eps with 0 < eps < 1.
|
|
|
|
c: int, optional (default: 1)
|
|
Success probability 1-n^-c of maxBlock.
|
|
|
|
flag_weight: bool, optional (default: False)
|
|
Denotes whether each edge has attribute 'weight'
|
|
|
|
Returns
|
|
-------
|
|
S_list : list
|
|
The list of each top-k structural hole spanners.
|
|
|
|
See Also
|
|
-------
|
|
maxBlockFast
|
|
|
|
Examples
|
|
--------
|
|
# >>> maxBlock(G, 100)
|
|
|
|
References
|
|
----------
|
|
.. [1] https://doi.org/10.1016/j.ins.2019.07.072
|
|
|
|
"""
|
|
if f_set is None:
|
|
f_set = {}
|
|
for node in G.nodes:
|
|
f_set[node] = random.random()
|
|
if not flag_weight:
|
|
for edge in G.edges:
|
|
G[edge[0]][edge[1]]["weight"] = random.random()
|
|
n = G.number_of_nodes()
|
|
approximate_opt = _get_estimated_opt(G, f_set, k, c, delta)
|
|
print("approximate_opt:", approximate_opt)
|
|
L_min = (k + c) * math.log(n, 2) + math.log(4, 2)
|
|
L_min = L_min * k * n * n * math.pow(eps, -2) * (8 * k + 2 * eps)
|
|
L_min = L_min / approximate_opt
|
|
L_min = math.ceil(L_min)
|
|
print("L_min:", L_min)
|
|
S_list, ave_H_Lt_S = _find_topk_shs_under_l(G, f_set, k, L_min)
|
|
return S_list
|
|
|
|
|
|
@not_implemented_for("multigraph")
|
|
def maxBlockFast(G, k, f_set=None, L=None, flag_weight=False):
|
|
"""Structural hole spanners detection via maxBlockFast method.
|
|
|
|
Parameters
|
|
----------
|
|
G: easygraph.DiGraph
|
|
|
|
G: easygraph.DiGraph
|
|
|
|
k: int
|
|
top - k structural hole spanners.
|
|
|
|
f_set: dict, optional
|
|
user vi shares his/her information on network G at a rate fi.
|
|
default is a random [0,1) integer for each node
|
|
|
|
L: int, optional (default: log2n)
|
|
Simulation time L for maxBlockFast.
|
|
|
|
flag_weight: bool, optional (default: False)
|
|
Denotes whether each edge has attribute 'weight'
|
|
|
|
See Also
|
|
-------
|
|
maxBlock
|
|
|
|
Examples
|
|
--------
|
|
# >>> maxBlockFast(G, 100)
|
|
|
|
References
|
|
----------
|
|
.. [1] https://doi.org/10.1016/j.ins.2019.07.072
|
|
|
|
"""
|
|
h_set = {}
|
|
n = G.number_of_nodes()
|
|
if L is None:
|
|
L = math.ceil(math.log(n, 2))
|
|
# print("L:", L)
|
|
if f_set is None:
|
|
f_set = {}
|
|
for node in G.nodes:
|
|
f_set[node] = random.random()
|
|
for node in G.nodes:
|
|
h_set[node] = 0
|
|
if not flag_weight:
|
|
for edge in G.edges:
|
|
G[edge[0]][edge[1]]["weight"] = random.random()
|
|
for l in range(L):
|
|
if l % 10000 == 0:
|
|
print(l, "/", L, "...")
|
|
# Generate a graph G & = (V, E & ) from G under the live-edge graph model
|
|
G_live = G.copy()
|
|
for edge in G_live.edges:
|
|
wij = G_live[edge[0]][edge[1]]["weight"]
|
|
toss = random.random() + 0.1
|
|
if toss >= wij:
|
|
G_live.remove_edge(edge[0], edge[1])
|
|
|
|
G0 = G_live.copy()
|
|
d_dict = {}
|
|
ns = number_strongly_connected_components(G0)
|
|
non_considered_nodes = set()
|
|
for node in G0.nodes:
|
|
d_dict[node] = 1
|
|
non_considered_nodes.add(node)
|
|
G_p_1 = G0.copy()
|
|
for i in range(ns):
|
|
separation_nodes, SCC_mapping, incoming_info = _find_separation_nodes(G_p_1)
|
|
# print("separation_nodes:", separation_nodes)
|
|
if len(separation_nodes) > 0:
|
|
chosen_node = -1
|
|
for node in separation_nodes:
|
|
node_dict = eg.Dijkstra(G_p_1, node=node)
|
|
flag = True
|
|
for other_sep in separation_nodes:
|
|
if other_sep != node:
|
|
if node_dict[other_sep] < float("inf"):
|
|
flag = False
|
|
break
|
|
if flag:
|
|
chosen_node = node
|
|
break
|
|
# print("chosen_node:", chosen_node)
|
|
G_tr = eg.DiGraph()
|
|
n_set = {}
|
|
desc_set = {}
|
|
_get_idom(G_p_1, G_tr, chosen_node, n_set, desc_set)
|
|
ancestors = _find_ancestors_of_node(G_p_1, chosen_node)
|
|
sum_fi = 0
|
|
for node_av in ancestors:
|
|
sum_fi += f_set[node_av]
|
|
for node_u in G_tr.nodes:
|
|
D_u = 0
|
|
for desc in desc_set[node_u]:
|
|
if desc not in d_dict.keys():
|
|
print(
|
|
"Error: desc:",
|
|
desc,
|
|
"node_u",
|
|
node_u,
|
|
"d_dict:",
|
|
d_dict,
|
|
)
|
|
print(desc_set[node_u])
|
|
D_u += d_dict[desc]
|
|
if node_u != chosen_node:
|
|
h_set[node_u] += (f_set[chosen_node] + sum_fi) * D_u
|
|
elif node_u == chosen_node:
|
|
h_set[node_u] += sum_fi * D_u
|
|
d_dict[chosen_node] = 0
|
|
for node_vj in G_tr.nodes:
|
|
d_dict[chosen_node] += d_dict[node_vj]
|
|
G_p = G_p_1.copy()
|
|
for neighbor in G_p_1.neighbors(node=chosen_node):
|
|
G_p.remove_edge(chosen_node, neighbor)
|
|
G_p_1 = G_p.copy()
|
|
non_considered_nodes.remove(chosen_node)
|
|
else:
|
|
V_set = set()
|
|
for key in SCC_mapping.keys():
|
|
for node in SCC_mapping[key]:
|
|
if (node in non_considered_nodes) and (
|
|
node not in incoming_info.keys()
|
|
):
|
|
V_set.add(node)
|
|
if len(V_set) > 0:
|
|
break
|
|
# print("V_set:", V_set)
|
|
for node_v in V_set:
|
|
G_tr = eg.DiGraph()
|
|
n_set = {}
|
|
desc_set = {}
|
|
_get_idom(G_p_1, G_tr, node_v, n_set, desc_set)
|
|
for node_u in G_tr.nodes:
|
|
D_u = 0
|
|
for desc in desc_set[node_u]:
|
|
if desc not in d_dict.keys():
|
|
print(
|
|
"Error: desc:",
|
|
desc,
|
|
"node_u",
|
|
node_u,
|
|
"d_dict:",
|
|
d_dict,
|
|
)
|
|
print(desc_set[node_u])
|
|
D_u += d_dict[desc]
|
|
h_set[node_u] += f_set[node_v] * D_u
|
|
G_p = G_p_1.copy()
|
|
for node_v in V_set:
|
|
non_considered_nodes.remove(node_v)
|
|
for neighbor in G_p_1.neighbors(node=node_v):
|
|
G_p.remove_edge(node_v, neighbor)
|
|
G_p_1 = G_p.copy()
|
|
ave_H_set = {}
|
|
for node in G.nodes:
|
|
ave_H_set[node] = h_set[node] * n / L
|
|
ordered_set = sorted(ave_H_set.items(), key=lambda x: x[1], reverse=True)
|
|
S_list = []
|
|
for i in range(k):
|
|
S_list.append((ordered_set[i])[0])
|
|
return S_list
|