CODEWITHSUNDEEP
algorithmgraph
user1389892
user1389892

Reputation: 63

How to identify loosely-connected components of a graph

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.

Upvotes: 4

Views: 1203

Answers (3)

Vincent Labatut
Vincent Labatut

Reputation: 1808

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 :

People in Cross Validated also talk about community detection :

Upvotes: 2

David Eisenstat
David Eisenstat

Reputation: 65458

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.

Upvotes: 1

Codor
Codor

Reputation: 17605

The answer might be somewhat general, but you could could try to model your problem as a flow problem and generate a minimum cut; see here. The edges could be bidirectional with capacity 1, and a resulting cut would maybe yield the desired partition?

Upvotes: 0

Related Questions