Sparse network

In network science, a sparse network has much fewer links than the possible maximum number of links within that network (the opposite is a dense network). The study of sparse networks is a relatively new area primarily stimulated by the study of real networks, such as social and computer networks. ^[1]

The notion of much fewer links is, of course, colloquial and informal. While a threshold for a particular network may be invented, there is no universal threshold that defines what much fewer actually means. As a result, there is no formal sense of sparsity for any finite network, despite widespread agreement that most empirical networks are indeed sparse. There is, however, a formal sense of sparsity in the case of infinite network models, determined by the behavior of the number of edges (M) and/or the average degree (⟨k⟩) as the number of nodes (N) goes to infinity. ^[2]

Definitions

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.

Node degree distribution

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]

Common terminology

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]

Applications

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]

References

1. Barabási, Albert-László (2015). Network Science. Cambridge University Press. Retrieved 25 May 2015.
2. Newman, Mark. Networks 2nd Edition . Retrieved 14 Feb 2021.
3. Bollobás, Béla (1985). Random Graphs. Academic Press.
4. Janson, Svante (2018). "On Edge Exchangeable Random Graphs". J Stat Phys. 173 (3–4): 448–484. arXiv: 1702.06396 . Bibcode:2018JSP...173..448J. doi:10.1007/s10955-017-1832-9. PMC   6405020 . PMID   30930480.
5. van der Hofstad, Remco (2017). Random Graphs and Complex Networks. Cambridge University Press. doi:10.1017/9781316779422. ISBN   9781316779422.
6. Scholz, Matthias (7 January 2015). "Node similarity as a basic principle behind connectivity in complex networks". Journal of Data Mining and Digital Humanities. 2015 (77). arXiv: 1010.0803 . doi: 10.46298/jdmdh.33 . S2CID   221799 . Retrieved 25 May 2015.
7. Nykamp, Duane Q. "An introduction to networks". Math Insight. Retrieved 25 May 2015.
8. Gribonval, Rémi. "Sparse Models, Algorithms and Learning for Large-scale data". SMALL. Retrieved 25 May 2015.