复杂网络综述3——网络特性

Answer 1

网络特性综述

随机图模型在无向边被随机分配到节点之间时形成，边出现概率相等，每个节点的连边数服从泊松分布。随机图被广泛研究，形成了众多成果。然而，真实网络的有趣特征与随机网络大相径庭，显示了指导网络形成机制和通过研究网络结构实现特定目标的可能性。

小世界效应在众多网络中被证实，最著名的例子是Stanley Milgram的实验，表明大多数网络中两点间的路径很短，与Frigyes Karinthy在小说中提出的观点相呼应。路径长度公式包含节点间最短路径，利用广度优先遍历在有限时间内计算得出。小世界效应影响动态过程，如信息传播、中继器数量、航班安排和疾病传播，甚至影响室内游戏，如“Erdos数”和“Bacon数”的计算。

小世界网络的定义基于节点接近中心点时度数的增长速率，指数增长表明网络具有小世界效应。Bollobas和Riordan等人的研究表明，在power-law网络中，增长速度不会快于某个特定值。Cohen和Havlin探讨了真实网络可能更慢增长的理论。

在许多网络中，节点A和B相连时，B和C也常相连，即“你朋友的朋友也是你的朋友”现象。聚集系数度量这种可能性的大小，Dorogovtsev, Goltsev,Mendes和 Szabo,Alava,Kertesz等人发现scale-free网络中聚集系数正比于节点度，这一特征在真实网络中也被证实。

节点的度是其连接边的数量，比例定义为在网络中随机选择一条边，其度为k的概率。真实网络的度分布通常右偏，形成长尾。度分布长尾的量化需要特殊技巧，常用的统计方法包括指数间隔统计和累计分布函数。

在scale-free网络中，度分布遵循幂律，广泛存在于引用网络、WWW网、因特网、代谢网络、电话网络和人类性关系网络中。最大度依赖于网络规模，随机删除节点不会显著影响网络结构，但按照节点度的顺序删除却会迅速增加路径长度，显示网络对最大度点的脆弱性。

节点间的连接模式揭示网络的深层次特性，选择性连接在社交网络中表现为相称混合性或同质性。同配性解释了社团现象，相似背景的人更倾向于建立联系。然而，网络可能是同配的，却未表现出明显的社团结构。

社团检测方法如聚类分析和层次聚类，通过边介数等连接强度定义实现。网络中的最大连通分支代表最大交流比例，衡量网络效率，通常等同于最大连通子图。第二大连通分支通常显著小于最大连通分支。

节点的中介中心性也是网络特性之一，Goh等人发现许多网络中节点的介数服从幂律分布。中介中心性有时也反映网络的弹性。