158
Chapter 11. Summary
cannot quite be true — there are forces arising from the way the human mind works,
and from the ways human society works that influence each individual decision.
By looking at the structure of the social network, we can infer these higher-level
forces, deepening our understanding of psychology and sociology, as well as more
operational properties such as influence, advertising, power, and emotional bonding.
Understanding the backdrop of normality in social connections also enables us to
detect anomalies that may represent criminality or concealment.
All of these properties can, in principle, be computed directly from a representation of the social network as a graph. However, many of these computations
have complexities that are cubic in the number of nodes in the graph, so that computing them directly does not scale well to large graphs. This is particularly true if
the graph is changing since such properties are brittle in the sense that a change in a
single edge, or adding or deleting a single node, can result in changes throughout the
graph. Spectral embedding has become the standard way to avoid these difficulties.
Once a graph has been embedded in a geometry in such a way that distance accurately reflects dissimilarity, many of the useful emergent properties can be calculated
directly in the geometry. If the geometry is low-dimensional, visualizations make it
possible for analysts to see and understand emergent properties directly.
However, most social network analysis has been limited to modelling settings
where relationships are of a single type, usually with an associated (positive) intensity. We have argued that this is limiting; real-world relationships are multifaceted,
including at least: being of multiple, qualitatively different types; asymmetric; negative, as well as positive; and varying with time. There have been attempts to model
each of these possibilities individually, with varying amounts of success.
We have introduced a single, comprehensive approach — the layered model
— that allows many different edge properties to be modelled in essentially the same
way. Instead of trying to represent edge properties directly, the key idea is to replicate
each node into multiple versions, each of which can carry the semantics of different
edge properties; and then connect simple untyped edges to the appropriate versions
of these nodes to preserve their semantics.
The result is a nominally larger graph, but one which includes only a linear
number of extra edges, so that if the original graph was sparse (and, in practice, it
usually is), the resulting graph is also sparse. This means that the eigendecomposition at the heart of spectral embedding remains inexpensive to compute.
When this layered subgraph process is followed, the layers have to be bound
together by edges that connect the versions of the same node to one another. There
are strong reasons to use a clique as the basic connection pattern. Choosing the
weights requires some skill, perhaps some understanding of the domain from which
the social networks are taken, and perhaps some experimentation. We have made
some arguments for principled ways in which these weights might be chosen.
Because the larger graph has undirected edges, the embedding step is completely standard, and the embedded graph can be visualized in a few dimensions.
All of the theory of spectral embedding applies to the larger graph, so most of its
properties follow directly.
The embeddings of the edges added between the layers (the “vertical” edges)
Chapter 11. Summary
cannot quite be true — there are forces arising from the way the human mind works,
and from the ways human society works that influence each individual decision.
By looking at the structure of the social network, we can infer these higher-level
forces, deepening our understanding of psychology and sociology, as well as more
operational properties such as influence, advertising, power, and emotional bonding.
Understanding the backdrop of normality in social connections also enables us to
detect anomalies that may represent criminality or concealment.
All of these properties can, in principle, be computed directly from a representation of the social network as a graph. However, many of these computations
have complexities that are cubic in the number of nodes in the graph, so that computing them directly does not scale well to large graphs. This is particularly true if
the graph is changing since such properties are brittle in the sense that a change in a
single edge, or adding or deleting a single node, can result in changes throughout the
graph. Spectral embedding has become the standard way to avoid these difficulties.
Once a graph has been embedded in a geometry in such a way that distance accurately reflects dissimilarity, many of the useful emergent properties can be calculated
directly in the geometry. If the geometry is low-dimensional, visualizations make it
possible for analysts to see and understand emergent properties directly.
However, most social network analysis has been limited to modelling settings
where relationships are of a single type, usually with an associated (positive) intensity. We have argued that this is limiting; real-world relationships are multifaceted,
including at least: being of multiple, qualitatively different types; asymmetric; negative, as well as positive; and varying with time. There have been attempts to model
each of these possibilities individually, with varying amounts of success.
We have introduced a single, comprehensive approach — the layered model
— that allows many different edge properties to be modelled in essentially the same
way. Instead of trying to represent edge properties directly, the key idea is to replicate
each node into multiple versions, each of which can carry the semantics of different
edge properties; and then connect simple untyped edges to the appropriate versions
of these nodes to preserve their semantics.
The result is a nominally larger graph, but one which includes only a linear
number of extra edges, so that if the original graph was sparse (and, in practice, it
usually is), the resulting graph is also sparse. This means that the eigendecomposition at the heart of spectral embedding remains inexpensive to compute.
When this layered subgraph process is followed, the layers have to be bound
together by edges that connect the versions of the same node to one another. There
are strong reasons to use a clique as the basic connection pattern. Choosing the
weights requires some skill, perhaps some understanding of the domain from which
the social networks are taken, and perhaps some experimentation. We have made
some arguments for principled ways in which these weights might be chosen.
Because the larger graph has undirected edges, the embedding step is completely standard, and the embedded graph can be visualized in a few dimensions.
All of the theory of spectral embedding applies to the larger graph, so most of its
properties follow directly.
The embeddings of the edges added between the layers (the “vertical” edges)