Description
The algorithm builds the histogram of the values of the indegree of all nodes, which will be delivered in the two output files.
Pros & Cons
The network to analyze must be directed, otherwise there are no special constraints.
Applications
Basic analysis tool, not particular for special disciplines or problems.
Implementation Details
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 indegrees 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 indegree. In the first output, the occurrence of any indegree 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 indegree values in the interval with their probabilities.
The second output gives the binned distribution, i.e. the interval spanned by the values of indegree 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 indegree 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 indegree values compensates for the fact that not many nodes have high indegree 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.
Links
Acknowledgements
The algorithm was implemented and documented by S. Fortunato, integrated by S. Fortunato and W. Huang.
References
Bollobas, B. (2002) Modern Graph Theory. Springer Verlag, New York.
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.(2002) 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.