目錄

１、環境配置

２、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实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。