小世界网络模型.ppt

复杂网络简介 LiuChang 目录 背景 基本概念 网络模型 基本有哪些信誉好的足球投注网站算法 目录 背景 技术网络 社会网络 交通运输网络 生物网络 复杂网络研究进程 1736，欧拉：哥尼斯堡七桥→图论 1950，Erdos, Renyi: 随机图论 20世纪60年代末，弱连接的强度(Mark Granovetter) 1998，Strogatz, Barabasi: 小世界实验 世纪之交，新纪元 为什么现在才开始研究复杂网络？ 计算机技术的发展： 使我们拥有各种网络的数据库，并有可能对大规模的网络进行实证研究 普适性的发现： 许多实际网络具有相同的定性性质 且已有的理论不能描述和解释 理论研究的发展 小世界网络 (Small World Network), 无标度网络 (Scale-free Network) 统计物理学的研究手段 目录 基本概念 对网络结构的描述 度（Degree）：朋友的个数 介数（Betweenness）：经过我的最短路径的条数 集聚系数（群系数）（Clustering coefficient）：朋友的朋友还是不是朋友的情况 最短路径（Shortest path）：两个顶点之间边数最少的路径 聚类系数（clustering coefficient） 假设一个节点 有 条边与它相连，这 个节点就是节点 的邻居，则节点的聚类系数就是 的邻居节点互相连接的边数和邻居节点全部连接的所有边数的比值。 clustering coefficient 目录 网络模型 复杂网络的结构 规则网络 小世界网络模型 WS小世界模型构造算法（随机化重连） 1、从最近邻耦合网络开始 2、随机化重连：以概率p随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。 小世界网络模型 NW小世界模型构造算法（随机化加边） 1、一个环状的规则网络开始 2、随机化加边：以概率p在随机选取的一对节点之间加上一条边。其中，任意两个不同节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。 改变p值可以实现从最近邻耦合网络(p=0)向全局耦合网络(p=1)转变。当p足够小和N足够大时，NW小世界模型本质上等同于WS小世界模型。 小世界网络模型 无标度网络 BA无标度模型构造算法 1、增长：从一个具有 个节点 的网络开始，每次引入一个新的节 点，并连到 个已存在的节点上，这里 2、优先连接：一个新节点与一个已经存在的节点 相连接的概率 与节点 的度 ,节点 的度 满足： 目录 基本有哪些信誉好的足球投注网站算法 基本有哪些信誉好的足球投注网站算法 广度优先有哪些信誉好的足球投注网站算法 深度优先有哪些信誉好的足球投注网站算法 最大度有哪些信誉好的足球投注网站算法 随机游走有哪些信誉好的足球投注网站算法 K遍历器随机游走与最大度相结合的混合算法 广度优先有哪些信誉好的足球投注网站算法（BFS） 首先查询源节点的所有邻居节点中是否存在目标节点，若存在，则将其返回给源节点；若不存在，邻居节点将信息专递给它们各自的邻居节点，重复上述过程，直到找到目标节点为止。 深度优先有哪些信誉好的足球投注网站算法（DFS） DFS在源节点的邻居节点中沿着树的深度遍历树的节点,尽可能深的有哪些信誉好的足球投注网站树的分支。 当节点i的所有邻居节点都已经被查询过，有哪些信誉好的足球投注网站将回到把查询信息传递给节点i那个起始节点。 重复这一过程直到已发现目标节点为止。 最大度有哪些信誉好的足球投注网站算法（DS） DS是有哪些信誉好的足球投注网站其邻居中最大节点度的节点。 若该节点是目标节点,则返回信息。 否则,继续有哪些信誉好的足球投注网站最大节点度的节点的邻居节点,直到有哪些信誉好的足球投注网站到目标节点为止。 随机游走有哪些信誉好的足球投注网站算法（RWS） 随机游走算法判断源节点是不是目标节点,如果是,则停止有哪些信誉好的足球投注网站。否则,随机选择一个邻居将信息传送过去,直到找到目标节点为止。 随机游走的有哪些信誉好的足球投注网站步数大,但是在有哪些信誉好的足球投注网站的过程中信息产生量少,这样在网络中就不会产生很大的流量。 3种随机游走算法 1 无限制随机游走 2 不返回上一步节点的随机游走 3 不重复访问节点的随机游走 K遍历器随机游走与最大度相结合的混合算法(KRDS) 网络中每个节点都知道它们邻居节点的信息 源节点随机选择k个邻居节点传送信息,若发现目标节点,则将返回信息。 否则,它们分别选择它们邻居中度最大的节点传递信息。 K遍历器随机游走与最大度相结合的混合算法(KRDS) 如果依然没有有哪些信誉好的足球投注网站到目标节点,则用随机游走进行查询。 重复这个过程直到有哪些信誉好的足球投注网站到目标节点为止。 在该算法中,k有一个约束条件,即它要小于等于当前节点的度数。 对比 “我认为下个世纪将是复杂性的世纪。” ————史