http://www.wretch.cc/album/show.php?i=tear2001&b=1&f=1135926836&p=0
Network biology offers a quantifiable description of the networks that characterize various biological systems.Here we define the most basic network measures that allow us to compare and characterize different complex networks.
Degree
The most elementary characteristic of a node is its degree (or connectivity), k,which tells us how many links the node has to other nodes. For example, in the undirected network shown in part of the figure, node A has degree k = 5. In networks in which each link has a selected direction (see figure, part b) there is an incoming degree, kin,which denotes the number of links that point to a node, and an outgoing degree, kout,which denotes the number of links that start from it. For example, node A in part b of the figure has kin = 4 and kout = 1. An undirected network with N nodes and L links is characterized by an average degree = 2L/N (where <> denotes the average).
Degree distribution
The degree distribution,P(k), gives the probability that a selected node has exactly k links.P(k) is obtained by counting the number of nodes N(k) with k = 1, 2… links and dividing by the total number of nodes N. The degree distribution allows us to distinguish between different classes of networks. For example, a peaked degree distribution, as seen in a random network, indicates that the system has a characteristic degree and that there are no highly connected nodes (which are also known as hubs).By contrast, a power-law degree distribution indicates that a few hubs hold together numerous small nodes.
Scale-free networks and the degree exponent
Most biological networks are scale-free,which means that their degree distribution approximates a power law,P(k) ~ k exp(–γ), where γ is the degree exponent and ~ indicates ‘proportional to’. The value of γ determines many properties of the system. The smaller the value of γ, the more important the role of the hubs is in the network.Whereas for γ>3 the hubs are not relevant, for 2> γ>3 there is a hierarchy of hubs,with the most connected hub being in contact with a small fraction of all nodes, and for γ = 2 a hub-and-spoke network emerges,with the largest hub being in contact with a large fraction of all nodes. In general, the unusual properties of scale-free networks are valid only for γ<3,when the dispersion of the P(k) distribution,which is defined as σ2 = – 2, increases with the number of nodes (that is,σ diverges),resulting in a series of unexpected features, such as a high degree of robustness against accidental node failures71. For γ>3, however,most unusual features are absent, and in many respects the scale-free network behaves like a random one.
Shortest path and mean path length
Distance in networks is measured with the path length,which tells us how many links we need to pass through to travel between two nodes.As there are many alternative paths between two nodes, the shortest path — the path with the smallest number of links between the selected nodes — has a special role. In directed networks, the distance AB from node A to node B is often different from the distance BA from B to A. For example, in part b of the figure,BA = 1, whereas AB = 3. Often there is no direct path between two nodes.As shown in part b of the figure, although there is a path from C to A, there is no path from A to C. The mean path length,< >, represents the average over the shortest paths between all pairs of nodes and offers a measure of a network’s overall navigability.
Clustering coefficient
In many networks, if node A is connected to B, and B is connected to C, then it is highly probable that A also has a direct link to C. This phenomenon can be quantified using the clustering coefficient33 CI = 2nI/k(k–1),where nI is the number of links connecting the kI neighbours of node I to each other. In other words,CI gives the number of ‘triangles’that go through node I, whereas kI(kI –1)/2 is the total number of triangles that could pass through node I, should all of node I’s neighbours be connected to each other. For example, only one pair of node A’s five neighbours in part a of the figure are linked together (B and C),which gives nA = 1 and CA = 2/20.By contrast, none of node F’s neighbours link to each other, giving CF = 0. The average clustering coefficient,, characterizes the overall tendency of nodes to form clusters or groups.An important measure of the network’s structure is the function C(k),which is defined as the average clustering coefficient of all nodes with k links.For many real networks C(k) ~ k – 1,which is an indication of a network’s hierarchical character.
The average degree , average path length < > and average clustering coefficient depend on the number of nodes and links (N and L) in the network.By contrast, the P(k) and C(k) functions are independent of the network’s size and they therefore capture a network’s generic features,which allows them to be used to classify various networks.
Network biology offers a quantifiable description of the networks that characterize various biological systems.Here we define the most basic network measures that allow us to compare and characterize different complex networks.
Degree
The most elementary characteristic of a node is its degree (or connectivity), k,which tells us how many links the node has to other nodes. For example, in the undirected network shown in part of the figure, node A has degree k = 5. In networks in which each link has a selected direction (see figure, part b) there is an incoming degree, kin,which denotes the number of links that point to a node, and an outgoing degree, kout,which denotes the number of links that start from it. For example, node A in part b of the figure has kin = 4 and kout = 1. An undirected network with N nodes and L links is characterized by an average degree = 2L/N (where <> denotes the average).
Degree distribution
The degree distribution,P(k), gives the probability that a selected node has exactly k links.P(k) is obtained by counting the number of nodes N(k) with k = 1, 2… links and dividing by the total number of nodes N. The degree distribution allows us to distinguish between different classes of networks. For example, a peaked degree distribution, as seen in a random network, indicates that the system has a characteristic degree and that there are no highly connected nodes (which are also known as hubs).By contrast, a power-law degree distribution indicates that a few hubs hold together numerous small nodes.
Scale-free networks and the degree exponent
Most biological networks are scale-free,which means that their degree distribution approximates a power law,P(k) ~ k exp(–γ), where γ is the degree exponent and ~ indicates ‘proportional to’. The value of γ determines many properties of the system. The smaller the value of γ, the more important the role of the hubs is in the network.Whereas for γ>3 the hubs are not relevant, for 2> γ>3 there is a hierarchy of hubs,with the most connected hub being in contact with a small fraction of all nodes, and for γ = 2 a hub-and-spoke network emerges,with the largest hub being in contact with a large fraction of all nodes. In general, the unusual properties of scale-free networks are valid only for γ<3,when the dispersion of the P(k) distribution,which is defined as σ2 = – 2, increases with the number of nodes (that is,σ diverges),resulting in a series of unexpected features, such as a high degree of robustness against accidental node failures71. For γ>3, however,most unusual features are absent, and in many respects the scale-free network behaves like a random one.
Shortest path and mean path length
Distance in networks is measured with the path length,which tells us how many links we need to pass through to travel between two nodes.As there are many alternative paths between two nodes, the shortest path — the path with the smallest number of links between the selected nodes — has a special role. In directed networks, the distance AB from node A to node B is often different from the distance BA from B to A. For example, in part b of the figure,BA = 1, whereas AB = 3. Often there is no direct path between two nodes.As shown in part b of the figure, although there is a path from C to A, there is no path from A to C. The mean path length,< >, represents the average over the shortest paths between all pairs of nodes and offers a measure of a network’s overall navigability.
Clustering coefficient
In many networks, if node A is connected to B, and B is connected to C, then it is highly probable that A also has a direct link to C. This phenomenon can be quantified using the clustering coefficient33 CI = 2nI/k(k–1),where nI is the number of links connecting the kI neighbours of node I to each other. In other words,CI gives the number of ‘triangles’that go through node I, whereas kI(kI –1)/2 is the total number of triangles that could pass through node I, should all of node I’s neighbours be connected to each other. For example, only one pair of node A’s five neighbours in part a of the figure are linked together (B and C),which gives nA = 1 and CA = 2/20.By contrast, none of node F’s neighbours link to each other, giving CF = 0. The average clustering coefficient,, characterizes the overall tendency of nodes to form clusters or groups.An important measure of the network’s structure is the function C(k),which is defined as the average clustering coefficient of all nodes with k links.For many real networks C(k) ~ k – 1,which is an indication of a network’s hierarchical character.
The average degree , average path length < > and average clustering coefficient depend on the number of nodes and links (N and L) in the network.By contrast, the P(k) and C(k) functions are independent of the network’s size and they therefore capture a network’s generic features,which allows them to be used to classify various networks.
文章標籤
全站熱搜
NGS (2)