Description
Study of the correlation between the clustering coefficient (defined a la Watts-Strogatz) and the degree of the nodes of a network. The correlation is expressed through the function c(k), which represents the average clustering coefficient of all nodes with degree k.
Pros & Cons
The network to analyze must be undirected, otherwise there are no special constraints.
Applications
The correlation function c(k) can help to identify hierarchical organization in networks.
Implementation Details
The algorithm requires two inputs, the file where the edges of the network are listed and the number of points for the binned correlation function 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 degree of all nodes is calculated and the edges are stored in an array. Then the clustering coefficients for all nodes are calculated. The program generates one output file, corresponding to the binned correlation function, i.e. the interval spanned by the values of the 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 average clustering coefficient of nodes whose degree falls within each bin. Because of the different sizes of the bins, these averages must be divided by the respective bin size, to have consistent results.
This technique is particularly suitable to study skewed correlation functions: the fact that the size of the bins grows large for large values of the degree compensates for the fact that not many nodes have high degrees, 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 correlation function, the points of the latter will appear equally spaced on the x-axis.
The algorithm runs in a time , where is the number of nodes of the network and is the average degree squared.
Usage Hints
A simple application of this algorithm could be to calculate c(k) for networks created by the modeling algorithms of the NWB. For instance, the inputfile can be created through the Barabasi-Albert model.
Links
Acknowledgements
The algorithm was implemented and documented by S. Fortunato, integrated by S. Fortunato and W. Huang.
References
Vazquez, A., Pastor-Satorras, R., Vespignani, A. (2002) Large-scale topological and dynamical properties of Internet
Physical Review E 65:066130.