CODEWITHSUNDEEP
pythonnetworkx
swiss_knight
swiss_knight

Reputation: 7821

find number of connected edges to a node and node with max connected edges

In a graph, how do I find the number of connected (directly bound) edges to a node?
And then, it would be trivial, but if there is any direct method to find the unique(s) node(s) with the maximum edges connected to them it would be nice.
I'm using Python 2.7 and Networkx.

Until now, I'm doing like this:

sG            = list(nx.connected_component_subgraphs(G)) # sG is a sub_graph of main graph G
nb_sG         = len(sub_graphs)
max_con_node  = list()
for m in xrange(nb_sG):
    sG_nodes      = [(node, len(sG[m].edges(node)), sG[m].edges(node)) for node in sG[m].nodes()]
    connexions    = [i[1] for i in sG_nodes]
    idx           = [i for i,x in enumerate(connexions) if x==max(connexions)]
    max_con_node.append((max(connexions), [sG_nodes[i][0] for i in idx]))

Thanks.

Upvotes: 1

Views: 9068

Answers (3)

user7864386
user7864386

Reputation:

We can build a graph, then cast the DegreeView object to a dictionary constructor and use collections.Counter.most_common method to find the maximum degree:

import networkx as nx
from collections import Counter
lst = [('a','b'), ('a','c'), ('b','e'), ('a','d')]

G = nx.Graph()
G.add_edges_from(lst)
degreeView = G.degree()

degree_counts = Counter(dict(degreeView ))
max_degree_node = degree_counts.most_common(1)

Output:

('a', 3)

Node 'a' has the most number of edges (3), i.e. maximum degree.

Upvotes: 0

Joel
Joel

Reputation: 23827

edit -- I've updated for new version of networkx. In general, please look at the Migration Guide for how to update your code from networkx 1.11 to 2.x.

I think you are asking for how to find how many edges a node has. This is known as the degree of a node.

For networkx v2.x, G.degree(node ) gives you the dgree of the node and G.degree() is a 'DegreeView' object. It can be converted into a dict using dict(G.degree()). 

G = nx.Graph()
G.add_edges_from([[1,2],[1,3],[2,4],[2,5]])
G.degree()
> DegreeView({1: 2, 2: 3, 3: 1, 4: 1, 5: 1})
max(dict(G.degree()).items(), key = lambda x : x[1])
> (2,3)

in networkx v1.11 and lower: G.degree(node) gives you the degree of the node and G.degree() is a dict whose keys are the nodes and whose values are the corresponding degrees.

So max(G.degree().items(), key = lambda x: x[1]) is a simple one-liner that returns (node, degree) for the node with maximum degree.

Here is an example:

G = nx.Graph()
G.add_edges_from([[1,2],[1,3],[2,4],[2,5]])
G.degree()
> {1: 2, 2: 3, 3: 1, 4: 1, 5: 1}
max(G.degree().items(), key = lambda x: x[1])
> (2,3)

Upvotes: 6

victor
victor

Reputation: 1644

It looks like you are using an adjacency list to represent your graph. Thus, to find the number of edges connected to a node you could find the size of your adjacency list for that node.

To find the node that has the most connected edges, you could iterate through all of your nodes and find the one with the most connected edges. If you have to repeat this operation often, you could keep a pointer to the node with the most edges and simply check and possibly replace it with a new node whenever you connect extra edges or add a new node.

Check out the Wikipedia page for more information: https://en.wikipedia.org/wiki/Adjacency_list

Upvotes: 0

Related Questions