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 ?