markov_clustering package

Submodules

markov_clustering.drawing module

Visualization of clusters

markov_clustering.drawing.draw_graph(matrix, clusters, **kwargs)

Visualize the clustering

Parameters:

• matrix – The unprocessed adjacency matrix
• clusters – list of tuples containing clusters as returned by ‘get_clusters’
• kwargs – Additional keyword arguments to be passed to networkx.draw_networkx

markov_clustering.mcl module

markov_clustering.mcl.add_self_loops(matrix, loop_value)

Add self-loops to the matrix by setting the diagonal to loop_value

Parameters:

• matrix – The matrix to add loops to
• loop_value – Value to use for self-loops

Returns:

The matrix with self-loops

markov_clustering.mcl.converged(matrix1, matrix2)

Check for convergence by determining if matrix1 and matrix2 are approximately equal.

Parameters:

• matrix1 – The matrix to compare with matrix2
• matrix2 – The matrix to compare with matrix1

Returns:

True if matrix1 and matrix2 approximately equal

markov_clustering.mcl.expand(matrix, power)

Apply cluster expansion to the given matrix by raising the matrix to the given power.

Parameters:

• matrix – The matrix to be expanded
• power – Cluster expansion parameter

Returns:

The expanded matrix

markov_clustering.mcl.get_clusters(matrix)

Retrieve the clusters from the matrix

Parameters:matrix – The matrix produced by the MCL algorithm Returns:A list of tuples where each tuple represents a cluster and contains the indices of the nodes belonging to the cluster

markov_clustering.mcl.inflate(matrix, power)

Apply cluster inflation to the given matrix by raising each element to the given power.

Parameters:

• matrix – The matrix to be inflated
• power – Cluster inflation parameter

Returns:

The inflated matrix

markov_clustering.mcl.iterate(matrix, expansion, inflation)

Run a single iteration (expansion + inflation) of the mcl algorithm

Parameters:

• matrix – The matrix to perform the iteration on
• expansion – Cluster expansion factor
• inflation – Cluster inflation factor

markov_clustering.mcl.normalize(matrix)

Normalize the columns of the given matrix

Parameters:matrix – The matrix to be normalized Returns:The normalized matrix

markov_clustering.mcl.prune(matrix, threshold)

Prune the matrix so that very small edges are removed. The maximum value in each column is never pruned.

Parameters:

• matrix – The matrix to be pruned
• threshold – The value below which edges will be removed

Returns:

The pruned matrix

markov_clustering.mcl.run_mcl(matrix, expansion=2, inflation=2, loop_value=1, iterations=100, pruning_threshold=0.001, pruning_frequency=1, convergence_check_frequency=1, verbose=False)

Perform MCL on the given similarity matrix

Parameters:

• matrix – The similarity matrix to cluster
• expansion – The cluster expansion factor
• inflation – The cluster inflation factor
• loop_value – Initialization value for self-loops
• iterations – Maximum number of iterations (actual number of iterations will be less if convergence is reached)
• pruning_threshold – Threshold below which matrix elements will be set set to 0
• pruning_frequency – Perform pruning every ‘pruning_frequency’ iterations.
• convergence_check_frequency – Perform the check for convergence every convergence_check_frequency iterations
• verbose – Print extra information to the console

Returns:

The final matrix

markov_clustering.mcl.sparse_allclose(a, b, rtol=1e-05, atol=1e-08)

Version of np.allclose for use with sparse matrices

markov_clustering.modularity module

Computation of the modularity of a clustering

markov_clustering.modularity.convert_to_adjacency_matrix(matrix)

Converts transition matrix into adjacency matrix

Parameters:matrix – The matrix to be converted Returns:adjacency matrix

markov_clustering.modularity.delta_matrix(matrix, clusters)

Compute delta matrix where delta[i,j]=1 if i and j belong to same cluster and i!=j

Parameters:

• matrix – The adjacency matrix
• clusters – The clusters returned by get_clusters

Returns:

delta matrix

markov_clustering.modularity.is_undirected(matrix)

Determine if the matrix reprensents a directed graph

Parameters:matrix – The matrix to tested Returns:boolean

markov_clustering.modularity.modularity(matrix, clusters)

Compute the modularity

Parameters:

• matrix – The adjacency matrix
• clusters – The clusters returned by get_clusters

Returns:

modularity value

markov_clustering.utils module

Simple togglable printer class

class markov_clustering.utils.MessagePrinter(enabled)

Bases: object

disable()

enable()

print(string)

Module contents