枢纽节点

来自集智百科
跳到导航 跳到搜索

本词条由Ryan初步翻译,已由Alienxj审校。 模板:Redirect

In network science, a hub is a node with a number of links that greatly exceeds the average. Emergence of hubs is a consequence of a scale-free property of networks.[1] While hubs cannot be observed in a random network, they are expected to emerge in scale-free networks. The uprise of hubs in scale-free networks is associated with power-law distribution. Hubs have a significant impact on the network topology. Hubs can be found in many real networks, such as Brain Network or Internet.

In network science, a hub is a node with a number of links that greatly exceeds the average. Emergence of hubs is a consequence of a scale-free property of networks. While hubs cannot be observed in a random network, they are expected to emerge in scale-free networks. The uprise of hubs in scale-free networks is associated with power-law distribution. Hubs have a significant impact on the network topology. Hubs can be found in many real networks, such as Brain Network or Internet.

网络科学 Network Science中,枢纽 Hub指的是其链接数远超过平均值的节点。网络的无标度性质 Scale-Free Property是枢纽出现的主要原因。[2] 虽然在随机网络中难以观察到枢纽,但它们却有望出现于无标度网络中。无标度网络中枢纽的出现与其幂律分布 Power-Law Distribution的性质有关。枢纽对网络的拓扑结构有着重要的影响。我们可以在很多真实的网络中发现枢纽,比如大脑网络或者因特网。

文件:Network representation of brain connectivity.JPG
图1:Network representation of brain connectivity. Hubs are highlighted 图1:大脑连接性的网络表示,其中枢纽被突出显示
文件:Internet map 4096.png
图2:Partial map of the Internet based on the January 15, 2005. Hubs are highlighted 图2:2005年1月15日的因特网局部图,其中枢纽被突出显示

A hub is a component of a network with a high-degree node. Hubs have a significantly larger number of links in comparison with other nodes in the network. The number of links (degrees) for a hub in a scale-free network is much higher than for the biggest node in a random network, keeping the size N of the network and average degree <k> constant. The existence of hubs is the biggest difference between random networks and scale-free networks. In random networks, the degree k is comparable for every node; it is therefore not possible for hubs to emerge. In scale-free networks, a few nodes (hubs) have a high degree k while the other nodes have a small number of links.

A hub is a component of a network with a high-degree node. Hubs have a significantly larger number of links in comparison with other nodes in the network. The number of links (degrees) for a hub in a scale-free network is much higher than for the biggest node in a random network, keeping the size N of the network and average degree <k> constant. The existence of hubs is the biggest difference between random networks and scale-free networks. In random networks, the degree k is comparable for every node; it is therefore not possible for hubs to emerge. In scale-free networks, a few nodes (hubs) have a high degree k while the other nodes have a small number of links.

枢纽是拥有大度节点网络的重要构件。与网络中的其他节点相比,枢纽拥有的链接数量明显更多。在保持网络规模N和平均度 <k>不变的情况下,无标度网络中枢纽拥有的链接数(度)远远高于随机网络中链接数最大的节点。枢纽的存在是随机网络和无标度网络的最大区别。在随机网络中,对于每个节点而言,度k是相当的,因此不可能出现枢纽节点。而在无标度网络中,少数节点(即枢纽)具有较高的度值 k,而其他节点则只拥有少量的链接。

Emergence 涌现

图3:Random network (a) and scale-free network (b). In the scale-free network, the larger hubs are highlighted. 图3:随机网络(a),无标度网络(b)。在无标度网络中,大型枢纽被突出显示。

Emergence of hubs can be explained by the difference between scale-free networks and random networks. Scale-free networks (Barabási–Albert model) are different from random networks (Erdős–Rényi model) in two aspects: (a) growth, (b) preferential attachment.

Emergence of hubs can be explained by the difference between scale-free networks and random networks. Scale-free networks (Barabási–Albert model) are different from random networks (Erdős–Rényi model) in two aspects: (a) growth, (b) preferential attachment.

