Feature: Preferential Attachment Network Generation (C#)
Relevant source files
The following files were used as context for generating this wiki page:
This feature provides a C# console application for generating scale-free networks using the Barabási-Albert model, which is based on the concept of preferential attachment. The implementation allows for the creation of a network with a specified number of nodes and degree, and then saves the resulting network structure as an edgelist file. This generator is part of a larger project aimed at studying network science concepts, which also includes a separate C# Windows Forms application for network analysis and visualization.
Sources: README.md, Barabasi.cs:7-18
Architecture and Core Components
The network generation logic is encapsulated within a single console application defined in Barabasi.cs. This application is self-contained for the purpose of generation and outputs a file that can be consumed by other tools, such as the Charts network analyzer application included in the repository.
Sources: Barabasi.cs, Program.cs
Key Classes
The generation process relies on a few simple classes to represent the network structure.
| Class | File | Description |
|---|---|---|
Program | Barabasi.cs | The main class for the console application, containing the Main entry point and the definitions for Edge and Edgelist. |
Edge | Barabasi.cs | A simple data structure representing a link between two nodes, a and b. A similar Edge class also exists in the analysis tool. |
Edgelist | Barabasi.cs | A class that holds a List<Edge> and contains the core logic for network generation, rewiring, and writing to a file. |
Sources: Barabasi.cs:9-100, Form1.cs:52-62
The relationship between these classes is shown in the diagram below.
This diagram illustrates the composition of the Edgelist class, which holds multiple Edge objects, and its usage by the main Program.
Sources: Barabasi.cs:9-100
Network Generation Algorithm
The core of the feature is the implementation of the Barabási-Albert model in the Edgelist class constructor. This process follows the principles of "growth" and "preferential attachment".
Sources: Barabasi.cs:50-71
Generation Flow
The generation process can be broken down into the following steps:
- Initialization: The network starts with a small, initial connected graph. In this implementation, it is a square of four nodes (0, 1, 2, 3).
- Growth: The network grows by adding one new node at a time, from node
4up to the total number ofnodesspecified. - Preferential Attachment: For each
new_nodeadded, a number of edges equal todegreeare created. The other endpoint for each new edge (old_node) is selected from the existing nodes in the network. The selection is "preferential" because nodes with a higher degree have a higher probability of being chosen. - Edge Creation: A new
Edgeis added to theedgelistconnecting thenew_nodeand the selectedold_node.
The following diagram shows the workflow for generating the network.
This flowchart visualizes the nested loops for adding nodes and creating preferential attachments.
Sources: Barabasi.cs:53-70
Preferential Selection Mechanism
The preferential attachment mechanism is implemented by treating the edgelist as a flat list of node identifiers. Since a node's identifier appears in the edgelist once for each edge connected to it, its frequency is proportional to its degree.
A random integer rnd_node_idx is chosen from 1 to count * 2, where count is the current number of edges. This index is then mapped back to either the a or b property of an edge in the list, effectively selecting a node with a probability proportional to its degree.
// Barabasi.cs:61-66
rnd_node_idx = rnd.Next(1, count * 2 + 1); //Treat edge list as single (one-based) node list
if (rnd_node_idx % 2 == 0)
old_node = edgelist[rnd_node_idx / 2 - 1].b;
else
old_node = edgelist[(int)rnd_node_idx / 2].a;
This snippet shows the logic for selecting an existing node based on its prevalence in the current edgelist.
Sources: Barabasi.cs:61-66
Constructor Parameters
The Edgelist constructor takes the following parameters to control the network generation:
| Parameter | Type | Description |
|---|---|---|
nodes | int | The total number of nodes the final network should have. |
degree | int | The number of new edges to add for each new node. |
multi | bool | If false, prevents a new node from linking to the same old_node twice. |
Sources: Barabasi.cs:50-52
Post-Processing: Edge Rewiring
After generation, the network can be modified using the Associate method. This method performs edge rewiring on a specified percentage of the links to adjust the network's assortativity (degree correlation).
Sources: Barabasi.cs:72-95
Rewiring Logic
The Associate method randomly selects two edges from the list and rewires them. The positive parameter controls the type of rewiring:
- Associative (
positive = true): The two nodes with the lowest IDs are connected, and the two nodes with the highest IDs are connected. This tends to link nodes of similar degree. - Disassociative (
positive = false): The lowest ID node is connected to the highest, and the two middle ID nodes are connected. This tends to link high-degree nodes to low-degree nodes.
The process is repeated for a number of links determined by the percentage p.
This flowchart details the logic inside the Associate method for network rewiring.
Sources: Barabasi.cs:72-95
Execution and Output
The Main method in Barabasi.cs orchestrates the entire process. It defines the network parameters, instantiates the Edgelist to generate the network, calls the Associate method for rewiring, and finally writes the edgelist to a file.
The following sequence diagram shows the execution flow.
This diagram illustrates the sequence of calls from the program's entry point to generate, modify, and save the network.
Sources: Barabasi.cs:11-18, Barabasi.cs:96-99
The output is a simple text file where each line contains two tab-separated node IDs, representing one edge. This format is compatible with the openToolStripMenuItem_Click handler in the Charts analysis application.
Sources: Barabasi.cs:98, Form1.cs:214-217
Conclusion
The preferential attachment network generation feature is a foundational component of this Network Science project. It provides a direct C# implementation of the Barabási-Albert model through a simple console application. The generated output is a standard edgelist file, which can be easily imported into the accompanying Charts analysis tool or other third-party software for further investigation of network properties like degree distribution, clustering, and correlations. The inclusion of an edge rewiring function adds flexibility, allowing for the study of assortative and disassortative mixing patterns.
Sources: Barabasi.cs, README.md