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#

hierarchical_markov_clustering(...)

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#

markov_params

hierarchical_markov_analysis

markov_analysis

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:

  • matrix – Adjacency matrix.

  • 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:

  • matrix – Adjacency matrix (non-negative, IR/FAD convention).

  • mu – Evaporation constant (>1.0).

Note

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

  • A_s: normalized adjacency matrix with added evaporation sink.

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

Adjacency matrix dimension.

property sink_matrix: numpy.ndarray#

Column normalized adjacency matrix with an added evaporation sink.

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.

class ragraph.analysis.cluster._markov.MarkovRelative(adj: numpy.ndarray, mu: float)#

Markov relative influence and dependency calculations.

Parameters:

  • matrix – Adjacency matrix (non-negative, IR/FAD convention).

  • 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:

  • matrix – Adjacency matrix.

  • mu – Evaporation constant.

Returns:

Normalized flow distribution matrix with an added evaporation sink node at the

bottom right.

Note

Matrix structure of: [a00 a01 … a0n 0] [a10 a11 … a1n 0] [… … … … .] [an0 an1 … ann 0] [ e e … e 0] Where all columns are normalized [0.0, 1.0]