32
Chapter 4. Modelling relationships of different types
4.1 Typed edge model approach
Formally, we model a graph with n nodes and c different edge types by extracting c
subgraphs, each one consisting of copies of all of the nodes, but just the edges of one
particular type. We then connect the subgraphs (layers) together by adding edges
connecting the c versions of each node together in a c-clique. We cannot use a path
to connect the c versions of each node because (a) there is no obvious order for the
different colors, and (b) the embedding of a path is a curved structure which makes
the top and bottom layers special, aggravating (a).
This new, enhanced graph will then be embedded, using a standard spectral
embedding since it is just a conventional graph with cn nodes. Information associated
with the types of edges has been coded in their connection pattern, that is which
nodes they are connected to.
The weights on the edges in each subgraph are just the weights from the original graph. The embedding of each subgraph, therefore, reflects the intensity of the
connections of that particular type — a popular social individual may be richly connected in the social subgraph and so will tend to be embedded centrally within the
embedding of that layer.
However, new edges have been created between the versions of the same node
in different subgraphs. What weights should be allocated to these edges that connect
the c copies of each of the original nodes into a c-clique? These edges serve to
align the embeddings of each subgraph because they force the copies of nodes that
represent the same individual to be close to one another. The greater the weights on
these edges, the more the global embedding aligns the subgraphs. It is therefore a
critical choice.
4.2 Typed edge spectral embedding
We have hinted at a principled way to allocate weights to the new vertical edges that
connect the versions of the same node: compute the total degree incident at a node
in a layer, divide the weights of all of the incident edges in that layer by two, and
allocate the remaining half evenly among the c − 1 edges that connect the node to
its versions in the other c − 1 layers. The motivation for this choice is that, from the
perspective of each individual subgraph (layer), it behaves like a lazy random walk
— the transitions to other layers are similar to the transitions around a self-loop.
Implicit in our layered model is that each individual plays a different role in the
specialized social networks of each layer. An individual’s role in the friendship social
network is not necessarily the same as in a work-related social network. In particular,
the same individual might be quite central in a friendship social network, but quite
peripheral in a work-related social network. Thus we expect that the (weighted)
degree of versions of the same node might be quite different in different subgraphs.
It is possible that a node might have versions with no connections in a particular subgraph — they have no relationships of a particular kind. However, the addition
of the vertical edges ensures that they are connected in the larger graph.
The vertical edges model a kind of resistance associated with the differences
Chapter 4. Modelling relationships of different types
4.1 Typed edge model approach
Formally, we model a graph with n nodes and c different edge types by extracting c
subgraphs, each one consisting of copies of all of the nodes, but just the edges of one
particular type. We then connect the subgraphs (layers) together by adding edges
connecting the c versions of each node together in a c-clique. We cannot use a path
to connect the c versions of each node because (a) there is no obvious order for the
different colors, and (b) the embedding of a path is a curved structure which makes
the top and bottom layers special, aggravating (a).
This new, enhanced graph will then be embedded, using a standard spectral
embedding since it is just a conventional graph with cn nodes. Information associated
with the types of edges has been coded in their connection pattern, that is which
nodes they are connected to.
The weights on the edges in each subgraph are just the weights from the original graph. The embedding of each subgraph, therefore, reflects the intensity of the
connections of that particular type — a popular social individual may be richly connected in the social subgraph and so will tend to be embedded centrally within the
embedding of that layer.
However, new edges have been created between the versions of the same node
in different subgraphs. What weights should be allocated to these edges that connect
the c copies of each of the original nodes into a c-clique? These edges serve to
align the embeddings of each subgraph because they force the copies of nodes that
represent the same individual to be close to one another. The greater the weights on
these edges, the more the global embedding aligns the subgraphs. It is therefore a
critical choice.
4.2 Typed edge spectral embedding
We have hinted at a principled way to allocate weights to the new vertical edges that
connect the versions of the same node: compute the total degree incident at a node
in a layer, divide the weights of all of the incident edges in that layer by two, and
allocate the remaining half evenly among the c − 1 edges that connect the node to
its versions in the other c − 1 layers. The motivation for this choice is that, from the
perspective of each individual subgraph (layer), it behaves like a lazy random walk
— the transitions to other layers are similar to the transitions around a self-loop.
Implicit in our layered model is that each individual plays a different role in the
specialized social networks of each layer. An individual’s role in the friendship social
network is not necessarily the same as in a work-related social network. In particular,
the same individual might be quite central in a friendship social network, but quite
peripheral in a work-related social network. Thus we expect that the (weighted)
degree of versions of the same node might be quite different in different subgraphs.
It is possible that a node might have versions with no connections in a particular subgraph — they have no relationships of a particular kind. However, the addition
of the vertical edges ensures that they are connected in the larger graph.
The vertical edges model a kind of resistance associated with the differences