問題描述

作為一名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