Есть идеи по поводу изменения диаметра сети / графа по мере увеличения количества узлов?

Question

У меня вопрос по поводу увеличения / уменьшения диаметра сети. Я думаю, что когда кто-то добавляет больше узлов в существующую сеть, плотность должна эффективно увеличиваться, и вероятность появления ребер, созданных новыми узлами, может привести к более высокой степени кластеризации. Если это так, то я предполагаю, что диаметр сети должен уменьшаться, когда мы добавляем больше узлов, из-за вероятности, что более короткие геодезические пути могут теперь существовать и стать новым диаметром. Я не прав с этой логикой? Или есть лучшее объяснение или, может быть, я что-то упускаю?

Answer 1

Работа Лесковца, Кляйнберга и Фалаутсоса специально исследовала этот вопрос [ 1, 2]. Они находят:

"Во-первых, графики с течением времени уплотняются, а количество ребер суперлинейно увеличивается в количестве узлов. Во-вторых, среднее расстояние между узлами часто уменьшается со временем, в отличие от общепринятого мнения, что такие параметры расстояния должны медленно увеличиваться как функция количества узлов."