I am using the NetworkX library for Python in my application that does some graph processing. One task is to call the all_simple_paths() function of NetworkX to give me all non-looping paths in the graph (up to a certain max. length of paths). This is working well.
Using this list of all simple paths in the graph the task is now to find a number of n paths out of this list, where each of these n paths should be as different from all other n paths as possible. Or in other words: any two paths from the resulting n paths should have as few common nodes as possible. Or in even other words: each path in the resulting n paths should be as unique as possible.
Can you guys think of any (non brute force) algorithm to achieve this?
It depends a lot on your particular needs. There are a few options. Two built-in, and one that requires a bit more work, but might be faster.
If what you really want is to find two non-intersecting paths, then you can use a filtered graph - after finding one path, induce a subgraph with the intermediate nodes removed, and find the shortest path in that graph.
If you can't guarantee that the paths won't be non-intersecting, then you are back to brute-force. Since paths don't include cycles, and they are simple lists, finding the number of intersecting nodes is as simple as generating sets from the two paths and finding the length of their difference, which is pretty fast. Check all pairs and find the one with the fewest intersection.
Which of the above two is faster depends on your particular graph - is it sparse or dense? How many nodes are there? etc. 
Since all_simple_paths is a generator, you can actually focus that algorithm somewhat. i.e. if you graph the first two paths, and they are completely non-intersecting, then you 
already have your minimal case and don't need to look at any more. There may be a lot of paths, but you can bound with an upper limit of how many to look at, or a threshold that is allowable (i.e. instead of absolutely 0, if these only have 1 in common, it's good enough, return it), or some other combination that uses both how many paths I've looked at and the current maximum to bound the calculation time.
If calculation time is really critical to your algorithm, also consider switching to igraph... networkx is MUCH easier to deal with, and usually performance is 'good enough', but for large brute force algorithms like this, igraph will probably be at least an order of magnitude faster.
One last possibility is to avoid using all_simple_paths at all, and use the bfs tree instead. I am not sure if all_simple_paths is BFS, it probably is, but that might give you a better selection of initial paths to look at with the second algorithm, not sure. E.G. if you know that your source node has multiple successors, you may get decent results by just forcing your starting two paths to start with two different successors instead of just from the initial node. Note that this can also bite you too - this greedy algorithm can lead you astray as well, unless your graph is already a good fit for it (which you may already know, or may not).
How to find n most different paths in a graph?