I'm working on my paper revolving around finding the best possible set of nodes of a graph so that the final set would reach a maximum of certain parameter. Currently I have a 32-node network with double-oriented edges with given weights.
I'm trying to extract a set of 6 so that the sum of the 'synergy indicator' -as I call it now, of each would be the highest possible. (synergy indicator of a node is calculated as: $I = \mathrm{in-degree}\times\mathrm{in-power} + \mathrm{out-degree}\times\mathrm{out-power}$, where degree is obviously the amount of in- and out-coming edges and power is a sum of their respective weights)
I'm calculating all this with python so it is still possible to brute-force it creating all possibilities of 6-node sets and choosing the best one. Number of possible sets is already just shy of a million and my goal is to choose a set of 64 from virtually however many (I was planning on 4000), so the numbers increase very unpleasantly.
So far I'm trying to measure Total Synergy Indicator, store it with the respective set, then remove the weakest node and search for a one that would make the TSI maximum. Then add it to the set and repeat.
I was wondering if anyone has done something like this before and if maybe there is a nice tidy way of searching the best outcome.
The problem of finding an optimal set of $k$ nodes is NP-hard in general (i.e. in the case where $k$ is not a constant). This is true even in the simplest unweighted, undirected case, and follows because in this case a $k$-node clique, if it exists, will be optimal, so this problem is at least as hard as determining whether a $k$-node clique exists, which in turn is NP-complete.
For the case where $k$ is fixed, a brute force search is polynomial time but the degree of the polynomial grows with $k$. It's believed that CLIQUE is not fixed-parameter tractable, i.e. for any correct algorithm, the degree of the polynomial must go to infinity as $k$ increases (see wikipedia).
There are algorithms for CLIQUE which slightly improve over the trivial $O(n^k)$ brute-force algorithm, but they are complex and probably don't extend well to your problem of finding the closest thing to a clique (let alone in the weighted/directed case). I'm not an expert on algorithms, but the most relevant paper I could find was this one by Eisenbrand and Grandoni. They give the running time of their algorithm in terms of the running time of matrix multiplication, but I think the upshot is that they get $O(n^{f(k)})$ where $f(k)\approx 0.79k$. Even if this did extend to your problem, you'd have no hope of anything better than $O(n^{50})$ for $k=64$.