Социальные сети, как правило, хорошие экспандеры?

11

Меня интересуют комбинаторные свойства социальных сетей в виде графиков. Люди смотрели на такие вещи, как распределение степеней, коэффициент кластеризации и сжимаемость этих графиков. Один основной вопрос: действительно ли эти графики являются хорошими графами расширителей?

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

graph-theory application-of-theory expanders Зур Лурия
источник

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

по

обычно требует

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

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

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

n

$n$

n

$n$

c n^{2}

$cn^2$

n = 10^{5}

$n=10^5$

n

$n$

Андрас Саламон

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

Zur Luria

8

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

На что можно надеяться, так это на хорошее расширение вершин / ребер для достаточно больших множеств. Однако, если у вас есть сплоченные сообщества в сети, то опять же вы ожидаете низкого расширения.

Я не уверен, что он вполне отвечает на ваш вопрос, но в следующей эмпирической статье рассматриваются свойства, подобные расширению, в социальных сетях. Ответ, кажется, варьируется от сети к сети. http://fragkiskos.me/papers/expansion_SNSMW11.pdf

Я уверен, что есть другая работа в этом направлении, возможно, замаскированная с использованием альтернативной терминологии («структура сообщества», размеры разрезов и т. Д.).

Адам Смит
источник

1

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

Thatchaphol
источник

Идея о том, что социальные сети распространяются как законы власти, была недавно оспорена в результате очень строгого анализа данных: nature.com/articles/s41467-019-08746-5

Стелла Бидерман,

Социальные сети, как правило, хорошие экспандеры?

Ответы: