# Is there an efficient way to cluster a graph according to Jaccard similarity?

Is there an efficient way to cluster nodes in a graph using Jaccard similarity such that each cluster has at least k nodes?

Jaccard similarity between nodes i and j: Let S be the set of neighbours of i and T be the set of neighbours of j. Then, the similarity between i and j is given by $\frac{|(S \cap T)|}{|(S \cup T)|}$.

With agglomerative (bottom-up) clustering, you simply keep merging clusters until all clusters have at least $k$ nodes.
With top-down clustering, you keep splitting clusters, except that if the algorithm tells you to split some cluster in a way that would leave one of its subclusters with fewer than $k$ nodes, you cancel the split and mark that cluster as finalized.
In general, hierarchical clustering gives you a tree. You can pick any consistent cut through the tree that leaves all clusters of size $\ge k$. So, it is easy to adapt any hierarchical clustering algorithm to satisfy your requirement that all clusters have at least $k$ nodes. Many of the hierarchical clustering methods let you use any pairwise distance function, so you can use them with your Jaccard similarity metric.