用于图中心性计算的高效节点分组技术

Question

我正在优化一些代码，这些代码涉及频繁访问与图中每个节点的中心性相关的值。由于具有相同邻居的节点在我的计算中具有相同的值，我认为将具有相同邻居集的节点分组在一起可能是有益的。这样，我可以通过只对每个组执行一次而不是对每个单独的节点执行一次来减少计算次数。但是，我不确定如何有效地实现这种分组方法。任何有关解决此问题的最佳方法的建议或意见将不胜感激。

这是我所做的实现，但它非常基础。如您所见，我有 2 个循环，代码大约为 O(n^2)，这在大图上使用时相当多。 正如@ravenspoint 和@PaulBrodersen 正确指出的那样，我的循环没有正常工作，所以我更改了实现。

def group_similar_nodes(G):
    node_groups = []
    lonely_node = []
    nbNodes = 0
    neighbors = {}
    for node in G.nodes():
        neighbors[node] = set(G.neighbors(node))
        lonely_node.append(node)
        nbNodes+=1
    for node in range(nbNodes):
        if node in lonely_node:
            group = [node]
            lonely_node.remove(node)
            for node2 in range(node+1,nbNodes):
                if(node !=node2) and (node2 in lonely_node):
                    diff = neighbors[node] ^ neighbors[node2]
                    diff.discard(node)
                    diff.discard(node2)
                    if(not diff):
                        group.append(node2)
                        lonely_node.remove(node2)
            node_groups.append(group)
    return node_groups

如果你想测试代码，这里有一个 MRE

import networkx as nx

def group_similar_nodes(G):
    node_groups = []
    lonely_node = []
    nbNodes = 0
    neighbors = {}
    for node in G.nodes():
        neighbors[node] = set(G.neighbors(node))
        lonely_node.append(node)
        nbNodes+=1
    for node in range(nbNodes):
        if node in lonely_node:
            group = [node]
            lonely_node.remove(node)
            for node2 in range(node+1,nbNodes):
                if(node !=node2) and (node2 in lonely_node):
                    diff = neighbors[node] ^ neighbors[node2]
                    diff.discard(node)
                    diff.discard(node2)
                    if(not diff):
                        group.append(node2)
                        lonely_node.remove(node2)
            node_groups.append(group)
    return node_groups

i = 4 #number of communitues
n = 5 # number of nodes per communitues
p_in = 1 # probability of an edge within a community
p_out = 0.1 # probability of an edge between communities

G = nx.planted_partition_graph(i, n, p_in, p_out, seed=42) 
print(group_similar_nodes(G))
#expected result
# [[0, 1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13, 14], [15], [16], [17], [18], [19]]

Answer 1

   for node2 in lonely_node

此循环导致对每对节点进行两次检查（一次使用 X,Y，一次使用 Y,X）

我不知道如何在 python 中修复它。在 C++ 中它会是这样的

for( node_index = 0;
     node_index < lonely_node.size();
     node_index++ )
   for( node_index2 = node_index+1;
        node_index2 < lonely_node.size();
        node_index++ )

---

既然你关心性能，你应该考虑从 python 转向编译语言，比如 C++。这会给你带来性能提升，有时运行相同算法的速度会快 50 倍。

Answer 2

在最终正确理解问题之后，答案非常简单，并且可以在创建

nx.Graph

对象后在线性时间内完成。核心的

nx.Graph

对象将图形表示为它的邻接列表，即节点到它们的（无序列表）邻居的映射。我们想要一个邻居到节点的映射。因此，我们需要做的就是规范化邻居集的表示，然后反转映射：

import networkx as nx

def invert_dict(d):
    # https://stackoverflow.com/a/485368/2912349
    inverted = dict()
    for k, v in d.items():
        inverted[v] = inverted.get(v, []) + [k]
    return inverted

if __name__ == '__main__':

    G = nx.Graph([(0, 1), (1, 2), (2, 3), (3, 0)]) # square graph

    d = dict()
    for node in G:
        d[node] = tuple(sorted(G.neighbors(node)))

    inverted = invert_dict(d)
    print(list(inverted.values()))
    # [[0, 2], [1, 3]]