Consider an undirected graph that models a social network. Each vertex is a person, each arch represents a friendship relation between two persons. Each arc is decorated by its average 'usage': how much, on average, the arc is used to read/send some information (ie: send my status update to my friends).

By default, the graph structure models the friendship relationship between people; but as we all know not all friends are the same: some are more important than others, and we want to receive news more reliable/faster than from others (ie: on facebook, some friends can be ignored). An arc would be more 'used' if we receive more often news by the person associated with it.

So, from the social graph made by the 'who-knows-who' relationship, we can infer a subgraph of the 'who-ignores-who' with its dual 'who-cares_about-who'.

The problem that I'd like to solve is how to split/transform the original 'who-knows-who' graph into the two described sub-graphs as clusters, such as the arcs between these 2 clusters is minimal.

Is this problem tractable ? Can it be reduced to the 'min-bisection' (or similar NP-hard) problems ?

thanks, valerio

  • 2
    $\begingroup$ Unless I've misunderstood your question, it seems like it is very similar to the min-cut problem (en.wikipedia.org/wiki/Minimum_cut) which is well-solved. $\endgroup$
    – mhum
    Dec 20, 2010 at 19:31

1 Answer 1


I assume that the edge weights express how much the users interact to one another, rather than the amount of communication , i.e. the communication is always mutual and not in risk of being just one-sided. This is more an issue of modeling and not of the problem itself.

The sets in general are not disjoint, as a cut would require them to be, unless you are referring to the subgraph of a certain person's friends (the adjacent vertices). In the social network graph, complex relations can be formed. For example, think of a triangle graph of 3 friends: You (A) might care for a friend B who also cares for your mutual friend C, however you ignore C. It is unclear in which subgraph C belongs. Experimenting with graphs allows you to find a lot of examples where the two sets are not disjoint.

Even if the subgraphs were disjoint and you wanted to know how communities, i.e. groups of people that care for each other, appear in the graph, this is the min-k-cut problem , which is NP-complete, unless you know the number of communities (which in general you don't).

However, you can easily obtain the two subgraphs you want, by selecting a threshold and then on one graph include all edges (and their adjacent vertices) that pass that threshold, constructing the "who-cares_about-who" subgraph and in the other one include the edges that do not and also invert the weights, so that the bigger the weight, the higher the lack of interest between two friends. The problem with this approach is that deciding the value of the threshold is an optimization problem which seems to be reduced to the previous NP-complete problem. Still, you can use a number of techniques from statistics and experimental data to have a fixed threshold, perhaps associated with a level of confidence. Furthermore, you can use fuzzy logic so that the threshold is an interval instead of a fixed point, increasing the accuracy but risking false positives.


Your Answer

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

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