Data Mining - Comment utiliser python pour implémenter l'algorithme dans « Analyse du problème de maximisation de l'influence de plusieurs réseaux sociaux » ?
PHP中文网
PHP中文网 2017-05-18 10:58:59
0
1
705

En tant que novice en Python, mon instructeur m'a demandé d'utiliser Python pour implémenter l'algorithme dans l'article. J'étais confus quant aux points techniques requis et à la manière d'implémenter l'algorithme. Actuellement, j'ai suivi le didacticiel python du professeur Liao en python et je lis actuellement la documentation networkx.
J'espère que vous pourrez m'aider à résoudre les problèmes suivants :
1. Points techniques nécessaires à la mise en œuvre de l'algorithme
2 Comment gérer ce type de papier
3.

Adresse papier : http://cjc.ict.ac.cn/online/o...

PHP中文网
PHP中文网

认证高级PHP讲师

répondre à tous (1)
黄舟

经过一周,现已初步完成,其中多出代码不够美观以及效率不高,还请指点

# _*_ coding:utf-8 _*_ # ================================================================================== # # Description: Influence Maximization on Multiple Social Networks # # ================================================================================== import matplotlib.pyplot as plt import networkx as nx import heapq #总图 G = nx.DiGraph() def load_graph(file): ''' 加载文件为列表格式,并得到G,画出图结构 ''' #将总列表设成全局格式 global gllist #迭代文件中每个元素 with open(file) as f: lines = f.readlines() mylist = [line.strip().split() for line in lines] gllist = [] #将字符串型转换为整型 for i in mylist: gllist.append(i[:-2]+map(lambda x: float(x), i[-2:])) print '初始全局列表:' print gllist drawlist=[] #提取二维列表mylist每行前三个元素,赋给新的列表drawlist for i in range(len(mylist)): drawlist.append([]) for j in range(3): drawlist[i].append(mylist[i][j]) #将列表drawlist加载为有向加权图 G.add_weighted_edges_from(drawlist) nx.draw(G, with_labels=True, width=1, node_color='y', edge_color='b') plt.show() print 'G图中所有节点:',G.nodes() print 'G图中所有边:',G.edges() print '\n' def get_self_node(gllist, target=None): ''' 获取目标节点的自传播节点,返回selflist并包含目标节点 ''' #初始化自传播节点列表 selflist = [target] #存放已传播节点列表 haslist = [] flag = 0 while (flag != 0): flag = 0 for target in selflist: if target not in haslist: for i in range(len(gllist)): #判断二维列表中,每行第三个元素是否为1,若为1,则为自传播节点 if ((gllist[i][0] == target)or(gllist[i][1]==target))and(gllist[i][3]==1.0): if gllist[i][0] == target: if gllist[i][1] not in haslist: selflist.append(gllist[i][1]) haslist.append(gllist[i][1]) flag += 1 else: if gllist[i][0] not in haslist: selflist.append(gllist[i][0]) haslist.append(gllist[i][0]) flag += 1 #去除重复元素 haslist = set(haslist) selflist = set(selflist) #去除重复元素 selflist = set(selflist) return selflist def longest_path(gllist,source=None,target=None): ''' 获取起始点到实体的最大路径集合,返回为longestpath列表 ''' longestpath = [] newlist = [] for i in range(len(gllist)): newlist.append([]) for j in range(3): newlist[i].append(gllist[i][j]) #构建图结构 G1 = nx.DiGraph() #添加带权有向边 G1.add_weighted_edges_from(newlist) #获取目标节点的所有自传播街边,并存入selflist中 selflist = get_self_node(gllist, target) max_path = 0 val_path = 1 #获取初始节点到目标节点及目标节点的自传播节点的最大路径 for v in selflist: if v != source: #遍历两点之间所有路径,并进行比对 for path in nx.all_simple_paths(G1,source=source,target=v): #判断路径后两个元素是否为相同实体(如:b1->b2) if is_self_transmit_node(path[-2], v) == 0: for i in range(0, len(path)-1): val_path *= G1.get_edge_data(path[i], path[i+1])['weight'] if max_path < val_path: max_path = val_path val_path = 1 #若目标节点为起始节点则直接跳出 else: continue ############ 有待商榷 ############## longestpath.append(max_path) #返回初始节点到实体的最大路径 return longestpath def is_self_transmit_node(u, v): ''' 判断目标节点不为起始节点的自传播点 ''' flag = 0 #获得起始节点的所有自传播点 selflist = get_self_node(gllist, v) for x in selflist: if u == x: flag = 1 return flag def single_strong_infl(longestpath): ''' 计算起始点到实体的传播概率(影响强度),返回影响强度stronginfl ''' temp = 1 for x in longestpath: temp *= 1-x stronginfl = 1-temp return stronginfl def all_strong_infl(G): ''' 获得每个节点对实体的影响概率 ''' allstrong = [] #初始化所有节点的加权影响范围列表 gnodes = [] #初始化节点列表 tempnodes = [] #初始化临时节点列表 gnodes = G.nodes() for u in gnodes: strong = 0 #存储初始节点对每个实体的影响范围加权,初始化为0 #重置临时节点列表 tempnodes = G.nodes() for v in tempnodes: #非自身节点 if u != v: #判断目标节点不为起始节点的自传播点 if is_self_transmit_node(v, u) == 0: #获取起始节点到实体间最大加权路径,并存入longestpath longestpath = longest_path(gllist, u, v) #去除已遍历目标节点的所有自传播节点 renode = get_self_node(gllist, v) for x in renode: if x != v: tempnodes.remove(x) #计算起始节点到实体间传播概率(影响强度) stronginfl = single_strong_infl(longestpath) strong += stronginfl #添加单个节点到所有实体的加权影响范围 allstrong.append([u, round(strong, 2)]) #返回每个节点到所有实体的加权影响范围 return allstrong #output allstrong : [['a1', 2.48], ['a2', 1.6880000000000002], ['b1', 0.7], ['b2', 0], ['c1', 0], ['d2', 0.6]] def uS_e_uppergain(u, ev, S): ''' 获取节点u在集合S的基础上对实体ev的影响增益, 传入候选节点,上界gain(u|S, ev) ''' #获取目前实体的所有自传播节点 selflist = get_self_node(gllist, ev) stronglist = [] #遍历自传遍节点 for v in selflist: ''' 判断节点v是否存在种子集合S中 其中v为单个节点,如v(ev, Gi) S为种子节点集合,如['a1','a2','b1','b2','c1','d2'] ''' if v in S: ppSv = 1 else: longestpath = [] #遍历种子集合 for s in S: #初始化路径权值与最大路径权值 val_path = 1 max_path = 0 #遍历两点之间所有路径,并进行比对 for path in nx.all_simple_paths(G,source=s,target=v): #判断路径后两个元素是否为相同实体(如:b1->b2) if is_self_transmit_node(path[-2], v) == 0: for i in range(0, len(path)-1): val_path *= G.get_edge_data(path[i], path[i+1])['weight'] if max_path < val_path: max_path = val_path #重置路径权值为1 val_path = 1 #将最大加权路径存入longestpath列表 longestpath.append(max_path) #得到上界pp(S,v)的影响概率,上界pp(S,v) ppSv = single_strong_infl(longestpath) stronglist.append(ppSv) #得到上界pp(S,ev)的影响概率,上界pp(S,ev) ppSev = single_strong_infl(stronglist) #获取pp(u,ev) ppuev = single_strong_infl(longest_path(gllist, u, ev)) #计算上界gain(u|S,ev) uSevgain = (1 - ppSev) * ppuev return uSevgain def uppergain(u, emu, ems, S): ''' 在已有种子集合S的基础上,求得节点u的影响增益上界, 其中传进参数ems为二维列表,如[['a1',2.48],['a2',1.688]],S则为['a1','a2'] ''' uSgain = 0.0 #遍历emu得到列表形式,得到如['a1',2.48]形式 for ev in emu: #判断节点是否存在种子集合中 if ev[0] in S: uSgain += uS_e_uppergain(u, ev[0], S) else: uSgain += ev[1] #返回上界gain(u|S) return uSgain def bound_base_imms(G, k): ''' 完全使用影响增益上界的方式选择top-k个种子节点的过程 ''' #初始化emu,H,初始化ems=空集,S=空集 Htemp = [] Htemp = all_strong_infl(G) H = [] #遍历Htemp=[['a1',2.48],['a2',1.688]],得到如['a1',2.48]形式 for x in Htemp: #逐个获取二维列表中每一行,形式为['a1',2.48,0] H.append([x[0],x[1],0]) emu = [] emu = all_strong_infl(G) ems = [] S = [] for i in range(k): #提取堆顶元素,tnode的形式为['a1',2.48,0] tnode = heapq.nlargest(1, H, key=lambda x: x[1]) #将[['b2', 3.1, 0]]格式改为['b2', 3.1, 0]格式 tnode = sum(tnode, []) while (tnode[2] != i): gain = 0.0 #获取节点u的影响增益上界 gain = uppergain(tnode, emu, ems, S) #赋值影响范围 tnode[1] = gain #修改status tnode[2] = i #对堆进行排序 H = heapq.nlargest(len(H), H, key=lambda x: x[1]) #获取堆顶元素 tnode = heapq.nlargest(1, H, key=lambda x: x[1]) tnode = sum(tnode, []) #添加node到种子集合 S.append([tnode[0]]) #更新ems,添加新节点及节点对每个实体的影响范围加权 ems.append([tnode[0], tnode[1]]) #删除堆顶元素 H.remove(tnode) print ems return sum(S, []) if __name__=='__main__': #大小为k的种子集合S k = 60 #加载文件数据,得到图G和初始列表gllist load_graph('test.txt') #完全使用影响增益上界值的计算过程函数,打印种子集合S print '种子集合:',bound_base_imms(G, k)

test.txt
a1 b1 0.2 0
a1 c1 0.8 0
a2 b2 0.4 0
a2 d2 1 0
b1 c1 0.7 0
c2 a2 0.8 0
d2 b2 0.6 0
a1 a2 1 1
a2 a1 0.1 1
....
a1 l1 0.5 0
a1 m1 0.5 0
a1 q1 0.5 0
a1 v1 0.5 0
a1 z1 0.5 0
a1 s1 0.5 0
a1 w1 0.5 0
a1 u1 0.5 0
其中前两列为传播实体,第三列为实体间传播概率,最后一列为0代表同一网络传播,为1代表网络间自传播。

下来要进行优化:
1.采用独立级联模型,设置阈值
2.将最大路径改为最短路径,利用log

    Derniers téléchargements
    Plus>
    effets Web
    Code source du site Web
    Matériel du site Web
    Modèle frontal
    À propos de nous Clause de non-responsabilité Sitemap
    Site Web PHP chinois:Formation PHP en ligne sur le bien-être public,Aidez les apprenants PHP à grandir rapidement!