Partitioning signed social networks

doi:10.1016/j.socnet.2008.08.001

Social Networks

Volume 31, Issue 1, January 2009, Pages 1-11

https://doi.org/10.1016/j.socnet.2008.08.001 Get rights and content

Abstract

Structural balance theory has proven useful for delineating the blockmodel structure of signed social networks. Even so, most of the observed signed networks are not perfectly balanced. One possibility for this is that in examining the dynamics underlying the generation of signed social networks, insufficient attention has been given to other processes and features of signed networks. These include: actors who have positive ties to pairs of actors linked by a negative relation or who belong to two mutually hostile subgroups; some actors that are viewed positively across the network despite the presence of negative ties and subsets of actors with negative ties towards each other. We suggest that instead viewing these situations as violations of structural balance, they can be seen as belonging to other relevant processes we call mediation, differential popularity and internal subgroup hostility. Formalizing these ideas leads to the relaxed structural balance blockmodel as a proper generalization of structural balance blockmodels. Some formal properties concerning the relation between these two models are presented along with the properties of the fitting method proposed for the new blockmodel type. The new method is applied to four empirical data sets where improved fits with more nuanced interpretations are obtained.

Introduction

Some social relations are signed in the sense of having ties between actors that can be positive or negative. Examples include like/dislike and respect/disrespect for people. Analyses of the network structure of signed relations have to accommodate the additional information contained in the negative part of the signed ties. Structural balance theory, one variant of ‘consistency’ theories, has its origins in the work of Heider (1946). Cartwright and Harary (1956) then formalized Heider’s formulation and provided the foundation for discerning the overall structure of a network of signed ties. This structure for a ‘balanced’ network is given by the first structure theorem described below. A generalization proposed by Davis (1967) leads to the second structure theorem. However, for most observed signed structures for social groups, exact structural balance does not hold. Even so, it is still necessary to delineate the structure of these groups at points in time. Based on the structure theorems, Doreian and Mrvar (1996) proposed an empirical method for establishing the partition structure(s) of a signed relation for groups that is (are) as close to exact balance as is possible. Their method was subsumed within the rubric of generalized blockmodeling (Doreian et al., 2005). Even though these methods have been useful, the blockmodel structure discerned may not be appropriate for all signed networks for groups. We provide some illustrative examples and then broaden the types of blockmodel that can be specified and identified for signed networks within the generalized blockmodeling framework. We then apply this new blockmodel type to four real data sets and provide commentary on the new results.

Section snippets

Structural balance theory and partitions

In Cartwright and Harary’s (1956) generalization of Heider’s (1946) formulation, the difference between sentiment (social) relations and unit formation relations was ignored with attention confined, in effect, to signed social relations. Following Doreian et al. (2005), a binary signed network is an ordered pair, $(G, σ)$ , where:

(1)
$G = (U, A)$ is a digraph, without loops, having a set of units (vertices), $U$ , and a set of arcs, $A \subseteq U \times U$ ; and
(2)
$σ : A \to {p, n}$ is a sign function. The arcs with the sign p are positive

Blockmodels of signed social networks

The generalized blockmodeling approach is a direct method that analyzes the network data rather than some transformation of them. It requires a criterion function that is optimized by a relocation algorithm. See Doreian et al. (2005) for details of this approach to delineating network structure. The criterion function for signed networks is designed in terms of the structure theorems via a count of elements that are not consistent with an ideal k-balance partition. These inconsistencies take

Relaxing the structural balance blockmodel

When the signed network shown in Fig. 2 is partitioned according to structural balance $P (C^{\min}) = 2.5$ for $k = 2$ . With $α = 0.5$ this implies five ties are inconsistent with structural balance. (For $k = 3$ there are six optimal partitions, each with 4.5 as the value of the criterion function. From Theorem 3, the unique partition for $k = 2$ is the best possible partition under structural balance.) The partition structure is given in Table 3 where the five inconsistent ties are bolded and italicized. The

The newcomb data (last week)

The Newcomb data (see Nordlie, 1958, Newcomb, 1961) are well known and have been analyzed many times. Originally, the data were reported with rankings made by 17 men of each other while they lived in a pseudo-dormatory at a university. Previously unknown to each other, these men provided sociometric data that were used to study the evolution of network ties over time. Doreian et al. (2005) report the shift over time in the overall structure leading to a blockmodel of the signed relation at the

Discussion

Partitioning based on structural balance has proven useful for delineating the structure of signed social networks. While most observed signed social networks have not been balanced, in the sense of having a line index of balance that is non-zero, the delineated structures have been interpretable. For the few signed networks where data have been available over time, a tendency towards balance has been observed, notably in the Sampson (1968) data (Doreian and Mrvar, 1996) where the measure of

Conclusion

