Знаковый граф
В области теории графов в математике — знаковый граф это граф, в котором каждое ребро имеет положительный или отрицательный знак.
Знаковый граф сбалансирован , если произведение знаков ребер каждого цикла положительно. Название «график со знаком» и понятие баланса впервые появились в математической статье Фрэнка Харари в 1953 году. [1] Денес Кениг уже изучал эквивалентные понятия в 1936 году, используя другую терминологию, но не осознавая значимости группы знаков. [2] В Центре групповой динамики Мичиганского университета Дорвин Картрайт и Харари обобщили Фрица Хейдера психологическую теорию баланса в треугольниках настроений до психологической теории баланса в знаковых графиках. [3] [4]
Знаковые графы открывались заново много раз, поскольку они естественным образом возникают во многих несвязанных между собой областях. [5] Например, они позволяют описывать и анализировать геометрию подмножеств классических корневых систем . Они появляются в топологической теории графов и теории групп . Они являются естественным контекстом для вопросов о нечетных и четных циклах в графах. Они появляются при вычислении энергии основного состояния в неферромагнитной модели Изинга ; для этого нужно найти наибольшее сбалансированное множество ребер в Σ. Они применялись для классификации данных при корреляционной кластеризации .
Основная теорема
Знак пути есть произведение знаков его ребер. Таким образом, путь положителен только в том случае, если в нем есть четное число отрицательных ребер (где ноль четен). В теории математического баланса Фрэнка Харари знаковый граф сбалансирован , когда каждый цикл положителен. Харари доказывает, что знаковый граф сбалансирован, когда (1) для каждой пары узлов все пути между ними имеют одинаковый знак или (2) вершины разбиваются на пару подмножеств (возможно, пустых), каждое из которых содержит только положительные ребра, но соединены отрицательными краями. [1] Он обобщает теорему о том, что обычный (беззнаковый) граф является двудольным тогда и только тогда, когда каждый цикл имеет четную длину.
Простое доказательство использует метод переключения. Переключение знакового графа означает изменение знаков всех ребер между подмножеством вершин и его дополнением. Чтобы доказать теорему Харари, по индукции показывают, что Σ можно сделать полностью положительной тогда и только тогда, когда она сбалансирована.
Более слабая теорема, но с более простым доказательством, состоит в том, что если каждый 3-цикл в полном графе со знаком положителен, то граф сбалансирован. Для доказательства выберите произвольный узел n и поместите его и все те узлы, которые связаны с n положительным ребром, в одну группу, называемую A те узлы, которые связаны с n отрицательным ребром, в другую, называемую B. , и все Поскольку это полный граф, каждые два узла в A должны быть друзьями, а каждые два узла в B должны быть друзьями, иначе будет несбалансированный трехцикл. (Поскольку это полный граф, любое отрицательное ребро приведет к несбалансированному трехциклу.) Аналогично, все отрицательные ребра должны проходить между двумя группами. [6]
Разочарование [ править ]
Индекс разочарования [ править ]
Индекс разочарования (ранее называемый линейным индексом баланса) [7] ) из Σ — это наименьшее число ребер, удаление которых или, что то же самое, изменение знака (теорема Харари [7] ), делает Σ сбалансированным. Причина эквивалентности заключается в том, что индекс фрустрации равен наименьшему числу ребер, отрицание которых (или, что то же самое, удаление) делает Σ сбалансированным.
Второй способ описания индекса фрустрации состоит в том, что это наименьшее количество ребер, охватывающих все отрицательные циклы. Эту величину назвали числом покрытия отрицательного цикла .
Существует еще одно эквивалентное определение (которое легко доказать переключением). Присвойте каждой вершине значение +1 или −1; мы называем это состоянием Σ. Ребро называется удовлетворенным, если оно положительное и обе конечные точки имеют одинаковое значение, или оно отрицательное и конечные точки имеют противоположные значения. Ребро, которое не удовлетворено, называется неудовлетворенным . Наименьшее количество фрустрированных ребер среди всех состояний — это индекс фрустрации. Это определение было впервые введено в другой записи Абельсоном и Розенбергом под (устаревшим) названием сложность . [8] Дополнением такого множества является сбалансированный подграф Σ с наибольшим количеством возможных ребер.
Нахождение индекса разочарования является NP-сложной задачей. Ареф и др. предложить модели двоичного программирования, способные вычислять индекс разочарования графов до 10 5 края в разумные сроки. [9] [10] [11] В NP-сложности можно убедиться, заметив, что индекс фрустрации графа со всеми отрицательными знаками такой же, как и задача максимального разреза в теории графов, которая является NP-трудной.
Индекс фрустрации важен в модели спиновых стекол , смешанной модели Изинга . В этой модели подписанный граф фиксирован. Состояние состоит из вращения каждой вершины либо «вверх», либо «вниз». Мы думаем, что вращение вверх равно +1, а вращение вниз – как −1. Таким образом, каждое состояние имеет ряд неудовлетворенных ребер. Энергия состояния тем больше, чем больше у него неудовлетворенных ребер, поэтому основное состояние — это состояние с наименьшим количеством неудовлетворенной энергии. Таким образом, чтобы найти энергию основного состояния Σ, необходимо найти индекс фрустрации.
Число разочарования [ править ]
Аналогичным числом вершин является число фрустрации , определяемое как наименьшее количество вершин, удаление которых из Σ приводит к балансу. Эквивалентно, нужен наибольший порядок сбалансированного индуцированного подграфа Σ.
Алгоритмические задачи [ править ]
Три фундаментальных вопроса о знаковом графе: сбалансирован ли он? Каков наибольший размер установленной в нем сбалансированной кромки? Какое наименьшее количество вершин необходимо удалить, чтобы сделать его сбалансированным? Первый вопрос легко решить за полиномиальное время. Второй вопрос называется проблемой индекса разочарования или максимального сбалансированного подграфа . Это NP-трудная задача , поскольку ее частным случаем (когда все ребра графа отрицательны) является NP-трудная задача Maximum Cut . Третий вопрос называется « Число разочарования» или «Проблема максимального сбалансированного индуцированного подграфа» , он также является NP-сложным ; см., например [12]
Теория матроидов [ править ]
Есть два матроида , связанные со знаковым графом, называемые матроидом знаковой графики (также называемым матроидом кадра или иногда матроидом смещения ) и матроидом подъема , оба из которых обобщают матроид цикла графа. Они являются частными случаями одних и тех же матроидов смещенного графа .
Матроид кадра (или знаковой графики ) M ( G ) имеет в качестве основы множество ребер E. матроид [13] Набор ребер является независимым, если каждый компонент не содержит окружностей или содержит только одну окружность, что является отрицательным. (В теории матроида полуребро действует точно так же, как отрицательная петля.) Контур матроида представляет собой либо положительный круг, либо пару отрицательных кругов вместе с соединяющим простым путем, так что два круга либо не пересекаются (тогда соединительный путь имеет один общий конец с каждым кругом и в противном случае не пересекается с обоими) или имеет только одну общую вершину (в этом случае соединительный путь - это одна вершина). Ранг множества ребер S равен n − b , где n — количество вершин G , а b — количество сбалансированных компонентов S , считая изолированные вершины сбалансированными компонентами. Этот матроид является матроидом столбца матрицы инцидентности графа со знаком.Поэтому он описывает линейные зависимости корней классической корневой системы.
Расширенный матроид подъема L0 , ( G ) имеет в качестве основного множества множество E0 с объединение множества ребер E дополнительной точкой мы обозначим e0 , которую . Лифт -матроид L ( G ограниченный E. ) — это расширенный лифт-матроид , Дополнительная точка действует точно так же, как отрицательный цикл, поэтому мы опишем только матроид подъема. Набор ребер является независимым, если он не содержит окружностей или содержит только одну окружность, что является отрицательным. (Это то же правило, которое применяется отдельно к каждому компоненту матроида со знаком.) Схема матроида представляет собой либо положительный круг, либо пару отрицательных кругов, которые либо не пересекаются, либо имеют только общую вершину. Ранг множества ребер S равен n − c + ε, где c — количество компонентов S с учетом изолированных вершин, а ε равно 0, если S сбалансировано, и 1, если это не так.
Другие виды «подписанного графа» [ править ]
Иногда за знаки принимаются +1 и -1. Это всего лишь разница в обозначениях, если знаки по-прежнему умножаются по кругу и важен знак произведения. Однако есть два других способа обработки меток ребер, которые не вписываются в теорию знаковых графов.
Термин «подписной граф» иногда применяется к графам, в которых каждое ребро имеет вес w ( e ) = +1 или -1. Это разные знаковые графы; это взвешенные графы с ограниченным набором весов. Разница в том, что веса складываются, а не умножаются. Проблемы и методы совершенно разные.
Это название также применяется к графам, в которых знаки действуют как цвета на краях. Значение цвета состоит в том, что он определяет различные веса, приложенные к ребру, а не в том, что его знак имеет существенное значение. Так обстоит дело в теории узлов , где единственное значение знаков состоит в том, что они могут быть заменены группой из двух элементов, но нет внутренней разницы между положительными и отрицательными. Матроид графа со знаком цвета — это матроид цикла базового графа; это не каркас или лифт-матроид подписанного графа. Метки знаков вместо смены матроида становятся знаками элементов матроида.
В этой статье мы обсуждаем только теорию знаковых графов в строгом смысле этого слова. Для цветных графов см. цветные матроиды .
Подписанный орграф [ править ]
— Знаковый орграф это ориентированный граф со знаковыми дугами. Знаковые орграфы гораздо сложнее знаковых графов, поскольку значимы только знаки направленных циклов. Например, существует несколько определений баланса, каждое из которых трудно охарактеризовать, что сильно контрастирует с ситуацией для знаковых неориентированных графов.
Знаковые орграфы не следует путать с ориентированными знаковыми графами . Последние являются двунаправленными графами , а не ориентированными (за исключением тривиального случая всех положительных знаков).
Знаки вершин [ править ]
Знаковый граф , иногда называемый маркированным графом , — это граф, вершинам которого присвоены знаки. Круг называется последовательным (но это не имеет отношения к логической непротиворечивости) или гармоничным , если произведение знаков его вершин положительно, и несовместным или негармоничным , если произведение отрицательно. Не существует простой характеристики гармоничных графов со знаком вершин, аналогичной теореме о балансе Харари; вместо этого, характеристика была сложной проблемой, которую лучше всего решили (даже в более общем плане) Джоглекар, Шах и Диван (2012). [14]
Зачастую к теории знаков вершин легко добавить знаки ребер без серьезных изменений; таким образом, многие результаты для графов со знаком вершин (или «графов с помеченными знаками») естественным образом распространяются на графы со знаками вершин и ребер. Это особенно верно в отношении характеристики гармонии Джоглекара, Шаха и Дивана (2012).
Разница между помеченным знаковым графом и знаковым графом с функцией состояния (как в § Разочарование ) заключается в том, что знаки вершин в первом являются частью существенной структуры, тогда как функция состояния является переменной функцией на знаковом графе.
Заметим, что термин «маркированный граф» широко используется в сетях Петри совсем в другом значении; см. статью о размеченных графиках .
Раскраска [ править ]
Как и в случае с беззнаковыми графами , существует понятие раскраски знаковых графов. Если раскраска графа представляет собой отображение набора вершин в натуральные числа, то раскраска знакового графа представляет собой отображение набора вершин в целые числа.Ограничения на правильную раскраску исходят от ребер графа со знаком. Целые числа, присвоенные двум вершинам, должны быть различными, если они соединены положительным ребром. Метки на соседних вершинах не должны быть аддитивными обратными, если вершины соединены отрицательным ребром. Не может быть правильной раскраски знакового графа с положительной петлей.
При ограничении меток вершин набором целых чисел с величиной не более натурального числа k набор правильных раскрасок знакового графа конечен. Связь между числом таких собственных раскрасок и k является полиномом от k ; когда выражается в терминах он называется хроматическим многочленом знакового графа. Он аналогичен хроматическому многочлену беззнакового графа.
Приложения [ править ]
Социальная психология [ править ]
В социальной психологии подписанные графы использовались для моделирования социальных ситуаций, где положительные края представляют дружбу, а отрицательные — вражду между узлами, которые представляют людей. [3] Тогда, например, положительный 3-цикл – это либо три общих друга, либо два друга с общим врагом; тогда как отрицательный 3-цикл — это либо три общих врага, либо два врага, у которых есть общий друг. Согласно теории баланса , положительные циклы сбалансированы и считаются стабильными социальными ситуациями, тогда как отрицательные циклы несбалансированы и считаются нестабильными. Согласно теории, в случае трёх общих врагов это происходит потому, что наличие общего врага, скорее всего, приведет к тому, что двое из врагов станут друзьями . В случае, когда у двух врагов есть общий друг, общий друг, скорее всего, предпочтет одного другому и превратит одного из своих друзей во врага.
Антал, Крапивский и Редер рассматривают социальную динамику как смену знака на краю знакового графа. [15] Социальные отношения с предыдущими друзьями разводящейся пары используются для иллюстрации эволюции знакового графа в обществе. Другая иллюстрация описывает изменение международных союзов между европейскими державами за десятилетия до Первой мировой войны . Они рассматривают динамику локальных триад и динамику ограниченных триад, где в последнем случае изменение отношений происходит только тогда, когда общее количество несбалансированных триад уменьшается. Моделирование предполагало полный граф со случайными отношениями, имеющими случайную несбалансированную триаду, выбранную для преобразования. Эволюция подписанного графа с N узлами в этом процессе изучается и моделируется для описания стационарной плотности дружественных ссылок.
Теория баланса подверглась серьезному сомнению, особенно в ее применении к большим системам, на теоретическом основании, что дружеские отношения связывают общество вместе, в то время как общество, разделенное на два лагеря врагов, будет крайне нестабильным. [16] Экспериментальные исследования также дали лишь слабое подтверждение предсказаний теории структурного баланса. [17]
Спиновые очки [ править ]
В физике знаковые графики являются естественным контекстом для неферромагнитной модели Изинга , которая применяется для изучения спиновых стекол .
Сложные системы [ править ]
Используя аналитический метод, первоначально разработанный в популяционной биологии и экологии, но теперь используемый во многих научных дисциплинах, знаковые орграфы нашли применение в рассуждениях о поведении сложных причинных систем. [18] [19] Такой анализ отвечает на вопросы об обратной связи на заданных уровнях системы, а также о направлении переменных реакций при возмущении системы в одной или нескольких точках, переменных корреляциях при таких возмущениях, распределении дисперсии по системе и чувствительности или нечувствительность отдельных переменных к возмущениям системы.
Кластеризация данных [ править ]
Корреляционная кластеризация ищет естественную кластеризацию данных по сходству. Точки данных представлены в виде вершин графа с положительным ребром, соединяющим похожие элементы, и отрицательным ребром, соединяющим разнородные элементы.
Нейронаука [ править ]
Мозг можно рассматривать как знаковый граф, где синхронность и антисинхронность между моделями активности областей мозга определяют положительные и отрицательные края. В связи с этим можно изучить стабильность и энергию сети мозга. [20] Кроме того, недавно концепция фрустрации была использована в анализе мозговых сетей для выявления нетривиальной совокупности нейронных связей и выделения регулируемых элементов мозга. [21]
Обобщения [ править ]
Знаковый граф — это особый вид графа усиления , в котором группа усиления имеет порядок 2. Пара ( G , B (Σ)) определяемая знаковым графом Σ, представляет собой особый вид смещенного графа . Группа знаков обладает особым свойством, не свойственным более крупным группам усиления, заключающимся в том, что знаки ребер определяются до переключения набором B (Σ) сбалансированных циклов. [22]
Примечания [ править ]
- ↑ Перейти обратно: Перейти обратно: а б Харари, Фрэнк (1955), «О понятии баланса знакового графа» , Michigan Mathematical Journal , 2 : 143–146, MR 0067468 , заархивировано из оригинала 15 апреля 2013 г.
- ^ Кениг, Денес (1936), Akademische Verlagsgesellschaft (редактор), Теория конечных и бесконечных графов
- ↑ Перейти обратно: Перейти обратно: а б Картрайт, Д.; Харари, Фрэнк (1956). «Структурный баланс: обобщение теории Хайдера» (PDF) . Психологический обзор . 63 (5): 277–293. дои : 10.1037/h0046049 . ПМИД 13359597 .
- ↑ Стивен Строгац (2010), Враг моего врага , The New York Times , 14 февраля 2010 г.
- ^ Заславский, Томас (1998), «Математическая библиография графов знаков и коэффициентов усиления и родственных областей» , Электронный журнал комбинаторики , 5 , Dynamic Surveys 8, 124 стр., MR 1744869 .
- ^ Лекция Луиса фон Ана «Наука Интернета» 3 стр. 28
- ↑ Перейти обратно: Перейти обратно: а б Харари, Франк (1959), Об измерении структурного баланса, Поведенческая наука 4, 316–323.
- ^ Роберт П. Абельсон; Милтон Дж. Розенберг (1958), Символическая психология: модель установочного познания, Поведенческая наука 3, 1–13.
- ^ Ареф, Самин; Мейсон, Эндрю Дж.; Уилсон, Марк К. (2019). «Моделирование и вычислительное исследование индекса разочарования в подписанных сетях». arXiv : 1611.09030 [ cs.SI ].
- ^ Ареф, Самин; Мейсон, Эндрю Дж.; Уилсон, Марк К. (2018), Голденгорин, Борис (редактор), «Вычисление линейного индекса баланса с использованием оптимизации целочисленного программирования», Проблемы оптимизации в теории графов: в честь 60-летия Григория З. Гутина , оптимизация Спрингера и ее Приложения, Springer International Publishing, стр. 65–84, arXiv : 1710.09876 , doi : 10.1007/978-3-319-94830-0_3 , ISBN 9783319948300 , S2CID 27936778
- ^ Ареф, Самин; Уилсон, Марк С. (01 апреля 2019 г.). Эстрада, Эрнесто (ред.). «Баланс и разочарование в подписанных сетях». Журнал сложных сетей . 7 (2): 163–189. arXiv : 1712.04628 . дои : 10.1093/comnet/cny015 . ISSN 2051-1329 .
- ^ Гюльпинар, Н.; Гутин Г. ; Митра, Г.; Зверович, А. (2004). «Извлечение чистых сетевых подматриц в линейных программах с использованием знаковых графов». Дискретное приложение. Математика. 137 (3): 359–372. дои : 10.1016/S0166-218X(03)00361-5 .
- ^ Заславский, Томас (1982), «Знаковые графики», Дискретная прикладная математика , 4 (1): 47–74, doi : 10.1016/0166-218X(82)90033-6 , hdl : 10338.dmlcz/127957 , MR 0676405 . Ошибка. Дискретная прикладная математика , 5 (1983), 248
- ^ Манас Джоглекар, Нисарг Шах и Аджит А. Диван (2012), «Графы с метками сбалансированной группы», Дискретная математика , том. 312, нет. 9, стр. 1542–1549.
- ^ Т. Антал, П. Л. Крапивский и С. Реднер (2006) Социальный баланс в сетях: динамика дружбы и вражды
- ^ Б. Андерсон, «Перспективы исследования социальных сетей» , изд. П.В. Холланд и С. Лейнхардт. Нью-Йорк: Академик Пресс, 1979.
- ^ Морриссетт, Джулиан О.; Янке, Джон К. (1967). «Нет отношений и отношений нулевой силы в теории структурного баланса». Человеческие отношения . 20 (2): 189–195. дои : 10.1177/001872676702000207 . S2CID 143210382 .
- ^ Пучча, Чарльз Дж. и Левинс, Ричард (1986). Качественное моделирование сложных систем: введение в циклический анализ и усреднение по времени . Издательство Гарвардского университета, Кембридж, Массачусетс.
- ^ Дамбахер, Джеффри М.; Ли, Хирам В.; Россиньоль, Филипп А. (2002). «Значение структуры сообщества для оценки неопределенности экологических прогнозов». Экология . 83 (5): 1372–1385. doi : 10.1890/0012-9658(2002)083[1372:rocsia]2.0.co;2 . JSTOR 3071950 .
- ^ Сабери М., Хосровабади Р., Хатиби А., Мисич Б., Джафари Г. (январь 2021 г.). «Топологическое влияние отрицательных связей на стабильность сети мозга в состоянии покоя» . Научные отчеты . 11 (1): 2176. Бибкод : 2021NatSR..11.2176S . дои : 10.1038/s41598-021-81767-7 . ПМЦ 7838299 . ПМИД 33500525 .
- ^ Сабери М., Хосровабади Р., Хатиби А., Мисич Б., Джафари Г. (октябрь 2022 г.). «Закономерность формирования фрустрации в функциональной сети мозга» . Сетевая нейронаука . 6 (4): 1334–1356. дои : 10.1162/netn_a_00268 .
- ^ Заславский, Томас (1981). «Характеристика знаковых графов». Журнал теории графов . 5 (4): 401–406. дои : 10.1002/jgt.3190050409 .
Ссылки [ править ]
- Картрайт, Д.; Харари, Ф. (1956), «Структурный баланс: обобщение теории Хайдера», Psychoological Review , 63 (5): 277–293, doi : 10.1037/h0046049 , PMID 13359597 .
- Зайдель, Дж. Дж. (1976), «Обзор двух графов», Международный коллоквиум по комбинаторным теориям (Рим, 1973), Том I , Труды конференций Линчеи, том. 17, Рим: Национальная академия Линчеи , стр. 481–511, МР 0550136 .
- Заславский, Томас (1998), «Математическая библиография графов знаков и коэффициентов усиления и родственных областей» , Электронный журнал комбинаторики , 5 , Dynamic Surveys 8, 124 стр., MR 1744869