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]],
]