HOME

TheInfoList



OR:

In
network science 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 repr ...
, a gradient network is a directed
subnetwork A subnetwork or subnet is a logical subdivision of an IP network. Updated by RFC 6918. The practice of dividing a network into two or more networks is called subnetting. Computers that belong to the same subnet are addressed with an identica ...
of an undirected "substrate"
network Network, networking and networked may refer to: Science and technology * Network theory, the study of graphs as a representation of relations between discrete objects * Network science, an academic field that studies complex networks Mathematics ...
where each
node In general, a node is a localized swelling (a "knot") or a point of intersection (a vertex). Node may refer to: In mathematics * Vertex (graph theory), a vertex in a mathematical graph * Vertex (geometry), a point where two or more curves, line ...
has an associated
scalar potential In mathematical physics, scalar potential, simply stated, describes the situation where the difference in the potential energies of an object in two different positions depends only on the positions, not upon the path taken by the object in trav ...
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 = \ and the set of edges E = \ . Given a node ''i'', we can define its set of neighbors in G by Si(1) = . Let us also consider a scalar field, ''h'' = 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'') ∈ Si(1) ∪ , and hμ has the maximum value in . ''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.


Motivation and history

The concept of a gradient network was first introduced by Toroczkai and Bassler (2004). Generally, real-world networks (such as citation graphs, the
Internet The Internet (or internet) is the global system of interconnected computer networks that uses the Internet protocol suite (TCP/IP) to communicate between networks and devices. It is a ''internetworking, network of networks'' that consists ...
, 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 get replaced by several interconnected new routers. 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 In mathematics and physics, a scalar field is a function associating a single number to every point in a space – possibly physical space. The scalar may either be a pure mathematical number ( dimensionless) or a scalar physical quantit ...
distributed on the network. Recent research investigates the connection between
network topology Network topology is the arrangement of the elements ( links, nodes, etc.) of a communication network. Network topology can be used to define or describe the arrangement of various types of telecommunication networks, including command and contr ...
and the flow efficiency of the transportation.


In-degree distribution of gradient networks

In a gradient network, the
in-degree In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pai ...
of a node i, ''ki (in)'' is the number of gradient edges pointing into i, and the in-degree distribution is ''R(l)= P\ .'' 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 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 The Barabási–Albert (BA) model is an algorithm for generating random scale-free networks using a preferential attachment mechanism. Several natural and human-made systems, including the Internet, the World Wide Web, citation networks, and s ...
, then the gradient network also follow the power-law with the same exponent as those of G.


The congestion on networks

The fact that the topology of the substrate network influence the level of
network congestion Network congestion in data networking and queueing theory is the reduced quality of service that occurs when a network node or link is carrying more data than it can handle. Typical effects include queueing delay, packet loss or the blocking ...
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. 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 \rangle_h \rangle_\text = R(0) where ''N''receive 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; 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 \left 1 + O(\frac) \rightrightarrow 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.


Approaches to control congestion

One problem in communication networks is understanding how to control congestion and maintain normal and efficient network function. 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. Ana L Pastore y Piontti et al. (2008) showed that relaxational dynamics can reduce network congestion. 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. Niu and Pan (2016) showed that congestion can be reduced by introducing a correlation between the gradient field and the local network topology.


See also

*
Network dynamics Network dynamics is a research field for the study of networks whose status changes in time. The dynamics may refer to the structure of connections of the units of a network, to the collective internal state of the network, or both. The networked ...
*
Network topology Network topology is the arrangement of the elements ( links, nodes, etc.) of a communication network. Network topology can be used to define or describe the arrangement of various types of telecommunication networks, including command and contr ...
*
Quantum complex network Quantum complex networks are complex networks whose nodes are quantum computing devices. Quantum mechanics has been used to create secure quantum communications channels that are protected from hacking. Quantum communications offer the potential ...


References

{{Portal bar, Internet, Engineering, Mathematics, Science Networks