3

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.

user1389892
  • 53
  • 1
  • 4
  • Tim Roughgarden's [lectures on minimum cuts](https://www.youtube.com/watch?v=Zfc1iUQGy48&list=PLLH73N9cB21W1TZ6zz1dLkyIm50HylGyg) might give a good introduction. – Mihai Todor Mar 27 '14 at 10:56

3 Answers3

2

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 :

Finally, there's a proposal in Area 51 for a new Network Science site, which would be more directly related to this problem.

Community
  • 1
  • 1
Vincent Labatut
  • 1,788
  • 1
  • 25
  • 38
1

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.

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
0

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?

Codor
  • 17,447
  • 9
  • 29
  • 56