西安交通大学Xian Jiao Tong University (XJTU)论文题目：社会网络中的信息传播优化专业 班级：作者 学号：社会网络中的信息传播优化摘要本次实验基于独立级联模型，假定传播概率均为p=1,以CELF算法为基础，用邻接表储存社会网络图，通过提出影响力因子，改进算法，完成了对给定社会网络图的信息传播优化。关键词：独立级联模型 CELF 影响力因子 邻接表引言信息爆炸的时代，任何人都不能独善其身，置于信息网络之外，在网络搭建的交际圈中，我们无时无刻不在处于接受、发送信息的状态。正是因为如此，诞生了一种新的营销模式病毒营销。病毒营销（viral marketing，又称病毒式营销、病毒性营销、基因行销或核爆式行销），是一种常用的网络营销方法，常用于进行网站推广、品牌推广等。考虑到营销成本，为使营销成本最低，需要找出特定的、数量较少的营销初始点，但需要达到营销效果较大化(在此不考虑明星价值的高额性）。为此，需要优化信息在社会网络中的传播。一、 社会网络社会网络是指社会个体成员之间因为互动而形成的相对稳定的关系体系。一个社会网络（如微博）可以用一张图来表示，其中节点（node）代表人，边（edge）代表人与人之间的关注关系，边的方向为信息传播方向（被关注）。信息在社会网络中以个人节点为载体，沿着节点之间的边进行传播。信息传播的方向与边的指向一致。在网络中，从不同节点开始传播的信息，其传播效果可能大不相同。有向图：信息的传播是单向的；无向图：信息的传播是双向的。二、社会网络中信息优化传播的模型在以往的研究中，关于社会网络信息传播优化的研究模型较为流行的主要有独立级联模型和线性阈值模型。本次实验主要采用独立级联模型，故只对独立级联模型进行相关的介绍。级联模型是哥登伯格最早提出的。在级联模型中,每个节点在自身转变为活动状态后,都有一定概率机会去激活其邻居节点。如果成功,则在下一步,其邻居节点变为活动状态。而后，其邻居节点再去激活与其相连的节点，如此反复，直到没有新的节点被激活时，传播停止。独立级联模型是级联模型的一种简单形式。在独立级联模型中,节点在“独立地”接受某一个新活动邻居节点的扩散影响,而与其他节点的扩散影响无关。三、本次实验的研究对象 本次实验主要通过对给定的较小模式的社会网络图进行处理，从而完成实验的两个要求。本次实验的社会网络图包括1377个点和2279条边，具体的社会网络图如下：社会网络图 待解决的问题：1.如何选择10个初始节点，使得信息的传播范围最广？2.如果希望信息的传播能覆盖800个以上的节点，则最少应该选择哪些用户作为传播的起始节点？四、问题的简化与影响力因子问题的简化：假定传播的概率都相等，且传播时无阻尼，即p=1。影响力因子：在本次实验中，社会网络图以邻接表的形式储存，影响力因子是基于每一个节点所对应的邻接表的长度提出的。用字母b表示该因子。b是一个可变量，其表征相应的节点在所有节点中传播范围的大小，其受到其他节点的制约，具体计算方法如下：其中为第个节点的邻接表的子集。五、模型的建立在影响力因子的提出基础上，利用01 规划，可以很容易的建立以下两个模型：（其中a表示0或1，b表示影响力因子）针对问题1：针对问题2：模型的分析：通过对模型的分析，求解该模型可转移到对影响力因子的求解。六、模型的求解算法以下两个算法都是在CELF算法的基础上进行设计的，关于算法的可行性，理论和实践证明，CELF是可行的，在解决NP-hard问题上，CELF算法得出的解可达到最优解的63%。算法1：初始化：nodes=vi|i1,2,.1377;final nodes=；final array=(final_array中将储存将要找到的节点，final_nodes中将储存final_array中的节点作为初始节点能够激活的总的节点）。Step1:寻找影响力因子最大的节点，将其作为初始节点：将图以邻接表的形式储存起来，找出邻接表最长的节点，将其归入集合final_array中，并将其从集合nodes中删除。另外将该节点对应的邻接表中的节点归入到final_nodes中。Step2：处于集合nodes中的节点对应的邻接表与final_nodes做差集，得出新的邻接表，重新计算每个节点的影响力因子，找出影响力因子最大的节点，将其归入final_array中，将其对应的邻接表与final_nodes做并集，得到新的集合final_nodes，并从nodes中删除该节点。Step3：重复步骤2九次后停止。 算法2：初始化：nodes=vi|i1,2,.1377;final nodes=；final array=(final_array中将储存将要找到的节点，final_nodes中将储存final_array中的节点作为初始节点能够激活的总的节点）。Step1:寻找影响力因子最大的节点，将其作为初始节点：将图以邻接表的形式储存起来，找出邻接表最长的节点，将其归入集合final_array中，并将其从集合nodes中删除。另外将该节点对应的邻接表中的节点归入到final_nodes中，若length(final_nodes)=800,停止计算，否则进入下一步。Step2：处于集合nodes中的节点对应的邻接表与final_nodes做差集，得出新的邻接表，重新计算每个节点的影响力因子，找出影响力因子最大的节点，将其归入final_array中，将其对应的邻接表与final_nodes做并集，得到新的集合final_nodes，并从nodes中删除该节点。Step3：若length（final_nodes）800，转回步骤2，否则停止计算。七、程序设计本次实验的程序采用python语言编写，运行平台为Ubuntu64 python 2.7.6 编译平台,虚拟机内存为1G，PC机主频2.4GHZ，运行时间为：问题1：1.5s;问题2：20s左右.具体代码见代码段附录。八、实验结果问题1：想要使得信息的传播范围最广，可选的是个节点为：1667516751, 1722445411, 1253383617, 1497554923, 1518610444, 1657301617, 1080547893, 1400142285, 1623666844, 1258151463；最终的传播范围为97个节点。问题2：若要使得传播范围达到800个节点，需要的初始节点为525个，其中125个节点可以使得传播范围达到400个节点，其他的400个点影响力因子仅为1.九、实验的改进与拓展本次实验是基于独立级联模型且p=1，由于信息在社会网络图中传播会遇到一定的阻力，不可能以p=1的概率将信息传播下去，所以本次实验假设p=1这一假设条件过于理想化。参考文献：1宫秀文. 社交网络影响力最大化传播模型与算法研究D.安徽师范大学,2014.2马寅. 社会网络影响力最大化算法及传播模型的研究D.兰州大学,2012.附录（代码）：算法1：class item: def _init_(self): self.name=0; self.list=; self.influence=1;import xlrdfrom collections import Counterimport timestartTimeStamp=time.time()file_name=xlrd.open_workbook(/home/shitouhe/Desktop/DATA.xls);table1=file_name.sheets()0;table2=file_name.sheets()1;num11=table1.nrows;num12=table1.ncols;num21=table2.ncols;num22=table2.nrows;print table1.nrows ,table2.ncolsarc=0 for col in range(num21) for row in range(num22)for i in range(0,num12): nodes=table1.col_values(i);for i in range(0,len(nodes): nodesi=int(nodesi);arc1=table2.col_values(0);arc2=table2.col_values(1);for i in range(0,num22): arc1i=int(arc1i); arc2i=int(arc2i);print len(list(set(arc1).intersection(set(arc2)arc1.extend(arc2);print len(arc1),len(arc2)for i in range(0,num22): for j in range(0,num21): arcij=int(table2.cell(i,j).value);first delete the isolate nodesarc1=list(set(arc1)nodes=list(set(nodes)print len(arc1),len(nodes)print list(set(nodes).difference(set(arc1)above resulte indicate there is no isolate nodesnext we will find a node which has the greatest influencecompute the influence of every nodesnode=table1.col_values(0);for i in range(len(node): nodei=int(nodei);for i in range(num11): nodesi=item(); nodesi.name=nodei;print nodes3.namearray=for i in range(num11): nodesi.list.append(nodei); for j in range(num22): if arcj0=nodesi.name: nodesi.list.append(arcj1); for k in range(i): if nodesi.name in nodesk.list: nodesk.list.append(arcj1) if arcj1=nodesk.name: nodes