8.4. Applications of signed networks
107
where dis i j is the Euclidean distance between node i and node j in the embedding.
The second is the average node ratio (ANR). This measure computes the average embedded lengths of edges from the perspective of each node; in other words, it
computes the ratio of the average “pull” on nodes to the average “push” on nodes:
ANR =
n
∑
i=1
n
∑
j=1
w
+
i j dis i j /d
+
i
/|V | +
n
∑
i=1
n
∑
j=1
w
−
i j dis i j /d
−
i
/|V | −
,
where |V | + and |V | − are the numbers of nodes with positive edges and negative
edges, respectively.
The third is the median edge ratio (MER), which is computed by dividing the
median embedded edge length of positively weighted edges by the median embedded
edge length of negatively weighted edges:
MER =
median(dis i j |W
+
i j > 0)
median(dis i j |W
−
i j > 0)
.
The three measures are similar, but they emphasize different aspects of an embedding. AER focuses on the total edge lengths. ANR moderates the edge lengths
by how they are incident at nodes. MER limits the effects of extreme values, for
example a single node embedded far from the rest of the graph.
Gahuku–Gama network
We begin with a small dataset described by Read [78] and used by Hage and Harary
[37]. This dataset contains the relations between 16 tribes of the Eastern Central
Highlands of New Guinea. Read suggested an alliance structure among three tribal
groupings. The dataset is an unweighted signed network, where positive edges are
alliance (“rova”) relations and negative edges are antagonistic (“hina”) relations. The
enemy of an enemy is sometimes a friend and sometimes an enemy. The dataset is
small enough that we can visualize the embeddings.
The tribe dataset embeddings based on the three signed Laplacian are shown
in Figure 8.5. In all three embeddings the positive (solid) edges are short, and the
negative (dashed) edges are long. The known alliance structure among three tribal
groups is shown clearly in the three embeddings, with only negative edges between
groups.
However, there are some important differences among the Laplacian embeddings. First we focus on the tribes in the upper left group. The tribe MASIL not only
does not have any enemies, but also plays a key broker role between the upper left
and lower left groups. This means that tribe MASIL should be placed close to the
center of the embedding. In the embedding of Figure 8.5(a), tribe MASIL is not as
close to the right-hand group as it is in the other two embeddings. Furthermore, in
the upper-left group, tribes GEHAM, GAHUK and ASARO are most antagonistic
107
where dis i j is the Euclidean distance between node i and node j in the embedding.
The second is the average node ratio (ANR). This measure computes the average embedded lengths of edges from the perspective of each node; in other words, it
computes the ratio of the average “pull” on nodes to the average “push” on nodes:
ANR =
n
∑
i=1
n
∑
j=1
w
+
i j dis i j /d
+
i
/|V | +
n
∑
i=1
n
∑
j=1
w
−
i j dis i j /d
−
i
/|V | −
,
where |V | + and |V | − are the numbers of nodes with positive edges and negative
edges, respectively.
The third is the median edge ratio (MER), which is computed by dividing the
median embedded edge length of positively weighted edges by the median embedded
edge length of negatively weighted edges:
MER =
median(dis i j |W
+
i j > 0)
median(dis i j |W
−
i j > 0)
.
The three measures are similar, but they emphasize different aspects of an embedding. AER focuses on the total edge lengths. ANR moderates the edge lengths
by how they are incident at nodes. MER limits the effects of extreme values, for
example a single node embedded far from the rest of the graph.
Gahuku–Gama network
We begin with a small dataset described by Read [78] and used by Hage and Harary
[37]. This dataset contains the relations between 16 tribes of the Eastern Central
Highlands of New Guinea. Read suggested an alliance structure among three tribal
groupings. The dataset is an unweighted signed network, where positive edges are
alliance (“rova”) relations and negative edges are antagonistic (“hina”) relations. The
enemy of an enemy is sometimes a friend and sometimes an enemy. The dataset is
small enough that we can visualize the embeddings.
The tribe dataset embeddings based on the three signed Laplacian are shown
in Figure 8.5. In all three embeddings the positive (solid) edges are short, and the
negative (dashed) edges are long. The known alliance structure among three tribal
groups is shown clearly in the three embeddings, with only negative edges between
groups.
However, there are some important differences among the Laplacian embeddings. First we focus on the tribes in the upper left group. The tribe MASIL not only
does not have any enemies, but also plays a key broker role between the upper left
and lower left groups. This means that tribe MASIL should be placed close to the
center of the embedding. In the embedding of Figure 8.5(a), tribe MASIL is not as
close to the right-hand group as it is in the other two embeddings. Furthermore, in
the upper-left group, tribes GEHAM, GAHUK and ASARO are most antagonistic