Sparse network

A simple unweighted network of size ${\displaystyle N}$ is called sparse if the number of links ${\displaystyle M}$ in it is much smaller than the maximum possible number of links ${\displaystyle M_{max}}$:[1]

${\displaystyle M\ll M_{max}={N \choose 2}}$ .

In any given (real) network, the number of nodes N and links M are just two numbers, therefore the meaning of the much smaller sign (${\displaystyle \ll }$ above) is purely colloquial and informal, and so are statements like "many real networks are sparse."

However, if we deal with a synthetic graph sequence ${\displaystyle G_{N}}$, or a network model that is well defined for networks ${\displaystyle G_{N}}$ of any size N = 1,2,...,${\displaystyle \infty }$, then the ${\displaystyle \ll }$ attains its usual formal meaning:

${\displaystyle M\ll M_{max}\iff M=o(M_{max})\iff \lim _{N\rightarrow \infty }{\frac {M}{M_{max}}}=0}$.

In other words, a network sequence or model ${\displaystyle G_{N}}$ is called dense or sparse depending on whether the (expected) average degree ${\displaystyle \langle k\rangle =2M/N}$ in ${\displaystyle G_{N}}$ scales linearly or sublinearly with N:[2][3]

${\displaystyle G_{N}}$ is dense if ${\displaystyle \langle k\rangle =O(N)}$;

${\displaystyle G_{N}}$ is sparse if ${\displaystyle \langle k\rangle =o(N)}$.

An important subclass of sparse networks are networks whose average degree is either constant or converges to a constant. Some authors call only such networks sparse, while others reserve special names for them: [4]

${\displaystyle G_{N}}$ is truly sparse or extremely sparse or ultrasparse if ${\displaystyle \langle k\rangle =O(1)}$.

There also exist alternative, stricter definitions of network sparsity requiring the convergence of the degree distribution in ${\displaystyle G_{N}}$ to a well defined limit at ${\displaystyle N\rightarrow \infty }$.[5] According to this definition, the N-star graph ${\displaystyle S_{N}}$, for example, is not sparse.

The node degree distribution changes with the increasing connectivity. Different link densities in the complex networks have different node-degree distribution, as Flickr Network Analysis suggests.[6] The sparsely connected networks have a scale free, power law distribution. With increasing connectivity, the networks show increasing divergence from power law. One of the main factors, influencing on the network connectivity is the node similarity. For instance, in social networks, people are likely to be linked to each other if they share common social background, interests, tastes, beliefs, etc. In context of biological networks, proteins or other molecules are linked if they have exact or complementary fit of their complex surfaces.[6]

If the nodes in the networks are not weighted, the structural components of the network can be shown through adjacency matrix. If the most elements in the matrix are zero, such matrix is referred as sparse matrix. In contrast, if most of the elements are nonzero, then the matrix is dense. The sparsity or density of the matrix is identified by the fraction of the zero element to the total number of the elements in the matrix. Similarly, in the context of graph theory, if the number of links is close to its maximum, then the graph would be known as dense graph. If the number of links is lower than the maximum number of links, this type of graphs are referred as sparse graph.[7]

Sparse Network can be found in social, computer and biological networks, as well as, its applications can be found in transportation, power-line, citation networks, etc. Since most real networks are large and sparse, there were several models developed to understand and analyze them.[8] These networks have inspired sparse network-on-chip design in multiprocessor embedded computer engineering.

Sparse networks also induce cheaper computations by making it efficient to store the network as an Adjacency list, rather than an Adjacency matrix. For example, when using an adjacency list, iterating over a node's neighbors can be achieved in O(M/N), whereas it is achieved in O(N) with an adjacency matrix.[2]