diff --git a/markov_clustering/mcl.py b/markov_clustering/mcl.py
index <HASH>..<HASH> 100644
--- a/markov_clustering/mcl.py
+++ b/markov_clustering/mcl.py
@@ -81,7 +81,8 @@ def add_self_loops(matrix, loop_value):
 
 def prune(matrix, threshold):
     """
-    Prune the matrix so that very small edges are removed
+    Prune the matrix so that very small edges are removed.
+    The maximum value in each column is never pruned.
     
     :param matrix: The matrix to be pruned
     :param threshold: The value below which edges will be removed
@@ -95,6 +96,12 @@ def prune(matrix, threshold):
         pruned = matrix.copy()
         pruned[pruned < threshold] = 0
 
+    # keep max value in each column. same behaviour for dense/sparse
+    num_cols = matrix.shape[1]
+    row_indices = matrix.argmax(axis=0).reshape((num_cols,))
+    col_indices = np.arange(num_cols)
+    pruned[row_indices, col_indices] = matrix[row_indices, col_indices]
+
     return pruned
make sure columns are not zeroed entirely while pruning