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

Question

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

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

Answer 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