Измерение «удаленности» узла в графе

Question

Я наметил все грани графика в древней BBS-игре TradeWars 2002. Есть 1000 узлов. Граф официально является ориентированным графом, хотя большинство ребер между узлами являются ненаправленными. Граф сильно связан.

Я моделировал вселенную в networkx. Я хотел бы использовать методы networkx для определения «самых удаленных» узлов в сети. Я не знаю, как сформулировать «наиболее удаленный» в терминологии теории графов. Но у меня есть идея - узлы, в которые можно столкнуться очень редко, когда кто-то проходит между двумя другими произвольными узлами. И идея о том, что на краю хорошо соединенных узлов может быть цепочка узлов, которые простираются вдоль одного пути, который заканчивается.

Я представляю себе то, что я себе представляю, это узел 733. Маловероятно, что кто-то случайно наткнется на него, по сравнению с другими, лучше связанными узлами.

Что я мог бы использовать из библиотеки networkx для количественной оценки некоторой степени «удаленности»?

Это вся вселенная:

Answer 1

Но у меня есть идея - узлы, в которые очень редко сталкиваются, когда кто-то проходит между двумя другими произвольными узлами.

Как упомянул @Joel, существует много доступных мер центральности, и между ними часто бывают сильные корреляции, так что многие из них, вероятно, дадут вам больше или меньше того, что вы хотите.

При этом, я думаю, что класс центральности, который наиболее точно отражает вашу интуицию, основан на случайных прогулках . Некоторые из них довольно дороги для вычисления (хотя см. эту статью для некоторых недавних улучшений в этом направлении), но, к счастью, существует сильное соответствие между центральностью собственного вектора и частотой, с которой узлы посещаются случайный ходок .

Реализация в networkx доступна через networkx.algorithms.centrality.eigenvector_centrality.

Answer 2

networkx имеет набор алгоритмов для таких задач: центральность . Например, вы можете использовать простейшую функцию: closeness_centrality :

# Create a random graph
G = nx.gnp_random_graph(50, 0.1)

nx.closeness_centrality(G)

{0: 0.3888888888888889,
 1: 0.45794392523364486,
 2: 0.35507246376811596,
 3: 0.4375,
 4: 0.4083333333333333,
 5: 0.3684210526315789,
...

# Draw the graph
labels = {n: n for n in G.nodes}
nx.draw(G, with_labels=True, labels=labels)

А самые удаленные (менее центральные) узлы можно перечислить, возвращая узлы с наименьшим closeness_centrality (обратите внимание на идентификаторы узлов и узлы в синих кружках на верхнем рисунке:

c = nx.closeness_centrality(G)
sorted(c.items(), key=lambda x: x[1])[:5]

[(48, 0.28823529411764703),
 (7, 0.33793103448275863),
 (11, 0.35251798561151076),
 (2, 0.35507246376811596),
 (46, 0.362962962962963)]