Social Balance on Networks Local Minima and Best Edge Dynamics Krishnendu Chatterjee Jakub Svoboda and Ðorđe Žikelić IST Austria Am Campus 1 3400 Klosterneuburg Austria

2025-05-03 0 0 1.79MB 13 页 10玖币

侵权投诉

Social Balance on Networks: Local Minima and Best Edge Dynamics

Krishnendu Chatterjee, Jakub Svoboda, and Ðorđe Žikelić

IST Austria, Am Campus 1, 3400 Klosterneuburg, Austria

Andreas Pavlogiannis

Department of Computer Science, Aarhus University, Aabogade 34, 8200 Aarhus, Denmark

Josef Tkadlec

Department of Mathematics, Harvard University, Cambridge, MA 02138, USA

Structural balance theory is an established framework for studying social relationships of friend-

ship and enmity. These relationships are modeled by a signed network whose energy potential

measures the level of imbalance, while stochastic dynamics drives the network towards a state of

minimum energy that captures social balance. It is known that this energy landscape has local

minima that can trap socially-aware dynamics, preventing it from reaching balance. Here we ﬁrst

study the robustness and attractor properties of these local minima. We show that a stochastic

process can reach them from an abundance of initial states, and that some local minima cannot be

escaped by mild perturbations of the network. Motivated by these anomalies, we introduce Best

Edge Dynamics (BED), a new plausible stochastic process. We prove that BED always reaches

balance, and that it does so fast in various interesting settings.

I. INTRODUCTION

The formation of social relationships is a complex pro-

cess that has long fascinated researchers. It is well-

understood that, besides pairwise interactions, friend-

ships and rivalries are aﬀected by social context. The

study of such phenomena dates back to Heider’s theory

of social balance [1–3], which can be seen as a rigorous

realization of the proverb “the enemy of my enemy is my

friend”. The theory classiﬁes a social state as balanced

whenever every group of three entities (a triad ) is bal-

anced: it consists of either three mutual friendships, or

one friendship whose both parties have a mutual enemy.

The other types of triads create social unrest that even-

tually gets resolved by changing the relationship between

two parties. For example, a triad with three mutual en-

mities will eventually lead to two entities forming an al-

liance against the common enemy. A triad with exactly

one enmity will either see a reconciliation to a friendship

under the uniting inﬂuence of the common friend, or lead

to the break of one friendship following the social axiom

“the friend of my enemy is my enemy” [4].

Cartwright and Harary developed a graph-theoretic

model of Heider’s theory [5], and showed that any bal-

anced state is either a utopia without any enmities, or it

consist of two mutually antagonistic groups [6, 7]. This

structural theory of social balance has seen applications

across various ﬁelds ranging from philosophy, sociology,

or political science [8–12] all the way to ﬁelds such as neu-

roscience or computer science [13–16], It has also been

supported by empirical evidence [17–19], see also [20]

for a review. The setting is attractive to physicists due

to its intimate connection to the Ising model and spin

glasses [21], and indeed tools and techniques from statis-

tical physics have proved to be instrumental in improving

our understanding of such systems [22–24], see also [25]

for a review.

It is natural to associate each network state with

apotential energy that counts the diﬀerence of imbal-

anced minus balanced triads; hence the perfectly bal-

anced states are those that minimize the energy of the

network [26]. Understanding how energy is minimized

in a system is a fundamental problem studied across dif-

ferent physics ﬁelds, and signed graphs present a clean

theoretical framework to study this problem in a setting

with a population structure. It is well known that the en-

ergy landscape over signed graphs has local minima (also

known as jammed states) [27], that is, states from which

all paths to social balance must temporarily increase the

number of imbalanced triads.

When the network state is imbalanced, we expect that

a social process will perturb it until balance is reached.

The seminal work [28] introduced a stochastic process

known as Local Triad Dynamics (LTD), according to

which imbalanced triads are sampled at random, and the

sampled triad is balanced by ﬂipping the relationship of

two of its entities. This step is called an edge ﬂip. The

same work also introduced Constrained Triad Dynam-

ics (CTD), a socially-aware variant of LTD under which

an edge ﬂip is only possible if it reduces the number of

imbalanced triads. Unfortunately, the existence of local

minima in the energy landscape implies that CTD can

get stuck in jammed states and thus remain permanently

imbalanced.

Although the existence of jammed states is well under-

stood in terms of the energy landscape, little is known

about them from the perspective of the stochastic pro-

cess, that is, about their reachability properties. For ex-

ample, from which initial states is it possible to reach a

jammed state? Moreover, if a jammed state is reached,

can the process escape if we slightly perturb the network?

Finally, is there a plausible, socially-aware stochastic dy-

namics (like CTD) that always reaches balance (unlike

arXiv:2210.02394v1 [cs.SI] 5 Oct 2022

CTD)? We tackle these questions in this work.

First, we study the robustness and attractor properties

of the local minima of the energy landscape. We show

