复杂网络仿真
- 格式：docx
- 大小：95.90 KB
- 文档页数：4
模型仿真：
1.仿真整体思想
对于题中模型，我们不能采用传统的直接仿真的策略，因为计算规模太大，无法在短时间内实现对其的仿真。
必须降低仿真数据的规模才能进行数据仿真。
根据社交网络有小世界网络的特性，可以知道，相识的人之间拥有相类似的朋友。
所以我们可以将所有用户划归到数个好友圈当中去。
以好友圈为单位，进行模型的仿真，这样我们可以很大限度的降低仿真规模。
我们采用的仿真解决方案流程图如下：
2.仿真具体步骤
1）随机网络的生成
根据无标度网络的特性，我们将节点度数按照
23
p k m k-
=其中
()2,m=60
的幂律分布生成一张5,000,000个节点的无标度网络。
2）CPM聚类算法
复杂网络聚类是一个研究的热点问题，现根据本题实际情况我们选用CPM算法[1]，以实现对重叠网络结构簇的聚类（因为同一个人可能属于多个的朋友圈子）。
该算法的基本假设是[2]:网络簇由多个相邻的k-团(k-clique)组成,相邻的两个k-团，至少共享k−1个节点,每个k-团唯一地属于某个网络簇,但属于不同网络簇的k-团可能会共享某些节点.基于以上启发式信息,CPM 算法通过如下步骤识别出重叠网络簇结构:(1) 对给定的参数K,计算出网络中的全部k-团(k≤K),并建立团-团重叠矩阵(clique-clique overlap matrix);(2) 根据以上矩阵,计算出重叠网络簇结构。
由文献[2]提供几种复杂网络聚类算法的效率比对图，可看出该算法具有较高的效率：
Fig.1 Actual running time of algorithms against networks with different scales 所以在此种情况下，我们选用CPM算法能在保证解决问题针对性的前提下，而且可以将元胞空间维度降低到2维，还提高算法效率，实为上佳选择。
3）元胞自动机仿真
元胞自动机是一种离散的动力系统，适用于本题模型的仿真。
现将此次元胞自动机仿真设计描述如下。
①元胞：朋友圈（CPM聚类产生的重叠网络结构网络簇）
②元胞状态：{0,1}，其中0代表该朋友圈内未盛行该消息，1代表该朋友圈已盛行该消息。
关于消息在某个朋友圈内盛行与否，我们可以作如下解释。
由
21
(125%)199.74%
-<-
和3σ小概率事件原则可知，某人只要看过21次该消息就基本上会转发该消息。
假定任何
人在其任一朋友圈内认识的人数占该朋友圈比例为β以上。
则该朋友圈内只需有21
β的人转
发该消息，该消息就会在该朋友圈盛行（转发开去）。
③元胞邻居：由于CPM算法产生的网络簇具有2维空间的特点，所以这里元胞空间是2维的。
故可以选用Moore邻居模型。
④变换规则：根据每一个朋友圈的人数不同，定义两个朋友圈之间的影响力与各自人数分别成正相关。
当然，只有状态为1的元胞具有影响其他元胞的能力。
当某状态为0的中心元胞被邻居影响力的和大于某个阈值时，我们就认为它的状态将在下一时刻转化为1。
经估算和实验，应用朋友圈缩小规模后，做元胞自动机仿真，大约能将仿真算法复杂度
降低到
1.5
()~()
o N o N的水平（其中N为初始网络中的节点数目）。
4）统计仿真结果并给出结论
根据10次仿真的结果统计各个结果（天数）出现的次数，并从中找到80%概率知道该消息的结果（天数）。
3.仿真结果
在这里，我们只选取了第（1）问的情形做了仿真模拟。
通过上述仿真方法，我们得到了如下结果。
Fig 2. The times of different result appearing
从上图中，我们可以的出结论当消息传播进行到第二天的时候，B以80%的概率知道A 发出的消息是2天的时候。
[1] Palla G, Derenyi I, Farkas I, Vicsek T. Uncovering the overlapping community structures of complex networks in nature and society. Nature, 2005,435(7043):814−818.
[2]YANG Bo1,2, LIU Da-You1,2+, LIU Jiming3, JIN Di1,2, MA Hai-Bin1,2. Complex Network Clustering Algorithms . Journal of Software Vol.20, No.1, January 2009。
