Gradient network

Last updated

In network science, a gradient network is a directed subnetwork of an undirected "substrate" network where each node has an associated scalar potential and one out-link that points to the node with the smallest (or largest) potential in its neighborhood, defined as the union of itself and its neighbors on the substrate network. [1]

Contents

Definition

Transport takes place on a fixed network called the substrate graph. It has N nodes, and the set of edges . Given a node i, we can define its set of neighbors in G by Si(1) = {j ∈ V | (i,j)∈ E}.

An example of a gradient network. Gradient network (sample diagram).jpg
An example of a gradient network.

Let us also consider a scalar field, h = {h0, .., hN1} defined on the set of nodes V, so that every node i has a scalar value hi associated to it.

Gradient ∇hi on a network: ∇hi(i, μ(i)) i.e. the directed edge from i to μ(i), where μ(i) ∈ Si(1) ∪ {i}, and hμ has the maximum value in .

Gradient network : where F is the set of gradient edges on G.

In general, the scalar field depends on time, due to the flow, external sources and sinks on the network. Therefore, the gradient network ∇ will be dynamic. [3]

Motivation and history

The concept of a gradient network was first introduced by Toroczkai and Bassler (2004). [4] [5]

Generally, real-world networks (such as citation graphs, the Internet, cellular metabolic networks, the worldwide airport network), which often evolve to transport entities such as information, cars, power, water, forces, and so on, are not globally designed; instead, they evolve and grow through local changes. For example, if a router on the Internet is frequently congested and packets are lost or delayed due to that, it will be replaced by several interconnected new routers. [2]

Moreover, this flow is often generated or influenced by local gradients of a scalar. For example: electric current is driven by a gradient of electric potential. In information networks, properties of nodes will generate a bias in the way of information is transmitted from a node to its neighbors. This idea motivated the approach to study the flow efficiency of a network by using gradient networks, when the flow is driven by gradients of a scalar field distributed on the network. [2] [3]

Recent research[ which? ][ needs update ] investigates the connection between network topology and the flow efficiency of the transportation. [2]

The gradient at node i is a directed edge pointing towards the largest increase of the scalar potential in the node's neighborhood. Gradient network with node pointing to largest increase.jpg
The gradient at node i is a directed edge pointing towards the largest increase of the scalar potential in the node's neighborhood.

In-degree distribution of gradient networks

In a gradient network, the in-degree of a node i, ki(in) is the number of gradient edges pointing into i, and the in-degree distribution is .

The degree distributions of the gradient network and the substrate(BA Model). Degree distributions of gradient network and substrate (BA model).jpg
The degree distributions of the gradient network and the substrate(BA Model).

When the substrate G is a random graph and each pair of nodes is connected with probability P (i.e. an Erdős–Rényi random graph), the scalars hi are i.i.d. (independent identically distributed) the exact expression for R(l) is given by

[3]

In the limit and , the degree distribution becomes the power law

This shows in this limit, the gradient network of random network is scale-free. [3]

Furthermore, if the substrate network G is scale-free, like in the Barabási–Albert model, then the gradient network also follow the power-law with the same exponent as those of G. [2]

The congestion on networks

The fact that the topology of the substrate network influence the level of network congestion can be illustrated by a simple example: if the network has a star-like structure, then at the central node, the flow would become congested because the central node should handle all the flow from other nodes. However, if the network has a ring-like structure, since every node takes the same role, there is no flow congestion.

Illustrating the influence of structure on flows. Star network vs ring network.jpg
Illustrating the influence of structure on flows.

Under assumption that the flow is generated by gradients in the network, flow efficiency on networks can be characterized through the jamming factor (or congestion factor), defined as follows:

where Nreceive is the number of nodes that receive gradient flow and Nsend is the number of nodes that send gradient flow. The value of J is between 0 and 1; means no congestion, and corresponds to maximal congestion. In the limit , for an Erdős–Rényi random graph, the congestion factor becomes

This result shows that random networks are maximally congested in that limit. On the contrary, for a scale-free network, J is a constant for any N, which means that scale-free networks are not prone to maximal jamming. [6]

Fig.7. The congestion coefficient for random graphs and scale-free networks. Congestion coefficient for random graphs and scale-free networks.jpg
Fig.7. The congestion coefficient for random graphs and scale-free networks.

