98
Chapter 8. Modelling positive and negative relationships
each in two ways: arguing from Rayleigh quotients as objective functions whose
minima represent good node placement, and from cut functions that are the signed
analogues of standard cuts. The methods produce, in each case, the same Laplacian
matrix representations of a signed graph, increasing confidence that this captures a
reasonable model of the balance between positive and negative edges. The difference
between them is how they address the issue of what makes a good cut (or, equivalently, good clusters). The resulting Laplacians can be used as embeddings by using
some or all of the eigenvectors of an eigendecomposition of such a matrix.
We compare these new embedding techniques with a previously suggested
spectral method for signed graphs [48] and show the performance of all of the algorithms on real-world datasets from Epinions, Slashdot, and the Africa Armed Conflict Location & Event Data (ACLED), as well as two small datasets, the Gahuku–
Gama alliance network of tribes in New Guinea, and the Sampson monastery network. For the small datasets, we validate our techniques by appealing to visualizations; for the larger datasets we compute measures based on the distances between
positively and between negatively connected nodes in the embedding.
8.2 Unnormalized spectral Laplacians of signed
graphs
The embedding of a signed network should place nodes that are positively related
close together, but must place nodes that are negatively related far from one another,
balancing these two different objectives in a globally consistent way that reflects the
underlying reality of the social network. We first define an unnormalized Laplacian
for signed graphs, and argue for the validity of the resulting construction based on
both Rayleigh quotient and graph cut points of views.
There is no reason why there cannot be both a positive and negative relationship between the same two individuals, and this is not necessarily the same as a
single relationship whose weight is the difference between the two intensities. In
other words, if A has a positive relationship with B with intensity 3, and a negative
relationship with intensity −2, this is not necessarily the same as a single relationship
of intensity +1. In other words, positive and negative relationships are qualitatively
different, and do not necessarily cancel out.
Therefore, we begin from two adjacency matrices: W + which contains positive
values representing the intensity of positive relationships between the pairs of nodes,
and W − which also contains positive values representing the intensity of negative
relationships between the pairs of nodes. For the time being, we will consider the
edges to be undirected, and so both matrices are symmetric.
Let D + be the diagonal degree matrix of W + , that is D
+
ii = ∑
n
j=1 W
+
i j and D −
be the diagonal degree matrix of W − , that is D
−
ii = ∑
n
j=1 W
−
i j . The total degree matrix
is therefore: D = D + + D − .
A method proposed by Kunegis et al. [48] extends the conventional Laplacian
Chapter 8. Modelling positive and negative relationships
each in two ways: arguing from Rayleigh quotients as objective functions whose
minima represent good node placement, and from cut functions that are the signed
analogues of standard cuts. The methods produce, in each case, the same Laplacian
matrix representations of a signed graph, increasing confidence that this captures a
reasonable model of the balance between positive and negative edges. The difference
between them is how they address the issue of what makes a good cut (or, equivalently, good clusters). The resulting Laplacians can be used as embeddings by using
some or all of the eigenvectors of an eigendecomposition of such a matrix.
We compare these new embedding techniques with a previously suggested
spectral method for signed graphs [48] and show the performance of all of the algorithms on real-world datasets from Epinions, Slashdot, and the Africa Armed Conflict Location & Event Data (ACLED), as well as two small datasets, the Gahuku–
Gama alliance network of tribes in New Guinea, and the Sampson monastery network. For the small datasets, we validate our techniques by appealing to visualizations; for the larger datasets we compute measures based on the distances between
positively and between negatively connected nodes in the embedding.
8.2 Unnormalized spectral Laplacians of signed
graphs
The embedding of a signed network should place nodes that are positively related
close together, but must place nodes that are negatively related far from one another,
balancing these two different objectives in a globally consistent way that reflects the
underlying reality of the social network. We first define an unnormalized Laplacian
for signed graphs, and argue for the validity of the resulting construction based on
both Rayleigh quotient and graph cut points of views.
There is no reason why there cannot be both a positive and negative relationship between the same two individuals, and this is not necessarily the same as a
single relationship whose weight is the difference between the two intensities. In
other words, if A has a positive relationship with B with intensity 3, and a negative
relationship with intensity −2, this is not necessarily the same as a single relationship
of intensity +1. In other words, positive and negative relationships are qualitatively
different, and do not necessarily cancel out.
Therefore, we begin from two adjacency matrices: W + which contains positive
values representing the intensity of positive relationships between the pairs of nodes,
and W − which also contains positive values representing the intensity of negative
relationships between the pairs of nodes. For the time being, we will consider the
edges to be undirected, and so both matrices are symmetric.
Let D + be the diagonal degree matrix of W + , that is D
+
ii = ∑
n
j=1 W
+
i j and D −
be the diagonal degree matrix of W − , that is D
−
ii = ∑
n
j=1 W
−
i j . The total degree matrix
is therefore: D = D + + D − .
A method proposed by Kunegis et al. [48] extends the conventional Laplacian