8
Chapter 1. Introduction
as axes for a space in which each of nodes can be placed. Because of the properties
of the eigendecomposition, it can be proven that the representation using, say, k
eigenvectors is the most faithful possible in that dimensionality in the sense that the
distances between nodes most accurately reflect the global similarity between them
implied by the entire connection structure. In other words, this embedding is, in a
strong sense, the best embedding from the point of view of representing the graph’s
structure (although it might not be the easiest to understand visually).
Using a spectral embedding, a social network is embedded in a geometry. The
key property of the embedded network is that distances between nodes are meaningful — they reflect the similarities between every pair of nodes, as far as that is
possible in a low-dimensional space — similar nodes are close, and dissimilar nodes
are far apart. Properties that are based on similarity can be computed directly on the
embedded graph, nodes that are placed centrally are in fact the most central nodes,
and directions capture differences. The embedding can be rendered as a visualization
which is accurate, even if it is not necessarily beautiful or easily comprehensible.
In particular, this distance measures the similarities between nodes that were
not connected in the original graph, that is the social distance between two individuals who do not have an existing mutual relationship. Two individuals who are
embedded close to one another can be thought of as being about to have a relationship, or having a relationship that failed to be noticed when the data for the network
was collected. This approach is the basis of edge prediction or link prediction and is
used for recommendation in several social media systems.
The magnitude of the distance between two nodes that are embedded close
together could also be exploited to predict the intensity of the relationship that might
come into existence. However, as we shall see, predicting intensity is much more
difficult than predicting existence.
Many other useful properties of the social network can be read off from the
visualization of the embedding. For example, nodes that are well connected tend to
be placed centrally, so measures such as centrality are immediately apparent. Nodes
that are mutually well connected are placed close together, so that clustering is also
immediately visible.
The standard spectral embedding process requires that the adjacency matrix be
symmetric. Thus the process can only be directly applied to social networks where
the edges are undirected (although they can be weighted). As we have seen, this
is extremely limiting. The remainder of this book is about a general construction
that allows the full richness of edge types to be married to the power of spectral
embedding techniques to enable general social networks to be modelled in their full
detail.
Chapter 1. Introduction
as axes for a space in which each of nodes can be placed. Because of the properties
of the eigendecomposition, it can be proven that the representation using, say, k
eigenvectors is the most faithful possible in that dimensionality in the sense that the
distances between nodes most accurately reflect the global similarity between them
implied by the entire connection structure. In other words, this embedding is, in a
strong sense, the best embedding from the point of view of representing the graph’s
structure (although it might not be the easiest to understand visually).
Using a spectral embedding, a social network is embedded in a geometry. The
key property of the embedded network is that distances between nodes are meaningful — they reflect the similarities between every pair of nodes, as far as that is
possible in a low-dimensional space — similar nodes are close, and dissimilar nodes
are far apart. Properties that are based on similarity can be computed directly on the
embedded graph, nodes that are placed centrally are in fact the most central nodes,
and directions capture differences. The embedding can be rendered as a visualization
which is accurate, even if it is not necessarily beautiful or easily comprehensible.
In particular, this distance measures the similarities between nodes that were
not connected in the original graph, that is the social distance between two individuals who do not have an existing mutual relationship. Two individuals who are
embedded close to one another can be thought of as being about to have a relationship, or having a relationship that failed to be noticed when the data for the network
was collected. This approach is the basis of edge prediction or link prediction and is
used for recommendation in several social media systems.
The magnitude of the distance between two nodes that are embedded close
together could also be exploited to predict the intensity of the relationship that might
come into existence. However, as we shall see, predicting intensity is much more
difficult than predicting existence.
Many other useful properties of the social network can be read off from the
visualization of the embedding. For example, nodes that are well connected tend to
be placed centrally, so measures such as centrality are immediately apparent. Nodes
that are mutually well connected are placed close together, so that clustering is also
immediately visible.
The standard spectral embedding process requires that the adjacency matrix be
symmetric. Thus the process can only be directly applied to social networks where
the edges are undirected (although they can be weighted). As we have seen, this
is extremely limiting. The remainder of this book is about a general construction
that allows the full richness of edge types to be married to the power of spectral
embedding techniques to enable general social networks to be modelled in their full
detail.