Знаковый граф

Знаковый граф — это взвешенный ориентированный или неориентированный граф, каждому ребру которого приписан знак «+» (положительная связь) или «−» (отрицательная связь). Знаковые графы используются для моделирования отношений между объектами, которые могут быть как дружественными, так и враждебными, и находят применение в социальных сетях, политологии, психологии и анализе данных.

История

Понятие знакового графа было введено в 1940-х годах в рамках теории социального баланса, разработанной американским психологом Фрицем Хайдером. В 1946 году Хайдер опубликовал работу «Attitudes and Cognitive Organization», в которой описал, как люди стремятся к когнитивной согласованности в восприятии социальных отношений. В 1950-х годах идеи Хайдера были формализованы математически: Дорвин Картрайт и Фрэнк Харари в 1956 году предложили модель, где социальная группа представляется в виде знакового графа, а баланс определяется как отсутствие циклов с нечётным числом отрицательных рёбер.

В 1960-х годах теория была расширена Робертом Абельсоном и Милтоном Розенбергом для анализа политических и идеологических систем. С развитием вычислительной техники в 1990-х годах знаковые графы стали применяться для анализа больших социальных сетей, таких как эпистолярные переписки и онлайн-сообщества. В 2000-х годах методы машинного обучения позволили автоматически определять знаки рёбер на основе данных из социальных медиа.

Определение и основные понятия

Знаковый граф \( G = (V, E, s) \) состоит из множества вершин \( V \), множества рёбер \( E \) и функции знака \( s: E \to \{+, -\} \). В неориентированных графах каждое ребро соединяет две вершины, а в ориентированных — имеет направление. Знак «+» обычно интерпретируется как положительное отношение (дружба, симпатия, согласие), а знак «−» — как отрицательное (вражда, антипатия, несогласие).

Баланс и кластеризация

Ключевым свойством знаковых графов является баланс. Граф называется сбалансированным, если все его циклы (замкнутые пути) содержат чётное число отрицательных рёбер. В сбалансированном графе вершины можно разделить на два подмножества (кластера) так, что все рёбра внутри каждого подмножества положительны, а рёбра между подмножествами — отрицательны. Это свойство называется теоремой Картрайта — Харари.

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

Статус и знаки

В ориентированных знаковых графах дополнительно вводится понятие статуса: для каждой вершины можно определить её «статус» как сумму знаков входящих рёбер. В социальных сетях это может отражать популярность или авторитет.

Классификация знаковых графов

Знаковые графы классифицируются по нескольким признакам:

• По типу рёбер: неориентированные (отношения симметричны) и ориентированные (отношения могут быть асимметричными).
• По структуре: полные (все возможные рёбра присутствуют) и разреженные (только часть рёбер).
• По динамике: статические (отношения фиксированы) и динамические (знаки и рёбра могут меняться со временем).
• По приложению: социальные (дружба/вражда), политические (союз/конфликт), когнитивные (согласие/несогласие).

Применение

Социальные сети и анализ отношений

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

Политология и международные отношения

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

Психология и когнитивная наука

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

Машинное обучение и рекомендательные системы

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

Примеры

• Социальная сеть Epinions: пользователи могут выражать доверие (положительное) или недоверие (отрицательное) к другим пользователям. Граф этой сети содержит около 130 000 вершин и 800 000 рёбер.
• Международные отношения: граф, построенный на основе данных о союзах и конфликтах между странами в XX веке, показывает, что большинство циклов сбалансированы, что подтверждает теорию баланса.
• Когнитивные модели: в экспериментах Хайдера испытуемым предлагали оценить отношения между людьми, и результаты показали, что несбалансированные ситуации вызывают психологический дискомфорт.

Критика и ограничения

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

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

Интересные факты

• В 1950-х годах Картрайт и Харари доказали, что любой сбалансированный знаковый граф можно представить как полный двудольный граф с положительными рёбрами внутри долей и отрицательными между ними.
• Понятие знакового графа тесно связано с теорией игр, где знаки могут интерпретироваться как выигрыши или проигрыши в кооперативных и некооперативных играх.
• В 2010-х годах были разработаны алгоритмы для автоматического определения знаков рёбер на основе текстовых данных, что позволило анализировать отношения в социальных медиа без явных меток.

Источники

• Картрайт Д., Харари Ф. «Структурный баланс: обобщение теории Хайдера». // Социальные сети, 1956.
• Хайдер Ф. «Психология межличностных отношений». — М.: Издательство МГУ, 1980.
• Уоссерман С., Фауст К. «Анализ социальных сетей: методы и приложения». — Кембридж: Cambridge University Press, 1994.
• Лесковец Ю., Раджараман А., Ульман Д. «Анализ больших социальных сетей». — М.: ДМК Пресс, 2016.
• Эверетт М., Боргетти С. «Знаковые графы и социальный баланс». // Journal of Social Structure, 2010.