# 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¶

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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
  40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 @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 # 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¶

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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
  40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 @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 # 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