<p>For an undirected weighted complete graph $G = (V, E)$. Assuming the edge weight indicates the similarity between different nodes, the smaller $w_{ij}$ is, it means $i$ and $j$ are more similar towards each other.</p>

<p>I'm trying to find a subset of size $k$ nodes such that they look not so "similar" towards one another, $\textrm{i.e.}$ $k$ nodes $G_k = (V_k, E_k)$ s.t. $\sum_{(i,j) \in E_k} w_{ij}$ is maximized.</p>

<p>I'm not looking for an exact solution but I do want to know whether there is an approximation algorithm that is easy to implement and can still have some kind of performance guarantee.</p>

CC BY-SA 3.0
2013-03-02T04:07:35.040Z
Do you really want an approximation algorithm that is NOT easy to implement?
Yoshio Okamoto
CC BY-SA 3.0
2013-03-02T05:57:25.523Z
Negative of the function you are trying to maximize can be shown to be a [submodular function](http://en.wikipedia.org/wiki/Submodular_set_function) on the set of nodes. So your problem can be stated as a submodular minimization problem, which has been well studied. There must be some approximation algorithms for minimizing over subsets of fixed size $k$.
polkjh
CC BY-SA 3.0
2013-03-02T06:11:02.433Z
@YoshioOkamoto: Oops...should be "easy to implement". :)
derekhh
CC BY-SA 3.0
2013-03-02T06:11:34.757Z
@polkjh: Thanks, can you point out some more useful links or references?
derekhh
CC BY-SA 3.0
2013-03-02T07:13:36.717Z
The submodular function we get in your case is even more special, it is an increasing function. It might be possible to use that too. But these are some papers on minimizing general submodular functions with constraints on size of subsets. http://algorithmofsaintqdd.googlecode.com/svn/trunk/Papers/ML/ICML2011/icml2011proceedings/506_icmlpaper.pdf and http://arxiv.org/pdf/0805.1071v3.pdf
polkjh
CC BY-SA 3.0
2013-03-02T07:21:17.763Z
In fact, it seems your problem is a standard one, called densest $k$-subgraph problem. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.9443
polkjh
CC BY-SA 4.0
2018-08-21T03:01:29.893Z
@derekhh, did you ever find a decent answer to this question? I was thinking about this problem in the context of https://projecteuler.net/problem=60
Alex Coventry
<graph-algorithms><approximation-algorithms><clique>
Finding minimum weight $k$ cliques in a complete graph
derekhh
# Finding minimum weight $k$ cliques in a complete graph

(Asked by: username_0 on 2013-03-02)

For an undirected weighted complete graph $G = (V, E)$. Assuming the edge weight indicates the similarity between different nodes, the smaller $w\_{ij}$ is, it means $i$ and $j$ are more similar towards each other.

I'm trying to find a subset of size $k$ nodes such that they look not so "similar" towards one another, $\textrm{i.e.}$ $k$ nodes $G\_k = (V\_k, E\_k)$ s.t. $\sum\_{(i,j) \in E\_k} w\_{ij}$ is maximized.

I'm not looking for an exact solution but I do want to know whether there is an approximation algorithm that is easy to implement and can still have some kind of performance guarantee.

**Tags:** graph-algorithms, approximation-algorithms, clique

> **Comments:**
> **username_1**: Do you really want an approximation algorithm that is NOT easy to implement?  
> **username_2**: Negative of the function you are trying to maximize can be shown to be a [submodular function](http://en.wikipedia.org/wiki/Submodular_set_function) on the set of nodes. So your problem can be stated as a submodular minimization problem, which has been well studied. There must be some approximation algorithms for minimizing over subsets of fixed size $k$.  
> **username_0**: @YoshioOkamoto: Oops...should be "easy to implement". :)  
> **username_0**: @username_2: Thanks, can you point out some more useful links or references?  
> **username_2**: The submodular function we get in your case is even more special, it is an increasing function. It might be possible to use that too. But these are some papers on minimizing general submodular functions with constraints on size of subsets. http://algorithmofsaintqdd.googlecode.com/svn/trunk/Papers/ML/ICML2011/icml2011proceedings/506_icmlpaper.pdf and http://arxiv.org/pdf/0805.1071v3.pdf  
> **username_2**: In fact, it seems your problem is a standard one, called densest $k$-subgraph problem. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.9443  
> **username_3**: @username_0, did you ever find a decent answer to this question? I was thinking about this problem in the context of https://projecteuler.net/problem=60  

---

## 0 answers