Approaches to control congestion

One problem in communication networks is understanding how to control congestion and maintain normal and efficient network function. [7]

Zonghua Liu et al. (2006) showed that congestion is more likely to occur at the nodes with high degrees in networks, and an efficient approach of selectively enhancing the message-process capability of a small fraction (e.g. 3%) of nodes is shown to perform just as well as enhancing the capability of all nodes. [7]

Ana L Pastore y Piontti et al. (2008) showed that relaxational dynamics[ clarification needed ] can reduce network congestion. [8]

Pan et al. (2011) studied jamming properties in a scheme where edges are given weights of a power of the scalar difference between node potentials. [9] [ clarification needed ]

Niu and Pan (2016) showed that congestion can be reduced by introducing a correlation between the gradient field and the local network topology. [10] [ clarification needed ]

<n(k)> is the average packet number as a function of degree, packet-processing capabilities: 0 (circles), 0.05 (squares), 0.1 (stars). Average packet number as a function of degree (congestion graph).jpg
<n(k)> is the average packet number as a function of degree, packet-processing capabilities: 0 (circles), 0.05 (squares), 0.1 (stars).
The comparison between the efficient approach (circles) with the capability of top 3% degree nodes enhanced and the normal approach (stars) with the capability of all nodes enhanced. (a) packet-processing capability equals to 0.05, (b) packet-processing capability equals to 0.1. <n(k)> is the average packet number as a function of degree. Comparison between enhanced and normal approaches (packet-processing capability).jpg
The comparison between the efficient approach (circles) with the capability of top 3% degree nodes enhanced and the normal approach (stars) with the capability of all nodes enhanced. (a) packet-processing capability equals to 0.05, (b) packet-processing capability equals to 0.1. <n(k)> is the average packet number as a function of degree.

See also

Related Research Articles

<span class="mw-page-title-main">Scale-free network</span> Network whose degree distribution follows a power law

A scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction P(k) of nodes in the network having k connections to other nodes goes for large values of k as

<span class="mw-page-title-main">Boltzmann machine</span> Type of stochastic recurrent neural network

A Boltzmann machine is a stochastic spin-glass model with an external field, i.e., a Sherrington–Kirkpatrick model, that is a stochastic Ising model. It is a statistical physics technique applied in the context of cognitive science. It is also classified as a Markov random field.

In graph theory, a clustering coefficient is a measure of the degree to which nodes in a graph tend to cluster together. Evidence suggests that in most real-world networks, and in particular social networks, nodes tend to create tightly knit groups characterised by a relatively high density of ties; this likelihood tends to be greater than the average probability of a tie randomly established between two nodes.

<span class="mw-page-title-main">Centrality</span> Degree of connectedness within a graph

In graph theory and network analysis, indicators of centrality assign numbers or rankings to nodes within a graph corresponding to their network position. Applications include identifying the most influential person(s) in a social network, key infrastructure nodes in the Internet or urban networks, super-spreaders of disease, and brain networks. Centrality concepts were first developed in social network analysis, and many of the terms used to measure centrality reflect their sociological origin.

<span class="mw-page-title-main">Degree distribution</span>

In the study of graphs and networks, the degree of a node in a network is the number of connections it has to other nodes and the degree distribution is the probability distribution of these degrees over the whole network.

<span class="mw-page-title-main">Watts–Strogatz model</span> Method of generating random small-world graphs

The Watts–Strogatz model is a random graph generation model that produces graphs with small-world properties, including short average path lengths and high clustering. It was proposed by Duncan J. Watts and Steven Strogatz in their article published in 1998 in the Nature scientific journal. The model also became known as the (Watts) beta model after Watts used to formulate it in his popular science book Six Degrees.

Mixing patterns refer to systematic tendencies of one type of nodes in a network to connect to another type. For instance, nodes might tend to link to others that are very similar or very different. This feature is common in many social networks, although it also appears sometimes in non-social networks. Mixing patterns are closely related to assortativity; however, for the purposes of this article, the term is used to refer to assortative or disassortative mixing based on real-world factors, either topological or sociological.

<span class="mw-page-title-main">Erdős–Rényi model</span> Two closely related models for generating random graphs

