查找连接到一个节点和具有最大连接边的节点的数量
问题描述:
在图中,如何查找连接(直接绑定)到一个节点的边数?
然后,这将是微不足道的,但如果有任何直接的方法来找到最大边连接到他们的独特(S)节点(S),这将是很好的。
我正在使用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]))
感谢。
答
看起来您正在使用邻接列表来表示图。因此,要查找连接到节点的边的数量,您可以找到该节点的邻接列表的大小。
要查找具有最多连接边的节点,可以遍历所有节点并找到边连接最多的节点。如果你不得不经常重复这个操作,你可以保留一个指向最边缘的节点的指针,并且只要检查并且可能用新节点替换它,只要你连接额外的边或添加一个新的节点。
退房更多信息,*页面: https://en.wikipedia.org/wiki/Adjacency_list
答
我认为你询问如何找到一个节点有多少边了。这被称为节点的程度。
G.degree(node)
给你节点的程度和G.degree()
是一个字典,其键是节点,其值是相应的度数。
所以max(G.degree().items(), key = lambda x: x[1])
是一个简单的单线程,返回节点的最大度数(节点,度)。
下面是一个例子:
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)