Найден оптимальный алгоритм выявления «скрытых пружин» в устройстве общества.

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

Чем больше и сложнее сеть участников социальных взаимодействий, тем больше в нем скрытых иерархий, порою неведомых самим участникам коммуникаций.
Выявление архитектуры таких иерархий – критически важная задача для:
- понимания характера существующих и предсказания возникновения новых иерархий;
- увязки этих иерархий со «струями и течениями» социальных взаимодействий;
- оказания влияния на них в целях управления динамикой социальных коммуникаций.
Т.е. в наше время, - это важнейшая задача для социологов, политтехнологов, спецслужб и СМИ.

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

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

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

Он также может выявлять и предсказывать появление ненаблюдаемых ребер в сети, - так сказать выявлять «скрытые пружины», влияющие на поведение общества.

Принципиальное преимущество SpringRank перед прежними алгоритмами в том, что
- старые алгоритмы, как правило, лишь «выявляют элиту» - дают высокие ранги небольшому числу важных узлов, что дает мало информации об иерархии узлов с более низким рейтингом;
- новый алгоритм выявляет всю многоуровневую иерархию, - и в том числе, латентную: неявную, скрытую и неочевидную.

Новый алгоритм, возможно, произведет революцию в т.н. «системах одобрения» (Systems of Endorsement ), в которых статус участников обусловлен престижем, репутацией или социальным положением.
К ним, в той или иной мере, относится почти все: от рекомендательных систем в Интернете, до социального устройства общества.

Подробней см. только что опубликованную работу «A physical model for efficient ranking in networks» http://advances.sciencemag.org/content/4/7/eaar8260

#СоциальныеСети #СоциальнаяИерархия #МоделиАлгоритмы

http://advances.sciencemag.org/content/4/7/eaar8260

A physical model for efficient ranking in networks

We present a physically inspired model and an efficient algorithm to infer hierarchical rankings of nodes in directed networks. It assigns real-valued ranks to nodes rather than simply ordinal ranks, and it formalizes the assumption that interactions are more likely to occur between individuals with similar ranks. It provides a natural statistical significance test for the inferred hierarchy, and it can be used to perform inference tasks such as predicting the existence or direction of edges. The ranking is obtained by solving a linear system of equations, which is sparse if the network is; thus, the resulting algorithm is extremely efficient and scalable. We illustrate these findings by analyzing real and synthetic data, including data sets from animal behavior, faculty hiring, social support networks, and sports tournaments. We show that our method often outperforms a variety of others, in both speed and accuracy, in recovering the underlying ranks and predicting edge directions.
| Science Advances