1
$\begingroup$

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)|}$.

$\endgroup$
1
$\begingroup$

Any hierarchical clustering algorithm should meet your needs. There are many efficient methods for hierarchical clustering; you can use any of them for your application.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.