Skip to content

Graph Generators

Graph generators create synthetic graphs with specific properties for testing and analysis.

Random Graph Models

Erdos-Renyi (ER)

pg.core.erdos_renyi(n, p, seed=None)

Random graph where each edge exists with probability p.

  • Properties: Uniform random
  • Uses: Null model, baseline comparisons
  • Time: O(V²)

Barabasi-Albert (BA)

pg.core.barabasi_albert(n, m, seed=None)

Preferential attachment model - new nodes attach to existing high-degree nodes.

  • Properties: Scale-free, power-law degree distribution
  • Uses: Social networks, web graphs
  • Time: O(V·m)

Watts-Strogatz (WS)

pg.core.watts_strogatz(n, k, beta, seed)

Small-world model - regular lattice with random rewiring.

  • Properties: High clustering, low diameter
  • Uses: Social networks, biological networks
  • Time: O(V)

Structured Graphs

Complete Graph

pg.core.complete_graph(n)

All possible edges present (K_n).

  • Edges: n(n-1)/2
  • Density: 1.0
  • Diameter: 1

Cycle Graph

pg.core.cycle_graph(n)

Nodes arranged in a circle.

  • Edges: n
  • Diameter: n/2
  • Uses: Ring networks

Path Graph

pg.core.path_graph(n)

Linear chain of nodes.

  • Edges: n-1
  • Diameter: n-1
  • Uses: Sequential structures

Examples

import pygraphina as pg

# Generate different types of graphs
er = pg.core.erdos_renyi(100, 0.1, seed=42)
ba = pg.core.barabasi_albert(100, 3, seed=42)
ws = pg.core.watts_strogatz(100, 4, beta=0.1, seed=42)

# Analyze properties
print(f"ER density: {er.density():.3f}")
print(f"BA avg clustering: {ba.average_clustering():.3f}")
print(f"WS diameter: {ws.diameter()}")

# Use for testing
for graph in [er, ba, ws]:
    centrality = pg.centrality.pagerank(graph, 0.85, 100, 1e-6)
    print(f"Nodes: {graph.node_count()}, PageRank range: {min(centrality.values()):.4f} - {max(centrality.values()):.4f}")

Use Cases

  • Algorithm testing
  • Benchmark creation
  • Network model comparison
  • Synthetic data generation
  • Hypothesis testing

Properties Comparison

Property ER BA WS
Clustering Low Low-Medium High
Diameter Small Small-Medium Small
Degree Distribution Binomial Power-law Regular
Realism Low High Medium

Seeding

All random graph generators require a seed parameter for reproducibility:

# Same seed produces identical graphs
g1 = pg.core.erdos_renyi(100, 0.1, seed=42)
g2 = pg.core.erdos_renyi(100, 0.1, seed=42)
# g1 and g2 are identical

# Use different seeds for different random graphs
g3 = pg.core.erdos_renyi(100, 0.1, seed=123)
g4 = pg.core.erdos_renyi(100, 0.1, seed=456)
# g3 and g4 are different random graphs

Seed Parameter

The seed parameter is required (not optional) for all random graph generators (Erdős-Rényi, Barabási-Albert, Watts-Strogatz, Bipartite). This ensures reproducibility of generated graphs. Deterministic generators (Complete, Cycle, Star) do not require a seed.