Conflict Cascades and Self-Organized Criticality in Dynamic Networks
Table of contents
Share
Metrics
Conflict Cascades and Self-Organized Criticality in Dynamic Networks
Annotation
PII
S207751800000076-2-1
Publication type
Article
Статус публикации
Published
Authors
Maxim Tsvetovat 
Affiliation: Center for Social Complexity, George Mason University
Address: United States,
Mark Rouleau
Affiliation: Assistant Professor, Computational Social Science, George Mason University
Address: United States,
Abstract
The complexity of human social structures often masks the simplicity involved in their development. Social networks are a product of dynamic processes and feedback. In other words, the ties that people make affect the topology of a network and the form of a network affects the ties that people make. Therefore, social network structure evolves in a path-dependent manner. In this paper, we begin to sift through the complexity of social network ties in an effort to unearth the fundamental rules of social interaction and their impact on network formation and evolution.
Keywords
dynamic networks, conflict cascades, self-organized criticality, social structures, social networks
Received
18.04.2008
Date of publication
30.05.2008
Number of purchasers
2
Views
1408
Readers community rating
0.0 (0 votes)
Cite Download pdf

To download PDF you should sign in

1

1. Введение

2

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

3

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

4

Рассмотренный выше пример является иллюстрацией нескольких моментов. Во-первых, это возможность изменения структуры сети (в особенности изменения разрушительной природы) и распространения как сеть, с оказанием потенциального влияния на большое количество людей. Во-вторых, сеть качественно по-разному реагирует на добавление и устранение ребер, в зависимости от фазы изменения их плотности (Newman, Barabasi, Watts, 2006). В-третьих, в реальности наблюдается (Kumar, Novak, Tomkins, 2006) склонность сетей останавливаться при определенной плотности, что становится индикатором существования динамического равновесия (Leskovec, Faloutsos, 2005). Наша гипотеза состоит в том, что конфликты играют регулирующую роль в социальных сетях и помогают установить и поддерживать это динамическое равновесие. Большое количество исследований (Tsvetovat, Carley, 2005), (Frantz, Carley, 2005), (Roth, 2005) посвящено этому генерирующему процессу создания сетей. Такие процессы варьируют от чисто случайных моделей (Erdos, Renyi, 1960) до генерирования малых сетей (Watts, Strogatz, 1998) и внемасштабных сетей (Albert, Barabasi, 2002). Методы создания сетей и результаты исследований различаются, однако у всех методов есть одно общее свойство: они рассматривают лишь процессы, которые добавляют или изменяют ребра в сети. Хотя с теоретической точки зрения вполне корректно иметь дело с процессами, генерирующими гигантские компонентные сети, в реальных сетях ответственные за их формирование силы в значительной степени ослаблены неизвестными противостоящими процессами. Так как генерирующая и противостоящая силы стремятся балансировать друг друга, система приходит к определенному динамическому равновесию и продолжает колебаться вокруг него. В данной работе нам хотелось бы остановиться на роли деструктивных процессов, таких как исчезновение связей и открытый конфликт, имеющих одинаково важное влияние на сетевую топологию.

5

Мы строим простую агент-ориентированную модель для изучения сложности сетевых структур и влияния конфликтов на эти структуры. Объектом нашего научного интереса становятся микроуровневые механизмы, порождающие наблюдаемые в реальности макроуровневые процессы. Законы на уровне агентов основаны на теории структурного баланса (Doreian, Kapuscinski, Krackhardt, Szczypula, 1996), восходящей к теории баланса Хейдера (Heider, 1979). Теория баланса предполагает, что с индивидуальной точки зрения, люди имеют склонность к балансу. Несбалансированные структуры возникают в случае, когда исходные индивиды ощущают диссонанс между последствиями их собственных действий и действий других людей. Реакцией на этот диссонанс становится изменение агентом своих действий, и таким образом, изменение и всей структуры сети.

6

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

7

Реакцией агентов на изменения их дружеских привязанностей и на конфликты становится набор простых правил триадного взаимодействия:

8

Правило 1 Друг моего друга – мой друг (связи Симмелиана (Krackhardt, 1999))

9

Правило 2A Враг моего друга – мой враг (социальный баланс (Doreian, Kapuscinski, Krackhardt, Szczypula, 1996))

10

Правило 2B Друг моего врага – мой враг

11

Правило 2C Враг моего врага – мой друг

12

Правила 2A, 2B и 2C в действительности представляют ту же самую сбалансированную триаду, содержащую две конфликтные связи и одну дружескую – с единственной разницей в идентификации узла, отвечающего за правило. Так, поведение агента может упрощенно передаваться следующим образом:

13

Каждый узел стремиться быть вовлеченным в сбалансированные триады, которые либо полностью связаны – триады Симмелиана (Правило 1), либо конфликтно связаны (Правило 2).

14

2. Симуляционная модель

15

Для изучения плотности сетей нами была создана простая вычислительная модель: агент-ориентированная версия сильно упрощенной социальной сети. Модель становится средством для осуществления экспериментов при действии вышеописанных четырех «социальных правил».

