49
个编辑
更改
跳到导航
跳到搜索
第1,288行：
第1,288行： − + − 传统随机图模型假设网络的平均度保持常数，即边数随节点数线性增长。然而实证研究表明，大多数真实网络会随时间逐渐变得更加致密，节点之间的连接数以超线性方式增长。具体而言，网络的边数 [math]\displaystyle e(t)[/math] 与节点数 [math]\displaystyle n(t)[/math] 之间满足幂律关系：+ − + − + + − 在 Leskovec 等人的研究中，涵盖了多种异质系统，包括论文引用网络（arXiv HEP–TH, HEP–PH）、美国专利引用网络（Patents）、互联网自治系统（AS）、作者–论文隶属网络（Affiliation Graphs）及电子邮件通信网络等。+ + + + + + + + + + + + + + + + + + + + + + − + + + + + + +
→复杂网络
== 复杂网络 ==
== 复杂网络 ==
在复杂系统研究中，网络（graph）是一种重要的抽象形式，用于刻画社会、技术、信息系统中的交互关系。Leskovec、Kleinberg 与 Faloutsos（2005, 2007）通过对多种真实网络的时间序列分析，发现复杂网络在演化过程中遵循两条普遍的规模法则：致密化定律（densification law）与收缩直径定律（shrinking diameter law）<ref>Leskovec, J., Kleinberg, J., & Faloutsos, C. (2007). Graph evolution. ''ACM Transactions on Knowledge Discovery from Data'', ''1''(1), 2. <nowiki>https://doi.org/10.1145/1217299.1217301</nowiki></ref> <ref>Leskovec, J., Kleinberg, J., & Faloutsos, C. (2005). Graphs over time. ''Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining'', 177–187. <nowiki>https://doi.org/10.1145/1081870.1081893</nowiki></ref>。这些规律揭示了网络在增长过程中所体现出的自组织特征与临界动力学机制。
在复杂系统研究中，网络（graph）是一种重要的抽象形式，用于刻画社会、技术、信息系统中的交互关系。Leskovec、Kleinberg 与 Faloutsos（2005, 2007）通过对多种真实网络的时间序列分析，发现复杂网络在演化过程中遵循两条普遍的规模法则：致密化定律（densification law）与收缩直径定律（shrinking diameter law）<ref name=":17">Leskovec, J., Kleinberg, J., & Faloutsos, C. (2007). Graph evolution. ''ACM Transactions on Knowledge Discovery from Data'', ''1''(1), 2. <nowiki>https://doi.org/10.1145/1217299.1217301</nowiki></ref> <ref name=":18">Leskovec, J., Kleinberg, J., & Faloutsos, C. (2005). Graphs over time. ''Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining'', 177–187. <nowiki>https://doi.org/10.1145/1081870.1081893</nowiki></ref>。这些规律揭示了网络在增长过程中所体现出的自组织特征与临界动力学机制。
=== 致密化幂律（densification law） ===
=== 致密化幂律（densification law） ===
传统随机图模型假设网络的平均度保持常数，即边数随节点数线性增长。然而研究表明，大多数真实网络会随时间逐渐变得更加致密，节点之间的连接数以超线性方式增长。具体而言，网络的边数 [math]\displaystyle e(t)[/math] 与节点数 [math]\displaystyle n(t)[/math] 之间满足幂律关系：
[math]\displaystyle e(t) \propto n(t)^{a}, \quad 1<a<2.[/math]
[math]\displaystyle e(t) \propto n(t)^{a}, \quad 1<a<2.[/math] <ref name=":17" />
其中 [math]\displaystyle a[/math] 称为致密化指数（densification exponent）。当 [math]\displaystyle a=1[/math] 时，平均度保持不变；当 [math]\displaystyle a=2[/math] 时，网络接近完全图。大量实证结果显示 [math]\displaystyle a[/math] 稳定地处于 1 与 2 之间，表明平均度随时间单调上升。
其中 [math]\displaystyle a[/math] 称为致密化指数（densification exponent）。当 [math]\displaystyle a=1[/math] 时，平均度保持不变；当 [math]\displaystyle a=2[/math] 时，网络接近完全图。大量实证结果显示 [math]\displaystyle a[/math] 稳定地处于 1 与 2 之间，表明平均度随时间单调上升。在 Leskovec 等人的研究中，涵盖了多种异质系统，包括论文引用网络（arXiv HEP–TH, HEP–PH）、美国专利引用网络（Patents）、互联网自治系统（AS）、作者–论文隶属网络（Affiliation Graphs）及电子邮件通信网络等。
[[文件:DensificationLaw.png|无|缩略图|图 2：几个图的边数 e(t) 与节点数 n(t) 的关系图（双对数坐标）。所有 4 个图均符合密度幂律，拟合效果良好。斜率分别为：a = 1.68、1.66、1.18 和 1.15。]]
=== 收缩直径定律（Shrinking Diameter Law） ===
<nowiki>另一项发现是，网络的有效直径（effective diameter）并非随着规模扩张而增长，而是随时间减小。有效直径定义为网络中 90% 可达节点对之间的最短路径长度 [math]\displaystyle D_{\text{eff}}[/math]：</nowiki>
<nowiki>[math]\displaystyle D_{\text{eff}} = \min{d : g(d) \ge 0.9},[/math] </nowiki><ref name=":18" />
其中 [math]\displaystyle g(d)[/math] 表示距离不超过 [math]\displaystyle d[/math] 的节点对比例。
<nowiki>在所有实测网络（包括 arXiv、Patents、AS 等）中，随着时间推移， [math]\displaystyle D_{\text{eff}}(t)[/math] 呈现单调下降或先降后稳的趋势。例如在 HEP–TH 引用网络中，平均最短路径从约 8 减至 5，而在 AS 网络中，从 4.2 降至 3.8。这一规律表明，随着网络增长，信息或影响在系统中传播的路径反而更短，网络呈现出“超小世界”特性。</nowiki>
[[文件:Shrinking Diameter Law.png|无|缩略图|图 3：有效直径随时间的变化。]]
=== 生成机制：社区引导与森林火灾模型 ===
为解释上述规模现象，研究者提出了两类生成模型。
（一）社区引导附着模型（Community Guided Attachment, CGA）
假设网络节点嵌套于层级化的社区结构中，跨社区形成连接的概率随层级深度 [math]\displaystyle d[/math] 指数性衰减。若跨层连接概率为 [math]\displaystyle p(l) \propto c^{-l}[/math]，则可推出网络的边数与节点数满足：
[math]\displaystyle e(t) \propto n(t)^{a}, \quad a = 1+\frac{1}{(1+\alpha)d},[/math] <ref name=":18" />
其中 [math]\displaystyle \alpha[/math] 为社区紧密度参数。当 [math]\displaystyle \alpha[/math] 较小时，跨社区连接容易形成，系统趋向超线性致密化；当 [math]\displaystyle \alpha[/math] 较大时，网络增长趋近线性。
（二）森林火灾模型（Forest Fire Model）
=== 收缩直径定律（Shrinking Diameter Law） ===
为同时解释致密化与收缩直径，Leskovec 等人提出了森林火灾模型。新节点以概率 [math]\displaystyle p_f[/math]（前向燃烧）与 [math]\displaystyle p_b[/math]（反向燃烧）递归连接到已有节点及其邻居：新节点选择一个“点火节点”；按概率 [math]\displaystyle p_f[/math] 连接其出邻居，按 [math]\displaystyle p_b[/math] 连接其入邻居；对新连接的节点重复此过程，直到燃烧终止。
模型模拟表明，在特定参数区域，网络自发满足：
<nowiki>[math]\displaystyle e(t)\propto n(t)^{a}, \quad 1<a<2, \qquad D_{\text{eff}}(t)\downarrow, [/math] </nowiki><ref name=":18" />
即同时实现超线性致密化与直径收缩。这一过程存在相变：当 [math]\displaystyle p_f[/math] 太小，网络稀疏；过大则迅速饱和；仅在临界区域产生现实网络的拓扑特征。
== 临界态 ==
== 临界态 ==