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

11

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

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

Зур Лурия
источник
Поскольку каждый шаг в итеративном алгоритме собственных значений для матриц по n обычно требует c n 2 шагов, графики, для которых мы можем легко решить, являются ли они расширителями, намного меньше, чем запрашиваемые вами графики веб-масштаба. Даже n = 10 5 является проблемой. Тем не менее, социальные сети являются совершенно особенными. По сути, вы спрашиваете, можно ли аппроксимировать собственное значение в чем-то вроде квазилинейного времени и квазилинейного пространства в n , если входной граф разрежен, а его вершинные степени подчиняются степенному закону. nncn2n=105n
Андрас Саламон
Да, я слишком долго занимался теорией. Мне даже в голову не приходило, что график facebook может быть настолько большим, что вычислить его спектральный разрыв будет невозможно.
Zur Luria

Ответы:

8

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

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

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

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

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

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

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