枢纽的涌现可以用无标度网络和随机网络的区别来解释。无标度网络 Scale-Free Networks(Barabási-Albert模型)与随机网络 Random Networks(Erdős–Rényi model)的区别主要存在于如下两个方面: (a)增长 Growth,(b)优先链接 Preferential Attachment

  • (a) Scale-free networks assume a continuous growth of the number of nodes N, compared to random networks which assume a fixed number of nodes. In scale-free networks the degree of the largest hub rises polynomially with the size of the network. Therefore, the degree of a hub can be high in a scale-free network. In random networks the degree of the largest node rises logaritmically (or slower) with N, thus the hub number will be small even in a very large network.
  • (a)无标度网络假设节点数量N保持持续的增长,而随机网络则假设节点数量是固定的。在无标度网络中,最大枢纽的度随着网络规模的增大,呈多项式地上升。因此,在无标度网络中,枢纽的度可以很高。而在随机网络中,最大节点的度随N的增大而呈对数式(或更慢)的上升。因此即使在一个非常大的随机网络中,枢纽的数量也会很小。
  • (b) A new node in a scale-free network has a tendency to link to a node with a higher degree, compared to a new node in a random network which links itself to a random node. This process is called preferential attachment. The tendency of a new node to link to a node with a high degree k is characterized by power-law distribution (also known as rich-gets-richer process). This idea was introduced by Vilfredo Pareto and it explained why a small percentage of the population earns most of the money. This process is present in networks as well, for example 80 percent of web links point to 15 percent of webpages. The emergence of scale-free networks is not typical only of networks created by human action, but also of such networks as metabolic networks or illness networks.[3] This phenomenon may be explained by the example of hubs on the World Wide Web such as Facebook or Google. These webpages are very well known and therefore the tendency of other webpages pointing to them is much higher than linking to random small webpages.
  • (b)无标度网络中的新节点倾向于链接到度较高的节点,而随机网络中的新节点则与其他节点随机相连。这一过程称为优先链接。新节点链接到度k较高节点的倾向可以用幂律分布来刻画(即,富者越富)。这一想法由维尔弗雷多·帕累托 Vilfredo Pareto提出,它解释了为什么一小部分人赚了大部分的钱。这个过程也存在于网络中,例如80%的网络链接指向15%的网页。无标度网络的出现并不仅仅是人类行为所创造的网络的典型现象,在新陈代谢网络或疾病网络中这一现象也十分常见。[4] 这种现象可以由像Facebook或谷歌这样的万维网枢纽的来解释。这些网页是非常有名的,因此相较于指向随机的小网页,其他网页指向他们的倾向要高得多。

The mathematical explanation for Barabási–Albert model:

The mathematical explanation for Barabási–Albert model:

Barabási-Albert模型的数学解释:

