Degree distribution

In the study of graphs and networks, the degree of a node in a network is the number of connections it has to other nodes and the degree distribution is the probability distribution of these degrees over the whole network.

DefinitionEdit

The degree of a node in a network (sometimes referred to incorrectly as the connectivity) is the number of connections or edges the node has to other nodes. If a network is directed, meaning that edges point in one direction from one node to another node, then nodes have two different degrees, the in-degree, which is the number of incoming edges, and the out-degree, which is the number of outgoing edges.

The degree distribution P(k) of a network is then defined to be the fraction of nodes in the network with degree k. Thus if there are n nodes in total in a network and nk of them have degree k, we have  .

The same information is also sometimes presented in the form of a cumulative degree distribution, the fraction of nodes with degree smaller than k, or even the complementary cumulative degree distribution, the fraction of nodes with degree greater than or equal to k (1 - C) if one considers C as the cumulative degree distribution; i.e. the complement of C.

Observed degree distributionsEdit

The degree distribution is very important in studying both real networks, such as the Internet and social networks, and theoretical networks. The simplest network model, for example, the (Erdős–Rényi model) random graph, in which each of n nodes is independently connected (or not) with probability p (or 1 − p), has a binomial distribution of degrees k:

 

(or Poisson in the limit of large n, if the average degree   is held fixed). Most networks in the real world, however, have degree distributions very different from this. Most are highly right-skewed, meaning that a large majority of nodes have low degree but a small number, known as "hubs", have high degree. Some networks, notably the Internet, the world wide web, and some social networks were argued to have degree distributions that approximately follow a power law:  , where γ is a constant. Such networks are called scale-free networks and have attracted particular attention for their structural and dynamical properties.[1][2][3][4] However, a survey of a wide range of real world networks suggests that scale-free networks are rare when assessed using statistically rigorous measures.[5] Some researchers have disputed these findings arguing that the definitions used in the study are inappropriately strict,[6] while others have argued that the precise functional form of the degree distribution is less important than knowing whether the degree distribution is fat-tailed or not.[7] The over-interpretation of specific forms of the degree distribution has also been criticised for failing to consider how networks may evolve over time.[8]

Excess degree distributionEdit

Excess degree distribution is the probability distribution, for a node reached by following an edge, of the number of other edges attached to that node.[9] In other words, it is the distribution of outgoing links from a node reached by following a link.

Suppose a network has a degree distribution  , by selecting one node (randomly or not) and going to one of its neighbors (assuming to have one neighbor at least), then the probability of that node to have   neighbors is not given by  . The reason is that, whenever some node is selected in a heterogeneous network, it is more probable to reach the hubs by following one of the existing neighbors of that node. The true probability of such nodes to have degree   is   which is called the excess degree of that node. In the configuration model, which correlations between the nodes have been ignored and every node is assumed to be connected to any other nodes in the network with the same probability, the excess degree distribution can be found as:[9]

 

where   is the mean-degree (average degree) of the model. It follows to that fact that the average degree of the neighbor of any node is greater than the average degree of that node. In social networks, it mean that your friends, on average, have more friends than you. This is famous as the friendship paradox. It can be shown that a network can have a giant component, if its average excess degree is larger than one:

 

Bear in mind that the last two equations are just for the configuration model and to derive the excess degree distribution of a real-word network, we should also add degree correlations into account.[9]

The Generating Functions MethodEdit

Generating functions can be used to calculate different properties of random networks. Given the degree distribution and the excess degree distribution of some network,   and   respectively, it is possible to write two power series in the following forms:

  and  

  can also be obtained from derivatives of  :

 

If we know the generating function for a probability distribution   then we can recover the values of   by differentiating:

 

Some properties, e.g. the moments, can be easily calculated from   and its derivatives:

  •  
  •  

And in general:[9]

  •  

For Poisson-distributed random networks, such as the ER graph,  , that is the reason why the theory of random networks of this type is especially simple. The probability distributions for the 1st and 2nd-nearest neighbors are generated by the functions   and  . By extension, the distribution of  -th neighbors is generated by:

 , with   iterations of the function   acting on itself.[10]

The average number of 1st neighbors,  , is   and the average number of 2nd neighbors is:  

Degree distribution for directed networksEdit

 
In/out degree distribution for Wikipedia's hyperlink graph (logarithmic scales)

In a directed network, each node has some in-degree   and some out-degree   which are the number of links which have run into and out of that node respectfully. If   is the probability that a randomly chosen node has in-degree   and out-degree   then the generating function assigned to this joint probability distribution can be written with two valuables   and   as:

 

Since every link in a directed network must leave some node and enter another, the net average number of links entering a node is zero. Therefore,

 ,

which implies that, the generation function must satisfy:

 

