Gradient network

Last updated November 07, 2023

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]

Definition

Transport takes place on a fixed network $G=G(V,E)$ called the substrate graph. It has N nodes, $V=\{0,1,...,N-1\}$ and the set of edges $E=\{(i,j)|i,j\in V\}$ . Given a node i, we can define its set of neighbors in G by S_i⁽¹⁾ = {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 = {h₀, .., h_N−1} defined on the set of nodes V, so that every node i has a scalar value h_i associated to it.

Gradient ∇h_i on a network: ∇h_i $=$ (i, μ(i)) i.e. the directed edge from i to μ(i), where μ(i) ∈ S_i⁽¹⁾ ∪ {i}, and h_μ has the maximum value in ${h_{j}|j\in S_{i}^{(1)}\cup {i}}$ .

Gradient network : ∇ $G=$ ∇ $G$ $(V,F)$ 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 ∇ $G$ 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, k_i⁽ⁱⁿ⁾ is the number of gradient edges pointing into i, and the in-degree distribution is $R(l)=P\{k_{i}^{(in)}=l\}$ .

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 h_i are i.i.d. (independent identically distributed) the exact expression for R(l) is given by

R(l)={\frac {1}{N}}\sum _{n=0}^{N-1}\mathrm {C} _{l}^{N-1-n}[1-p(1-p)]^{N-1-n-l}[p(1-p)^{n}]^{l}]

^[3]

In the limit $N\to \infty$ and $P\to 0$ , the degree distribution becomes the power law

R(l)\approx l^{-1}

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:

J=1-\langle \langle {\frac {N_{\text{receive}}}{N_{\text{send}}}}\rangle _{h}\rangle _{\text{network}}=R(0)

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

J(N,P)=1-{\frac {\ln N}{N\ln({\frac {1}{1-P}})}}\left[1+O({\frac {1}{N}})\right]\rightarrow 1.

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.

Related Research Articles

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.$

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.

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

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

References

↑ 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.
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.
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.
↑ 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.
↑ 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.
↑ 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.
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.
↑ 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.
↑ 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.
↑ 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.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[grad2-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.

[toro-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.

[grad-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.

[nature-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.

[control-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.

[1]

[3]

[4]

[5]

[2]

[6]

[7]

[8]

[9]

[10]