The algorithm builds the histogram of the values of the degree of all nodes, which will be delivered in the two output files.
Pros & Cons
The network to analyze must be undirected, otherwise there are no special constraints.
Basic analysis tool, not particular for special disciplines or problems.
The algorithm requires two inputs, the file where the edges of the network are listed and the number of points one wishes to have in the binned distribution described below. A first read-in of the inputfile will set the values of the number of nodes and edges of the network. In the second read-in the degrees of all nodes will be calculated. Then the distribution is calculated.
The program generates two output files, corresponding to two different ways of partitioning the interval spanned by the values of degree. In the first output, the occurrence of any degree value between the minimum and the maximum is estimated and divided by the number of nodes of the network, so to obtain the probability: the output displays all degree values in the interval with their probabilities.
The second output gives the binned distribution, i.e. the interval spanned by the values of degree is divided into bins whose size grows while going to higher values of the variable. The size of each bin is obtained by multiplying by a fixed number the size of the previous bin. The program calculates the fraction of nodes whose degree falls within each bin. Because of the different sizes of the bins, these fractions must be divided by the respective bin size, to have meaningful averages.
This technique is particularly suitable to study skewed distributions: the fact that the size of the bins grows large for large degree values compensates for the fact that not many nodes have high degree values, so it suppresses the fluctuations that one would observe by using bins of equal size. On a double logarithmic scale, which is very useful to determine the possible power law behavior of the distribution, the points of the latter will appear equally spaced on the x-axis.
The program runs in a time O(m), m being the number of edges of the network.
A simple application of this algorithm could be to calculate the degree distribution of networks created by the modeling algorithms of the NWB. For instance, the network file can be created through the Barabasi-Albert model.
The algorithm was implemented and documented by S. Fortunato, integrated by S. Fortunato and W. Huang.
Albert, R., and Barabasi, A.-L. (2002) Statistical mechanics of complex networks. Review of Modern Physics 74:47-97.
Newman, M.E.J. (2003) The structure and function of complex networks. SIAM Review 45:167-256.
Pastor-Satorras, R., Vespignani, A. (2004) Evolution and Structure of the Internet. Cambridge University Press.
Boccaletti, S., Latora, V., Moreno, Y.,Chavez, M., Hwang, D.-U. (2006) Complex networks: Structure and dynamics. Physics Reports 424: 175-308.