In the mathematical field of graph theory, the Erdős–Rényi model refers to one of two closely related models for generating random graphs or the evolution of a random network. These models are named after Hungarian mathematicians Paul Erdős and Alfréd Rényi, who introduced one of the models in 1959. Edgar Gilbert introduced the other model contemporaneously with and independently of Erdős and Rényi. In the model of Erdős and Rényi, all graphs on a fixed vertex set with a fixed number of edges are equally likely. In the model introduced by Gilbert, also called the Erdős–Rényi–Gilbert model, each edge has a fixed probability of being present or absent, independently of the other edges. These models can be used in the probabilistic method to prove the existence of graphs satisfying various properties, or to provide a rigorous definition of what it means for a property to hold for almost all graphs.

<span class="mw-page-title-main">Random geometric graph</span> In graph theory, the mathematically simplest spatial network

In graph theory, a random geometric graph (RGG) is the mathematically simplest spatial network, namely an undirected graph constructed by randomly placing N nodes in some metric space and connecting two nodes by a link if and only if their distance is in a given range, e.g. smaller than a certain neighborhood radius, r.

<span class="mw-page-title-main">Network science</span> Academic field

Network science is an academic field which studies complex networks such as telecommunication networks, computer networks, biological networks, cognitive and semantic networks, and social networks, considering distinct elements or actors represented by nodes and the connections between the elements or actors as links. The field draws on theories and methods including graph theory from mathematics, statistical mechanics from physics, data mining and information visualization from computer science, inferential modeling from statistics, and social structure from sociology. The United States National Research Council defines network science as "the study of network representations of physical, biological, and social phenomena leading to predictive models of these phenomena."

<span class="mw-page-title-main">Closeness centrality</span>

In a connected graph, closeness centrality of a node is a measure of centrality in a network, calculated as the reciprocal of the sum of the length of the shortest paths between the node and all other nodes in the graph. Thus, the more central a node is, the closer it is to all other nodes.

<span class="mw-page-title-main">Betweenness centrality</span> Measure of a graphs centrality, based on shortest paths

In graph theory, betweenness centrality is a measure of centrality in a graph based on shortest paths. For every pair of vertices in a connected graph, there exists at least one shortest path between the vertices such that either the number of edges that the path passes through or the sum of the weights of the edges is minimized. The betweenness centrality for each vertex is the number of these shortest paths that pass through the vertex.

<span class="mw-page-title-main">Exponential family random graph models</span>

Exponential Random Graph Models (ERGMs) are a family of statistical models for analyzing data from social and other networks. Examples of networks examined using ERGM include knowledge networks, organizational networks, colleague networks, social media networks, networks of scientific development, and others.

Price's model is a mathematical model for the growth of citation networks. It was the first model which generalized the Simon model to be used for networks, especially for growing networks. Price's model belongs to the broader class of network growing models whose primary target is to explain the origination of networks with strongly skewed degree distributions. The model picked up the ideas of the Simon model reflecting the concept of rich get richer, also known as the Matthew effect. Price took the example of a network of citations between scientific papers and expressed its properties. His idea was that the way an old vertex gets new edges should be proportional to the number of existing edges the vertex already has. This was referred to as cumulative advantage, now also known as preferential attachment. Price's work is also significant in providing the first known example of a scale-free network. His ideas were used to describe many real-world networks such as the Web.

<span class="mw-page-title-main">Efficiency (network science)</span>

In network science, the efficiency of a network is a measure of how efficiently it exchanges information and it is also called communication efficiency. The underlying idea is that the more distant two nodes are in the network, the less efficient their communication will be. The concept of efficiency can be applied to both local and global scales in a network. On a global scale, efficiency quantifies the exchange of information across the whole network where information is concurrently exchanged. The local efficiency quantifies a network's resistance to failure on a small scale. That is the local efficiency of a node characterizes how well information is exchanged by its neighbors when it is removed.

<span class="mw-page-title-main">Hub (network science)</span> Node with a number of links that greatly exceeds the average

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 the brain or the Internet.

<span class="mw-page-title-main">Configuration model</span>

In network science, the configuration model is a method for generating random networks from a given degree sequence. It is widely used as a reference model for real-life social networks, because it allows the modeler to incorporate arbitrary degree distributions.