where   is the mean degree (both in and out) of the nodes in the network;  

Using the function  , we can again find the generation function for the in/out-degree distribution and in/out-excess degree distribution, as before.   can be defined as generating functions for the number of arriving links at a randomly chosen node, and  can be defined as the number of arriving links at a node reached by following a randomly chosen link. We can also define generating functions   and   for the number leaving such a node:[10]

  •  
  •  
  •  
  •  

Here, the average number of 1st neighbors,  , or as previously introduced as  , is   and the average number of 2nd neighbors reachable from a randomly chosen node is given by:  . These are also the numbers of 1st and 2nd neighbors from which a random node can be reached, since these equations are manifestly symmetric in   and  .[10]

Degree distribution for signed networksEdit

In a signed network, each node has a positive-degree   and a negative degree   which are the positive number of links and negative number of links connected to that node respectfully. So   and   denote negative degree distribution and positive degree distribution of the signed network.[11][12]

See alsoEdit

ReferencesEdit

  1. ^ Barabási, Albert-László; Albert, Réka (1999-10-15). "Emergence of Scaling in Random Networks". Science. 286 (5439): 509–512. arXiv:cond-mat/9910332. Bibcode:1999Sci...286..509B. doi:10.1126/science.286.5439.509. ISSN 0036-8075. PMID 10521342.
  2. ^ Albert, Réka; Barabási, Albert-László (2000-12-11). "Topology of Evolving Networks: Local Events and Universality" (PDF). Physical Review Letters. 85 (24): 5234–5237. arXiv:cond-mat/0005085. Bibcode:2000PhRvL..85.5234A. doi:10.1103/physrevlett.85.5234. hdl:2047/d20000695. ISSN 0031-9007. PMID 11102229.
  3. ^ Dorogovtsev, S. N.; Mendes, J. F. F.; Samukhin, A. N. (2001-05-21). "Size-dependent degree distribution of a scale-free growing network". Physical Review E. 63 (6): 062101. arXiv:cond-mat/0011115. Bibcode:2001PhRvE..63f2101D. doi:10.1103/physreve.63.062101. ISSN 1063-651X. PMID 11415146.
  4. ^ Pachon, Angelica; Sacerdote, Laura; Yang, Shuyi (2018). "Scale-free behavior of networks with the copresence of preferential and uniform attachment rules". Physica D: Nonlinear Phenomena. 371: 1–12. arXiv:1704.08597. Bibcode:2018PhyD..371....1P. doi:10.1016/j.physd.2018.01.005.
  5. ^ Broido, Anna D.; Clauset, Aaron (2019-03-04). "Scale-free networks are rare". Nature Communications. 10 (1): 1017. doi:10.1038/s41467-019-08746-5. ISSN 2041-1723.
  6. ^ Voitalov, Ivan; van der Hoorn, Pim; van der Hofstad, Remco; Krioukov, Dmitri (18 October 2019). "Scale-free networks well done". Physical Review Research. 1 (3): 033034. doi:10.1103/PhysRevResearch.1.033034.
  7. ^ Holme, Petter (2019-03-04). "Rare and everywhere: Perspectives on scale-free networks". Nature Communications. 10 (1): 1016. Bibcode:2019NatCo..10.1016H. doi:10.1038/s41467-019-09038-8. ISSN 2041-1723. PMC 6399274. PMID 30833568.
  8. ^ Falkenberg, Max; Lee, Jong-Hyeok; Amano, Shun-ichi; Ogawa, Ken-ichiro; Yano, Kazuo; Miyake, Yoshihiro; Evans, Tim S.; Christensen, Kim (18 June 2020). "Identifying time dependence in network growth". Physical Review Research. 2 (2): 023352. doi:10.1103/PhysRevResearch.2.023352.
  9. ^ a b c d Newman, Mark (2018-10-18). Networks. 1. Oxford University Press. doi:10.1093/oso/9780198805090.001.0001. ISBN 978-0-19-880509-0.
  10. ^ a b c Newman, M. E. J.; Strogatz, S. H.; Watts, D. J. (2001-07-24). "Random graphs with arbitrary degree distributions and their applications". Physical Review E. 64 (2): 026118. doi:10.1103/PhysRevE.64.026118. ISSN 1063-651X.
  11. ^ Saberi M, Khosrowabadi R, Khatibi A, Misic B, Jafari G (January 2021). "Topological impact of negative links on the stability of resting-state brain network". Scientific Reports. doi:10.1038/s41598-021-81767-7. PMC 7838299. PMID 33500525.
  12. ^ Ciotti V (2015). "Degree correlations in signed social networks". Physica A: Statistical Mechanics and its Applications. arXiv:1412.1024. doi:10.1016/j.physa.2014.11.062.