Skip to content

ragraph.analysis.bus

Bus detection algorithms

Bus detection algorithms find bus nodes in graphs, also called "hubs" or "integrative components". Typical bus nodes have a high node degree or "centrality" score.

All bus detection algorithms have the following arguments:

  • graph: Graph to find bus nodes in.
  • root: Root node to perform bus detection in.
  • leafs: Optional list of leaf nodes to consider during the bus detection cycle. If not supplied, the leaf node descendants of the root will be considered.

They always return two lists of nodes:

  • Leaf nodes that have been marked as bus nodes.
  • The remaining leaf nodes.

They currently do NOT change anything in the graph in-place. That is up to the user.

Available algorithms

The following algorithms are directly available after importing ragraph.analysis.bus:

  • gamma: Gamma bus detection.

gamma

gamma(
    graph: Graph,
    root: Optional[Union[Node, str]] = None,
    leafs: Optional[Union[List[Node], List[str]]] = None,
    inherit: bool = True,
    loops: bool = False,
    edge_weights: Optional[List[str]] = None,
    names: bool = False,
    gamma: float = gamma_params["gamma"].default,
    safe: bool = True,
    **kwargs
) -> Union[
    Tuple[List[Node], List[Node]],
    Tuple[List[str], List[str]],
]

Detect bus nodes in a graph.

Parameters:

Name Type Description Default
graph Graph

Graph to detect bus nodes in.

required
root Optional[Union[Node, str]]

Root node of this bus detection analysis.

None
leafs Optional[Union[List[Node], List[str]]]

Optional list of nodes to consider leafs during this bus detection cycle.

None
inherit bool

Whether edges between descendants of nodes should be taken into account (if applicable).

True
loops bool

Whether self-loop edges should be taken into account (if applicable).

False
gamma float

Bus threshold w.r.t. median of nonzero node degrees.

default
names bool

Whether to return node names or node instances.

False

Returns:

Type Description
Union[Tuple[List[Node], List[Node]], Tuple[List[str], List[str]]]

Bus leafs.

Union[Tuple[List[Node], List[Node]], Tuple[List[str], List[str]]]

Nonbus leafs.

Note

Works by selecting node degree outliers by some factor gamma w.r.t. median of nonzero node degrees.

Reference

Wilschut, T., Etman, L. F. P., Rooda, J. E., & Adan, I. J. B. F. (2017). Multilevel Flow-Based Markov Clustering for Design Structure Matrices. Journal of Mechanical Design, 139(12), 121402. https://doi.org/10.1115/1.4037626

Source code in ragraph/analysis/bus/_gamma.py
@gamma_analysis
def gamma_bus_detection(
    graph: Graph,
    root: Optional[Union[Node, str]] = None,
    leafs: Optional[Union[List[Node], List[str]]] = None,
    inherit: bool = True,
    loops: bool = False,
    edge_weights: Optional[List[str]] = None,
    names: bool = False,
    gamma: float = gamma_params["gamma"].default,  # type: ignore
    safe: bool = True,
    **kwargs,
) -> Union[Tuple[List[Node], List[Node]], Tuple[List[str], List[str]]]:
    """Detect bus nodes in a graph.

    Arguments:
        graph: Graph to detect bus nodes in.
        root: Root node of this bus detection analysis.
        leafs: Optional list of nodes to consider leafs during this bus detection cycle.
        inherit: Whether edges between descendants of nodes should be taken into account
            (if applicable).
        loops: Whether self-loop edges should be taken into account (if applicable).
        gamma: Bus threshold w.r.t. median of nonzero node degrees.
        names: Whether to return node names or node instances.

    Returns:
        Bus leafs.
        Nonbus leafs.

    Note:
        Works by selecting node degree outliers by some factor gamma w.r.t. median of
        nonzero node degrees.

    Reference:
        Wilschut, T., Etman, L. F. P., Rooda, J. E., & Adan, I. J. B. F. (2017). Multilevel
        Flow-Based Markov Clustering for Design Structure Matrices. Journal of Mechanical
        Design, 139(12), 121402. https://doi.org/10.1115/1.4037626
    """
    matrix = graph.get_adjacency_matrix(
        nodes=leafs, inherit=inherit, loops=loops, only=edge_weights
    )
    assert isinstance(matrix, np.ndarray)
    assert leafs is not None
    dim = matrix.shape[0]

    # Calculate interface matrix and node degrees.
    interfaces = matrix > 0
    degrees = interfaces.sum(0) + interfaces.sum(1)

    # Initialize arrays and enter heuristic.
    nonbus_idxs: np.ndarray = np.arange(dim)
    bus_idxs: np.ndarray = np.int_([])
    while nonbus_idxs.size > 1:
        nonbus_nonzero_degrees = degrees[nonbus_idxs][degrees[nonbus_idxs] > 0]

        # Calculate threshold if nonzero degree nonbus nodes are left.
        if not nonbus_nonzero_degrees.size:
            break
        threshold = gamma * np.median(nonbus_nonzero_degrees)

        # Transfer nodes to bus if found.
        add_bus = nonbus_idxs[degrees[nonbus_idxs] >= threshold]
        if not add_bus.size:
            break
        setdiff = np.setdiff1d(nonbus_idxs, add_bus, assume_unique=True)
        bus_idxs = np.hstack((bus_idxs, add_bus))
        nonbus_idxs = setdiff

    # If all nodes were assigned to the bus, actually none are.
    if len(bus_idxs) != dim and len(bus_idxs) > 0:
        bus_leafs = [leafs[i] for i in bus_idxs]
        nonbus_leafs = [leafs[i] for i in nonbus_idxs]
    else:
        bus_leafs = []
        nonbus_leafs = leafs

    return bus_leafs, nonbus_leafs

