Perlombongan Data - Bagaimana untuk menggunakan python untuk melaksanakan algoritma dalam "Analisis Masalah Memaksimumkan Pengaruh Pelbagai Rangkaian Sosial"?

Question

Sebagai pemula python, pengajar saya meminta saya menggunakan python untuk melaksanakan algoritma dalam kertas saya keliru tentang perkara teknikal yang diperlukan dan bagaimana untuk melaksanakan algoritma. Pada masa ini, saya telah menyelesaikan tutorial Python oleh Teacher Liao dan sedang membaca dokumentasi networkx. Saya harap anda dapat membantu saya menyelesaikan masalah berikut: 1. Laksanakan algoritma...

黄舟 · Answer

Selepas seminggu, pada mulanya kod tambahan tidak cukup cantik dan tidak cekap Tolong beri saya nasihat

# _*_ 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 '
'


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 02
a2 b2 0.8 02 1 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
a1 w1 pertama disenaraikan sebagai Penyebaran entiti, lajur ketiga mewakili kebarangkalian penyebaran antara entiti, lajur terakhir mewakili 0 untuk penyebaran dalam rangkaian yang sama, dan 1 mewakili penyebaran sendiri antara rangkaian.

Langkah seterusnya ialah mengoptimumkan:
1. Gunakan model lata bebas dan tetapkan ambang
2. Tukar laluan maksimum kepada laluan terpendek dan gunakan log