找到一个节点的连接边数和具有最大连接边的节点

Question

在图中，如何找到连接（直接绑定）到节点的边数？
然后，这将是微不足道的，但是如果有任何直接的方法可以找到连接到它们的最大边缘的唯一节点，那就太好了。
我正在使用 Python 2.7 和 Networkx。

到目前为止，我是这样做的：

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]))

谢谢。

Answer 1

您似乎在使用邻接表来表示您的图形。因此，要找到连接到节点的边数，您可以找到该节点的邻接列表的大小。

要找到连接边最多的节点，您可以遍历所有节点并找到连接边最多的节点。如果您必须经常重复此操作，您可以保留指向具有最多边的节点的指针，并在连接额外边或添加新节点时简单地检查并可能用新节点替换它。

查看维基百科页面了解更多信息： https://en.wikipedia.org/wiki/Adjacency_list

Answer 2

编辑 -- 我已经更新了新版本的 networkx。一般来说，请查看 Migration Guide 以了解如何将您的代码从 networkx 1.11 更新到 2.x。

我想你是在问如何找到一个节点有多少条边。这被称为节点的度。

对于 networkx v2.x，G.degree(node ) 给你节点的 dgree 而 G.degree() 是一个 'DegreeView' 对象.可以使用 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)

在 networkx v1.11 及更低版本中： G.degree(node) 给出节点的度数，G.degree() 是一个字典，其键是节点，其值是相应的度数。

所以max(G.degree().items(), key = lambda x: x[1])是一个简单的单线，returns (node, degree)表示度数最大的节点。

这是一个例子：

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)

Answer 3

我们可以构建一个图，然后将 DegreeView 对象转换为字典构造函数并使用 collections.Counter.most_common 方法找到最大度数：

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)

输出：

('a', 3)

节点'a'的边数最多(3)，即度数最大。

找到一个节点的连接边数和具有最大连接边的节点

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

python

networkx