Structural Balance Considerations for Networks with Preference Orders as Node Attributes Olle Abrahamsson Danyo Danev and Erik G. Larsson

2025-05-02 0 0 456.67KB 7 页 10玖币

侵权投诉

Structural Balance Considerations for Networks

with Preference Orders as Node Attributes

Olle Abrahamsson, Danyo Danev and Erik G. Larsson

Dept. of Electrical Engineering (ISY),

Link¨

oping University, 58183 Link¨

oping, Sweden

Email: {olle.abrahamsson, danyo.danev, erik.g.larsson}@liu.se

Abstract—We discuss possible deﬁnitions of structural balance

conditions in a network with preference orderings as node

attributes. The main result is that for the case with three

alternatives (A, B, C) we reduce the (3!)3= 216 possible

conﬁgurations of triangles to 10 equivalence classes, and use these

as measures of balance of a triangle towards possible extensions

of structural balance theory. Moreover, we derive a general

formula for the number of equivalent classes for preferences

on nalternatives. Finally, we analyze a real-world data set and

compare its empirical distribution of triangle equivalence classes

to a null hypothesis in which preferences are randomly assigned

to the nodes.

I. INTRODUCTION

In network science, nodes and edges may be associated

with attributes that encode various properties. An important

example of a node attribute is when each node is assigned a

particular type. Various homophily measures, with modularity

as the most important example [1], are then available to quan-

tify whether edges between nodes of the same type are more

prevalent than edges between nodes of different types. Edge

attributes may consist of, for example, a weight that describes

how strongly two nodes are connected, or a sign (+/−) that

determines whether the the relation between two nodes is

friendly or antagonistic. For complete networks with signed

edges, a celebrated result is the structural balance theorem

[2]. This theorem states that if every triangle in a (complete)

network has the signs either +++ or +−−, then the network

can be partitioned into two subnetworks Aand B, such that

all edges within Aare +, all edges within Bare +, but all

edges between Aand Bare −(as illustrated in Figure 1). The

network is then said to be balanced. The popular interpretation

is that the “enemy’s enemy is a friend”: in a balanced network

either all three nodes in every triangle are friends, or two team

up against a third, common, enemy. Thus, in signed networks

balance means polarization, i.e., there are two camps of friends

with mutual antagonism between them.

In this paper we are concerned with extensions of the

structural balance concept that go beyond signed networks.

Speciﬁcally we consider networks where nodes have pref-

erence orderings as attributes. A preference ordering is de-

This work was supported in part by ELLIIT and the KAW foundation.

v3v4

− −

Fig. 1. A balanced network with subnetworks A, induced by the nodes v1

and v2, and B, induced by v3and v4. All edges within Aand Bhave positive

signs, but the edges between Aand Bhave negative signs.

ﬁned in terms of a strict linear order of alternatives (e.g.,

ABC) and may be interpreted as an expression

of the opinion that Ais preferable to B, which in turn is

preferable to C, and so on. The extent to which two neighbors’

preference orderings differ can be viewed as a measure of

agreement or disagreement. In the extreme cases when a pair

of neighbors have the exact same preferences or maximally

different preferences (e.g., according to some distance metric),

it would be quite natural to associate their edge with a +

or −, respectively. In the case of partial disagreement, one

could either extend the number of edge weights or argue for

a way to project the partial disagreements onto the two signs

+/−. In view of this intuitive connection between preference

orderings as node attributes and signed edges, one might ask a

more general question: Can triangles of nodes with preference

orderings as node attributes be associated with a notion of

balance? We approach, and partially answer this question by

enumerating all possible combinations of preference orderings

that can appear in a triangle, and categorize them into classes

that are equivalent in a certain sense.

A. Related Work

1) Preference Orderings as Node Attributes: The motiva-

tion for studying networks with preference orderings is clear.

For example, it is reported in the literature that the use of pref-

erence orderings to express opinions is superior to the use of

numerical scores [3], [4]. In the ﬁeld of collaborative ﬁltering-

based recommender systems, several papers have leveraged on

arXiv:2210.01858v1 [cs.SI] 4 Oct 2022

users’ preference orderings data [5]–[7], and in social choice

theory, an important problem is how to aggregate preference

orderings in a group of people [8], with applications in the

design of voting methods and ethical AI systems [9].

Yet, only scattered results are available in the literature

on networks with preference orderings as node attributes. In

[4], opinion diffusion processes were considered and it was

concluded that the outcome of a diffusion process depends

both on the structure of the social network (e.g., directed

or undirected; cyclic or acyclic) and on the properties of

the initial preferences of each agent, for example whether

the initial preference proﬁles satisfy the Condorcet condition

or not. In [10] (with results reﬁned in [11]), preference

aggregation via a form of “emphatic” voting was considered,

taking into account the connections between nodes in addition

to their opinions in the aggregation. In [12], two closely

related problems were tackled: Preference inference and group

recommendation based on partially observed ranking data.

The main idea was to utilize the underlying social network

structure under the assumption that the homophily and/or

social inﬂuence shapes the network dynamics. The proposed

models were tested empirically on several data sets, one of

which was the Flixter data set [13], consisting of a social

