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 (⟨k⟩) as the number of nodes (N) goes to infinity.
Definitions A simple unweighted network of size N {\displaystyle N} is called sparse if the number of links L {\displaystyle L} in it is much smaller than the maximum possible number of links L m a x {\displaystyle L_{max}} :
L ≪ L m a x = ( N 2 ) {\displaystyle 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 ( ≪ {\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 G N {\displaystyle G_{N}} , or a network model that is well defined for networks G N {\displaystyle G_{N}} of any size N = 1,2,..., ∞ {\displaystyle \infty } , then the ≪ {\displaystyle \ll } attains its usual formal meaning:
L ≪ L m a x ⟺ L = o ( L m a x ) ⟺ lim N → ∞ L L m a x = 0 {\displaystyle 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 {\displaystyle G_{N}} is called dense or sparse depending on whether the (expected) average degree ⟨ k ⟩ = 2 L / N {\displaystyle \langle k\rangle =2L/N} in G N {\displaystyle G_{N}} scales linearly or sublinearly with N:
G N {\displaystyle G_{N}} is dense if ⟨ k ⟩ = O ( N ) {\displaystyle \langle k\rangle =O(N)} ;
G N {\displaystyle G_{N}} is sparse if ⟨ k ⟩ = o ( N ) {\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:
G N {\displaystyle G_{N}} is truly sparse or extremely sparse or ultrasparse if ⟨ k ⟩ = O ( 1 ) {\displaystyle \langle k\rangle =O(1)} . There also exist alternative, stricter definitions of network sparsity requiring the convergence of the degree distribution in G N {\displaystyle G_{N}} to a well defined limit at N → ∞ {\displaystyle N\rightarrow \infty } . According to this definition, the N-star graph S N {\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. 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.
… excerpt ends here. Continue reading the full article.
