networkx/networkx — pull request #1010 by francis-liberty (2013-11-15 12:56:08+00:00)
Title: Add feature: finding denset k-node subgraph. Corresponding to issue #999

Answering the wish list #999. I implemented the approximate algorithms proposed in the [paper 2](http://arxiv.org/abs/0912.5327) @hagberg mentioned in his comment.

paper 2 is based on previous work of [paper 1](http://link.springer.com/article/10.1007/s004530010050). Both are referred in the code.

Basically, this problem is NP-hard. The algorithm proposed is a combination of 5 different algorithms (as in the code, they correspond to ```__trivial(), __greedy(), __walks2(), __walks3(), __walks4()```. For reference, better see in paper 1, since paper 2 didn't mention all 5 algorithms in detail), each of which can solve one aspect of this problem, and by choosing the best result out of 5 different results, the paper claim it has constant approximation ratio. Combining first 3 is called algorithmA, while adding the left 2 is called algorithmB. algorithmA alone can give reasonable approximation in average cases, algorithmB is brought up to deal with the worst cases. The work of paper 2 is mainly dealing with worst cases, too, besides more rigorous performance proof.

However, I found the 4th and 5th algorithm (hence algorithmB) too complicated, and slow. Meanwhile, as proven in the paper, I don't think they contribute much to the average case. I did write algorithm 4 (```__walks3()```), but I found it really consuming since it makes quite a lot of calls on the other 3 algorithms. So I dropped them, waiting for your review and suggestion, for now I don't want to dive into this blindly. I'm not math student, all the formulas made me dizzy already, so forgive me I didn't work it through.

For the tests, I used one graph from the [wikipedia page](en.wikipedia.org/wiki/Dense_subgraph) for this program. And one using nx.wheel_graph(), because the centre of wheel_graph must be included if k > 1. in doc tests, I used nx.house_graph(), again, the triangle is the optimum solution when k == 3.

Waiting for your review. I would be happy to listen to your suggestion, and of course, open to bug fixes ;)