We have proposed a generalization of structural balance where the notion of positive and negative blocks has been retained but with the modification that they can appear anywhere in the blockmodel of a signed network. Assuming that structural processes leave traces found in the network structure, as delineated by blocks, it is now possible to identify structural features additional to those implied by the operation of structural balance processes. Differential popularity, differential receipt

References (21)

P. Arabie et al.
Constructing blockmodels: how and why
Journal of Mathematical Psychology
(1978)
R.L. Breiger et al.
An algorithm for clustering relational data with applications to social network analysis and comparison to multidimensional scaling
Journal of Mathematical Psychology
(1975)
P. Doreian
A multiple indicator approach to blockmodeling signed relations
Social Networks
(2008)
P. Doreian et al.
A partitioning approach to structural balance
Social Networks
(1996)
K. Faust
Comparison of methods for positional analysis: structural and general equivalences
Social Networks
(1988)
J.E. Schwartz et al.
Structures of connectivity
Social Networks
(1984)
R.F. Bales
Personality and Interpersonal Behavior
(1970)
N. Bansal et al.
Correlation clustering
Machine Learning
(2004)
V. Batagelj et al.
Pajek—program for large network analysis
Connections
(1998)
D. Cartwright et al.
Structural balance: a generalization of Heider’s theory
Psychological Review
(1956)

There are more references available in the full text version of this article.

Cited by (186)

A review of heuristics and metaheuristics for community detection in complex networks: Current usage, emerging development and future directions
2021, Swarm and Evolutionary Computation
Sensibly highlighting the hidden structures of many real-world networks has attracted growing interest and triggered a vast array of techniques on what is called nowadays community detection (CD) problem. Non-deterministic metaheuristics are proved to competitively transcending the limits of the counterpart deterministic heuristics in solving community detection problem. Despite the increasing interest, most of the existing metaheuristic based community detection (MCD) algorithms reflect one traditional language. Generally, they tend to explicitly project some features of real communities into different definitions of single or multi-objective optimization functions. The design of other operators, however, remains canonical lacking any intense interest to reflect the domain knowledge. Moreover, all the published reviews did not make any direct effort to link heuristic and metaheuristic based community detection approaches, rather, they simply state them separately. The review introduced in this paper attempts to address this issue. Mainly, we review the main heuristic and metaheuristic based community detection algorithms. Then, we introduce two new taxonomies for community detection algorithms: hybrid metaheuristic and hyper heuristic that can serve as common grounds for designing a collection of new and more effective MCD algorithms. To this end, we introduce four new systematic frameworks integrating both heuristic and metaheuristic algorithms, illustrating the possible issues that would fuel the desire for researchers to direct their future interest towards developing more effective community detection instances from the context of these frameworks.
A signed network analysis-based Consensus Reaching Process in Group Decision Making
2021, Applied Soft Computing
In the previous Consensus Reaching Process (CRP) models, although it has been a common understanding that positive social relationships between experts can prompt cooperation, meanwhile the existence of negative relations and the consequent antagonistic behaviors have been largely overlooked. In an attempt to fill in that gap, in this paper a signed network analysis-based CRP is proposed, where both the positive and negative relations can be taken into full account. In our proposed model, two types of centrality are taken advantage of to derive the experts’ importance degrees from their signed social network. Such importance degrees are then incorporated into the aggregation process via an Importance-Induced Ordered Weighting Average operator, where experts with higher importance degrees are assigned more weights to reflect their credibility. Consensus indices are defined to measure each expert’s consensus level to the group. And to help those experts with insufficient consensus indices, a feedback mechanism is developed where personalized preference revision advices are generated based on two rules: first, experts are attracted to the opinions of their positive social connections; and second, experts are repelled by the opinions of their negative social connections. An illustrative example is implemented to demonstrate the practicality of our model, and to investigate possible factors that may affect the CRP outcome. Finally, comparative analyses to several existing social network-based CRP methods are conducted.
A general model for how attributes can reduce polarization in social groups
2023, Network Science
Towards a computational network theory of social groups
2022, Behavioral and Brain Sciences
SHEEP, a Signed Hamiltonian Eigenvector Embedding for Proximity
2024, Communications Physics
A new approach to finding overlapping community structure in signed networks based on Neutrosophic theory
2024, Journal of Complex Networks

View all citing articles on Scopus

^☆: Support from the Slovenian Research Agency under the Grant, Contract number 1000-07-780005, is greatly appreciated.

View full text

Partitioning signed social networks☆

Abstract

Introduction

Section snippets

Structural balance theory and partitions

Blockmodels of signed social networks

Relaxing the structural balance blockmodel

The newcomb data (last week)

Discussion

Conclusion

Journal of Mathematical Psychology

Journal of Mathematical Psychology

Social Networks

Social Networks

Social Networks

Social Networks

Personality and Interpersonal Behavior

Correlation clustering

Machine Learning

Pajek—program for large network analysis

Connections

Structural balance: a generalization of Heider’s theory

Psychological Review