2.2. Building layered models
11
degree, d, of each node), placing this value on the diagonal, and replacing each nonzero off-diagonal weight w by −w. If W is the adjacency matrix and D the diagonal
matrix of node degrees, the combinatorial Laplacian is given by:
L = D −W
The spectral embedding begins from the Laplacian matrix, computes an eigendecomposition, and uses k of the eigenvectors as the coordinates for the position of
each point. Because of the normalization, the eigenvectors chosen are those with the
smallest corresponding eigenvalues (rather than the largest, which is what happens
in conventional, eigendecomposition-based dimensionality reduction techniques).
If the graph is connected, then the smallest eigenvalue is zero, and the corresponding eigenvector is ignored — it represents, in a sense which we will make
rigorous later, a trivial embedding. In fact, the number of zero-valued eigenvalues
reveals the number of connected components of the graph.
It is easy to see why this approach is limited in its modelling power for some
kinds of edge properties. If some edge weights can be negative, then summing the
entries in a row no longer corresponds to the total weighted degree. If there is more
than one edge between the same pair of nodes, then there is nowhere to represent
the information about the second, and subsequent, edges. And the eigendecomposition requires that the Laplacian matrix be symmetric, which prevents the immediate
representation of edges with an orientation.
There are also some more subtle issues. The choice of this particular Laplacian implicitly assumes that the right model for similarity is the so-called electrical
resistance model — the distance between two nodes depends not just on the shortest
(weighted) path between them but on the number and weights of all paths between
them, with weights interpreted as the reciprocals of resistance [45]. This choice also
assumes that the degrees of nodes in different parts of the graph are roughly the
same, and we have seen that this is not typical in social networks. We will therefore
tend to prefer slightly different Laplacian normalizations that we will introduce in
Chapter 3.
2.2 Building layered models
The difficulty with representing multiple kinds of edges at once is that adjacency matrices only have a single “slot” to capture all of the information about the relationship
between a pair of individuals.
Our first key idea is to replicate the nodes of the social network so that each
copy becomes the representative, and connection point, for edges with a particular
property. When a social network has edges with many kinds of semantics, these
edges can be connected to the appropriate copies of the nodes to record and preserve
those semantics. In other words, an edge that has multiple associated semantics
becomes a constellation of edges, each with a single semantics that is carried by how
it is connected.
The second key idea is that we organize the different copies or versions of the
nodes by placing them, conceptually, in different layers. In other words, if there
11
degree, d, of each node), placing this value on the diagonal, and replacing each nonzero off-diagonal weight w by −w. If W is the adjacency matrix and D the diagonal
matrix of node degrees, the combinatorial Laplacian is given by:
L = D −W
The spectral embedding begins from the Laplacian matrix, computes an eigendecomposition, and uses k of the eigenvectors as the coordinates for the position of
each point. Because of the normalization, the eigenvectors chosen are those with the
smallest corresponding eigenvalues (rather than the largest, which is what happens
in conventional, eigendecomposition-based dimensionality reduction techniques).
If the graph is connected, then the smallest eigenvalue is zero, and the corresponding eigenvector is ignored — it represents, in a sense which we will make
rigorous later, a trivial embedding. In fact, the number of zero-valued eigenvalues
reveals the number of connected components of the graph.
It is easy to see why this approach is limited in its modelling power for some
kinds of edge properties. If some edge weights can be negative, then summing the
entries in a row no longer corresponds to the total weighted degree. If there is more
than one edge between the same pair of nodes, then there is nowhere to represent
the information about the second, and subsequent, edges. And the eigendecomposition requires that the Laplacian matrix be symmetric, which prevents the immediate
representation of edges with an orientation.
There are also some more subtle issues. The choice of this particular Laplacian implicitly assumes that the right model for similarity is the so-called electrical
resistance model — the distance between two nodes depends not just on the shortest
(weighted) path between them but on the number and weights of all paths between
them, with weights interpreted as the reciprocals of resistance [45]. This choice also
assumes that the degrees of nodes in different parts of the graph are roughly the
same, and we have seen that this is not typical in social networks. We will therefore
tend to prefer slightly different Laplacian normalizations that we will introduce in
Chapter 3.
2.2 Building layered models
The difficulty with representing multiple kinds of edges at once is that adjacency matrices only have a single “slot” to capture all of the information about the relationship
between a pair of individuals.
Our first key idea is to replicate the nodes of the social network so that each
copy becomes the representative, and connection point, for edges with a particular
property. When a social network has edges with many kinds of semantics, these
edges can be connected to the appropriate copies of the nodes to record and preserve
those semantics. In other words, an edge that has multiple associated semantics
becomes a constellation of edges, each with a single semantics that is carried by how
it is connected.
The second key idea is that we organize the different copies or versions of the
nodes by placing them, conceptually, in different layers. In other words, if there