0
$\begingroup$

Let $G=(N,E)$ be a undirected graph of nodes $N$ and edges $E$. Each node $n \in N$ has a weight $w(n)$. The weight of a graph is defined as the sum of the weights of its nodes, i.e., by $w(G) = \sum_{n \in N}w(n)$. The connectivity of the graph is defined to be $c(G) = \#E_G / (\#N_G \cdot (\#N_G - 1)/2)$ -- this measures the fraction of edges in comparison to the maximum possible number of edges.

Given $G$ and a number $x$, I want to find the maximal-weight subgraph $G'$ which has at least connectivity $x$, i.e., I want to find $G'$ that makes $w(G')$ as large as possible, subject to the requirement that $G'$ is a subgraph of $G$ and $c(G') \ge x$. This looks like some kind of generalization of the clique problem; here I essentially want to find a "pseudo-clique". Is there any efficient algorithm for this problem?

$\endgroup$
  • 1
    $\begingroup$ You are saying two things that compromise with each other - the more connected it is, the less weight it can have. What exactly do you want? Could you state your problem more formally (e.g. starting with "Let G be an undirected graph ...")? $\endgroup$ – WhatsUp Jul 23 '15 at 0:09
  • $\begingroup$ @WhatsUp I gave it a shot, I hope that this will clear things up. $\endgroup$ – Sim Jul 23 '15 at 11:18
  • $\begingroup$ Yes, the question is now clear (with a small typo: in the formula for connectivity(G), it should be #E_G instead of #W_G). $\endgroup$ – WhatsUp Jul 23 '15 at 12:09
  • $\begingroup$ Howevery I don't know how to answer your question... the problem seems quite hard to me. In this paper it is stated that finding a maximun density subgraph with given lower bound on the size (equivalent to your graph_weight if every node has weight 1) is NP hard. Not the same as what you're asking, but shows that these kinds of problems can be difficult. But if your potential application is Social Networks, maybe a greedy algorithm will be good enough in practice... $\endgroup$ – WhatsUp Jul 23 '15 at 12:20
2
$\begingroup$

Your problem is NP hard, because with $x=1$ (real clique) and the same weight for each node you get the maximum clique problem, which is NP complete. You can try to find a reduction in order to use a SAT solver, or just enumerate the $2^N$ subgraphs.

Furthermore, unless P = NP, there can be no polynomial time algorithm that approximates the maximum clique to within a factor better than $O(n^{1 − \varepsilon})$, for any $\varepsilon > 0$. Wikipédia

We can't even find a good probabilistic algorithm, unless NP is in BPP.

If your $x$ is fixed and $<1$, look at the following article:

An Efficient Algorithm for Solving Pseudo Clique Enumeration Problem. Takeaki Uno. Algorithmica, January 2010, Volume 56, Issue 1, pp 3-16.

It considers a variant of the problem with no weights, but you can substitute each vertex by a clique of size square root of its weight, if the weights are not too big, and then apply their techniques.

$\endgroup$
  • $\begingroup$ ah, thank you for the correction concerning the percentage. Yes I am aware that the problem is NP hard, but I was hoping that somebody smarter than me already thought about this and came up with an heuristic algorithm. As I am not really eager to bruteforce a graph with 3000 nodes and a couple million connections. $\endgroup$ – Sim Jul 23 '15 at 13:01
  • $\begingroup$ So relaxing the problem by saying that it does not have to be a 'real' clique but on e.g. 90% does not help? $\endgroup$ – Sim Jul 23 '15 at 13:20
  • $\begingroup$ @Sim Answer edited $\endgroup$ – François Jul 23 '15 at 13:36

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.