社交网络影响力最大化——线性阈值模型（LT模型）算法实现（Python实现）

目录

１、环境配置

２、LT传播模型算法实现

３、LT传播模型算法测试

４、测试文件Wiki-Vote.txt数据

---

社交网络影响力最大化——线性阈值模型（LT模型）算法实现（Python实现）

１、环境配置

环境配置：Win7 Pycharm Anaconda2

该算法每个节点的阈值设为 0.5

２、LT传播模型算法实现

linear_threshold.py (LT传播模型算法)

# -*- coding: utf-8 -*- """ Implement linear threshold models 社交网络影响力最大化 传播模型——线性阈值（LT）模型算法实现 """ import copy import itertools import random import math import networkx as nx__all__ = ['linear_threshold']#------------------------------------------------------------------------- # Some Famous Diffusion Models #-------------------------------------------------------------------------def linear_threshold(G, seeds, steps=0): #LT线性阈值算法"""Parameters----------G : networkx graph #所有节点构成的图The number of nodes.seeds: list of nodes #子节点集The seed nodes of the graphsteps: int #激活节点的层数（深度），当steps<=0时，返回子节点集能激活的所有节点The number of steps to diffuseWhen steps <= 0, the model diffuses until no more nodescan be activatedReturn------layer_i_nodes : list of list of activated nodeslayer_i_nodes[0]: the seeds #子节点集layer_i_nodes[k]: the nodes activated at the kth diffusion step #该子节点集激活的节点集Notes-----1. Each node is supposed to have an attribute "threshold". If not, thedefault value is given (0.5). #每个节点有一个阈值，这里默认阈值为：0.52. Each edge is supposed to have an attribute "influence". If not, thedefault value is given (1/in_degree) #每个边有一个权重值，这里默认为：1/入度References----------[1] GranovetterMark. Threshold models of collective behavior.The American journal of sociology, 1978."""if type(G) == nx.MultiGraph or type(G) == nx.MultiDiGraph:raise Exception( \"linear_threshold() is not defined for graphs with multiedges.")# make sure the seeds are in the graphfor s in seeds:if s not in G.nodes():raise Exception("seed", s, "is not in graph")# change to directed graphif not G.is_directed():DG = G.to_directed()else:DG = copy.deepcopy(G) # copy.deepcopy 深拷贝 拷贝对象及其子对象# init thresholdsfor n in DG.nodes():if 'threshold' not in DG.node[n]:DG.node[n]['threshold'] = 0.5elif DG.node[n]['threshold'] > 1:raise Exception("node threshold:", DG.node[n]['threshold'], \"cannot be larger than 1")# init influencesin_deg = DG.in_degree() #获取所有节点的入度for e in DG.edges():if 'influence' not in DG[e[0]][e[1]]:DG[e[0]][e[1]]['influence'] = 1.0 / in_deg[e[1]] #计算边的权重elif DG[e[0]][e[1]]['influence'] > 1:raise Exception("edge influence:", DG[e[0]][e[1]]['influence'], \"cannot be larger than 1")# perform diffusionA = copy.deepcopy(seeds)if steps <= 0:# perform diffusion until no more nodes can be activatedreturn _diffuse_all(DG, A)# perform diffusion for at most "steps" rounds onlyreturn _diffuse_k_rounds(DG, A, steps)def _diffuse_all(G, A):layer_i_nodes = [ ]layer_i_nodes.append([i for i in A])while True:len_old = len(A)A, activated_nodes_of_this_round = _diffuse_one_round(G, A)layer_i_nodes.append(activated_nodes_of_this_round)if len(A) == len_old:breakreturn layer_i_nodesdef _diffuse_k_rounds(G, A, steps):layer_i_nodes = [ ]layer_i_nodes.append([i for i in A])while steps > 0 and len(A) < len(G):len_old = len(A)A, activated_nodes_of_this_round = _diffuse_one_round(G, A)layer_i_nodes.append(activated_nodes_of_this_round)if len(A) == len_old:breaksteps -= 1return layer_i_nodesdef _diffuse_one_round(G, A):activated_nodes_of_this_round = set()for s in A:nbs = G.successors(s)for nb in nbs:if nb in A:continueactive_nb = list(set(G.predecessors(nb)).intersection(set(A)))if _influence_sum(G, active_nb, nb) >= G.node[nb]['threshold']:activated_nodes_of_this_round.add(nb)A.extend(list(activated_nodes_of_this_round))return A, list(activated_nodes_of_this_round)def _influence_sum(G, froms, to):influence_sum = 0.0for f in froms:influence_sum += G[f][to]['influence']return influence_sum

３、LT传播模型算法测试

test_linear_threshold.py（LT模型算法测试）

#!/usr/bin/env python # coding=UTF-8 #支持中文字符需要添加 coding=UTF-8 from nose.tools import * from networkx import * from linear_threshold import * import time """Test Diffusion Models ---------------------------- """ if __name__=='__main__':start=time.clock()datasets=[]f=open("Wiki-Vote.txt","r") #读取文件数据（边的数据）data=f.read()rows=data.split('\n')for row in rows:split_row=row.split('\t')name=(int(split_row[0]),int(split_row[1]))datasets.append(name) #将边的数据以元组的形式存放到列表中G=networkx.DiGraph() #建立一个空的有向图GG.add_edges_from(datasets) #向有向图G中添加边的数据列表layers=linear_threshold(G,[6],2) #调用LT线性阈值算法，返回子节点集和该子节点集的最大激活节点集del layers[-1]length=0for i in range(len(layers)):length =length+len(layers[i])lengths=length-len(layers[0]) #获得子节点的激活节点的个数（长度）end=time.clock()#测试数据输出结果print(layers) #[[25], [33, 3, 6, 8, 55, 80, 50, 19, 54, 23, 75, 28, 29, 30, 35]]print(lengths) #15print('Running time: %s Seconds'%(end-start)) #输出代码运行时间

社交网络影响力最大化（Python实现）及Wiki-Vote数据集资源下载：

社交网络影响力最大化（Python实现）及Wiki-Vote数据集-机器学习文档类资源-CSDN下载

本人博文社交网络影响力最大化项目实战基础学习

1、社交网络影响力最大化（独立级联（IC）模型和线性阈值（LT）模型）介绍

2、社交网络影响力最大化—线性阈值模型（LT模型）算法实现（Python实现)

3、社交网络影响力最大化—贪心算法实现（Python实现）

4、社交网络影响力最大化项目实战源代码和Wiki-Vote数据集下载

交流学习资料共享欢迎入群：955817470（群一），801295159（群二）

总结

以上是生活随笔为你收集整理的社交网络影响力最大化——线性阈值模型（LT模型）算法实现（Python实现）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。