I wonder if there are papers that uses max cut algorithm(s) to cluster data. For example, if an edge between two nodes $u$ and $v$ indicate that $u$ and $v$ are different, then the max-cut in some sense partition the data into two clusters in a meaningful way.
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ Usually you want to cut as few edges as possible, so min cut or sparsest cut seems more appropriate. $\endgroup$– Yuval FilmusJun 30, 2018 at 6:33
-
$\begingroup$ And you usually have edges between nodes that are similar and not different. Then you get back the classic clustering problem. $\endgroup$– Pål GDJun 30, 2018 at 7:25
-
$\begingroup$ Max-cut for general graphs is known to be $\text{NP-Complete}$. So usually, when people use graph-cuts to cluster data into two parts, they tend to use an "energy function" that penalize dividing the graph at certain points. Graph-cuts (with max-flow min-cut) are used a lot in Computer Graphics and Computer Vision for example. Here is one example for such use: csd.uwo.ca/~yuri/Papers/iccv01.pdf ("Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D Images") $\endgroup$– MickeyJun 30, 2018 at 17:24
-
$\begingroup$ I am aware of min cut formulation. However, I was wondering if there are applications where the notion of being "different" instead of being "similar", represented by graphs, is easier to see in the data. $\endgroup$– polar_bear_cheeseJun 30, 2018 at 20:37
Add a comment
|