Функции графа с низкой вычислительной сложностью ⇐ Python

[Anonymous]

Я пытаюсь сгруппировать несколько немаркированных невзвешенных неориентированных графов. Я хотел бы вычислить некоторые скалярные функции для каждого из них, чтобы построить вектор внедрения, а затем использовать алгоритм кластеризации, чтобы посмотреть, можно ли их различить без присмотра. Однако большинство функций, которые я планировал использовать (центральность по близости/между, коэффициент кластеризации), довольно сложно вычислить, и у меня нет доступа к какому-либо существенному оборудованию.
Что такое какие репрезентативные особенности графов, которые имеют меньшую вычислительную сложность, которые необходимо извлечь? Скажем, около O(n) или O(m)
Для этой задачи я использую библиотеку python networkx

Подробнее здесь: https://stackoverflow.com/questions/792 ... complexity