Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

One of the main tasks in network theory is the detection of communities. The question whether or not a network can be partitioned into clusters is not trivial and it is contingent on the question being asked. There are many criteria on how a community can be defined and detected (see [4] for an extensive review on the subject). In the context of social networks in general and historical networks in particular, clustering can have far-reaching consequences, especially when clusters are involved in conflicts. Under a sociological perspective, a natural way of grouping nodes is that of social balance theory, a model of human relationships that can be traced back to the works of F. Heider on cognitive dissonance theory [8]. It is built upon the notion that, in a triad of nodes, the positive or negative relation between two nodes is reflected in their relation to the third node (see Sect. 3.1). In order to test this idea in a historical setting, one of the authors studied the conflict that arose between the years of 1225 and 1235 in the Holy Roman Empire, a conflict which pitted the Emperor Frederick II against his heir, Henry VII [5]. Based on Heider’s theory, Gramsch showed that the dispute led to a rift among the prince-electors, thus threatening the stability of the empire [5].

The main goal of this paper is to use a clustering algorithm for this event, considering the role of negative links, and compare it to the results found by Gramsch. Far from trying to rewrite history anew, since historical events are extremely complex, spanning years and sometimes thousands of players, our goal is rather humble: to see if network analysis, particularly community detection, may be used as a viable tool to help historians see patterns which otherwise could not be seen.

This paper is organized as follows: we first give a brief overview of the crisis of 1225–1235 within the Holy Roman Empire. In Sect. 3, we present materials and methods. We then discuss the results obtained by a traditional historical analysis and show how a spin-glass-based community detection algorithm compares with this analysis.Footnote 1

2 Background and Related Work

In the present work we deal with particular aspects of the coalition and conflicting forces that underlie the reign of Henry VII in the Holy Roman Empire [5, 6]. In medieval times monarchic power was strongly restricted, and within the confines of the Holy Roman Empire, a coalition of many sovereigns, a consensus among rulers was extremely important for a successful rule of the elected Emperor. This became evident during the era of emperor Frederick II (1212–1250) and his son, King Henry VII (1220–1235). In 1235, due to the political incapacity of Henry, who sacked some princes of their power, Frederick II had to disavow his son, lest he cause further damage to the authority of the Staufian dynasty and lead to its demise. The conflict involved 68 sovereigns. Notwithstanding the complexity of relationships, Gramsch convincingly demonstrates that network analysis may provide new vistas on the overall structure of the conflict which lead to the deposition of Henry [5].

He depicted the political system of the medieval German empire as a network of princes, kings, counts, bishops and other sovereigns (henceforth called actors). Based on Heider’s structural balance theory [8] (see Sect. 3.1), he was able to characterize not only the existence of a relationship between actors A and B but also that such relationships could be neutral, negative (hostile), or positive (friendly). The conflicts are of various natures. The existence of negative relations is essential for the method to work. They normally represent conflicts of various natures such as territorial or status competition, legal or military conflicts. Positive relationships in this context can be kinship or political alliances. The analysis was carried out over a period of ten years of political relations and interactions among actors (from 1225 to 1235). These form the so-called socio-matrices, which can be identified with adjacency matrices, albeit with negative entries. Gramsch’s proposition is that within a cluster there should be no conflict among actors.

The most important feature is the dual structure in the network, where each group is separated by various conflicts. We recall that, previously, these conflicts were considered in isolation. However [6] showed that there were hidden relations between them. For instance, in 1225, emperor Frederick II predominantly collaborated with actors one group while Henry VII with opposing group. This then shows the origins of the later conflict between the father and the son.

Further, this analysis was able to show what happened between the years 1232 and 1235 (see figures in [6]), namely, which actors stayed together in one cluster, which ones changed political coalitions, and how the front line of conflicts changed geographically. In short, one can observe that the political situation in 1232 was characterized by an antagonism of two factions, each of which composed of two clusters. These two factions were, each, supported by Frederick and Henry, i.e., they favored different groups of princes. Between 1232 and 1234, Frederick decided to depose his son in order to avoid further consequences and recover the complete control over his empire. These two antagonistic factions then start to decay in 1233 and disappear almost completely by 1235.

3 Materials and Methods

In this section we discuss the main methods used in our approach: Heider’s structural balance theory and the Potts Model. Following, we discuss their use for analyzing the network of 68 actors who take part in the historical event mentioned in Sect. 2.

3.1 Heider’s Structural Balance Theory

In his seminal work of 1946 Heider asked the question about how an individual A’s attitude towards B influences the way a third individual C relates to B. It originated the so-called structural balance theory, which states that a society is balanced when ‘a friend’s friend (enemy) is also my friend (enemy)’. If all triads of a network of relationships are balanced, the network is said to be balanced. The question naturally arises whether a network of individuals with such relationships can be grouped into separate communities or not. Harary [7] showed that if a connected network is balanced, it can be split into two opposing clusters. This was later generalized to cycles with more than 3 individuals, to the idea of a k-cycle [1, 3]. A network is k-balanced if it can be divided into k clusters where within each cluster there are only positive relationships. In real life, however, not all clusters are balanced. There will always be within a cluster of positive relations some nodes with negative ones. The number of such misplaced links is called ‘frustration’, a term borrowed from the physics of spin systems. The task is to find a configuration which minimizes frustration. The similarity between Heider’s theory and a system of interaction spins led Reichardt and Bornholdt to introduce a method of community detection based on a mapping between a graph and a q-state Potts Model [9]. Their method was generalized by Traag and Bruggeman to account for the possibility of hostile links [10]. We describe their method below and would like to remark that other clustering algorithms cannot be used due to the presence of negative links.

