Сети, в которых распределение степеней вершин подчиняется степенному закону: немного «хабов» и очень много слабо связанных вершин.
- доля вершин со степенью k убывает степенным образом: много слабо связанных и несколько хабов
- типичный показатель реальных сетей. При γ < 3 дисперсия степеней бесконечна — хабы могут быть сколь угодно большими
Ключевые тезисы
- Механизм предпочтительного присоединения (Барабаши — Альберт) естественно порождает такую структуру.
- Устойчивы к случайным сбоям и крайне уязвимы к целенаправленной атаке на хабы.
- Прямое следствие для ML: признаки на графе имеют тяжёлые хвосты, их нужно логарифмировать.
Подробный разбор
2 подтем — раскройте любую, чтобы увидеть объяснение, формулы, примеры и интерактивные графики.
1Механизм возникновения
Богатые становятся богаче.
В модели Барабаши — Альберт новая вершина присоединяется к существующим с вероятностью, пропорциональной их степени. Такое предпочтительное присоединение неизбежно порождает степенное распределение степеней с показателем около 3.
2Устойчивость и уязвимость
Одно свойство — два противоположных следствия.
| Сценарий | Случайная сеть | Безмасштабная |
|---|---|---|
| Случайные отказы | быстро распадается | устойчива |
| Атака на хабы | устойчива | распадается почти сразу |
| Распространение информации | медленно | очень быстро через хабы |
Практический вывод для инфраструктуры и антифрода: защищать и мониторить нужно в первую очередь хабы, а не среднюю вершину.
Связанные темы
Тяжёлые хвосты и риск · Структура реальных сетей
Power Law95%
Степенное распределение · Теория вероятностей и распределенияПлотность убывает как степень: редкие события встречаются намного чаще, чем предсказывает нормальный закон. Распределения Парето и Ципфа — его классические формы.
Complex Systems95%
Сложные системы · Динамические системы и фракталыСистемы из множества взаимодействующих элементов, где коллективное поведение не сводится к сумме частей.
Small World80%
Феномен малого мира · Графы и сетиКороткие пути между любыми двумя вершинами при высокой локальной кластеризации.
Network Motifs80%
Мотивы и триады · Графы и сетиМаленькие повторяющиеся подграфы, встречающиеся чаще, чем в случайной сети. Хорошие признаки для классификации вершин.
Centrality80%
Центральности · Графы и сетиМеры важности вершины: по числу связей, по посредничеству, по близости и по влиянию соседей.
Heavy Tails75%
Тяжёлые хвосты · Теория вероятностей и распределенияРаспределения, у которых экстремальные значения не являются пренебрежимо редкими. Именно они ломают привычные оценки и метрики.
Extreme Value Theory75%
Теория экстремальных значений · Теория вероятностей и распределенияАппарат для моделирования максимумов и хвостов: как оценить вероятность события, которого ещё не случалось.
Log-normal Distribution75%
Логнормальное распределение · Теория вероятностей и распределенияВеличина, логарифм которой нормален. Возникает там, где эффекты перемножаются, а не складываются.
Self-similarity75%
Самоподобие · Динамические системы и фракталыСвойство структуры повторять себя на разных масштабах — точно или статистически.
Outliers75%
Выбросы · ДанныеНаблюдения, резко отличающиеся от остальных. Они бывают ошибками измерения, а бывают самым ценным сигналом.
MAPE75%
Средняя абсолютная процентная ошибка · МетрикиОтносительная ошибка в процентах — удобна для сравнения рядов разного масштаба.