enter image description hereI currently have an undirected weighted graph. I am trying to find a good algorithm for learning/finding a cluster of closely related nodes and/or loosely relationship within a cluster in a graph given a size of the cluster. For example, here the longer edges represent the farther relationship between 2 nodes. We identified 2 clusters where each cluster has a close relationship internally. I am new to computer science, could you please suggest an algorithm or a paper for this problem? Your help is really appreciated!


1 Answer 1


The problem you are trying to solve is called community detection or community structure, where several popular algorithms are listed, such as Girvan–Newman algorithm and Minimum-cut method.

You can find many related questions and answers on this site, on CrossValidate and on StackOverflow, such as the following:

A good introduction can be found at Community detection in graphs.

A recent survey can be found at Community detection in social networks.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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