16

Базовая модель состоит из статичного набора 100 агентов с Пуассоновым распределением. Изначально, ребра добавляются случайным образом, создавая случайным граф Эрдоса (Erdos, Renyi, 1960), с плотностью, линейно растущей пропорционально вероятности добавления ребра.

17

2.1. Фазовый переход от линейного к экспоненциальному росту.

18

В сам момент активации агенты запускают и пытаются закрыть все пронизывающие сеть открытые триады (т.е. «Друг моего друга – мой друг»). С увеличением плотности возрастающее количество триад «друг-не друг» начинает присоединяться к сбалансированным триадам и рост плотности сети ускоряется драматическим образом.

19

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

20

Рис. 1. Рост сети (a) в отсутствии и (b) присутствии конфликтов. (a) Рост сетевой плотности при режиме Правила 1 (отсутствие конфликта)

21

b) Рост сети при одновременном действии Правила 1 и Правила 2

22

2.2. Развитие конфликта

23

Конфликт вводится в сеть как постоянная вероятность, с которой одна дружеская связь изменяется на вражескую. Происходящие затем события отражены на рис. 2. В этом простом примере, состоящая из 4 закрытых триад сеть подвергается конфликту со стороны одного ребра. Триада A – B – C становится несбалансированной, в связи с конфликтом между B и C; таким образом, A вынужден принять чью-либо сторону в конфликте, оставаясь случайным образом либо с B либо C. Добавление конфликта к ребру A – C вызывает дисбаланс другой триады А – С – D. Таким образом, и агент D вовлекается в конфликт.

24

Если агент D затем решает изолировать C от остальной сети, то развитие конфликта может быть остановлено. Однако, если же он в этом случае отделяется от А, это приводит к дальнейшему развитию конфликта и разрушению большего количества связей. Чем больше у агента связей, тем выше вероятность формирования новых связей; однако тем также выше и вероятность того, что конфликт между двумя агентами распространится по всей сети. Таким образом, проникновение в сеть и дружбы и конфликта находится в зависимости от плотности и времени возникновения связей между агентами.

25

Рис. 2. Развитие конфликтов в плотной сети

26

Таблица 1 Значения параметров плотности сети

Параметр Эксперимент
A B C
Вероятность приобретения новых друзей 0.90 0.33 0.50
Вероятность встреч друзей друзей 0.90 0.33 0.50
Вероятность давать оценку дружбе 0.90 0.10 0.10
Вероятность конфликта 0.01 0.01 0.01
Вероятность угасания конфликта 1.00 0.75 0.50
Вероятность разрушения дружбы 0.00 0.75 0.50
27

3. Вычислительный эксперимент

28

Созданная модель позволяет проводить эксперименты с набором вероятностных параметров дружбы и конфликта: 1) вероятность приобретения новых друзей, 2) вероятность встречи друзей своих друзей, 3) вероятность возникновения конфликта между самим агентом и одним из его друзей и 4) вероятность возникновения необходимости давать оценку (пересматривать) свои нынешние дружеские связи из-за возникновения конфликта между друзьями.

29

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

30

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

31

Рис. 3. Развитие конфликта в сети – влияние на плотность и распределение степеней. (a) Распределение узловой степени до проникновения в сеть малого конфликта

32

(b) Распределение узловой степени до проникновения в сеть от среднего до большого конфликта

33

(c) Распределение узловой степени после в сеть крупного конфликта

34

3.1. Анализ чувствительности

35

После введения концепции проникновения конфликта и фазового перехода можно проводить эксперименты в отношении условий, необходимых для генерирования реалистичного развития конфликта и реалистичных сетевых структур как следствия этого развития конфликта. В продемонстрированных выше результатах на рис. 3-4, можно обнаружить 2 важные реалистичные черты присутствующей при этом процессе сетевой эволюции. Во-первых, наблюдается степенное правило в распределении узлов дружеских связей в ходе всего эксперимента, за исключением периодов в преддверии и сразу же после крупного конфликта. Во-вторых, можно отметить постоянную точку критической плотности. При достижении этой точки, сеть приходит к динамическому равновесию, в котором сбалансированы возникновение новых дружеских связей и продолжающиеся конфликты.

36

Рис. 4. Типичный вид низкоконфликтной фазы

37

Как видно из рис.3.1а, существует критическая точка со значением около 0.10, которую можно наблюдать при различных установках параметров. Рис. 3.1 демонстрирует похожий результат для более слабой вариации дружеских связей, более высоких вероятностей дружбы и более низких вероятностей разрушения. Поэтому эти два результата показывают, что реалистичное проникновение конфликта вполне может развиваться в рамках нашей модели при условиях, которые эмпирически также достаточно реалистичны.

38

Рис. 5. Стабильная сетевая плотность при реалистичных значениях параметров

39

4. Заключение

40

В данной работе была продемонстрирована методология простой агент-ориентированной модели, интегрирующей деструктивные процессы (конфликты) в механизм сетевой эволюции.

41

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

42

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

43

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