Configuration model with stub matching and rewiring

The configuration model, the maximally random network of a given degree sequence.

• Name: configuration_model
• Field: mathematics/networks
• Formalism: agent-based system
• References: Molloy and Reed 1995; Jensen 2023; Thurner et al. 2018

Select this system

from skcomplex.systems import create_simulation, create_system, describe

system = create_system('configuration_model')
entry = describe('configuration_model')
trajectory = create_simulation('configuration_model').prepare().run().trajectory_

Factory

@register_system(
    field='mathematics/networks',
    tags=('network', 'configuration model', 'random graph', 'degree sequence', 'friendship paradox'),
    references=('Molloy and Reed 1995', 'Jensen 2023', 'Thurner et al. 2018'),
    defaults={'until': 1, 'dt': 1},
)
def configuration_model(
    degrees: Sequence[int] | None = None,
    *,
    n_nodes: int = 1000,
    exponent: float = 2.5,
    min_degree: int = 2,
    simple: bool = True,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return the configuration model, the maximally random network of a given degree sequence.

    Every node gets as many half-links as its degree, and pairs of half-links drawn uniformly at random become links
    (Jensen 2023, section 8.5.1, and Thurner et al. 2018, section 4.5.1). Without a degree sequence the degrees are
    drawn from the power law `P(k) ~ k^-exponent` for `k >= min_degree`, cut at `sqrt(n_nodes)`, and one half-link
    is added to a random node when their sum is odd. The pairing leaves self-loops and multilinks, which the rewiring
    of Thurner et al. removes while it keeps every degree. A neighbour has the mean degree `<k²> / <k>`, above the
    mean degree, the friendship paradox.

    Args:
        degrees:
            The degree of every node, or `None` for degrees drawn from the power law.

        n_nodes:
            The number of nodes of the drawn degrees.

        exponent:
            The exponent of the power law of the drawn degrees.

        min_degree:
            The smallest drawn degree.

        simple:
            Whether self-loops and multilinks are rewired away, or dropped, which lowers some degrees.

        random_state:
            The seed or generator of the degrees, the pairing, and the rewiring.

    Returns:
        system:
            The system, with the group `nodes` and their states `degree` and `clustering`.

    Raises:
        ValidationError:
            The degree sum of a given sequence is odd, or rewiring cannot make the graph simple.

    Examples:
        >>> from skcomplex.systems.mathematics.networks import configuration_model
        >>> system = configuration_model([3, 3, 2, 2, 2])
        >>> system.elements[0].values['degree'].tolist()
        [3.0, 3.0, 2.0, 2.0, 2.0]
    """
    rng = np.random.default_rng(random_state)
    if degrees is None:
        support = np.arange(min_degree, max(min_degree, int(np.sqrt(n_nodes))) + 1)
        weights = support.astype(float) ** -exponent
        drawn = rng.choice(support, size=n_nodes, p=weights / weights.sum())
        drawn[int(rng.integers(n_nodes))] += int(drawn.sum() % 2)
    else:
        drawn = np.asarray(degrees, dtype=np.int64)
        if drawn.sum() % 2:
            error_msg = f'The degrees sum to {int(drawn.sum())}. Give a degree sequence with an even sum.'
            raise ValidationError(error_msg)
    links = _matched_stubs(drawn, rng)
    links = _simple(links, rng) if simple else [link for link in links if link[0] != link[1]]
    graph = nx.Graph()
    graph.add_nodes_from(range(drawn.size))
    graph.add_edges_from(links)
    return System(elements=[_node_group(graph)], space=NetworkSpace(graph))

Components

Elements:

• NetworkNodeElement, from Element

class NetworkNodeElement(Element):
    """Node of a network that carries its degree, clustering, betweenness, and community.

    Args:
        label:
            The label of the agent or group.

        visual:
            How the element is drawn, or `None` for `default_visual_`.

        degree:
            The degree of the node.

        clustering:
            The clustering coefficient of the node.

        betweenness:
            The normalized betweenness centrality of the node.

        community:
            The index of the community of the node.

    Examples:
        >>> from skcomplex.core.components.elements import GroupElement
        >>> from skcomplex.systems.mathematics.networks import NetworkNodeElement
        >>> group = GroupElement('nodes', element=NetworkNodeElement, size=3)
        >>> group.label, group.element.__name__, group.size
        ('nodes', 'NetworkNodeElement', 3)
    """

    def __init__(
        self,
        label: str,
        visual: VisualSpec | None = VisualSpec('agents', {'color_by': 'community'}),
        *,
        degree: Annotated[float, StateSpec(domain=NN)] = 0.0,
        clustering: Annotated[float, StateSpec(domain=RealSet.closed_open(0, oo))] = 0.0,
        betweenness: Annotated[float, StateSpec(domain=RealSet.closed_open(0, oo))] = 0.0,
        community: Annotated[float, StateSpec(domain=NN)] = 0.0,
    ) -> None:
        super().__init__(label, visual=visual)
        self.degree = degree
        self.clustering = clustering
        self.betweenness = betweenness
        self.community = community

    def _get_laws(self, s: SimpleNamespace) -> list[BaseLaw]:
        """Return the rule that keeps the node in place.

        Args:
            s:
                The namespace of the symbols the laws can use.

        Returns:
            laws:
                The laws of the component.
        """
        return [RuleLaw(self.stay)]

    def stay(self, agent: AgentView, system: SystemView) -> None:
        """Keep the node and its measures unchanged.

        Args:
            agent:
                The node.

            system:
                The system.
        """