文件:Barabasi Albert model.gif
图4:The steps of the growth of the network according to the Barabasi–Albert model ([math]\displaystyle{ m_0=m=2 }[/math]) 图4:基于Barabasi-Albert模型的网络增长([math]\displaystyle{ m_0=m=2 }[/math]

The network begins with an initial connected network of [math]\displaystyle{ m_0 }[/math] nodes.

The network begins with an initial connected network of [math]\displaystyle{ m_0 }[/math] nodes.

网络起始于由[math]\displaystyle{ m_0 }[/math]个节点组成的初始联通网络。

New nodes are added to the network one at a time. Each new node is connected to [math]\displaystyle{ m \le m_0 }[/math] existing nodes with a probability that is proportional to the number of links that the existing nodes already have. Formally, the probability [math]\displaystyle{ p_i }[/math] that the new node is connected to node [math]\displaystyle{ i }[/math] is[5]

New nodes are added to the network one at a time. Each new node is connected to [math]\displaystyle{ m \le m_0 }[/math] existing nodes with a probability that is proportional to the number of links that the existing nodes already have. Formally, the probability [math]\displaystyle{ p_i }[/math] that the new node is connected to node [math]\displaystyle{ i }[/math] is

每次向网络添加一个新节点。每个新的节点都被链接到[math]\displaystyle{ m \le m_0 }[/math]个现有的节点,其概率与现有节点已经拥有的链接数量成正比。形式上,新节点与现有节点[math]\displaystyle{ i }[/math]相连的概率[math]\displaystyle{ p_i }[/math][5]

[math]\displaystyle{ p_i = \frac{k_i}{\sum_j k_j}, }[/math]

[math]\displaystyle{ p_i = \frac{k_i}{\sum_j k_j}, }[/math]

where [math]\displaystyle{ k_i }[/math] is the degree of the node [math]\displaystyle{ i }[/math] and the sum is taken over all pre-existing nodes [math]\displaystyle{ j }[/math] (i.e. the denominator results in twice the current number of edges in the network).

where [math]\displaystyle{ k_i }[/math] is the degree of the node [math]\displaystyle{ i }[/math] and the sum is taken over all pre-existing nodes [math]\displaystyle{ j }[/math] (i.e. the denominator results in twice the current number of edges in the network).

其中[math]\displaystyle{ k_i }[/math]是节点[math]\displaystyle{ i }[/math]的度,求和则是针对所有预先存在的节点[math]\displaystyle{ j }[/math]进行的。(分母的数值是网络边数的两倍)。

Emergence of hubs in networks is also related to time. In scale-free networks, nodes which emerged earlier have a higher chance of becoming a hub than latecomers. This phenomenon is called first-mover advantage and it explains why some nodes become hubs and some do not. However, in a real network, the time of emergence is not the only factor that influences the size of the hub. For example, Facebook emerged 8 years later after Google became the largest hub on the World Wide Web and yet in 2011 Facebook became the largest hub of WWW. Therefore, in real networks the growth and the size of a hub depends also on various attributes such as popularity, quality or the aging of a node.

Emergence of hubs in networks is also related to time. In scale-free networks, nodes which emerged earlier have a higher chance of becoming a hub than latecomers. This phenomenon is called first-mover advantage and it explains why some nodes become hubs and some do not. However, in a real network, the time of emergence is not the only factor that influences the size of the hub. For example, Facebook emerged 8 years later after Google became the largest hub on the World Wide Web and yet in 2011 Facebook became the largest hub of WWW. Therefore, in real networks the growth and the size of a hub depends also on various attributes such as popularity, quality or the aging of a node.

网络中枢纽的涌现也与时间有关。在无标度网络中,较早出现的节点比后来者更有可能成为枢纽。这种现象被称为先发优势 First-Mover Advantage,它解释了为什么一些节点成为枢纽,而一些没有。然而,在一个真实的网络中,涌现的时间并不是影响枢纽规模的唯一因素。例如,在谷歌成为全球最大互联网枢纽的8年后,Facebook出现了,并于2011年成为了全球最大的互联网枢纽。因此,在实际网络中,枢纽的增长和规模也取决于各种各样的其他属性,如节点的流行程度、质量或老化程度。

Attributes 属性

There are several attributes of Hubs in a Scale-Free Network

There are several attributes of Hubs in a Scale-Free Network

无标度网络中的枢纽有诸多属性:

Shortening the path lengths in a network 缩短网络路径长度

The more observable hubs are in a network, the more they shrink distances between nodes. In a scale-free network, hubs serve as bridges between the small degree nodes.[6] Since the distance of two random nodes in a scale-free network is small, we refer to scale-free networks as "small" or "ultra small". While the difference between path distance in a very small network may not be noticeable, the difference in the path distance between a large random network and a scale-free network is remarkable.

The more observable hubs are in a network, the more they shrink distances between nodes. In a scale-free network, hubs serve as bridges between the small degree nodes. Since the distance of two random nodes in a scale-free network is small, we refer to scale-free networks as "small" or "ultra small". While the difference between path distance in a very small network may not be noticeable, the difference in the path distance between a large random network and a scale-free network is remarkable.

网络中可观察到的枢纽越多,节点之间的距离就越短。在无标度网络中,枢纽是连接小度节点的桥梁。[7]由于无标度网络中随机节点间的距离很小,我们称无标度网络为“小”或“超小”网络。虽然在一个非常小的网络中,路径长度的差异可能并不明显,但是在大型随机网络和无标度网络中,路径长度的差异是显著的。

Average path length in scale-free networks:

Average path length in scale-free networks:

无标度网络中的平均路径长度:

[math]\displaystyle{ \ell\sim\frac{\ln N}{\ln \ln N}. }[/math]

[math]\displaystyle{ \ell\sim\frac{\ln N}{\ln \ln N}. }[/math]

Aging of hubs (nodes) 枢纽(节点)的老化

The phenomenon present in real networks, when older hubs are shadowed in a network. This phenomenon is responsible for changes in evolution and topology of networks.[8] The example of aging phenomenon may be the case of Facebook overtaking the position of the largest hub on the Web, Google(which was the largest node since 2000).

The phenomenon present in real networks, when older hubs are shadowed in a network. This phenomenon is responsible for changes in evolution and topology of networks. The example of aging phenomenon may be the case of Facebook overtaking the position of the largest hub on the Web, Google(which was the largest node since 2000).

当旧的枢纽被隐藏在网络中时,这种现象便在真实网络中出现。这种现象导致了网络演化和拓扑结构的变化。[9] 老化现象的例子可参照 Facebook 超越了网络中最大的枢纽 Google (自2000年以来最大的节点)。

Robustness and Attack Tolerance 鲁棒性和抗毁性

During the random failure of nodes or targeted attack hubs are key components of the network. During the random failure of nodes in network hubs are responsible for exceptional robustness of network.

During the random failure of nodes or targeted attack hubs are key components of the network. During the random failure of nodes in network hubs are responsible for exceptional robustness of network.

当节点发生随机故障或特定攻击时,枢纽是网络的重要构件。当网络中的节点发生随机故障时,枢纽影响网络的鲁棒性。

The chance that a random failure would delete the hub is very small, because hubs coexists with a large number of small degree nodes. The removal of small degree nodes does not have a large effect on integrity of network. Even though the random removal would hit the hub, the chance of fragmantation of network is very small because the remaining hubs would hold the network together. In this case, hubs are the strength of a scale-free networks.

The chance that a random failure would delete the hub is very small, because hubs coexists with a large number of small degree nodes. The removal of small degree nodes does not have a large effect on integrity of network. Even though the random removal would hit the hub, the chance of fragmantation of network is very small because the remaining hubs would hold the network together. In this case, hubs are the strength of a scale-free networks.

由于枢纽与大量小度节点共存,随机故障删除枢纽的几率很小。而去除小度节点对网络的完整性影响不大。即使随机删除会作用到上枢纽,网络碎片化 Fragmantation of Network的可能性也非常小,因为剩余的枢纽仍能将网络连接在一起。在这种情况下,枢纽就是无标度网络的中坚力量。

During a targeted attack on hubs, the integrity of a network will fall apart relatively fast. Since small nodes are predominantly linked to hubs, the targeted attack on the largest hubs results in destroys the network in a short period of time. The financial market meltdown in 2008 is an example of such a network failure, when bankruptcy of the largest players (hubs) led to a continuous breakdown of the whole system.[10] On the other hand, it may have a positive effect when removing hubs in a terrorist network; targeted node deletion may destroy the whole terrorist group. The attack tolerance of a network may be increased by connecting its peripheral nodes, however it requires to double the number of links.

During a targeted attack on hubs, the integrity of a network will fall apart relatively fast. Since small nodes are predominantly linked to hubs, the targeted attack on the largest hubs results in destroys the network in a short period of time. The financial market meltdown in 2008 is an example of such a network failure, when bankruptcy of the largest players (hubs) led to a continuous breakdown of the whole system. On the other hand, it may have a positive effect when removing hubs in a terrorist network; targeted node deletion may destroy the whole terrorist group. The attack tolerance of a network may be increased by connecting its peripheral nodes, however it requires to double the number of links.

在对枢纽进行特定的攻击时,网络的完整性会相对较快地被破坏。由于小度节点大量的链接到枢纽,因此对最大枢纽的攻击会在短时间内破坏网络。2008年的金融市场崩溃就是这种网络失灵的一个例子,当时头号玩家(枢纽)的破产导致了整个系统的持续崩溃。[11]另一方面,去除恐怖主义网络中的枢纽可能会产生积极的影响,特定节点的消失可能会摧毁整个恐怖组织。网络的抗毁性可以通过连接其外围节点来提高,但是它需要加倍的链接数量。

Degree correlation 度相关

The perfect degree correlation means that each degree-k node is connected only to the same degree-k nodes. Such connectivity of nodes decide the topology of networks, which has an effect on robustness of network, the attribute discussed above. If the number of links between the hubs is the same as would be expected by chance, we refer to this network as Neutral Network. If hubs tend to connected to each other while avoiding linking to small-degree nodes we refer to this network as Assortative Network. This network is relatively resistant against attacks, because hubs form a core group, which is more reduntant against hub removal. If hubs avoid connecting to each other while linking to small-degree nodes, we refer to this network as Disassortative Network. This network has a hub-and-spoke character. Therefore, if we remove the hub in this type of network, it may damage or destroy the whole network.

The perfect degree correlation means that each degree-k node is connected only to the same degree-k nodes. Such connectivity of nodes decide the topology of networks, which has an effect on robustness of network, the attribute discussed above. If the number of links between the hubs is the same as would be expected by chance, we refer to this network as Neutral Network. If hubs tend to connected to each other while avoiding linking to small-degree nodes we refer to this network as Assortative Network. This network is relatively resistant against attacks, because hubs form a core group, which is more reduntant against hub removal. If hubs avoid connecting to each other while linking to small-degree nodes, we refer to this network as Disassortative Network. This network has a hub-and-spoke character. Therefore, if we remove the hub in this type of network, it may damage or destroy the whole network.

完全度相关 Perfect Degree Correlation意味着每个度值为k的节点只链接到相同度值的节点。节点之间的这种链接决定了网络的拓扑结构,从而影响了上文所讨论的网络鲁棒性。如果枢纽之间的链接数量与随机模式下的期望值相同,我们将这个网络称为中性网络 Neutral Network。如果枢纽倾向于相互连接,同时避免链接到小度节点,我们将这个网络称为同配网络 Assortative Network。这种网络的抗毁性相对较强,因为枢纽形成了一个核心团体,这对枢纽的移除来说是更加冗余的。如果枢纽避免相互链接,同时链接到小度节点,我们将这个网络称为异配网络 Disassortative Network。这种网络具有中心辐射特征 Hub-and-Spoke Character。因此,如果我们删除这种类型网络中的枢纽,可能会破坏或摧毁整个网络。

Spreading phenomenon 传播现象

The hubs are also responsible for effective spreading of material on network. In an analysis of disease spreading or information flow, hubs are referred to as super-spreaders. Super-spreaders may have a positive impact, such as effective information flow, but also devastating in a case of epidemic spreading such as H1N1 or AIDS. The mathematical models such as model of H1H1 Epidemic prediction [12] may allow us to predict the spread of diseases based on human mobility networks, infectiousness, or social interactions among humans. Hubs are also important in the eradication of disease. In a scale-free network hubs are most likely to be infected, because of the large number of connections they have. After the hub is infected, it broadcasts the disease to the nodes it is linked to. Therefore, the selective immunization of hubs may be the cost-effective strategy in eradication of spreading disease.

The hubs are also responsible for effective spreading of material on network. In an analysis of disease spreading or information flow, hubs are referred to as super-spreaders. Super-spreaders may have a positive impact, such as effective information flow, but also devastating in a case of epidemic spreading such as H1N1 or AIDS. The mathematical models such as model of H1H1 Epidemic prediction may allow us to predict the spread of diseases based on human mobility networks, infectiousness, or social interactions among humans. Hubs are also important in the eradication of disease. In a scale-free network hubs are most likely to be infected, because of the large number of connections they have. After the hub is infected, it broadcasts the disease to the nodes it is linked to. Therefore, the selective immunization of hubs may be the cost-effective strategy in eradication of spreading disease.

枢纽还负责要素在网络上的有效传播。在疾病传播或信息流动的分析中,枢纽被称为超级传播者。超级传播者可能会产生积极的影响,如有效的信息流动,但在H1N1或艾滋病等流行病传播的情况下也会产生毁灭性的影响。如H1H1流行病预测等数学模型,可以基于人类流动网络,传染性,或人与人之间的社会互动,让我们预测疾病的传播。在消灭疾病方面,枢纽也很重要。在无标度网络中,枢纽是最有可能被感染的,因为他们有大量的链接。在枢纽被感染后,它将将疾病传播到它所链接的节点。因此,选择性免疫那些枢纽可能是消灭传播性疾病的成本效率最高的策略。

References

  1. Barabási, Albert-László. Network Science: Graph Theory., p. 27
  2. Barabási, Albert-László. Network Science: Graph Theory., p. 27
  3. Barabási, Albert-László. Network Science: The Scale-Free Property., p. 8.[1]
  4. Barabási, Albert-László. Network Science: The Scale-Free Property., p. 8.[2]
  5. 5.0 5.1 引用错误:无效<ref>标签;未给name属性为RMP的引用提供文字
  6. Barabási, Albert-László. Network Science: The Scale-Free Property., p. 23.[3]
  7. Barabási, Albert-László. Network Science: The Scale-Free Property., p. 23.[4]
  8. Barabási, Albert-László. Network Science: Evolving Networks., p. 3
  9. Barabási, Albert-László. Network Science: Evolving Networks., p. 3
  10. S. V. Buldyrev; R. Parshani; G. Paul; H. E. Stanley; S. Havlin (2010). "Catastrophic cascade of failures in interdependent networks". Nature. 464 (7291): 1025–28. arXiv:1012.0206. Bibcode:2010Natur.464.1025B. doi:10.1038/nature08932. PMID 20393559.
  11. S. V. Buldyrev; R. Parshani; G. Paul; H. E. Stanley; S. Havlin (2010). "Catastrophic cascade of failures in interdependent networks". Nature. 464 (7291): 1025–28. arXiv:1012.0206. Bibcode:2010Natur.464.1025B. doi:10.1038/nature08932. PMID 20393559.
  12. Balcan, Duygu; Hu, Hao; Goncalves, Bruno; Bajardi, Paolo; Poletto, Chiara; Ramasco, Jose J.; Paolotti, Daniela; Perra, Nicola; Tizzoni, Michele; Van den Broeck, Wouter; Colizza, Vittoria; Vespignani, Alessandro (14 September 2009). "Seasonal transmission potential and activity peaks of the new influenza A(H1N1): a Monte Carlo likelihood analysis based on human mobility". BMC Medicine. 7 (45): 29. arXiv:0909.2417. doi:10.1186/1741-7015-7-45. PMC 2755471. PMID 19744314.

Category:Network theory

分类: 网络理论


This page was moved from wikipedia:en:Hub (network science). Its edit history can be viewed at 枢纽节点/edithistory