12
Chapter 2. The core model
are, say, three different edge properties we replicate each node of the original social
network into three versions, and imagine that the versions of the same flavor are
arranged in a layer. The edges appropriate to that layer connect these versions of
the nodes. Thus the expanded graph has three layers, each containing the matching
versions of all of the nodes and a subset of the edges. Looking “down” on the graph
from above, the layers cannot be seen, and the graph can be seen in its original
form. To keep the versions of the “same node” aligned, we also add “vertical” edges
between them to maintain the integrity of the entire social network.
We begin with the most intuitive case: the edges in the social network reflect
different kinds of relationships such as relatives, colleagues, and friends.
Consider a social network with n nodes and two different edge types, representing roles or behaviors. There may, of course, be more than one edge between the
same pair of nodes if, for example, they are friends and colleagues.
We begin by replicating the set of n nodes, arranging each of the versions of
the network in a layer. Each layer is assigned one of the possible connection types
or roles: friends and colleagues. The edges of the original social network are then
placed in the layer to which they naturally belong. For example, if A and B are
friends, then an edge joins the versions of A and B in the friends layer. As a result,
there is now at most a single edge between any two nodes in the expanded graph.
The semantics of an edge can be inferred from the layer in which it appears.
We now connect each of the versions of the same node (for example, A in both
her versions) by a “vertical” edge, binding the new graph into a consistent whole.
These vertical edges both ensure that the graph is connected, and enforce a weak
global consistency among the versions of the same node.
The resulting adjacency matrix is of size 2n × 2n. This is bigger than the
original n × n adjacency matrix, but the actual content has not increased by much.
The total number of within-layer connections in the 2n × 2n graph is the same as
the total number of connections in the original graph, since that is where they came
from. The additional edges are the “vertical” edges; these cause the off-diagonal
submatrices to be themselves diagonal matrices. If the vertical edges are undirected,
then these two submatrices are the same; if the vertical edges are directed, they need
not be.
Adjacency matrices representing social networks are typically sparse; the apparently much bigger matrix produced by the layer construction does not actually
have many more non-zero entries than there were to begin with. The cost of the
computations required for spectral embedding can be made to depend only on the
number of non-zero entries in the matrices (using sparse matrix eigendecomposition
techniques), so that the cost for the larger matrix increases only linearly, rather than
quadratically.
We can apply the spectral embedding technique to the new, larger graph and
embed it in a single geometric space. The distances between the positions of embedded nodes tell us how similar the corresponding nodes are in the context of the entire
social network, accounting fully for the different types of edges.
If we consider one of the subgraphs to be red, and the other to be green, Figure 2.1 shows some possible connection patterns.
Chapter 2. The core model
are, say, three different edge properties we replicate each node of the original social
network into three versions, and imagine that the versions of the same flavor are
arranged in a layer. The edges appropriate to that layer connect these versions of
the nodes. Thus the expanded graph has three layers, each containing the matching
versions of all of the nodes and a subset of the edges. Looking “down” on the graph
from above, the layers cannot be seen, and the graph can be seen in its original
form. To keep the versions of the “same node” aligned, we also add “vertical” edges
between them to maintain the integrity of the entire social network.
We begin with the most intuitive case: the edges in the social network reflect
different kinds of relationships such as relatives, colleagues, and friends.
Consider a social network with n nodes and two different edge types, representing roles or behaviors. There may, of course, be more than one edge between the
same pair of nodes if, for example, they are friends and colleagues.
We begin by replicating the set of n nodes, arranging each of the versions of
the network in a layer. Each layer is assigned one of the possible connection types
or roles: friends and colleagues. The edges of the original social network are then
placed in the layer to which they naturally belong. For example, if A and B are
friends, then an edge joins the versions of A and B in the friends layer. As a result,
there is now at most a single edge between any two nodes in the expanded graph.
The semantics of an edge can be inferred from the layer in which it appears.
We now connect each of the versions of the same node (for example, A in both
her versions) by a “vertical” edge, binding the new graph into a consistent whole.
These vertical edges both ensure that the graph is connected, and enforce a weak
global consistency among the versions of the same node.
The resulting adjacency matrix is of size 2n × 2n. This is bigger than the
original n × n adjacency matrix, but the actual content has not increased by much.
The total number of within-layer connections in the 2n × 2n graph is the same as
the total number of connections in the original graph, since that is where they came
from. The additional edges are the “vertical” edges; these cause the off-diagonal
submatrices to be themselves diagonal matrices. If the vertical edges are undirected,
then these two submatrices are the same; if the vertical edges are directed, they need
not be.
Adjacency matrices representing social networks are typically sparse; the apparently much bigger matrix produced by the layer construction does not actually
have many more non-zero entries than there were to begin with. The cost of the
computations required for spectral embedding can be made to depend only on the
number of non-zero entries in the matrices (using sparse matrix eigendecomposition
techniques), so that the cost for the larger matrix increases only linearly, rather than
quadratically.
We can apply the spectral embedding technique to the new, larger graph and
embed it in a single geometric space. The distances between the positions of embedded nodes tell us how similar the corresponding nodes are in the context of the entire
social network, accounting fully for the different types of edges.
If we consider one of the subgraphs to be red, and the other to be green, Figure 2.1 shows some possible connection patterns.