复杂网络局部结构涌现：共同邻居驱动网络演化

Presentation on theme: "复杂网络局部结构涌现：共同邻居驱动网络演化"— Presentation transcript:

1 复杂网络局部结构涌现：共同邻居驱动网络演化
报告人：崔爱香 导 师：傅 彦 合作者：周 涛 电子科技大学互联网科学中心

2 汇报提纲 研究背景 研究动机 模型构建 数值实验 研究结论

3 研究背景 大量复杂系统都可以通过复杂网络加以描述； 食物链网络 WWW

4 研究背景 对复杂网络演化的实证分析，以及相应的建模研究，是充分认识一切有关复杂网络的功能与应用的基础。
早期，研究者主要关注网络最基本的宏观特性，例如小世界现象、无标度特性等。

5 研究背景 规则网络 随机网络 小世界网络 [1] Erdos P, Renyi A. On the Evolution of Random Graphs. Publ. Math. Inst. Hung. Acad. Sci., 1960, 5:17-60 [2] Watts D J, Strogatz S H. Collective dynamics of small-world networks. Nature, 1998, 393:

6 研究背景 BA模型(增长+优先连接) www N=325729 <k>=5.46
[3] Barabasi A L, Albert R. Emergence of scaling in random networks. Science, 1999, 286:

7 研究背景 HK模型 [4] Holme P, Kim B J. Growing Scale-free Networks with Tunable Clustering. Phys. Rev. E, 2002, 65:

8 研究背景 随着对复杂网络演化模型研究的深入，近年来，研究的焦点开始转移到更为细致的网络局部结构，例如对网络中模块、环、紧密子图等结构的统计分析； 集团(clique)、集团度(clique degree)及其分布

9 研究背景 集团

10 研究背景 集团度

11 研究背景 集团度分布 [5] Xiao W K, Ren J, Qi F, et al. Empirical study on clique-degree distribution of networks. Phys. Rev. E, 2007, 76:

12 研究背景 集团度分布 [5] Xiao W K, Ren J, Qi F, et al. Empirical study on clique-degree distribution of networks. Phys. Rev. E, 2007, 76:

13 研究背景 集团度分布 实证研究发现，大量不同领域中抽象出来的网络都具有近似服从幂律的低阶集团度分布；
随着统计的集团阶数的上升，相应的集团度分布的幂律指数呈下降的趋势；

14 研究动机 研究问题 随机行走模型 如何再现真实网络的集团度分布特征?
[6] Yang H X, Wang B H, Liu J G, et al. Step-by-Step Random Walk Network with Power-Law Clique-Degree Distribution. Chin. Phys. Lett., 2008, 25:

15 模型构建 共同邻居驱动网络演化 实证研究 链路预测
实证研究 链路预测 [7] Kossinets G, Watts D J. Empirical Analysis of an Evolving Social Network. Science, 2006, 311: 88-90 [8] Zhou T, Lü L, Zhang Y C. Predicting missing links via local information. European Physical Journal B, 2009, 71:

16 模型构建 网络演化模型 (1) 初始时网络中包含m0个两两相互连接的节点； (2) 每次引入一个新节点和m条边，其中 ；
(3) 新引入的节点采用优先连接机制建立第一条连边。 (4) 基于共同邻居驱动机制添加其余 条边，考虑网络中所有未连接的节点对，其产生连边的概率正比于这对节点的共同邻居数，即 其中， 和 分别是节点i和节点j的邻点集

17 数值实验 簇系数 平均最短路径 m=m0=3

18 子图(a)-(d)分别对应模型的2至5阶集团度分布
数值实验 集团度分布 m=m0=3 N=10000 子图(a)-(d)分别对应模型的2至5阶集团度分布 指数变化规律与实证研究一致！！！

19 数值实验 集团度分布 BA网络

20 数值实验 集团度分布 HK网络

21 研究结论 本文提出一种基于“共同邻居驱动”的演化机制，相应的演化模型能够很好地再现所观测到的幂律集团度分布，且分布指数也随着集团阶数的增长而下降，与实证观察一致； 本文提供了研究网络局部结构形成机制的范例，所提出的“共同邻居驱动”的演化机制，符合我们对真实网络的认知；

22 谢谢！