Kronecker graphs

The Kronecker graph of two graphs, whose adjacency matrix is the Kronecker product of theirs.

• Name: kronecker_graph
• Field: mathematics/networks
• Formalism: agent-based system
• References: Leskovec et al. 2010; Gros 2015

Select this system

from skcomplex.systems import create_simulation, create_system, describe

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

Factory

@register_system(
    field='mathematics/networks',
    tags=('network', 'kronecker product', 'random graph', 'degree distribution'),
    references=('Leskovec et al. 2010', 'Gros 2015'),
    defaults={'until': 1, 'dt': 1},
)
def kronecker_graph(
    first: nx.Graph | None = None,
    second: nx.Graph | None = None,
    *,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return the Kronecker graph of two graphs, whose adjacency matrix is the Kronecker product of theirs.

    The node `(i, j)` joins `(k, l)` when `i` joins `k` in the first graph and `j` joins `l` in the second (Gros
    2015, exercise of chapter 1). The degree of `(i, j)` is the product of the degrees of `i` and `j`, so the mean
    degree is the product of the mean degrees, and the degree distribution is the distribution of the products.

    Args:
        first:
            The first graph, or `None` for a Barabási-Albert graph of 30 nodes with two edges per new node.

        second:
            The second graph, or `None` for a Barabási-Albert graph of 20 nodes with one edge per new node.

        random_state:
            The seed or generator of the default graphs.

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

    Examples:
        >>> import networkx as nx
        >>> from skcomplex.systems.mathematics.networks import kronecker_graph
        >>> kronecker_graph(nx.path_graph(3), nx.path_graph(2)).elements[0].prepare().size_
        6
    """
    rng = np.random.default_rng(random_state)
    first = nx.barabasi_albert_graph(30, 2, seed=int(rng.integers(2**31))) if first is None else first
    second = nx.barabasi_albert_graph(20, 1, seed=int(rng.integers(2**31))) if second is None else second
    graph = nx.convert_node_labels_to_integers(nx.tensor_product(first, second), label_attribute='pair')
    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.
        """