Minimal Dominating Set

network_diffusion provides functions for obtaining a Minimal Dominating Set (MDS) of actors in a multilayer network. This concept, originating from the domain of controllability, introduces the notion of a set through which all nodes (i.e. actor representatives on individual layers) can be reached via direct impulses from the MDS.

For reference, see: https://iopscience.iop.org/article/10.1088/1367-2630/14/7/073005/pdf https://arxiv.org/abs/2502.15236

Methods for obtaining the MDS

Script with functions for driver actor selection with greedy approach.

get_mds_greedy(net: MultilayerNetwork) → set[MLNetworkActor]

Get driver actors for a network a.k.a. a minimal dominating set.

The dominating set gets minimised before it gets returned, but it is not a minimum one. For more precise, but more time-consuming approach see get_mds_locimpr.

Parameters:

net – network to obtain minimal dominating set for

Returns:

(sub)minimal dominating set

Functions for driver actor selection with local improvement.

get_mds_locimpr(net: MultilayerNetwork, timeout: float | None = None, debug: bool = False) → set[MLNetworkActor]

Get driver actors for a network using greedy-based local improvement algo.

The routine works as follows: (1) get the initial solution with get_mds_greedy, (2) try to improve the solution by iteratively trying to prune it.

This method is inspired by a work by A Casado et al. “An iterated greedy algorithm for finding the minimum dominating set in graphs (https://doi.org/10.1016/j.matcom.2022.12.018) which was published in “Mathematics and Computers in Simulation”, 2023, Volume 207.

Parameters:

• net – network to obtain minimal dominating set for

• timeout – a timeout for bigger networks, if none then it will be set in proportion of 5 minutes per 1000 actors

• debug – if true print debug statements

Returns:

(sub)minimal dominating set