Sparse network

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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. 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 (L) and/or the average degree ( ) as the number of nodes (N) goes to infinity.

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. 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 (L) and/or the average degree ( ) as the number of nodes (N) goes to infinity. L \ll L_{max} = {N\choose 2} . In any given (real) network, the number of nodes N and links L are just two numbers, therefore the meaning of the much smaller sign ( \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 G_{N} , or a network model that is well defined for networks G_{N} of any size N = 1,2,..., \infty , then the \ll attains its usual formal meaning: L \ll L_{max} \iff L = o(L_{max}) \iff \lim_{N\rightarrow\infty}\frac{L}{L_{max}}=0 . In other words, a network sequence or model G_N is called dense or sparse depending on whether the (expected) average degree \langle k\rangle = 2L/N in G_N scales linearly or sublinearly with N: G_N is dense if \langle k\rangle = O(N) ; G_N is sparse if \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: G_N is truly sparse or extremely sparse or ultrasparse if \langle k\rangle = O(1) . There also exist alternative, stricter definitions of network sparsity requiring the convergence of the degree distribution in G_N to a well defined limit at N \rightarrow \infty . According to this definition, the N-star graph S_N , for example, is not sparse.

References

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

Provenance

snapshot enwiki-001315447731 · captured 1759769117.0 · version history

Cite this page as: encyclopegia.org, “Sparse network”, snapshot enwiki-001315447731. https://encyclopegia.org/a/sparse-network

Sources cited in this revision

5 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.