Given an undirected graph, is it possible to find a criteria that leads to a unique partition of the nodes? The graph is not weighted.

  • $\begingroup$ The loose phrase "community detection" seems relevant, breaking the graph up into subgraphs where a node is more closely related to nodes in its partition than to those in other partitions. A variety of criteria can be used to define what "closely related" means. $\endgroup$ – hardmath Apr 6 '13 at 0:18
  • 1
    $\begingroup$ It's unclear what sort of criteria you have in mind. Of course it's possible to partition the nodes of a graph in many ways, in particular by placing each node in its own subgraph (or somewhat less trivially, by using connected components to partition the graph). What do you mean by "leads to a unique partition"? $\endgroup$ – hardmath Apr 7 '13 at 1:13

This is impossible unless the graph is somehow labeled. For example, consider the complete graph $G = K_{2n}$ consisting of $2n$ vertices and edges between every pair of vertices. All balanced partitions look exactly the same in terms of this graph, so it is not possible to pick one out uniquely.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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