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?
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 &gt; 0$. Wikipédia

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

If your $x$ is fixed and $&lt;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.