import networkx as nx
import copy
import random
import time
from YHSF import ICModel
def weight(G, u, v):
if (G.has_edge(u, v)):
return G[u][v]['pp']
else:
return 0
class LDAG_Data:
def __init__(self, localDAG, node):
self.localDAG = localDAG
self.node = node
self.AP = {}
self.alpha = {}
self.deltaAP = {}
self.deltaAlpha = {}
def set_AP(self, u, value):
self.AP[u] = value
def set_alpha(self, u, value):
self.alpha[u] = value
def set_deltaAP(self, u, value):
self.deltaAP[u] = value
def set_deltaAlpha(self, u, value):
self.deltaAlpha[u] = value
def update_AP(self, u, value):
self.AP[u] += value
def update_alpha(self, u, value):
self.alpha[u] += value
def get_LDAG(self):
return self.localDAG
def get_node(self):
return self.node
def get_AP(self, u):
return self.AP[u]
def get_alpha(self, u):
return self.alpha[u]
def get_deltaAP(self, u):
return self.deltaAP[u]
def get_deltaAlpha(self, u):
return self.deltaAlpha[u]
def compute_alpha(self):
for u in self.localDAG:
self.alpha[u] = 0
self.alpha[self.node] = 1
sequenceP = list(reversed(list(nx.topological_sort(self.localDAG))))
for u in sequenceP:
if (u != self.node):
for x in self.localDAG.neighbors(u):
self.alpha[u] += weight(self.localDAG, u, x) * self.alpha[x]
def compute_deltaAP(self, s, seedNode):
sequenceP = list(nx.topological_sort(self.localDAG))
sIndex = sequenceP.index(s)
sequenceP = sequenceP[sIndex + 1:]
sequenceP = [x for x in sequenceP if x not in seedNode]
for u in sequenceP:
self.set_deltaAP(u, 0)
for x in self.localDAG.predecessors(u):
if (x in sequenceP):
self.deltaAP[u] += self.get_deltaAP(x) * weight(self.localDAG, x, u)
def compute_deltaAlpha(self, s, seedNode):
sequenceP = list(reversed(list(nx.topological_sort(self.localDAG))))
sIndex = sequenceP.index(s)
sequenceP = sequenceP[sIndex + 1:]
sequenceP = [x for x in sequenceP if x not in seedNode]
for u in sequenceP:
self.set_deltaAlpha(u, 0)
for x in self.localDAG.neighbors(u):
if (x in sequenceP):
self.deltaAlpha[u] += weight(self.localDAG, u, x) * self.get_deltaAlpha(x)
class LDAG:
def __init__(self):
pass
def preprocess(self, G):
directedGraph = nx.DiGraph()
for u in G.nodes():
for v in G.neighbors(u):
if (v != u):
propProb = G.number_of_edges(u, v) / G.in_degree(v)
directedGraph.add_edge(u, v, pp=propProb)
return directedGraph
def findLDAG(self, G, v, simThreshold):
LDAG = nx.DiGraph()
Inf = {}
selectedNodes = []
for node in G.nodes():
Inf[node] = 0
Inf[v] = 1
maxInf = v
selectedNodes.append(maxInf)
while (Inf[maxInf] >= simThreshold):
nodes = copy.deepcopy(LDAG.nodes())
for node in nodes:
LDAG.add_edge(maxInf, node, pp=weight(G, maxInf, node))
del nodes
LDAG.add_node(maxInf)
for node in G.predecessors(maxInf):
Inf[node] += weight(G, node, maxInf) * Inf[maxInf]
if (len(selectedNodes) >= len(G.nodes())):
break
maxInf = max({x: Inf[x] for x in Inf if x not in selectedNodes}, key=Inf.get)
selectedNodes.append(maxInf)
return LDAG
def findSeed(self, G, simThreshold, K):
# Preparation Phase (Line 1 - 3)
seedNode = []
IncInf = {}
for node in G.nodes():
IncInf[node] = 0
# Line 4 - 11
listOfLDAG = {}
startTime = time.time()
for v in G.nodes():
nodeLDAG = self.findLDAG(G, v, simThreshold) # (Line 5)
tempLDAG = LDAG_Data(nodeLDAG, v)
for u in nodeLDAG.nodes():
tempLDAG.set_AP(u, 0) # Line 7
tempLDAG.compute_alpha()
for u in nodeLDAG.nodes():
IncInf[u] += tempLDAG.get_alpha(u)
listOfLDAG[v] = tempLDAG
endTime = time.time()
totalFindLDAGTime = endTime - startTime
print("Time needed to find all LDAG : " + str(round(totalFindLDAGTime, 2)) + " seconds")
# Main Loop (Line 13)
for _ in range(K):
s = max({x: IncInf[x] for x in IncInf if x not in seedNode}, key=IncInf.get) # (Line 15)
InfSet = []
for v in listOfLDAG: # Find InfSet (Before Line 16)
if (v != s and v not in seedNode and s in list(listOfLDAG[v].localDAG.nodes())):
InfSet.append(v)
for v in InfSet: # (Start Line 16)
listOfLDAG[v].set_deltaAlpha(s, -(listOfLDAG[v].get_alpha(s))) # Line 18
for u in seedNode: # Line 18
listOfLDAG[v].set_deltaAlpha(u, 0)
listOfLDAG[v].compute_deltaAlpha(s, seedNode) # Line 19-20
sequenceP = list(reversed(list(nx.topological_sort(listOfLDAG[v].localDAG))))
sIndex = sequenceP.index(s)
sequenceP = sequenceP[sIndex:]
for u in sequenceP:
listOfLDAG[v].update_alpha(u, listOfLDAG[v].get_deltaAlpha(u)) # Line 21
IncInf[u] += listOfLDAG[v].get_deltaAlpha(u) * (1 - listOfLDAG[v].get_AP(u)) # Line 22
listOfLDAG[v].set_deltaAP(s, 1 - (listOfLDAG[v].get_AP(s))) # Line 24
for u in seedNode: # Line 24
listOfLDAG[v].set_deltaAP(u, 0)
listOfLDAG[v].compute_deltaAP(s, seedNode) # Line 25-26
sequenceP = list(nx.topological_sort(listOfLDAG[v].localDAG))
sIndex = sequenceP.index(s)
sequenceP = sequenceP[sIndex:]
for u in sequenceP:
listOfLDAG[v].update_AP(u, listOfLDAG[v].get_deltaAP(u))
IncInf[u] -= listOfLDAG[v].get_alpha(u) * listOfLDAG[v].get_deltaAP(u)
seedNode.append(s) # Line 30
return seedNode
def simulate(self, G, seedNode):
# Set Random threshold for every node ~ [0,1]
nodeThresholds = {}
for node in G.nodes():
nodeThresholds[node] = random.uniform(0, 1)
nodeValues = {}
for node in G.nodes():
nodeValues[node] = 0
newActive = True
currentActiveNodes = copy.deepcopy(seedNode)
newActiveNodes = set()
activatedNodes = copy.deepcopy(seedNode) # Prevent from activating node twice
influenceSpread = len(seedNode)
while (newActive):
for node in currentActiveNodes:
for neighbor in G.neighbors(node):
if (neighbor not in activatedNodes):
nodeValues[neighbor] += weight(G, node, neighbor)
if (nodeValues[neighbor] >= nodeThresholds[neighbor]):
newActiveNodes.add(neighbor)
activatedNodes.append(neighbor)
influenceSpread += len(newActiveNodes)
if newActiveNodes:
currentActiveNodes = list(newActiveNodes)
newActiveNodes = set()
else:
newActive = False
return influenceSpread
FILENAME = 'E:/新建文件夹/DPSO_demo-master/twitter.txt'
G = nx.read_edgelist(FILENAME,
评论0