复杂网络模型及形成机制探讨.ppt

复杂网络形成机制及建模探讨 复杂网络现象 复杂网络出现在自然系统或人造系统的各个领域 复杂网络现象(续) Internet(路由器，线路) WWW (web页面，超连接) 文章合作网络(作者，合作关系) 食物链(动物，捕食关系) 化学反应(分子，发生化学反应) …… 复杂网络的形成机制 自组织 孤立个体 优先粘贴 生长 涌现 高层次个体 高层次增长 网络增长的层次性 复杂网络形成的约束机制 老节点的年龄 建立连接的成本和节点的连接容量 节点类型因素 复杂网络建模规则 David J. Aldous 提出建立复杂网络模型应当遵循三条原则： 形式化 即对任何一个系统都要找到一个合理的数学公式来描述 适应性 即通过适当地调整模型的参数能够得到模型统计参数的变化 自然性 即网络模型的统计属性应该自然演化自一些简单的数学结构，而不是在模型中定义的 几个重要的复杂网络模型 随机网络模型 小世界网络模型 无标度网络模型 随机网络模型 Input: (n,p) n 是节点个数，p是边出现的概率。 算法 从n个孤立点开始 对任意一对顶点，以概率p连接。 随机网络的特征 (1) 聚集系数较小； (2) 网络平均距离小； (3) 节点度服从Poisson分布。 随着概率p 从0到1逐渐增加，网络的某些性质会突然出现。 Watts-Strogatz小世界模型 Input: (n, k ,p) n是网络节点数。每个节点与自己的第k个邻居建立无向连接。p是每条边被重置的概率。 算法 (1) 初始化时，n个初始节点均匀分布在圆周上，每个节点与自己的第k个邻居建立连接 (2) 对每条初始化后的边，以概率p用一条随机边取代。 Watts-Strogatz小世界模型（续） 无标度网络模型 Input: (n0, m, t) n0是网络的初始节点数。m (m ≤ n0)是每当一个新节点接入到网络中，该新节点所带的连接数。 t表示接入的新节点的个数。 算法: (1) 初始化，引入n0个孤立节点 (2) 对下面步骤执行t次：加入一个新节点v， v带有m条边连向已存在于网络中的m个节点。对任意一个已存在节点i，它与v建立连接的概率是： p(ki) (p(ki) =ki/∑kj)。 用模拟的方式动态建模 网络在t时刻的 状态无法用精确的解析表达式来预测。 无法通过构建系统的目标解析函数来优化系统性能。 复杂网络动态建模过程 如何计算已有节点被新节点选择的概率（考虑度、距离、成本等） 适当引入随机因素 新加入节点带来的某些边随机连向已有节点。 复杂网络动态建模过程（续） 谢谢！ * 复杂网络形成机制及建模研究 * 报告人:曹继伟 导 师: 刘玉华教授 华中师范大学计算机科学系 2005年3月 网络生长具有两个方向：自上而下、自下而上 高层主体－高层主体 低层主体－低层主体 高层主体－底层主体 规则 小世界 随机 P＝0 P＝1 随机性增强 节点的加入规则 网络拓扑演化 拓扑性能评价 修改规则 将规则写入仿真程序 提取网络相关参数 建立反馈机制