_gamma

Gamma bus detection

References

Wilschut, T., Etman, L. F. P., Rooda, J. E., & Adan, I. J. B. F. (2017). Multilevel Flow-Based Markov Clustering for Design Structure Matrices. Journal of Mechanical Design, 139(12), 121402. DOI: 10.1115/1.4037626

gamma_bus_detection

gamma_bus_detection(
    graph: Graph,
    root: Optional[Union[Node, str]] = None,
    leafs: Optional[Union[List[Node], List[str]]] = None,
    inherit: bool = True,
    loops: bool = False,
    edge_weights: Optional[List[str]] = None,
    names: bool = False,
    gamma: float = gamma_params["gamma"].default,
    safe: bool = True,
    **kwargs
) -> Union[
    Tuple[List[Node], List[Node]],
    Tuple[List[str], List[str]],
]

Detect bus nodes in a graph.

Parameters:

Name Type Description Default
graph Graph

Graph to detect bus nodes in.

required
root Optional[Union[Node, str]]

Root node of this bus detection analysis.

None
leafs Optional[Union[List[Node], List[str]]]

Optional list of nodes to consider leafs during this bus detection cycle.

None
inherit bool

Whether edges between descendants of nodes should be taken into account (if applicable).

True
loops bool

Whether self-loop edges should be taken into account (if applicable).

False
gamma float

Bus threshold w.r.t. median of nonzero node degrees.

default
names bool

Whether to return node names or node instances.

False

Returns:

Type Description
Union[Tuple[List[Node], List[Node]], Tuple[List[str], List[str]]]

Bus leafs.

Union[Tuple[List[Node], List[Node]], Tuple[List[str], List[str]]]

Nonbus leafs.

Note

Works by selecting node degree outliers by some factor gamma w.r.t. median of nonzero node degrees.

Reference

Wilschut, T., Etman, L. F. P., Rooda, J. E., & Adan, I. J. B. F. (2017). Multilevel Flow-Based Markov Clustering for Design Structure Matrices. Journal of Mechanical Design, 139(12), 121402. https://doi.org/10.1115/1.4037626

Source code in ragraph/analysis/bus/_gamma.py
@gamma_analysis
def gamma_bus_detection(
    graph: Graph,
    root: Optional[Union[Node, str]] = None,
    leafs: Optional[Union[List[Node], List[str]]] = None,
    inherit: bool = True,
    loops: bool = False,
    edge_weights: Optional[List[str]] = None,
    names: bool = False,
    gamma: float = gamma_params["gamma"].default,  # type: ignore
    safe: bool = True,
    **kwargs,
) -> Union[Tuple[List[Node], List[Node]], Tuple[List[str], List[str]]]:
    """Detect bus nodes in a graph.

    Arguments:
        graph: Graph to detect bus nodes in.
        root: Root node of this bus detection analysis.
        leafs: Optional list of nodes to consider leafs during this bus detection cycle.
        inherit: Whether edges between descendants of nodes should be taken into account
            (if applicable).
        loops: Whether self-loop edges should be taken into account (if applicable).
        gamma: Bus threshold w.r.t. median of nonzero node degrees.
        names: Whether to return node names or node instances.

    Returns:
        Bus leafs.
        Nonbus leafs.

    Note:
        Works by selecting node degree outliers by some factor gamma w.r.t. median of
        nonzero node degrees.

    Reference:
        Wilschut, T., Etman, L. F. P., Rooda, J. E., & Adan, I. J. B. F. (2017). Multilevel
        Flow-Based Markov Clustering for Design Structure Matrices. Journal of Mechanical
        Design, 139(12), 121402. https://doi.org/10.1115/1.4037626
    """
    matrix = graph.get_adjacency_matrix(
        nodes=leafs, inherit=inherit, loops=loops, only=edge_weights
    )
    assert isinstance(matrix, np.ndarray)
    assert leafs is not None
    dim = matrix.shape[0]

    # Calculate interface matrix and node degrees.
    interfaces = matrix > 0
    degrees = interfaces.sum(0) + interfaces.sum(1)

    # Initialize arrays and enter heuristic.
    nonbus_idxs: np.ndarray = np.arange(dim)
    bus_idxs: np.ndarray = np.int_([])
    while nonbus_idxs.size > 1:
        nonbus_nonzero_degrees = degrees[nonbus_idxs][degrees[nonbus_idxs] > 0]

        # Calculate threshold if nonzero degree nonbus nodes are left.
        if not nonbus_nonzero_degrees.size:
            break
        threshold = gamma * np.median(nonbus_nonzero_degrees)

        # Transfer nodes to bus if found.
        add_bus = nonbus_idxs[degrees[nonbus_idxs] >= threshold]
        if not add_bus.size:
            break
        setdiff = np.setdiff1d(nonbus_idxs, add_bus, assume_unique=True)
        bus_idxs = np.hstack((bus_idxs, add_bus))
        nonbus_idxs = setdiff

    # If all nodes were assigned to the bus, actually none are.
    if len(bus_idxs) != dim and len(bus_idxs) > 0:
        bus_leafs = [leafs[i] for i in bus_idxs]
        nonbus_leafs = [leafs[i] for i in nonbus_idxs]
    else:
        bus_leafs = []
        nonbus_leafs = leafs

    return bus_leafs, nonbus_leafs