Degree distribution

From Wikipedia, the free encyclopedia

In/out degree distribution for Wikipedia's hyperlink graph (log-log-log coordinates)

In graph theory, degree distribution gives the probability distribution of degrees in a network. Its use originates from the study of random graph by Paul Erdős and Alfréd Rényi ^[1], and it has become an important concept which describes the topology of complex networks.

1 Definition
- 1.1 Degree
- 1.2 Degree distribution
2 Degree distribution of various networks
3 References
4 References

[edit] Definition

[edit] Degree

The degree of a node (or connectivity) is, $k$ , tells how many links (or edges) the node has to other nodes.

In directed networks nodes have two types of degrees. The incoming degree k_in denotes the number of links that point to a node, and an outgoing degree k_out denotes the number of links that start from it. An undirected network with N nodes and L links is characterized by an average degree $< k > = 2 L / N$ (where <> denotes the average)^[2]. Otherwise, both incoming and outgoing links are counted in the undirected case.^[3]

[edit] Degree distribution

The degree distribution, $P (k)$ , is a function describing the total number of vertices in a graph with a given degree (number of connections to other vertices).

Formally, the degree distribution is

$p(k) = \sum_{v \in V | \deg(v)=k} 1$

where v is a vertex in the set of the graph's vertices V, and $deg(v)$ is the degree of vertex v.

This same information is often presented as the cumulative degree distribution,

$P(k) = \sum_{k' = k}^{\infty} p(k')$ .

[edit] Degree distribution of various networks

Different types of complex network have different characteristic of degree distributions $P (k)$ . Thus, the shape of a degree distribution allows us to distinguish between different classes of networks.

For example, the Erdős–Rényi random network has Binomial distribution,

$P(k_i = k) = C^{N-1}_k p^k(1 - p)^{N-1-k}$ ,

and the peaked degree distribution of this random network indicates that the system has a characteristic degree and that there are no highly connected nodes (which are also known as hubs). By contrast, for scale-free networks, a power-law degree distribution ^[4]

$P(k)\,\!\!\sim k^{-\gamma}$

indicates that a few hubs hold together numerous small nodes.

[edit] References

^ Erdos, P. and Renyi, A., 1959, Publ. Math. (Debrecen) 6, 290.
^ A.-L. Barabási and Z. N. Oltvai, Nature Reviews Genetics 5, 101-113 (2004)
^ Freeman, L.C., 1979. Centrality in networks: I. Conceptual clarification. Social Networks 1, 215–239.
^ R. Albert and A.-L. Barabási, Reviews of Modern Physics 74, 47-97 (2002).