Overview
The Barabasi-Albert model grows a graph one node at a time. Each new node connects to existing nodes with probability proportional to their degree, producing hubs through preferential attachment.
CoreSource checked
Barabasi-Albert Model
Generates scale-free-style networks by preferentially attaching new nodes to high-degree nodes.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Randomness & Sampling
- Difficulty
- Intermediate
- Family
- Random Graphs
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 5
- Code example
- Ready
- Visualization
- Ready
Core Concepts
scale-free graph generationrandom graphsrandom samplingrandomness sampling
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(V + E)
Average
O((V + E) log V)
Worst
O(V^2 + E)
Space
O(V + E)
When to Use
- Use when hub formation and growth are central to the model.
- Use as a baseline for networks with skewed degree distributions.
When Not to Use
- Avoid when clustering, communities, or edge aging are central but not modeled.
- Avoid when the network is not plausibly growth-based.
What It Does
- Starts from a small connected seed graph
- Adds new nodes with a fixed number of edges
- Chooses targets preferentially by degree
Use Cases
- Synthetic network experiments with hub structure
- Teaching preferential attachment
- Testing graph algorithms on heavy-tailed degree distributions
Inputs
- Vertex count n and model parameters (edge probability p, attachment count m, or degree sequence)
- PRNG seed
Outputs
- Sampled graph adjacency list G = (V, E)
- Realized degree distribution and connectivity structure
Pseudocode
- 1.Initialize a small seed graph
- 2.While more nodes are needed
- 3.Add a new node
- 4.Sample existing target nodes with probability proportional to degree
- 5.Connect the new node to the sampled targets
- 6.Return the generated graph
Canonical Example
- Input
- start with 3 connected nodes; add each new node with 2 edges
- Output
- a graph where early high-degree nodes tend to become hubs
- Explanation
- Nodes with higher degree receive more future attachments.
Implementation Notes
- Represent target selection so degree-proportional sampling is testable.
- Decide whether parallel edges and self-loops are allowed.
- Store the seed and model parameters with generated graphs.
Common Pitfalls
- Sampling targets uniformly instead of by degree removes preferential attachment.
- Allowing duplicate edges unintentionally changes degree growth.
- Seed graph and attachment count strongly affect small generated graphs.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow adding vertices with preferential attachment to high-degree vertices on a small scale-free graph generation example.
Step 1 of 6: Initialize a small seed graph
randomness-sampling-mechanismNotes
Preferential attachment explains hub growth but not all structure seen in real networks.
Sources (1)
What each reference supports for this entry.
Emergence of Scaling in Random Networks
PaperOriginal reference for preferential attachment and scale-free network generation.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toErdos-Renyi Graph Generation
Randomness & Sampling · Core
Barabasi-Albert creates degree hubs, while Erdos-Renyi samples edges independently.
Compare with thisRelationships
View full relationship pageAlternative toErdos-Renyi Graph Generation
Barabasi-Albert creates degree hubs, while Erdos-Renyi samples edges independently.
Alternative toWatts-Strogatz Model
Watts-Strogatz emphasizes clustering and short paths, while Barabasi-Albert emphasizes hubs.
Related Algorithms
Tags
Randomness & SamplingRandomnessGraph