《复杂网络形成机制及建模探讨.ppt》由会员分享，可在线阅读，更多相关《复杂网络形成机制及建模探讨.ppt（19页珍藏版）》请在三一文库上搜索。
1、1,复杂网络形成机制及建模探讨,曹继伟 刘玉华华中师范大学计算机科学系,2,复杂网络现象,复杂网络出现在自然系统或人造系统的各个领域,3,复杂网络现象(续),Internet(路由器，线路)WWW (web页面，超连接)文章合作网络(作者，合作关系)食物链(动物，捕食关系)化学反应(分子，发生化学反应),4,复杂网络的形成机制,自组织 孤立个体 优先粘贴 生长涌现 高层次个体 高层次增长,5,网络增长的层次性,网络生长具有两个方向：自上而下、自下而上,高层主体高层主体 低层主体低层主体 高层主体底层主体,6,复杂网络形成的约束机制,老节点的年龄 建立连接的成本和节点的连接容量 节点类型因素,7
2、,复杂网络建模规则,David J. Aldous 提出建立复杂网络模型应当遵循三条原则：形式化 即对任何一个系统都要找到一个合理的数学公式来描述适应性 即通过适当地调整模型的参数能够得到模型统计参数的变化自然性 即网络模型的统计属性应该自然演化自一些简单的数学结构，而不是在模型中定义的,8,几个重要的复杂网络模型,随机网络模型小世界网络模型无标度网络模型,9,随机网络模型,Input: (n,p) n 是节点个数，p是边出现的概率。算法 从n个孤立点开始 对任意一对顶点，以概率p连接。,10,随机网络的特征,(1) 聚集系数较小；(2) 网络平均距离小；(3) 节点度服从Poisson分布。
3、 随着概率p 从0到1逐渐增加，网络的某些性质会突然出现。,11,Watts-Strogatz小世界模型,Input: (n, k ,p) n是网络节点数。每个节点与自己的第k个邻居建立无向连接。p是每条边被重置的概率。算法 (1) 初始化时，n个初始节点均匀分布在圆周上，每个节点与自己的第k个邻居建立连接 (2) 对每条初始化后的边，以概率p用一条随机边取代。,12,Watts-Strogatz小世界模型（续）,规则 小世界 随机,P0,P1,随机性增强,13,无标度网络模型,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)。,14,用模拟的方式动态建模,网络在t时刻的 状态无法用精确的解析表达式来预测。无法通过构建系统的目标解析函数来优化系统性能。,15,复杂网络动态建模过程,如何计算已有节点被新节点选择的概率（考虑度、距离、成本等）适当引入随机因素 新加入节点带来的某些边随机连向已有节点。,16,复杂网络动态建模过程（续）,将规则写入仿真程序,提取网络相关参数,建立反馈机制,17,复杂网络动态建模过程(例子),计算机网络增长过程,1,编写模拟程序,提取拓扑数据,1,考虑到已有节点的时延、带宽、距离及已有节点容量、度、年龄等因素,2,2,每个节点有且仅有判断上面若干个因素的能力。不断有新节点加入,18,展望,利用动态模型，从拓扑机构出发优化网络性能。,19,谢谢！,