# pseudo clique with at least connectivity x and maximum weight of the nodes

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?

• 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 ...")? Jul 23, 2015 at 0:09
• @WhatsUp I gave it a shot, I hope that this will clear things up.
– Sim
Jul 23, 2015 at 11:18
• 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). Jul 23, 2015 at 12:09
• 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... Jul 23, 2015 at 12:20

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.

• 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.
– Sim
Jul 23, 2015 at 13:01
• So relaxing the problem by saying that it does not have to be a 'real' clique but on e.g. 90% does not help?
– Sim
Jul 23, 2015 at 13:20
• @Sim Answer edited Jul 23, 2015 at 13:36