Feature: Scale-Free Degree Distribution (Python)
Relevant source files
The following files were used as context for generating this wiki page:The Network.py script is a Python-based tool for analyzing network structures, specifically to determine if they exhibit a scale-free degree distribution. It reads a network from an edgelist file, calculates the degree of each node, bins the degrees logarithmically, and then performs a linear regression on the log-log plot to calculate the degree exponent (gamma, γ). The output is an interactive HTML chart visualizing the distribution and a CSV file containing the histogram data.
This script is part of a larger repository of study programs designed to accompany the Barabasi Network Science textbook. The repository also includes C# tools for generating networks using preferential attachment and for performing other network analyses, such as calculating clustering coefficients and degree correlation.
Sources: README.md, Network.py
Data Processing Pipeline
The Network.py script follows a clear pipeline to process the network data and generate the degree distribution analysis. It starts by reading a raw edgelist file and ends with generating a plot and summary statistics.
Sources: Network.py
The following diagram illustrates the data flow within the Network.py script.
Sources: Network.py:10-70
Input and Configuration
The script's behavior is controlled by a few variables set at the beginning of the file. The primary input is a tab-separated edgelist file.
| Parameter | Type | Default Value | Description |
|---|---|---|---|
dataset | string | "www.edgelist.txt" | The name of the input edgelist file. |
directed | bool | True | If True, the graph is treated as directed. |
want_in | bool | True | If directed is True, this determines whether to analyze in-degree (True) or out-degree (False). |
Sources: Network.py:10-12
Degree Calculation
Degrees are calculated using the pandas library. The script groups the edgelist by the source node (column 'A') to get out-degrees and by the target node (column 'B') to get in-degrees. It then combines these into a single DataFrame.
- Out-degree:
edgelist.groupby('A').count() - In-degree:
edgelist.groupby('B').count() - Total degree: Sum of in-degree and out-degree for each node.
Sources: Network.py:18-23
Scale-Free Analysis
The core of the script is its analysis of the degree distribution to find the power-law exponent (gamma), which is a key characteristic of scale-free networks.
Logarithmic Binning
To accurately visualize and analyze a power-law distribution, where many nodes have a low degree and a few "hub" nodes have a very high degree, the script uses logarithmic binning. This creates bins that are of equal size on a logarithmic scale.
# Network.py:34
bins = np.logspace(np.log10(min_deg), np.log10(max_deg), num=bins_count, base=10) # Logarithmic binning
Sources: Network.py:34
Gamma (γ) Exponent Calculation
The script transforms the binned degree counts and the degree values to a log-log scale. It then uses scipy.stats.linregress to perform a linear regression on this transformed data. For a scale-free network, the degree distribution P(k) follows a power law, P(k) ~ k-γ. On a log-log plot, this relationship becomes linear: log(P(k)) ~ -γ log(k). Therefore, the degree exponent gamma (γ) is the negative of the slope of the regression line.
# Network.py:40-43
x = histo['Log_Right']
y = histo['Log_Count']
slope, intercept, r_value, p_value, std_err = statlib.linregress(x, y)
The calculated gamma is then displayed in the output statistics.
# Network.py:53
string1 += "Gamma: %1.2f <br>" % -slope
Sources: Network.py:40-43, 53
Outputs
The script produces three main outputs: a set of summary statistics, an interactive HTML plot, and a CSV file with the histogram data.
| Output | Description |
|---|---|
| Summary Statistics | Displayed in the HTML file, including nodes, links, average degree, max degree, and the calculated gamma (γ). |
chart.htm | An interactive log-log plot generated with bokeh. It shows the degree distribution (blue circles) and the power-law fit from the linear regression (red line). |
<dataset>.histo.csv | A CSV file containing the binned degree data, including the bin ranges, counts, log-transformed values, and predicted counts from the regression model. |
Sources: Network.py:14, 45-61
Related C# Implementations
The repository contains C# applications that complement the Python script, providing tools for network generation and an alternative analysis approach.
Network Generation (Barabasi.cs)
The Barabasi.cs file contains logic to generate a network using the Barabasi-Albert model, which employs preferential attachment to create scale-free networks. The generated network is saved as an edgelist file, which can then be used as input for Network.py.
This diagram shows the classes used for network generation.
Sources: Barabasi.cs:23-91
Alternative Analysis in C# (Form1.cs)
The C# Charts application (Form1.cs) provides a GUI for network analysis. It also calculates the degree exponent, but it uses a different method based on the cumulative degree distribution.
In this approach, it fits a power function to the tail of the cumulative distribution P(k). The relationship for a cumulative distribution is P(k) ~ k-(γ-1). The code uses MathNet.Numerics.Fit.Power to find the exponent exp2 and then calculates gamma as 1 - exp2.
// Form1.cs:310
Tuple<double, double> r2 = MathNet.Numerics.Fit.Power(X2Values, Y2Values);
double c2 = r2.Item1;
double exp2 = r2.Item2;
lblGamma.Text = "Degree exponent (gamma): " + String.Format("{0:n3}", 1-exp2); //For cumulative distro gamma = 1 - exp
The UI for this application, defined in Form1.Designer.cs, explicitly includes a chart titled "Cumulative Degree Distribution".
Sources: Form1.cs:304-310, Form1.Designer.cs:181-192
Conclusion
The Network.py script is an effective tool for performing a foundational analysis in network science: testing for the scale-free property of a network's degree distribution. By calculating the degree exponent (gamma) through linear regression on log-log binned data and providing a clear bokeh visualization, it offers a direct way to investigate network topology. Its functionality is enhanced by the other components in the repository, such as the Barabasi.cs network generator and the alternative analysis methods in the C# Charts application, creating a small but comprehensive toolkit for studying network science principles.
Sources: README.md, Network.py, Barabasi.cs, Form1.cs