# `ragraph.analysis.cluster._markov`#

Markov clustering module.

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

## Module Contents#

### Classes#

 `MarkovFlow` Results of Markov steady-state flow analysis. `MarkovRelative` Markov relative influence and dependency calculations.

### Functions#

 `markov_clustering`(→ Tuple[ragraph.graph.Graph, ...) `calculate_tpm`(→ numpy.ndarray) Calculate Transfer Probability Matrix (TPM), which in turn is the sum of the `prune_matrix`(→ numpy.ndarray) Return a column normalized matrix for which all values below the threshold have `create_clusters`(→ List[ragraph.graph.Node]) Assign nodes in graph to new cluster nodes using a numbered array. `get_sink_matrix`(→ numpy.ndarray) Calculate a normalized flow distribution matrix with an evaporation sink node.

### Attributes#

ragraph.analysis.cluster._markov.markov_params#
ragraph.analysis.cluster._markov.hierarchical_markov_analysis#
ragraph.analysis.cluster._markov.hierarchical_markov_clustering(graph: ragraph.graph.Graph, root: Optional[Union[str, ragraph.graph.Node]] = None, leafs: Optional[Union[List[ragraph.graph.Node], List[str]]] = None, inherit: bool = True, loops: bool = False, edge_weights: Optional[List[str]] = None, alpha: int = markov_params['alpha'].default, beta: float = markov_params['beta'].default, mu: float = markov_params['mu'].default, max_iter: int = markov_params['max_iter'].default, symmetrize: bool = markov_params['symmetrize'].default, inplace: bool = True, names: bool = False, safe: bool = True, **kwargs) Tuple[ragraph.graph.Graph, Union[List[ragraph.graph.Node], List[str]]]#
ragraph.analysis.cluster._markov.markov_analysis#
ragraph.analysis.cluster._markov.markov_clustering(graph: ragraph.graph.Graph, root: Optional[Union[str, ragraph.graph.Node]] = None, leafs: Optional[Union[List[ragraph.graph.Node], List[str]]] = None, inherit: bool = True, loops: bool = False, edge_weights: Optional[List[str]] = None, alpha: int = markov_params['alpha'].default, beta: float = markov_params['beta'].default, mu: float = markov_params['mu'].default, max_iter: int = markov_params['max_iter'].default, symmetrize: bool = markov_params['symmetrize'], inplace: bool = True, names: bool = False, safe: bool = True, **kwargs) Tuple[ragraph.graph.Graph, Union[List[ragraph.graph.Node], List[str]]]#
ragraph.analysis.cluster._markov.calculate_tpm(matrix: numpy.ndarray, mu: float) numpy.ndarray#

Calculate Transfer Probability Matrix (TPM), which in turn is the sum of the Relative Influence and Relative Depencency Matrices (RIM, RDM).

Parameters:

• mu – Decay constant.

Returns:

Transfer Probability Matrix (TPM).

ragraph.analysis.cluster._markov.prune_matrix(matrix: numpy.ndarray, threshold: float) numpy.ndarray#

Return a column normalized matrix for which all values below the threshold have been pruned (set to 0.0).

Parameters:
• matrix – Matrix to prune.

• threshold – Cut-off threshold for normalized values.

Returns:

Pruned matrix.

ragraph.analysis.cluster._markov.create_clusters(graph: ragraph.graph.Graph, nodes: List[ragraph.graph.Node], cluster_ids: numpy.ndarray) List[ragraph.graph.Node]#

Assign nodes in graph to new cluster nodes using a numbered array.

Parameters:
• graph – Graph to add clusters into.

• nodes – Nodes that were clustered.

• cluster_ids – 1D array with numbered cluster assignment per node.

Returns:

Current root nodes in the graph.

class ragraph.analysis.cluster._markov.MarkovFlow(matrix: numpy.ndarray, mu: float, scale: bool)#

Results of Markov steady-state flow analysis.

Parameters:

• mu – Evaporation constant (>1.0).

Note

Solves the flow balance equation: A_s @ f + f_in = f, for which:

• f_in: injection vector (1.0 for every node except sink).

• f = inv(I - A_s) @ f_in (flow vector)

• Q = inv(I - A_s) (sensitivity matrix)

• f = Q @ f_in

• F = A_s * f.T (edge flow matrix)

property dim: int#

property sink_matrix: numpy.ndarray#

property sensitivity_matrix: numpy.ndarray#

Sensitivity matrix (Q) with respect to input flow. f = Q @ f_in.

property in_vector: numpy.ndarray#

Inflow vector used normally. 1.0 inflow at every node except the sink.

property flow_vector: numpy.ndarray#

Flow through every node if system is injected with `self.in_vector`.

property flow_matrix: numpy.ndarray#

Flow over every edge if nodal flow equal `self.flow_vector`.

Markov relative influence and dependency calculations.

Parameters:

• mu – Evaporation constant (>1.0).

Note

Solves specific cases of the Markov flow analysis where each node is injected with a flow of 1 to calculate the relative influence. The network is also reversed and injected again, which results in relative dependency.

property influence_matrix: numpy.ndarray#

Relative influence matrix (RIM). Percentage of influence originating from j on i.

property dependency_matrix: numpy.ndarray#

Relative Dependency Matrix (RDM). Percentage of dependency of j on i.

ragraph.analysis.cluster._markov.get_sink_matrix(matrix: numpy.ndarray, mu: float) numpy.ndarray#

Calculate a normalized flow distribution matrix with an evaporation sink node.

Parameters: