5.3. Applications of directed networks
49
the greater this distance, the more different their upstream and downstream sets of
neighbors.
For larger networks, where visualizations of the graph become cluttered and
hard to understand, tabulating edge lengths can indicate regions of the graphs whose
nodes are unusual in some way. For example, connected nodes that are placed far
from one another are anomalous, since connection and closeness are naturally associated. However, edges on the periphery of the graph tend to be long simply because
of their poor connectivity to the rest of the graph. We therefore need a measure that
differentiates expected long edges from unexpected long edges. An unexpected long
edge is one that is being “pulled” because different subsets of its neighbors all want
it to be close to them.
The embedding of a graph can be considered as the fixed point of a relaxation in which edge weight is proportional to internode pull. Therefore, globally,
the distance between two nodes reflects their global dissimilarity. In other words,
length ∝ 1/edgeweight. We call the product of length and edgeweight the normalized edge length of an edge. Normalized edge lengths should be roughly constant for
all “normal” edges of the graph. Edges for which this value is far from average, especially much larger than average, are those whose local environment is distorted. Such
edges are likely to connect nodes of special interest. For example, a node that acts
as a “broker” between two disparate subgroups will tend to have the relevant edges
pulled towards the subgroups; these edges will tend to be longer in the embedding
than their edge weight and local neighborhood would suggest.
We can now see why edge weight prediction is much harder than edge (existence) prediction. For the ordinary or typical regions of the network, the closeness
of two unconnected nodes may indeed reflect the strength of the potential relationship between them, and a weight prediction might be quite accurate. However, in
less typical regions of the network, those for which the normalized edge lengths are
far from average, the embedded distance is no longer an estimate of intensity. The
problem is that it is difficult to tell these regions apart since a deviation in normalized
edge length is a property of an edge and not of a region. In other words, a network
region may be typical (embedded edge lengths match edge weights), distorted (most
embedded lengths deviate from edge weights), or a hybrid (embedded lengths mostly
match edge weights, but some edge lengths deviate from their expected lengths).
The difference between a node that brokers symmetric flow and one that brokers asymmetric flow is shown in Figure 5.2. The graph consists of two directed
cliques connected to one another in two ways. One connection (via node 12) is bidirectional; the other (via node 11) is one-directional. The embedding shows, by the
length of the dotted line, the strength of the asymmetric flow through node 11, in
comparison to the flow through node 12.
Our second example is a more complex synthetic dataset. It consists of two
circles in two dimensions, with small random variations for each node, and a joining
bridge, shown in Figure 5.3(a), with the subgraphs given different shadings. Each
node is connected to its five nearest neighbors by outgoing directed edges. Hence
the nodes in the bridge are better connected to the adjacent circle nodes than those
circle nodes are connected to nodes in the bridge. Figure 5.3(b) shows the new
49
the greater this distance, the more different their upstream and downstream sets of
neighbors.
For larger networks, where visualizations of the graph become cluttered and
hard to understand, tabulating edge lengths can indicate regions of the graphs whose
nodes are unusual in some way. For example, connected nodes that are placed far
from one another are anomalous, since connection and closeness are naturally associated. However, edges on the periphery of the graph tend to be long simply because
of their poor connectivity to the rest of the graph. We therefore need a measure that
differentiates expected long edges from unexpected long edges. An unexpected long
edge is one that is being “pulled” because different subsets of its neighbors all want
it to be close to them.
The embedding of a graph can be considered as the fixed point of a relaxation in which edge weight is proportional to internode pull. Therefore, globally,
the distance between two nodes reflects their global dissimilarity. In other words,
length ∝ 1/edgeweight. We call the product of length and edgeweight the normalized edge length of an edge. Normalized edge lengths should be roughly constant for
all “normal” edges of the graph. Edges for which this value is far from average, especially much larger than average, are those whose local environment is distorted. Such
edges are likely to connect nodes of special interest. For example, a node that acts
as a “broker” between two disparate subgroups will tend to have the relevant edges
pulled towards the subgroups; these edges will tend to be longer in the embedding
than their edge weight and local neighborhood would suggest.
We can now see why edge weight prediction is much harder than edge (existence) prediction. For the ordinary or typical regions of the network, the closeness
of two unconnected nodes may indeed reflect the strength of the potential relationship between them, and a weight prediction might be quite accurate. However, in
less typical regions of the network, those for which the normalized edge lengths are
far from average, the embedded distance is no longer an estimate of intensity. The
problem is that it is difficult to tell these regions apart since a deviation in normalized
edge length is a property of an edge and not of a region. In other words, a network
region may be typical (embedded edge lengths match edge weights), distorted (most
embedded lengths deviate from edge weights), or a hybrid (embedded lengths mostly
match edge weights, but some edge lengths deviate from their expected lengths).
The difference between a node that brokers symmetric flow and one that brokers asymmetric flow is shown in Figure 5.2. The graph consists of two directed
cliques connected to one another in two ways. One connection (via node 12) is bidirectional; the other (via node 11) is one-directional. The embedding shows, by the
length of the dotted line, the strength of the asymmetric flow through node 11, in
comparison to the flow through node 12.
Our second example is a more complex synthetic dataset. It consists of two
circles in two dimensions, with small random variations for each node, and a joining
bridge, shown in Figure 5.3(a), with the subgraphs given different shadings. Each
node is connected to its five nearest neighbors by outgoing directed edges. Hence
the nodes in the bridge are better connected to the adjacent circle nodes than those
circle nodes are connected to nodes in the bridge. Figure 5.3(b) shows the new