CODEWITHSUNDEEP
pythonnetworkxknn
sairam rebbapragada
sairam rebbapragada

Reputation: 21

Find K nearest neighbors of a node in a Networkx graph

I am very new to using NetworkX package.

I am trying to find out if there is a way to find the K-nearest neighbors of a node in a weighted undirected graph.

My graph is as given below:

import networkx as nx

g = nx.graph()
g.add_node(0)
g.add_node(1)
g.add_node(2)
g.add_node(3)
g.add_edge(0,1,weight=2)
g.add_edge(0,2,weight=3)
g.add_edge(0,3,weight=4)
g.add_edge(1,2,weight=3)
g.add_edge(1,3,weight=5)
g.add_edge(2,3,weight=6)

Now, is there a direct function in networkx that would give me k nearest neighbors of a given node, something like:

knn(0) when k=2 should return 1 and 2 as among the edges from 0, (0,1) and (0,2) have the least weights.

Thank you.

Upvotes: 2

Views: 2391

Answers (2)

Riccardo Bucco
Riccardo Bucco

Reputation: 15384

Try with this approach:

import networks as nx
from operator import itemgetter

def knn(graph, node, n):
    return list(map(itemgetter(1),
                    sorted([(e[2]['weight'], e[1])
                            for e in graph.edges(node, data=True)])[:n]))

Here is an example:

>>> knn(g, 0, 2)
[1, 2]

Upvotes: 0

Jishan Shaikh
Jishan Shaikh

Reputation: 1806

K-Nearest Neighbor is deprecated and will be removed in v3.0, which was defined as:

k_nearest_neighbors(G, source="in+out", target="in+out", nodes=None, weight=None)

You can still use knn (with degree connectivity) as:

def k_nearest_neighbors(G, source="in+out", target="in+out", nodes=None, weight=None):
    import warnings

    msg = (
    "k_nearest_neighbors function is deprecated and will be removed in v3.0.\n"
    "Use `average_degree_connectivity` instead."
    )
    warnings.warn(msg, DeprecationWarning, stacklevel=2)
    return average_degree_connectivity(G, source, target, nodes, weight)

For a complete list of NetworkX algorithms, visit docs.

Upvotes: 0

Related Questions