A set of networks that satisfies given structural characteristics can be treated as a network ensemble. Brought up by Ginestra Bianconi in 2007, the entropy of a network ensemble measures the level of the order or uncertainty of a network ensemble.

In network science, the network entropy is a disorder measure derived from information theory to describe the level of randomness and the amount of information encoded in a graph. It is a relevant metric to quantitatively characterize real complex networks and can also be used to quantify network complexity

<span class="mw-page-title-main">Graph neural network</span> Class of artificial neural networks

A graph neural network (GNN) is a class of artificial neural networks for processing data that can be represented as graphs.

References

  1. Danila, Bogdan; Yu, Yong; Earl, Samuel; Marsh, John A.; Toroczkai, Zoltán; Bassler, Kevin E. (2006-10-19). "Congestion-gradient driven transport on complex networks". Physical Review E. 74 (4): 046114. arXiv: cond-mat/0603861 . Bibcode:2006PhRvE..74d6114D. doi:10.1103/physreve.74.046114. ISSN   1539-3755. PMID   17155140. S2CID   16009613.
  2. 1 2 3 4 5 6 7 "Gradient Networks" (PDF). cnls.lanl.gov. Archived (PDF) from the original on 4 October 2006. Retrieved 19 March 2021.
  3. 1 2 3 4 5 6 Toroczkai, Zoltán; Kozma, Balázs; Bassler, Kevin E; Hengartner, N W; Korniss, G (2008-04-02). "Gradient networks". Journal of Physics A: Mathematical and Theoretical. IOP Publishing. 41 (15): 155103. arXiv: cond-mat/0408262 . Bibcode:2008JPhA...41o5103T. doi:10.1088/1751-8113/41/15/155103. ISSN   1751-8113. S2CID   118983053.
  4. Niu, Rui-Wu; Pan, Gui-Jun (2016-04-01). "Transport optimization on complex gradient networks". Chinese Journal of Physics. 54 (2): 278–284. Bibcode:2016ChJPh..54..278N. doi:10.1016/j.cjph.2016.04.014. ISSN   0577-9073.
  5. Toroczkai, Zoltán; Bassler, Kevin E. (2004). "Jamming is limited in scale-free systems". Nature. 428 (6984): 716. doi: 10.1038/428716a . ISSN   1476-4687. PMID   15085122. S2CID   2839066.
  6. Toroczkai, Zoltán; Bassler, Kevin E. (2004). "Jamming is limited in scale-free systems". Nature. Springer Science and Business Media LLC. 428 (6984): 716. doi: 10.1038/428716a . ISSN   0028-0836. PMID   15085122. S2CID   2839066.
  7. 1 2 3 4 Liu, Zonghua; Ma, Weichuan; Zhang, Huan; Sun, Yin; Hui, P.M. (2006). "An efficient approach of controlling traffic congestion in scale-free networks". Physica A: Statistical Mechanics and Its Applications. Elsevier BV. 370 (2): 843–853. arXiv: 0806.1845 . Bibcode:2006PhyA..370..843L. doi:10.1016/j.physa.2006.02.021. ISSN   0378-4371. S2CID   17324268.
  8. L Pastore y Piontti, Ana; E La Rocca, Cristian; Toroczkai, Zoltán; A Braunstein, Lidia; A Macri, Pablo; López, Eduardo (14 May 2008). "Using relaxational dynamics to reduce network congestion". New Journal of Physics (published 5 September 2008). 10 (9): 093007. Bibcode:2008NJPh...10i3007P. doi: 10.1088/1367-2630/10/9/093007 . S2CID   11842310.
  9. Pan, Gui-Jun; Liu, Sheng-Hong; Li, Mei (2011-09-15). "Jamming in the weighted gradient networks". Physica A: Statistical Mechanics and Its Applications. 390 (18): 3178–3182. Bibcode:2011PhyA..390.3178P. doi:10.1016/j.physa.2011.03.018. ISSN   0378-4371.
  10. Niu, Rui-Wu; Pan, Gui-Jun (2016-04-01). "Transport optimization on complex gradient networks". Chinese Journal of Physics. 54 (2): 278–284. Bibcode:2016ChJPh..54..278N. doi:10.1016/j.cjph.2016.04.014. ISSN   0577-9073.