CODEWITHSUNDEEP
pythonnetworkxgraph-theorynearest-neighbor
baxbear
baxbear

Reputation: 890

How to find nearest neighbours of geometric subgraphs in networkx?

When I generate random geometric graphs using NetworkX in python the resulting graphs are not always connected. To change this property I would like to determine the separate subgraphs and find the two nodes in each respective subgraph that is closest to a node in the largest subgraph to connect them. Preferably I would like to be able to also determine the second closest and the third and so on.

Is there a utility in networkx that does it. If not do you know the mathematical most efficient way to solve this? (Maybe randomly select two points in each graph and then execute a k-d tree algorithm - still problem is that at least for the smaller subgraph I would need to execute the algorithm for all nodes?!?!)

Would be great if you could advise me whether there is something existing in networkx that gets the job done or tell me the most efficient way to implement such a routine.

Upvotes: 2

Views: 432

Answers (1)

ravenspoint
ravenspoint

Reputation: 20586

I would like to determine the separate subgraphs

This is the problem of finding the maximal cliques in a graph. That is the sets of vertices that are all reachable from each other, but not reachable from any vertex outside the set.

Here is the pseudo code for the algorithm

LOOP
    CONSTRUCT empty current set
    SELECT V arbitrary vertex
    add V to current set
    remove V from graph
    LOOP      // while set is growing
        added_to_set = false
        LOOP V over vertices in graph
            LOOP Vset over current set
                IF Vset connected to V
                     add V to current set
                     remove V from graph
                     added_to_set = true
                     break;
        IF added_to_set == false
           break;    // the set is maximal
    ADD current set to list of sets
    IF graph has no remaining vertices
       OUTPUT sets found
       STOP

For a C++ implementation of this see code at https://github.com/JamesBremner/PathFinder2/blob/dbd6ff06edabd6a6d35d5eb10ed7972dc2d779a6/src/cPathFinder.cpp#L483

find the node in each respective subgraph that is closest to a node in the largest subgraph

Probably the best and certainly simplest is to calculate the distance between every pair of nodes in the subgraphs, keeping the closest pair.

If you were satisfied with an approximate answer and if the subgraphs do not overlap then you could

calculate center of gravity of largest subgraph
compare distances of subgraph nodes to center of gravity ( instead of with every node in largest subgraph )

Upvotes: 1

Related Questions