large-network-generator 0.2.0

A Python implementation of a real-world network generation algorithm

Large Network Generator

A Python implementation of a real-world network generation algorithm, originally developed in C++. This package provides a pure Python implementation with no external dependencies.

Features

• Pure Python Implementation: No external libraries required
• Network Generation: Creates networks using random walks and friendship probabilities
• Configurable Parameters: Adjustable network size, connection patterns, and probabilities
• Lightweight: Minimal dependencies and fast execution

Installation

From PyPI (when published)

pip install large-network-generator

From Source

git clone https://github.com/jpcmorais16/network-generator.git
cd network-generator
pip install -e .

Quick Start

from large_network_generator import generate_network

# Generate a network with 1000 nodes
# Parameters: N=1000, m=5, p=0.5, fp=0.3
network = generate_network(N=1000, m=5, p=0.5, fp=0.3)

print(f"Generated network with {len(network)} nodes")

Usage

Basic Network Generation

from large_network_generator import generate_network

# Generate a small network for testing
network = generate_network(
    N=100,      # Number of additional nodes to add
    m=3,        # Number of marked nodes for each new node
    p=0.5,      # Step length probability parameter
    fp=0.3      # Friendship probability between marked nodes
)

Network Structure

The generated network is represented as a list of sets, where:

• network[i] is a set containing the neighbors of node i
• The network is undirected (if node A connects to node B, B also connects to A)
• Node indices start from 0

Example: Analyzing the Network

# Count total edges
total_edges = sum(len(neighbors) for neighbors in network) // 2

# Find node degrees
degrees = [len(neighbors) for neighbors in network]
max_degree = max(degrees)
min_degree = min(degrees)

print(f"Nodes: {len(network)}")
print(f"Edges: {total_edges}")
print(f"Max degree: {max_degree}")
print(f"Min degree: {min_degree}")

Algorithm Details

The network generation algorithm works as follows:

1. Initialization: Creates a ring of 10 nodes with random connections

2. Growth: Iteratively adds new nodes by:

   • Starting from a random existing node
   • Performing random walks to find marked nodes
   • Connecting the new node to all marked nodes
   • Creating friendships between marked nodes with probability fp

3. Parameters:

   • N: Number of additional nodes to add
   • m: Number of marked nodes for each new node
   • p: How much the marking of neighbor nodes is prioritized over the marking of nodes further from each other in the random walks
   • fp: The probability that marked nodes will create connections among each other

Finding Parameters from Target Properties

If you know the desired number of edges and clustering coefficient but not the low-level parameters (m, p, fp), use find_coefficients to discover them automatically:

from large_network_generator import find_coefficients

# Find parameters that produce ~5000 edges and ~0.3 clustering
result = find_coefficients(N=1000, target_n_edges=5000, target_clustering=0.3)

if result is not None:
    m, fp, p, actual_clustering = result
    print(f"m={m}, fp={fp:.4f}, p={p:.4f}, clustering={actual_clustering:.4f}")
else:
    print("No suitable parameters found for the given targets.")

The function searches over m (number of marked nodes), fp (friendship probability), and p (step-length probability) using binary search to match the requested edge count and clustering coefficient as closely as possible.

API Reference

generate_network(N, m, p, fp, starting_graph=None)

Generates a network using the specified parameters.

Parameters:

• N (int): Number of additional nodes to add
• m (int): Number of marked nodes for each new node
• p (float): How much the marking of neighbor nodes is prioritized over the marking of nodes further from each other in the random walks (0.0 to 1.0)
• fp (float): The probability that marked nodes will create connections among each other (0.0 to 1.0)
• starting_graph (list[set], optional): Initial graph to build upon. If None, starts with a ring of 10 nodes.

Returns:

• list[set]: List of sets representing the network adjacency lists

Raises:

• ValueError: If parameters are invalid:
  • N is negative
  • m is less than 1
  • p is outside the range 0.0–1.0
  • fp is outside the range 0.0–1.0

---

find_coefficients(N, target_n_edges, target_clustering)

Determines generation parameters (m, fp, p) that produce a network with the desired number of edges and clustering coefficient.

Parameters:

• N (int): Number of nodes to add to the initial ring
• target_n_edges (int | float): Desired number of edges (must be ≥ 2·N)
• target_clustering (float): Desired average local clustering coefficient

Returns:

• tuple[int, float, float, float] | None: A tuple (m, fp, p, actual_clustering) on success, or None if no suitable parameters could be found

Raises:

• ValueError: If target_n_edges < 2·N (the minimum number of edges the algorithm can produce)

Note: The function returns None (instead of raising) when the target combination is unreachable — for example, if m would need to exceed 10, or the desired edge count falls outside the achievable range for every valid m.

License

This project is licensed under the MIT License - see the LICENSE file for details.

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.

Citation

If you use this package in your research, please cite:

@software{large_network_generator,
  title={Large Network Generator},
  author={João Pedro Carolino Morais},
  year={2025},
  url={https://github.com/jpcmorais16/network-generator}
}