Data Mining – Wie implementiert man den Algorithmus in „Analyse des Einflussmaximierungsproblems mehrerer sozialer Netzwerke' mit Python?

Question

Als Python-Neuling bat mich mein Lehrer, den Algorithmus in der Arbeit mit Python zu implementieren. Ich war verwirrt über die erforderlichen technischen Punkte und die Implementierung des Algorithmus. Derzeit habe ich das Python-Tutorial von Lehrer Liao in Python bestanden und lese derzeit die Dokumentation zu networkx.
Ich hoffe, Sie können mir bei der Lösung der folgenden Probleme helfen:
1. Technische Punkte, die zur Implementierung des Algorithmus erforderlich sind
2 Wie man mit dieser Art von Arbeit umgeht
3

黄舟 · Answer

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

# _*_ 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 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代表网络间自传播。