View source for Gradient network

{{Primary sources|date=October 2021}}{{Confusing|date=October 2021}}

In [[network science]], a '''gradient network''' is a directed [[subnetwork]] of an undirected "substrate" [[computer network|network]] where each [[node (networking)|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 [[Neighbourhood (graph theory)|neighbors]] on the substrate network.<ref name="grad2">{{cite journal | last1=Danila | first1=Bogdan | last2=Yu | first2=Yong | last3=Earl | first3=Samuel | last4=Marsh | first4=John A. | last5=Toroczkai | first5=Zoltán | last6=Bassler | first6=Kevin E. | title=Congestion-gradient driven transport on complex networks | journal=Physical Review E | volume=74 | issue=4 | date=2006-10-19 | issn=1539-3755 | doi=10.1103/physreve.74.046114 | page=046114| pmid=17155140 | arxiv=cond-mat/0603861 | bibcode=2006PhRvE..74d6114D | s2cid=16009613 }}</ref>

==Definition==
Transport takes place on a fixed network <math>G = G(V,E) </math> called the substrate graph. It has ''N'' nodes, <math>V = \{0, 1, ...,N-1\} </math> and the set
of edges <math>E = \{(i,j) | i,j\in V\}  </math>. Given a node ''i'', we can define its set of neighbors in G by S<sub>i</sub><sup>(1)</sup> = {j ∈ V | (i,j)∈ E}. 
[[File:Gradient network (sample diagram).jpg|thumb|250px|right|An example of a gradient network.<ref name=toro/>]]

Let us also consider a scalar field, ''h'' = {''h''<sub>0</sub>, .., ''h''<sub>''N''&minus;1</sub>} defined on the set of nodes V, so that every node i has a scalar value ''h''<sub>''i''</sub> associated to it.

'''Gradient ∇''h''<sub>''i''</sub> on a network''': '''∇h'''''<sub>i</sub>'''<math>= </math>(i, μ(i))'''''
i.e. the directed edge from ''i'' to  ''μ(i)'', where ''μ''(''i'') ∈ S<sub>i</sub><sup>(1)</sup> ∪ {i}, and h<sub>μ</sub> has the maximum value in <math>{ h_j | j \in S_i^{(1)} \cup {i}}</math>.

'''''Gradient network''''' : '''''∇<math>G = </math> ∇<math>G </math> <math>  (V, F) </math>'''''
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 ∇<math>G </math> will be dynamic.<ref name="grad">{{cite journal|last1=Toroczkai|first1=Zoltán|last2=Kozma|first2=Balázs|last3=Bassler|first3=Kevin E|last4=Hengartner|first4=N W|last5=Korniss|first5=G|date=2008-04-02|title=Gradient networks|journal=Journal of Physics A: Mathematical and Theoretical|publisher=IOP Publishing|volume=41|issue=15|page=155103|arxiv=cond-mat/0408262|doi=10.1088/1751-8113/41/15/155103|bibcode=2008JPhA...41o5103T|s2cid=118983053|issn=1751-8113}}</ref>

== Motivation and history ==

The concept of a gradient network was first introduced by Toroczkai and Bassler (2004).<ref>{{Cite journal|last1=Niu|first1=Rui-Wu|last2=Pan|first2=Gui-Jun|date=2016-04-01|title=Transport optimization on complex gradient networks|url=https://www.sciencedirect.com/science/article/pii/S0577907316301654|journal=Chinese Journal of Physics|language=en|volume=54|issue=2|pages=278–284|doi=10.1016/j.cjph.2016.04.014|bibcode=2016ChJPh..54..278N|issn=0577-9073}}</ref><ref>{{Cite journal|last1=Toroczkai|first1=Zoltán|last2=Bassler|first2=Kevin E.|date=2004|title=Jamming is limited in scale-free systems|journal=Nature|language=en|volume=428|issue=6984|pages=716|doi=10.1038/428716a|pmid=15085122|s2cid=2839066|issn=1476-4687|doi-access=free}}</ref>

Generally, real-world networks (such as [[Citation graph|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 (computing)|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.<ref name="toro" /> 

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.<ref name="toro" /><ref name="grad" />

Recent research{{Which|date=October 2021}}{{Update inline|date=October 2021}} investigates the connection between [[network topology]] and the flow efficiency of the transportation.<ref name="toro">{{cite web|title=Gradient Networks|url=http://cnls.lanl.gov/External/people/highlights/Toroczkai_net.pdf|url-status=live|archive-url=https://web.archive.org/web/20061004090327/https://cnls.lanl.gov/External/people/highlights/Toroczkai_net.pdf|archive-date=4 October 2006|access-date=19 March 2021|website=cnls.lanl.gov}}</ref>

[[File:Gradient network with node pointing to largest increase.jpg|thumb|300px|left|The gradient at node i is a directed edge pointing towards the largest increase of the scalar potential in the node's neighborhood.<ref name="toro" />]]

== In-degree distribution of gradient networks ==
In a gradient network, the [[in-degree]] of a node i, ''k<sub>i</sub> <sup>(in)</sup>'' is the number of gradient edges pointing into i, and the in-degree distribution is '''''<math>R(l)= P\{k_i^{(in)}=l\}</math> .'''''
[[File:Degree distributions of gradient network and substrate (BA model).jpg|thumb|200px|left|The degree distributions of the gradient network and the
substrate([[BA Model]]).<ref name=grad/>]]
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 model|Erdős–Rényi random graph]]), the scalars'' h<sub>i</sub>'' are i.i.d. (independent identically distributed) the exact expression for '''''R(l)''''' is given by
{{center|1=<math>R(l)=\frac{1}{N}\sum_{n=0}^{N-1}\mathrm{C}^{N-1-n}_l[1-p(1-p)]^{N-1-n-l}[p(1-p)^n]^l]</math><ref name="grad" />}}

In the limit <math>N\to\infty </math> and <math>P\to 0  </math>, the degree distribution becomes the power law 
{{center|1=<math> R(l) \approx l^{-1} </math>}}
This shows in this limit, the gradient network of random network is scale-free.<ref name="grad" />

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.<ref name="toro" />

== 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.
[[File:Star network vs ring network.jpg|thumb|200px|left|Illustrating the influence of structure on flows.<ref name=grad/>]]

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:

: <math> J = 1 - \langle \langle \frac{N_\text{receive}}{N_\text{send}} \rangle_h \rangle_\text{network} = R(0)</math>

where ''N''<sub>receive</sub> is the number of nodes that receive gradient flow and N<sub>send</sub> is the number of nodes that send gradient flow.
The value of ''J'' is between 0 and 1; <math>J=0</math> means no congestion, and <math>J=1</math> corresponds to maximal congestion.
In the limit <math>N\to\infty</math>, for an [[Erdős–Rényi model|Erdős–Rényi random graph]], the congestion factor becomes

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

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.<ref name=nature>{{cite journal | last1=Toroczkai | first1=Zoltán | last2=Bassler | first2=Kevin E. | title=Jamming is limited in scale-free systems | journal=Nature | publisher=Springer Science and Business Media LLC | volume=428 | issue=6984 | year=2004 | issn=0028-0836 | doi=10.1038/428716a | pages=716| pmid=15085122 | s2cid=2839066 | doi-access=free }}</ref>
[[File:Congestion coefficient for random graphs and scale-free networks.jpg|thumb|250px|left|Fig.7. The congestion coefficient for random graphs and scale-free networks.<ref name=toro/>]]

== Approaches to control congestion ==
One problem in communication networks is understanding how to control congestion and maintain normal and efficient network function.<ref name=control>{{cite journal | last1=Liu | first1=Zonghua | last2=Ma | first2=Weichuan | last3=Zhang | first3=Huan | last4=Sun | first4=Yin | last5=Hui | first5=P.M. | title=An efficient approach of controlling traffic congestion in scale-free networks | journal=Physica A: Statistical Mechanics and Its Applications | publisher=Elsevier BV | volume=370 | issue=2 | year=2006 | issn=0378-4371 | doi=10.1016/j.physa.2006.02.021 | pages=843–853| arxiv=0806.1845 | bibcode=2006PhyA..370..843L | s2cid=17324268 }}</ref> 

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.<ref name="control" />

Ana L Pastore y Piontti et al. (2008) showed that relaxational dynamics{{Clarify|date=October 2021}} can reduce network congestion.<ref>{{Cite journal|last1=L Pastore y Piontti|first1=Ana|last2=E La Rocca|first2=Cristian|last3=Toroczkai|first3=Zoltán|last4=A Braunstein|first4=Lidia|last5=A Macri|first5=Pablo|last6=López|first6=Eduardo|date=14 May 2008|title=Using relaxational dynamics to reduce network congestion|journal=New Journal of Physics|volume=10|issue=9|page=093007|language=en|publication-date=5 September 2008|doi=10.1088/1367-2630/10/9/093007|bibcode=2008NJPh...10i3007P|s2cid=11842310|doi-access=free|arxiv=0803.3755}}</ref>

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.<ref>{{Cite journal|last1=Pan|first1=Gui-Jun|last2=Liu|first2=Sheng-Hong|last3=Li|first3=Mei|date=2011-09-15|title=Jamming in the weighted gradient networks|url=https://www.sciencedirect.com/science/article/pii/S0378437111002317|journal=Physica A: Statistical Mechanics and Its Applications|language=en|volume=390|issue=18|pages=3178–3182|doi=10.1016/j.physa.2011.03.018|bibcode=2011PhyA..390.3178P|issn=0378-4371}}</ref>{{Clarify|date=October 2021}}

Niu and Pan (2016) showed that congestion can be reduced by introducing a correlation between the gradient field and the local network topology.<ref>{{Cite journal|last1=Niu|first1=Rui-Wu|last2=Pan|first2=Gui-Jun|date=2016-04-01|title=Transport optimization on complex gradient networks|url=https://www.sciencedirect.com/science/article/pii/S0577907316301654|journal=Chinese Journal of Physics|language=en|volume=54|issue=2|pages=278–284|doi=10.1016/j.cjph.2016.04.014|bibcode=2016ChJPh..54..278N|issn=0577-9073}}</ref>{{Clarify|date=October 2021}}
[[File:Average packet number as a function of degree (congestion graph).jpg|thumb|250px|left|<n(k)> is the average packet number as a function of degree, packet-processing capabilities: 0 (circles), 0.05 (squares), 0.1 (stars).<ref name="control" />]]

[[File:Comparison between enhanced and normal approaches (packet-processing capability).jpg|thumb|250px|right|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.<ref name="control" />]]

== See also ==
*[[Network dynamics]]
*[[Network topology]]
*[[Quantum complex network]]

== References ==
<references/>

{{Portal bar|Internet|Engineering|Mathematics|Science}}
[[Category:Network science]]