ragraph.analysis.cluster
¶
Clustering algorithms¶
Clustering algorithms detect (nested) clusters of nodes in graphs that are relatively tightly connected by means of their edges. Both hierarchical and flat clustering algorithms are provided.
Apart of algorithm specific parameters, all of them feature the same basic parameters:
graph
: Graph to cluster containing the relevant nodes and edges.leafs
: Optional list of leaf nodes to cluster. If not provided all the graph's leaf nodes are selected.inplace
: Boolean toggle whether to create the new cluster nodes in the provided graph or provided a deepcopy of the graph with only the leaf nodes, their edges and newly created cluster nodes.
Available algorithms¶
MarkovFlow
¶
Results of Markov steady-state flow analysis.
Parameters:
Name | Type | Description | Default |
---|---|---|---|
matrix |
ndarray
|
Adjacency matrix (non-negative, IR/FAD convention). |
required |
mu |
float
|
Evaporation constant (>1.0). |
required |
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)
Source code in ragraph/analysis/cluster/_markov.py
MarkovRelative
¶
Markov relative influence and dependency calculations.
Parameters:
Name | Type | Description | Default |
---|---|---|---|
adj |
ndarray
|
Adjacency matrix (non-negative, IR/FAD convention). |
required |
mu |
float
|
Evaporation constant (>1.0). |
required |
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.
Source code in ragraph/analysis/cluster/_markov.py
calculate_tpm
¶
Calculate Transfer Probability Matrix (TPM), which in turn is the sum of the Relative Influence and Relative Depencency Matrices (RIM, RDM).
Parameters:
Name | Type | Description | Default |
---|---|---|---|
matrix |
ndarray
|
Adjacency matrix. |
required |
mu |
float
|
Decay constant. |
required |
Returns:
Type | Description |
---|---|
ndarray
|
Transfer Probability Matrix (TPM). |
Source code in ragraph/analysis/cluster/_markov.py
create_clusters
¶
Assign nodes in graph to new cluster nodes using a numbered array.
Parameters:
Name | Type | Description | Default |
---|---|---|---|
graph |
Graph
|
Graph to add clusters into. |
required |
nodes |
List[Node]
|
Nodes that were clustered. |
required |
cluster_ids |
ndarray
|
1D array with numbered cluster assignment per node. |
required |
Returns:
Type | Description |
---|---|
List[Node]
|
Current root nodes in the graph. |
Source code in ragraph/analysis/cluster/_markov.py
get_sink_matrix
¶
Calculate a normalized flow distribution matrix with an evaporation sink node.
Parameters:
Name | Type | Description | Default |
---|---|---|---|
matrix |
ndarray
|
Adjacency matrix. |
required |
mu |
float
|
Evaporation constant. |
required |
Returns:
Type | Description |
---|---|
ndarray
|
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]
Source code in ragraph/analysis/cluster/_markov.py
hierarchical_markov
¶
|
docstring stub
Source code in ragraph/analysis/cluster/_markov.py
markov
¶
|
docstring stub
Source code in ragraph/analysis/cluster/_markov.py
prune_matrix
¶
Return a column normalized matrix for which all values below the threshold have been pruned (set to 0.0).
Parameters:
Name | Type | Description | Default |
---|---|---|---|
matrix |
ndarray
|
Matrix to prune. |
required |
threshold |
float
|
Cut-off threshold for normalized values. |
required |
Returns:
Type | Description |
---|---|
ndarray
|
Pruned matrix. |
Source code in ragraph/analysis/cluster/_markov.py
tarjans_scc
¶
|
docstring stub
Source code in ragraph/analysis/cluster/_tarjan.py
_markov
¶
Markov clustering module¶
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. DOI: 10.1115/1.4037626
MarkovFlow
¶
Results of Markov steady-state flow analysis.
Parameters:
Name | Type | Description | Default |
---|---|---|---|
matrix |
ndarray
|
Adjacency matrix (non-negative, IR/FAD convention). |
required |
mu |
float
|
Evaporation constant (>1.0). |
required |
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)
Source code in ragraph/analysis/cluster/_markov.py
MarkovRelative
¶
Markov relative influence and dependency calculations.
Parameters:
Name | Type | Description | Default |
---|---|---|---|
adj |
ndarray
|
Adjacency matrix (non-negative, IR/FAD convention). |
required |
mu |
float
|
Evaporation constant (>1.0). |
required |
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.
Source code in ragraph/analysis/cluster/_markov.py
calculate_tpm
¶
Calculate Transfer Probability Matrix (TPM), which in turn is the sum of the Relative Influence and Relative Depencency Matrices (RIM, RDM).
Parameters:
Name | Type | Description | Default |
---|---|---|---|
matrix |
ndarray
|
Adjacency matrix. |
required |
mu |
float
|
Decay constant. |
required |
Returns:
Type | Description |
---|---|
ndarray
|
Transfer Probability Matrix (TPM). |
Source code in ragraph/analysis/cluster/_markov.py
create_clusters
¶
Assign nodes in graph to new cluster nodes using a numbered array.
Parameters:
Name | Type | Description | Default |
---|---|---|---|
graph |
Graph
|
Graph to add clusters into. |
required |
nodes |
List[Node]
|
Nodes that were clustered. |
required |
cluster_ids |
ndarray
|
1D array with numbered cluster assignment per node. |
required |
Returns:
Type | Description |
---|---|
List[Node]
|
Current root nodes in the graph. |
Source code in ragraph/analysis/cluster/_markov.py
get_sink_matrix
¶
Calculate a normalized flow distribution matrix with an evaporation sink node.
Parameters:
Name | Type | Description | Default |
---|---|---|---|
matrix |
ndarray
|
Adjacency matrix. |
required |
mu |
float
|
Evaporation constant. |
required |
Returns:
Type | Description |
---|---|
ndarray
|
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]
Source code in ragraph/analysis/cluster/_markov.py
hierarchical_markov
¶
|
docstring stub
Source code in ragraph/analysis/cluster/_markov.py
markov
¶
|
docstring stub
Source code in ragraph/analysis/cluster/_markov.py
prune_matrix
¶
Return a column normalized matrix for which all values below the threshold have been pruned (set to 0.0).
Parameters:
Name | Type | Description | Default |
---|---|---|---|
matrix |
ndarray
|
Matrix to prune. |
required |
threshold |
float
|
Cut-off threshold for normalized values. |
required |
Returns:
Type | Description |
---|---|
ndarray
|
Pruned matrix. |
Source code in ragraph/analysis/cluster/_markov.py
_tarjan
¶
Tarjan's strongly connected components algorithm.¶
Reference
Tarjan, R. (1972). Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing, 1(2), 146-160. [DOI: 10.1137/0201010] (https://doi.org/10.1137/0201010)
tarjans_scc
¶
|
docstring stub
Source code in ragraph/analysis/cluster/_tarjan.py
tarjans_scc_algorithm
¶
Tarjan's strongly connected components algorithm.
Parameters:
Name | Type | Description | Default |
---|---|---|---|
graph |
Graph
|
Graph to detect SCC's in (cycles). |
required |
nodes |
List[Node]
|
List of nodes (components) to detect SCC's for. |
required |
inherit |
bool
|
Whether to take into account (inherit) edges between children during calculations. |
required |
Returns:
Type | Description |
---|---|
List[List[Node]]
|
Lists of strongly connected components. |
Reference
Tarjan, R. (1972). Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing, 1(2), 146-160. https://doi.org/10.1137/0201010