3.2 Spin-Glass-Potts Model

The Potts model is a model of interacting spins where each spin can have q different values. The model is called spin-glass because spins are not spatially ordered (as in a crystal). Spins tend to align (or repel) themselves if they have the same (different) q. The attraction/repulsion is mediated by the Hamiltonian of the system, i.e. its energy for a given configuration {\(\sigma \)} \(=\) {\(\sigma _1, \sigma _2, \sigma _3,\ldots \)} of clusters \(\sigma _1\), \(\sigma _2\) etc. Minimizing the Hamiltonian is equivalent to minimizing Frustration [10]. Given the adjancency matrix with elements \(A_{ij}\), the Hamiltonian reads as in Eq. 1, where \(\delta \) is Kronecker’s delta function. The \(p^{\pm }_{ij}\)’s are the probabilities that links i and j are positively or negatively connected and \(\gamma \) are free parameters to tune the relative weight of positive and negative links.

$$\begin{aligned} H ({\sigma } ) = -\sum _{i,j}\left[ A_{ij} -(\gamma ^{+}p^{+}_{ij} - \gamma ^{-}p^{-}_{ij} )\right] \delta (\sigma _i, \sigma _j ) \end{aligned}$$
(1)

We refer the interested reader to [10] for more details on how to choose these probabilities.

3.3 Detecting Communities Using Spin-Glass

In order to detect the community structure for the conflict between Frederick and his son, we used the igraph implementation of the spin-glass algorithm (Python variant) [2]. Each actor is represented by an abbreviated name. As in [5], we use one socio-matrix (adjacency matrix) for each year (unless otherwise stated).

We use a set of adjacency matrices (prepared by R. Gramsch), where \(A_{ij}\) indicates whether or not there is a relationship between actors i and j, and, if there is, whether it is neutral, friendly, or hostile. Based on a suggestion of R. Gramsch we excluded all relationships involving Frederick II, Henry VII and the Pope, as these are the main actors of the conflict and served most of the time as liaisons between opposite groups. They introduce a bias in clustering, thus hiding important patterns. Results reported in the next section, thus, do not include these three actors. We remark that the same procedure was performed by Gramsch in his investigations; thus the results are comparable.

The spin-glass method needs as input the number n of communities. We chose \(n=2\), to see whether the method would lead to a partitioning of the network comparable to that found by Gramsch. If one gives a higher value of n, the method will produce n communities but normally for n above a certain threshold (in some of our cases 5 or above), the routine will give always at most 5 clusters, usually less.

4 Results

We have run the spin-glass with, as mentioned, the number of spins set to 2, producing thus partitions that should separate the conflicting parties. We did this for each year. Figures 1 and 2 show, for the sake of illustration, the clusterings for years 1225 and 1235 respectively.Footnote 2 Please notice the reduction of red edges (hostility) in the year 1235. Besides these edges, we have also yellow edges (neutral relationship) and black ones (friendly relationships).

Fig. 1
figure 1

The structure of the communities (clustering)—year 1225

Full size image
Fig. 2
figure 2

The structure of the communities (clustering)—year 1235

Full size image

In order to compare the quality of the clustering produced originally by Gramsch in [5, 6] with those from the spin-glass method, we use the Rand index, define in Eq. 2. In this equation a is the number of pairs of nodes that are in the same set in both partitions X, Y while b is the number of pairs that are in different sets in partition X and continue to be so in X; n is the number of nodes. A Rand index of 1 implies total agreement (clusters are identical) while a 0 implies total disagreement.

$$\begin{aligned} R=\frac{a+b}{\left( {\begin{array}{c}n\\ 2\end{array}}\right) } \end{aligned}$$
(2)

Table 1 shows the Rand indexes when we do a comparison, year by year, with the original partitioning of Gramsch. We remark that, since the spin-glass method is not deterministic, we ran spin-glass community detection 30 times for each year. Thus the table also shows the standard deviation associated with the mean value.

The values, as can be seen in the table, indicate a good agreement between the spin-glassmethod and Gramsch’s original partitioning, based on Heider’s structural balance. We would like to point out that, for the year 1230, the agreement is comparatively low. This is due to the fact that in 1230 there occurred a temporary agreement between sovereigns. Quoting Gramsch ([5], p. 222): ‘During the first quarter of the 1230, when peace talks between the Emperor and the Pope began, the sovereigns placed themselves in such a close [league] as it was never to be seen again: 58 joined into one coalition.’ So for this year there is only one cluster. Since the method requires a a priori number of cluster to be created, which was set to 2, the Rand index is smaller and is about 0.5, which corresponds to the probability of placing nodes with a 50–50 change on each cluster.

Table 1 Rand indexes (mean and standard deviation), by year
Full size table

5 Conclusion

In this paper we applied a community detection algorithm to determine clusters of opposing sovereigns in conflict in medieval Germany, which took place between 1225 and 1235 and pitted the Emperor Frederick II against his son Henry VII. We used a spin-glass-based algorithm to create clusters and to ascertain its feasibility as a tool in historical research, we compared the results with the partitioning previously done by one of the authors based on Heider’s structural balance theory. For this we calculated the Rand index to compare partitions. Our results show good agreement with the historical method, from a minimum of 50% in the worst case, as explained previously, to an agreement of 87%.