复杂网络形成机制和建模探讨.ppt

《复杂网络形成机制和建模探讨.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、复杂网络形成机制及建模探讨报告人:曹继伟导师:刘玉华教授华中师范大学计算机科学系2005年3月1复杂网络现象复杂网络出现在自然系统或人造系统的各个领域2复杂网络现象(续)Internet(路由器，线路)WWW(web页面，超连接)文章合作网络(作者，合作关系)食物链(动物，捕食关系)化学反应(分子，发生化学反应)……3复杂网络的形成机制自组织孤立个体优先粘贴生长涌现高层次个体高层次增长4网络增长的层次性网络生长具有两个方向：自上而下、自下而上高层主体－高层主体低层主体－低层主体高层主体－底层主体5复杂网络形成的约束机制老节点的年龄建立连接的成本和

2、节点的连接容量节点类型因素6复杂网络建模规则DavidJ.Aldous提出建立复杂网络模型应当遵循三条原则：形式化即对任何一个系统都要找到一个合理的数学公式来描述适应性即通过适当地调整模型的参数能够得到模型统计参数的变化自然性即网络模型的统计属性应该自然演化自一些简单的数学结构，而不是在模型中定义的7几个重要的复杂网络模型随机网络模型小世界网络模型无标度网络模型8随机网络模型Input:(n,p)n是节点个数，p是边出现的概率。算法从n个孤立点开始对任意一对顶点，以概率p连接。9随机网络的特征(1)聚集系数较小；(2)网络平均距离小；(3)节点度

3、服从Poisson分布。随着概率p从0到1逐渐增加，网络的某些性质会突然出现。10Watts-Strogatz小世界模型Input:(n,k,p)n是网络节点数。每个节点与自己的第k个邻居建立无向连接。p是每条边被重置的概率。算法(1)初始化时，n个初始节点均匀分布在圆周上，每个节点与自己的第k个邻居建立连接(2)对每条初始化后的边，以概率p用一条随机边取代。11Watts-Strogatz小世界模型（续）规则小世界随机P＝0P＝1随机性增强12无标度网络模型Input:(n0,m,t)n0是网络的初始节点数。m(m≤n0)是每当一个新节点接入到

4、网络中，该新节点所带的连接数。t表示接入的新节点的个数。算法:(1)初始化，引入n0个孤立节点(2)对下面步骤执行t次：加入一个新节点v，v带有m条边连向已存在于网络中的m个节点。对任意一个已存在节点i，它与v建立连接的概率是：p(ki)(p(ki)=ki/∑kj)。13用模拟的方式动态建模网络在t时刻的状态无法用精确的解析表达式来预测。无法通过构建系统的目标解析函数来优化系统性能。14复杂网络动态建模过程如何计算已有节点被新节点选择的概率（考虑度、距离、成本等）适当引入随机因素新加入节点带来的某些边随机连向已有节点。15复杂网络动态建模过程（续

5、）节点的加入规则网络拓扑演化拓扑性能评价修改规则将规则写入仿真程序提取网络相关参数建立反馈机制16谢谢！17