西安交通大学运筹学大作业报告

1、运筹学大作业报告 【问题】给定一个弱连通的有向网络，包含 1377 个节点network_nodes.txt和 2279条边network_edges.txt。此次的信息传播优化问题描述如下：1. 如何选择 10 个初始节点，使得信息的传播范围最广？【关键词】社会网络、信息传播、独立级联模型【研究背景】社会网络社会网络是指社会个体成员之间因为互动而形成的相对稳定的关系体系。社会网络以个人为节点node构成社会结构，人与人之间通过相互依赖关系联结起来。相互依赖关系可能是朋友关系、同学关系、生意伙伴关系、种族信仰关系等。一个社会网络可以用一张网络图来表示， 其中节点 node 代表人， 边 edg

2、e代表人与人之间的关系。如果两节点之间的关系是双方对等的例如朋友关系、同学关系等 ，那么边为无向边；如果两节点之间的关系是不对等的例如微博的关注关系、论文的引用关系等 ，那么边为有向边，从一个节点指向另一个节点。社会网络中的信息传播信息在社会网络中以个人节点为载体，沿着节点之间的边进行传播。信息传播的方向与边的指向一致。在网络中，从不同节点开始传播的信息，其传播效果可能大不相同。社会网络中的信息传播优化问题所要讨论的就是如何选择起始的传播节点，使得信息能获得最大范围的传播或到达指定的范围。独立级联模型社会网络中的信息传播过程可以用独立级联模型来描述。该模型将整个社会网络看做一个有向图 G( V

3、, E) ，其中 V 是所有节点的集合， E 是所有边的集合。 每条边有一个传播概率 p,0 p 1 ， 即信息有概率 p 可以沿着某条边从一个节点传播到另一个节点。在此假设所有边的传播概率都相同。信息传播的过程如下：在 t =0 时刻，信息从某些节点开始第一次传播。这些初始节点被认为是处于激活状态，构成初始激活集合S0 。在 t =1 时刻，集合S0 中的节点vS0 可以将信息以概率 p 传播给它们未被激活的邻居节点u S0 邻居节点即有边与之相连的节点，信息传播方向与边的指向一致 。如果传播成功，即 u 被激活，那么 u 将被参加 t =1 时刻的激活集合S1 。集合S1 包含S0 中的所

4、有节点，以及在t1 时刻被激活的所有节点。在 t 时刻， 集合St1中的节点vSt-1 可以将信息以概率 p 传播给它们未被激活的邻居节点uSt-1 。如果传播成功，即 u 被激活，那么 u 将被参加 t 时刻的激活集合St 。 集合St 包含uSt-1 中的所有节点， 以及在 t 时刻被激活的所有节点。不同节点的激活过程相互独立，互不影响。已被激活的节点将永远处于激活状态，未被激活的节点不具备记忆性，下一次有同样的概率 p 被激活。当网络中没有新的节点被激活时，传播过程停止。【程序】lj=zeros(1377,1377);for i=1:1179 m=1; n=1; for j=1:1377

5、 if e(i,1)v(j,1)&e(i,2)v(j,1) m=m+1;n=n+1; elseif e(i,1)v(j,1)&e(i,2)=v(j,1) m=m+1;n=n; elseif e(i,1)v(j,1) m=m;n=n+1; else m=m;n=n; end end lj(m,n)=1;End /建立邻接矩阵，把节点按从小到大排列并把有向图的边化为邻接矩阵上的点，例如第i个节点到第j个节点有边，那么lji，j=1s=zeros(1377,1377);for k=1:1377 s(k,k)=1; for c=1:8 for q=1:1377 if s(k,q)=1 for i=1:

6、1377 if lj(q,i)=1&s(k,i)=0 r= fix(rand(1)*4); if r=0 s(k,i)=1; end end end end end endEnd /建立一个s矩阵，第i行代表第i个节点作为起始点，对应的第j列为是否把信息传到达第j个节点。对于每个节点作为起始点进行遍历，对于每一次循环，查找该行中的1元素，表示该元素接受到信息，再对该元素在lj矩阵中进行查找，如果有以该元素起始的边，那么在0-4中生成一个随机数r，如果r=0，表示 传递成功，把边的终止节点在s矩阵中对应的值赋值为1quan=sum(s=0,2);u,i=sort(quan);sj=nchoose

7、k(1:18,10);for hang=1:43758 ui=0; for lie=1:10 yuan=sj(hang,lie); weizhi=1378-yuan; ywz=i(weizhi); io=s(ywz,:); ui=ui+io; end yui=sum(ui=0,2); tyu(hang,1)=yui;endzdz,a=max(tyu);ans=sj(a,:);bjs=1378 1378 1378 1378 1378 1378 1378 1378 1378 1378;fans=bjs-ans;for kll=1:10 qwer=fans(1,kll); ffans(kll,1)=

8、i(qwer);endfor dcv=1:10 tttt=ffans(dcv,1); fffans(dcv,1)=gg(tttt);endffansfffanszdz/比拟s矩阵中每一行非零元的个数即为每个元素作为起始元素时所能传播的范围，我们取最大的18个节点，对这个18个数中取10个的组合进行穷举，计算每一个组合中10个节点在s矩阵中对应行的和，再计算非零元个数，得出最大值，并通过找出最大值所对应的组合，来断定最大值所对应的节点，由于matlab显示数据有位数限制，我们在excel中对数据进行排序，通过对应的位置找出数据【结果与分析】测试效果欠佳，一些点不太准确。但计算速度很快，实时性好。改良方法，增加模拟次数，取最终结果中出现频率最高的十个点，可以减小随机误差。【总结】这次我们小组运用独立级联模型来解决社会网络中的信息传播优化问题。刚开始的时候我们想通过计算期望的方法来研究不同初始点开始传播信息对社会网络的影响，但这种方法运算量大，不利于快速处理，后来我们想到用Matlab生成随机数的方法来代替传播概率，模拟传播过程，这种方法比拟简便，但却具有较大的随机误差，在选取