数据挖掘 - 如何用python实现《多社交网络的影响力最大化问题分析》中的算法？

问题描述

作为一名python小白，导师让我用python实现论文中的算法，对于其中所要求的技术点以及如何实现算法显得一头雾水。目前python过完廖老师的python教程，正在看networkx文档。望各位帮我解决以下问题：1.实现算法所要求技术点2.如何应对此类论文3.数据挖掘方向学习建议

论文地址 ： http://cjc.ict.ac.cn/online/o...

问题解答

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

# _*_ coding:utf-8 _*_# ==================================================================================## Description: Influence Maximization on Multiple Social Networks## ==================================================================================import matplotlib.pyplot as plt import networkx as nximport 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 = 0while (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 += 1else: 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 selflistdef 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 longestpathdef is_self_transmit_node(u, v): ’’’ 判断目标节点不为起始节点的自传播点 ’’’ flag = 0 #获得起始节点的所有自传播点 selflist = get_self_node(gllist, v) for x in selflist:if u == x: flag = 1 return flagdef single_strong_infl(longestpath): ’’’ 计算起始点到实体的传播概率（影响强度）,返回影响强度stronginfl ’’’ temp = 1 for x in longestpath:temp *= 1-x stronginfl = 1-temp return stronginfldef 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 = 1else: longestpath = [] #遍历种子集合 for s in S:#初始化路径权值与最大路径权值val_path = 1max_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#重置路径权值为1val_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 uSevgaindef 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.txta1 b1 0.2 0a1 c1 0.8 0a2 b2 0.4 0a2 d2 1 0b1 c1 0.7 0c2 a2 0.8 0d2 b2 0.6 0a1 a2 1 1a2 a1 0.1 1....a1 l1 0.5 0a1 m1 0.5 0a1 q1 0.5 0a1 v1 0.5 0a1 z1 0.5 0a1 s1 0.5 0a1 w1 0.5 0a1 u1 0.5 0其中前两列为传播实体，第三列为实体间传播概率，最后一列为0代表同一网络传播，为1代表网络间自传播。

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