Sparse network

In the context of network science, a sparse network is a network with less number of links than the maximum possible number of links within the same network. The opposite of the sparse network is dense or complete 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]

Description

The number of links vary from network to network. The number of links in the network can be higher than the number of nodes in network, if each node is linked to every node in the network, such networks are called dense: L = links; N = nodes

If each node is linked to all other nodes, except itself, which means that network does not contain loops, than this type of network is referred as complete. If the number of links is smaller than the maximum number of links, then it is a sparse network. Sparse connectivity can be identified in networks in which nodes are difficult to be linked:

for

Most of the real networks are sparse, however they can still be efficiently analyzed. Typically, sparse networks have a scale-free (power-law) node-degree distribution, meaning that there are few extremely linked nodes and many sparsely linked nodes within the same network.[2]

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.[3] 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.[4]

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.[5]

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 of the real networks are large and sparse, there were several models developed to understand and analyze them.[6]

References

  1. ↑ Barabási, Albert-László (2015). Network Science. Cambridge University Press. Retrieved 25 May 2015.
  2. ↑ Scholz, Matthias. "Getting connected - The highly connected society". Network-Science. Retrieved 25 May 2015.
  3. ↑ http://jdmdh.episciences.org/77/pdf
  4. ↑ Scholz, Matthias (7 January 2015). "Node similarity as a basic principle behind connectivity in complex networks". Journal of Data Mining and Digital Humanities (77). Retrieved 25 May 2015.
  5. ↑ Nykamp, Duane Q. "An introduction to networks". Math Insight. Retrieved 25 May 2015.
  6. ↑ Gribonval, Rémi. "Sparse Models, Algorithms and Learning for Large-scale data". SMALL. Retrieved 25 May 2015.
This article is issued from Wikipedia - version of the 9/1/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.