network of movie watchers and their ratings of movies. Based

on the ratings for each user, the relative number of movies

of each genre watched by a speciﬁc user was calculated, and

from these so-called user-genre scores, ranking data of movie

genres was constructed. However, due to the sparsity typical

of movie ratings, only partial orders could be constructed in

a this manner. Finally, in [14], two models were proposed for

capturing how preferences are distributed among nodes in a

typical social network. By sampling a small subset of represen-

tative nodes, the algorithms can harness the network structure

to effectively construct an aggregate preference of the entire

network population, and for preferences related to personal

topics (such as lifestyle choices), the proposed approach was

shown to be advantageous over traditional random polling. The

said papers also connect to the (relatively rich) literature on

preference aggregation and voting theory. However, network

aspects seem to be rarely considered in that context, and we

are only aware of [10]–[12] and [14].

2) Structural Balance: The discovery of the structural

balance theorem in 1956 [2] has spawned a large literature on

empirical analysis of real-world networks [15]–[18], analysis

of dynamic processes [19], [20], partially balanced networks

[21], and perhaps most importantly in the current context,

extensions to cases beyond the canonical signed-link +/−

setup. The most representative extensions are [22] and [23].

In [22], the edge weights can be any real number drawn from

a total ordering. A distance metric is deﬁned such that the

negative (positive) are mapped to large (small) distances. A

triangle is then said to be structurally balanced if the three

distances involved satisfy the metric triangle inequality. In

[23], the authors considered signed digraphs and redeﬁne

structural balance as a local node property: A node is called

structurally balanced if a ceratin subgraph related to the node

can be bipartitioned such that all directed edges within a

partition have non-negative weights, and all directed edges

between partitions have non-positive weights.

Another interesting direction of research is the generaliza-

tion of structural balance in networks with node attributes. For

example, in [24], the authors deﬁned balance in fully signed

networks, i.e., networks where both the edges and the nodes

have signs. Such a network is then said to be balanced if

and only if it can be partitioned into clusters, within which

nodes have identical attributes and all edges are negative. The

authors provide an energy function whose minimum is taken

as a measure of partial network balance, and they also propose

an algorithm for the efﬁcient computation of this value. In [25]

the method was further generalized to fully signed networks

in which the number of attributes for each node is arbitrary

(that is, not only +or −).

However, none of the existing literature on balance, to our

knowledge, has dealt with networks with preference orderings

as attributes.

B. Contributions

In this paper we discuss possible deﬁnitions of structural

balance in a network with preference orderings as node

attributes. The main result (Theorem 1) is that for the three-

alternative case (A, B, C) we reduce the (3!)3= 216 possible

conﬁgurations of triangles to 10 equivalence classes. These 10

classes represent the 10 different types of triangles that can

occur in a network, and based on them, a notion of balance

can be deﬁned. We also give a general formula for the number

of equivalence classes for the n-alternative case (Theorem

2). Finally, we examine numerically the data set in [14] and

compare its empirical distribution of the equivalence classes to

a null hypothesis in which preference orderings are randomly

assigned to the nodes.

II. MAIN RESULTS

We deﬁne a preference ordering on nalternatives, n≥2,

as a permutation σon nelements. A preference triangle on

nalternatives, Pn, is then deﬁned to be a complete graph

on 3nodes (i.e., K3), where each node is associated with a

preference ordering. We introduce a relation Rand we say

that two preference triads P1

nand P2

nare related if P1

ncan be

transformed into P2

nby relabeling its nodes and by applying

the same permutation of the elements to all nodes (which

corresponds to to relabeling the elements). This is denoted

by P1

n∼P2

For example, the two preference triads depicted in Fig-

ure 2are related: In P1

3, change the node labels v1, v2, v3

to w3, w2, w1, respectively, and let elements Aand Bswap

places in all three permutations to obtain P2

It is easy to see that the relation Ris an equivalence

relation: Let P1

n, P 2

nand P3

nbe preference triads. Clearly

n∼P1

nsince no transformation is needed, so Ris reﬂexive.

Furthermore, if P1

n∼P2

n, then we can recover P1

nfrom

nby reversing the swaps and undo the relabeling, so Ris

symmetric. Finally, if P1

n∼P2

nand P2

n∼P3

nwe can ﬁrst

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

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

10 玖币 0人已下载

立即下载

摘要：

StructuralBalanceConsiderationsforNetworkswithPreferenceOrdersasNodeAttributesOlleAbrahamsson,DanyoDanevandErikG.LarssonDept.ofElectricalEngineering(ISY),Link¨opingUniversity,58183Link¨oping,SwedenEmail:folle.abrahamsson,danyo.danev,erik.g.larssong@liu.seAbstractWediscusspossibledenitionsofstructu...

展开>> 收起<<

Structural Balance Considerations for Networks with Preference Orders as Node Attributes Olle Abrahamsson Danyo Danev and Erik G. Larsson.pdf

共7页,预览2页

还剩页未读，继续阅读

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

Structural Balance Considerations for Networks with Preference Orders as Node Attributes Olle Abrahamsson Danyo Danev and Erik G. Larsson

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: