计算复杂度低的图特征

Question

我正在尝试对一些未标记的未加权无向图进行聚类。我想为它们中的每一个计算一些标量特征来构建嵌入向量，然后使用聚类算法来查看是否可以以无监督的方式区分它们。然而，我计划使用的大多数功能（接近度/介数中心性、聚类系数）都很难计算，而且我无法访问任何重要的硬件。

需要提取的计算复杂度较低的图有哪些代表性特征？比如说，大约

O(n)

或

O(m)

对于这个任务，我使用Python库

networkx

Answer 1

如果您正在使用

networkx

，我建议您查看他们的算法列表以找到一些想法。当然，并非所有这些都会以线性甚至多项式时间运行，但多项式时间对您来说可能足够快（取决于您要分析的图形的大小），如果您不确定运行时间，您可以总是可以运行一些经验测试来查看运行时间如何随图形大小变化。

这里有一个简短的功能列表，可以快速计算以帮助您入门：

import networkx as nx


def get_features(g: nx.Graph) -> list[float]:
    return [
        g.number_of_nodes(),
        g.number_of_edges(),
        nx.density(g),
        nx.number_of_isolates(g),
        len(
            # greedy approximation of chromatic number
            set(nx.coloring.greedy_color(g, strategy="largest_first").values())
        ),
    ]


graphs = [
    nx.cycle_graph(8),
    nx.empty_graph(8),
    nx.star_graph(7),
    nx.path_graph(8),
    nx.hypercube_graph(3),
]

for g in graphs:
    print(get_features(g))
# [8, 8, 0.2857142857142857, 0, 2]
# [8, 0, 0, 8, 1]
# [8, 7, 0.25, 0, 2]
# [8, 7, 0.25, 0, 2]
# [8, 12, 0.42857142857142855, 0, 2]