I am working on the following problem: Let $G = \left(V, E\right)$ an undirected graph such that every vertex $i\in V$, has a label $x_i \in \mathbb R$. For every vertex subset $S \subset V$, we define $$\text{Var}(S) = \frac1{|S|} \sum_{i \in S} \left(x_i - \frac1{|S|} \sum_{j\in S} x_j\right)^2$$ the variance of $S$. The question asks for partitioning $G$ into disjoint cliques $\left(C_k\right)_{k}$ in order to maximize the total variance $$\sum_{k}\text{Var}\left(C_k\right).$$ I think that K-means can be used here but I do not know how? Can anyone helps me to find an idea for solving this problem?

  • $\begingroup$ wait what is "the question"? Can you be more specific please? $\endgroup$ May 14, 2019 at 9:28
  • $\begingroup$ The question is to find an algorithm or a heuristic to have the best partition. $\endgroup$
    – Kroki
    May 14, 2019 at 18:34
  • $\begingroup$ that is computer science, not math. "algorithm" is very annoying to define rigorously $\endgroup$ May 14, 2019 at 19:43
  • $\begingroup$ Do the labels have anything to do with the graph structure? Your definition of variance doesn't seem to use the fact that there are edges at all. $\endgroup$ May 14, 2019 at 20:10
  • 1
    $\begingroup$ Oh, I see, you also require that every cluster is a clique, i.e. is a complete subgraph? In that case you're unlikely to have an efficient algorithm to do this - even checking whether graph has a k-clique of size k is NP complete. So if your plan is to do optimization on the space of all cliques, you might be able to do only slightly better than brute force. $\endgroup$ May 14, 2019 at 21:05


You must log in to answer this question.

Browse other questions tagged .