that the number of jammed states is super-exponential,

compared to the previously known exponential lower-

bound, and that jammed states are reachable from any

initial state that is not too friendship-dense. Moreover,

we show that some of those jammed states are strongly

attracting: even when perturbing a constant portion of

edges adjacent to each vertex, the same jammed state is

subsequently reached with probability 1. As a byproduct,

our results resolve an open problem from [26].

Second, we propose a new plausible dynamics called

Best Edge Dynamics (BED). Like CTD, BED is a

stochastic process in which edge ﬂips are socially-aware,

in the sense that they maximize the number of newly

balanced triads (see below for details). We prove that,

unlike CTD, BED always reaches a balanced state from

any initial state. Moreover, we show that BED converges

faster to a balanced state than CTD in various interest-

ing settings, such as when started from a state that is

already close to being balanced.

Finally, we complement our analytical results with

computer simulations in the cases when the initial friend-

ship edges form a random Erdős-Rényi network or a ran-

dom scale-free networks.

II. TRIAD DYNAMICS IN SOCIAL

NETWORKS

Balance on social networks is studied in terms of signed

graphs. A signed graph G= (V, E, s)consists of a ﬁnite

complete graph (V, E)on |V|=nvertices together with

an edge labeling

s:E→ {−1,+1}.

The labeling sassigns to each edge one of the two signs;

the edges labeled by +1 are friendships and those labeled

−1are enmities. Thus each pair of individuals (modeled

by vertices) has a deﬁned relationship: either they are

friends, or they are enemies.

Given a signed graph G= (V, E, s), a triad is a sub-

graph of Gdeﬁned by any three of its vertices. A triad is

of type ∆kfor k= 0,1,2,3if it contains exactly kedges

labeled −1. A triad is balanced if its type is ∆0or ∆2.

Intuitively, a triad is balanced if it satisﬁes the known

proverb “the enemy of my enemy is my friend”. For an

edge ein G, its rank reis the number of imbalanced tri-

ads containing e. Finally, a signed graph Gis balanced if

each triad in Gis balanced, see Fig. 1.

It is known that a signed graph is balanced if and only

if its enmity edges form a complete bipartite graph over

the vertex set [5]. This means that we may partition

the vertices of a balanced signed graph into two vertex

classes, such that all pairs of vertices from the same class

form friendship edges, and all pairs of vertices from dif-

ferent classes form enmity edges. Moreover, every signed

Balanced triads

Imbalanced triads

ﬂip

re= 1

friends

∆0

∆2

friends

enemies

∆1

∆3

Triangle dynamics

Edge rank

FIG. 1. A triad of type ∆kcontains kenmity edges. The im-

balanced triads ∆1and ∆3can be made balanced by ﬂipping

any one edge. A sequence of ﬂips typically reaches a state

where all triads are balanced. The rank reof edge eis the

number of imbalanced triads containing e.

graph which admits such a partitioning is clearly bal-

anced. In the special case where one of the vertex classes

in this partitioning is empty, each pair of vertices forms

a friendship edge and we refer to this balanced signed

graph as utopia.

The main interest in the study of social networks mod-

eled by signed graphs is the evolution of the network

according to some pre-speciﬁed dynamics, and the time

until the balance is reached. The goal is to understand

which simple dynamics ensure fast convergence to bal-

ance. Following the work of [28], we focus on those dy-

namics that, at each time step, select one edge eaccord-

ing to some rule and then ﬂip its sign. We then say

that “eis ﬂipped”. In [28], two such dynamics on signed

graphs were introduced: Local Triad Dynamics (LTD),

and Constrained Triad Dynamics (CTD). In the rest of

this section, we deﬁne these two dynamics and discuss

their advantages and limitations.

A. Local Triad Dynamics

Let Gbe a signed graph modeling a social network

with friendships and enmities.

The Local Triad Dynamics (LTD) with parameter p∈

[0,1] is a discrete-time random process that starts in G

and repeats the following procedure until there are no

imbalanced triads in G:

1. Select an imbalanced triad ∆uniformly at random.

2. If ∆is of type ∆3, then an edge of Tis chosen to

be ﬂipped uniformly at random. If ∆is of type ∆1,

then the unique edge with sign −1is chosen to be

ﬂipped with probability pand each of the two other

edges is chosen with probability 1−p

We refer to distinct signed graphs as states.

LTD is socially oblivious in the sense that once an im-

balanced triad is selected, the edge to be ﬂipped is cho-

sen according to a (stochastic) rule that disregards the

rest of the network. Moreover, the guarantees of LTD

on the expected time to reach a balanced state are not

very plausible: it was shown in [28] that if p < 1

2, then

the expected time grows exponentially with the size of

the signed graph. On the other hand, if p > 1

2, then

the dynamics is more likely to create rather than remove

friendships and it reaches utopia with high probability.

This means that the eventual balanced state is essentially

pre-determined.

B. Constrained Triad Dynamics

