#?-*-?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?graph

??steps:?int?????????????????????????????#激活節點的層數（深度），當steps<=0時，返回子節點集能激活的所有節點
??????The?number?of?steps?to?diffuse
??????When?steps?<=?0?the?model?diffuses?until?no?more?nodes
??????can?be?activated

??Return
??------
??layer_i_nodes?:?list?of?list?of?activated?nodes
????layer_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?the
?????default?value?is?given?（0.5）.????#每個節點有一個閾值，這里默認閾值為：0.5
??2.?Each?edge?is?supposed?to?have?an?attribute?“influence“.??If?not?the
?????default?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?graph
??for?s?in?seeds:
????if?s?not?in?G.nodes（）:
??????raise?Exception（“seed“?s?“is?not?in?graph“）

??#?change?to?directed?graph
??if?not?G.is_directed（）:
????DG?=?G.to_directed（）
??else:
????DG?=?copy.deepcopy（G）????????#?copy.deepcopy?深拷貝?拷貝對象及其子對象

??#?init?thresholds
??for?n?in?DG.nodes（）:
????if?‘threshold‘?not?in?DG.node[n]:
??????DG.node[n][‘threshold‘]?=?0.5
????elif?DG.node[n][‘threshold‘]?>?1:
??????raise?Exception（“node?threshold:“?DG.node[n][‘threshold‘]?\
??????????“cannot?be?larger?than?1“）

??#?init?influences
??in_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?diffusion
??A?=?copy.deepcopy（seeds）
??if?steps?<=?0:
????#?perform?diffusion?until?no?more?nodes?can?be?activated
????return?_diffuse_all（DG?A）
??#?perform?diffusion?for?at?most?“steps“?rounds?only
??return?_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_

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2018-05-21?15:34??Linear_Threshold\
?????目錄???????????0??2018-05-21?15:34??Linear_Threshold\Linear_Threshold\
?????文件????????4354??2018-03-24?09:37??Linear_Threshold\Linear_Threshold\linear_threshold.py
?????文件????????4273??2018-03-24?09:37??Linear_Threshold\Linear_Threshold\linear_threshold_clime.py
?????文件????????5519??2018-03-24?09:37??Linear_Threshold\Linear_Threshold\LT_improve.py
?????文件?????????103??2018-05-21?15:36??Linear_Threshold\Linear_Threshold\readme.txt
?????文件????????1348??2018-03-24?09:37??Linear_Threshold\Linear_Threshold\test_linear_threshold.py
?????文件????????2766??2018-03-24?09:37??Linear_Threshold\Linear_Threshold\test_linear_threshold_clime.py
?????文件?????????261??2018-03-24?09:37??Linear_Threshold\Linear_Threshold\Wiki-Vote.txt