Уточнение порядка и размера сети

Question

В социальных графах часто бывает, что количество узлов намного меньше количества ребер?

При анализе сети Twitter я получил такие результаты

узлов = 20000

ребра = 335000

Как я могу интерпретировать этот огромный разрыв между числами?

Answer 1

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

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

      WITH range(1,100) as id
UNWIND id as a
UNWIND id as b
WITH a, b
WHERE a < b
RETURN count(*)

Если все они связаны, без избыточных отношений мы получим 4950 отношений от 100 максимально связанных людей. На 1000 человек с максимальной связью у вас будет 499500 отношений. Для 10000 у вас будет немного меньше 49995000 отношений.

Есть формула для определения этого количества ребер, возможных для полного графа, и применить ее еще проще, чем наш предыдущий запрос:

      WITH 100 as n
RETURN (n * (n - 1)) / 2.0

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

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