The Constrained Triad Dynamics (CTD) is another

dynamics on signed graphs. Given a signed graph Gon

nvertices, CTD is a random process that starts in G

and repeats the following procedure until there are no

imbalanced triads in G:

1. Select an imbalanced triad ∆uniformly at random.

2. Select an edge eof ∆uniformly at random.

3. Flip eif re≥1

2n−1, that is, if the number of

imbalanced triads in Gdoes not increase upon the

ﬂip (in the case of equality, the ﬂip happens with

probability 1/2), otherwise do nothing.

Note that CTD introduces a non-local, socially-aware

rule: When deciding whether a selected edge should be

ﬂipped, we take into account all triads that contain it.

In [28] it was claimed that, starting from any initial

signed graph G, CTD converges to a balanced state and

that balance is reached fast – in a time that scales loga-

rithmically with the size nof the signed graph. If true,

this would imply that CTD overcomes the limitation of

LTD in which the expected convergence time could be

exponential in n. However the claim, which was sup-

ported by an informal argument, is not quite true, since

the energy landscape is rugged: There are states, called

jammed states, that are not balanced but where CTD can

not make a move, since any ﬂip would (temporarily) in-

crease the number of imbalanced triads [27]. Moreover, it

is known that there are at least roughly 3njammed states

(compared to roughly 2nbalanced states) and that some

of the jammed states have zero energy [26].

III. REACHING AND ESCAPING THE

JAMMED STATES

Even though there are exponentially many jammed

states, computer simulations on small populations were

used to suggest that they can eﬀectively be ignored [27].

In contrast, in this section we present three results which

indicate that for large population sizes the jammed states

are important.

First (“counting”), we study the number of jammed

states. It is known [27], that there are at least 3njammed

states, that is, at least exponentially many. Here we con-

struct a family of simple, previously unreported jammed

states and we show that the total number of jammed

states on nlabeled vertices is super-exponential, namely

at least 2Ω(nlog n). This shows that even on the loga-

rithmic scale, the jammed states are substantially more

numerous than the balanced states (of which there are

“only” 2n−1).

Our second result (“reaching”) shows that, starting

from any initial signed graph that is not too friendship-

dense, a speciﬁc jammed state J, which we construct

below, is reached with positive probability. In partic-

ular this implies that the expected time to balance in

this stochastic process is formally inﬁnite, even for signed

graphs that have a constant positive density of friendship

edges.

Our third result (“escaping”) shows that this speciﬁc

jammed state Jforms a deep well in the energy land-

scape: Once it is reached, it can not be escaped even if

we perturb a constant portion of edges incident to each

vertex.

In the rest of this section, we sketch the intuition be-

hind these results. For the formal statements and proofs,

see Theorems 2 to 4 in Appendix A, respectively.

Regarding the ﬁrst result (“counting”), the new

jammed states are deﬁned in terms of an integer param-

eter d. We partition the population into 4d+ 2 clusters

(4d+ 1 or 4d+ 3 would work too), arrange the clus-

ters along a circle, and assign a sign +1 to those (and

only those) edges that connect individuals who live in

clusters that are at most dsteps apart, see Fig. 2. We

then show that, for each friendship or enmity edge (u, v),

a strict majority 2(d+ 1) >1

2(4d+ 3) of clusters have

the property that any vertex win that cluster forms a

balanced triad (u, v, w)with (u, v). Thus, ﬂipping (u, v)

would increase the number of imbalanced triads. When

all the clusters are roughly equal in size, which is the

typical behavior for large population sizes, the state is

thus jammed. Our construction also resolves in aﬃrma-

tive an open question [26] which asks whether there exist

jammed states with an even number of friendship cliques

(here this number is 4d+ 2).

d+ 1

FIG. 2. A jammed state consisting of 4d+ 2 roughly equal

clusters, each connected by friendships to the clusters at most

dsteps apart.

Regarding the second result (“reaching”), we consider

any initial state Inon nvertices in which each vertex

is incident to at most n/12 −1edges labeled +1. We

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

SocialBalanceonNetworks:LocalMinimaandBestEdgeDynamicsKrishnenduChatterjee,JakubSvoboda,andÐoreikeli¢ISTAustria,AmCampus1,3400Klosterneuburg,AustriaAndreasPavlogiannisDepartmentofComputerScience,AarhusUniversity,Aabogade34,8200Aarhus,DenmarkJosefTkadlecDepartmentofMathematics,HarvardUniversity,Cam...

展开>> 收起<<

Social Balance on Networks Local Minima and Best Edge Dynamics Krishnendu Chatterjee Jakub Svoboda and Ðorđe Žikelić IST Austria Am Campus 1 3400 Klosterneuburg Austria.pdf

共13页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Social Balance on Networks Local Minima and Best Edge Dynamics Krishnendu Chatterjee Jakub Svoboda and Ðorđe Žikelić IST Austria Am Campus 1 3400 Klosterneuburg Austria

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: