Gradient network

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.

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. ==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 (1) = {j ∈ V | (i,j)∈ E}. Let us also consider a scalar field, h = {h 0 , .., 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 (1) ∪ {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. In a gradient network, the in-degree of a node i, k i (in) is the number of gradient edges pointing into i, and the in-degree distribution is R(l)= P\{k_i^{(in)}=l\} . ). ]] 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 In the limit N\to\infty and P\to 0 , the degree distribution becomes the power law This shows in this limit, the gradient network of random network is scale-free. 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. 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1348378333 under CC BY-SA 4.0; modifications have been made.