How to identify loosely-connected components of a graph

Question

Imagine that a graph has two relatively densely connected components that are only connected to each other by relatively few edges. How can I identify the components? I don't know the proper terminology, but the intuition is that a relatively densely connected subgraph is hanging onto another subgraph by a few threads. I want to identify these clumps that are only loosely connected to the rest of the graph.

Answer 1

If your graph represents a real-world system, this task is called community detection. You'll find many articles about that, starting with Fortunato's review (2010). He describes, amongst others, the min-cut based methods mentioned in the earlier answers.

There're also many posts on SO, such as :

• Are there implementations of algorithms for community detection in graphs?
• What are the differences between community detection algorithms in igraph?
• Community detection in Networkx

People in Cross Validated also talk about community detection :

• How to do community detection in a weighted social network/graph?
• How to find communities?

Answer 2

You probably want sparsest cut instead of min cut -- unless you can identify several nodes in a component, min cuts have a tendency to be very unbalanced when the degrees are small. One of the common approaches to sparsest cut is to compute an eigenvector of the graph's Laplacian and threshold it.