Topology · barabasi_albert

Barabási-Albert (Scale-Free)

Real-world scale-free model via preferential attachment (m=2). Mathematically guarantees that smaller graphs are subsets of larger ones, preventing zig-zagging curves.

Benchmark this topology

Evaluation

Linear · T ∘ E–iterations (left / right recursion)

Doubling · T ∘ T–iterations (double recursion)

1 / 1

iteration 1new pairs per iteration

Nodes · edges22 · 40

Closure |TC|74

Closure / edges1.9×

Size n22

A small instance from the generator the benchmark runs with n from 100 upwards.

Definition

Symbol

BA_{n,m}

Edges

\text{Scale-free network generated using preferential attachment with } m \text{ edges.}

Generator

engine.data_generator.DataGenerator.generate_barabasi_albert_graph

generate_db.py

    def generate_barabasi_albert_graph(self, n: int, m: int = 2) -> Generator[tuple[int, int], None, None]:
        """
        Generate a Barabási-Albert graph (the scale-free model of real-world networks).

        With the fixed seed, the graph of n nodes is a subgraph of the graph of any larger n.
        """
        import networkx as nx

        logging.info(f'Generating Barabási-Albert graph for n={n} (m={m})')

        if n <= m:
            for i in range(1, n + 1):
                for j in range(i + 1, n + 1):
                    yield (i, j)
        else:
            graph = nx.barabasi_albert_graph(n, m, seed=42)
            for u, v in graph.edges():
                yield (u + 1, v + 1)