1.3. Formally representing social networks
7
1.3 Formally representing social networks
Social networks are usually modelled as graphs. A graph consists of a set of nodes
(or vertices) that represent the individuals, and a set of edges that connect nodes.
These edges represent the relationship between the individuals associated with the
nodes. Graphs are a natural way to represent networks, but they require awkward
data structures, and so are difficult to work with computationally.
From the perspective of a drawing of a graph, it is easy to see how to model rich
edge types. Each edge in the graph can be drawn with (say) a color that represents
the qualitative kind of relationship (colleague vs. friend) it represents; an arrow
to indicate the directionality of the relationship; and a positive or negative weight
or label to indicate the positive or negative intensity of the relationship. However,
temporal changes are already problematic unless the drawing becomes a video.
Direct renderings of a social network like this also do not scale as the number of nodes and edges increases. Even a small network, say 20 nodes, becomes
a cluttered picture from which conclusions might be hard to draw visually. And
there remains the challenging, and long-studied, problem of how to place the nodes
for maximal effectiveness of the rendering (that is, for maximal interpretability by
human eyes) [95].
For more mathematical analysis, it is conventional to represent a graph by an
adjacency matrix. If the graph contains n nodes, its adjacency matrix is an n × n
structure where the entries are zeros except at positions (i, j) whenever node i has a
connection to node j.
For a simple social network, the i jth entry of the adjacency matrix is set to a
1 to indicate the existence of a connection between nodes i and j. If the edges are
undirected, a connection from node i to node j necessitates a connection from node
j to node i, so that the i jth and jith entries must always be the same. The adjacency
matrix is then said to be symmetric.
It is easy to extend the adjacency matrix representation to allow edges to be
positively or negatively weighted, by using the weight as the value in the corresponding entry of the adjacency matrix.
It is also easy to model directed edges (for then the i jth entry represents the
edge from node i to node j and the jith entry the reverse edge). However, there
is no convenient way to extend the adjacency matrix to represent different kinds
of (weighted) relationships, nor relationships whose intensities change with time.
Tensors (3-dimensional matrices) could be used, with one layer for the adjacency
matrix of each kind or time, but this has not become a popular approach.
Adjacency matrices allow most kinds of social networks to be represented, and
the machinery of linear algebra can be used to manipulate them, and to prove theorems about their properties. However, they do not provide an easy way for humandirected presentation of the graph’s properties,
It is common to get the best of both the computational world and the drawing or
rendering world by using spectral embedding techniques. This family of algorithms
transform an adjacency matrix into one of a family of Laplacian matrices, compute
an eigendecomposition of this Laplacian, and then use a subset of the eigenvectors
7
1.3 Formally representing social networks
Social networks are usually modelled as graphs. A graph consists of a set of nodes
(or vertices) that represent the individuals, and a set of edges that connect nodes.
These edges represent the relationship between the individuals associated with the
nodes. Graphs are a natural way to represent networks, but they require awkward
data structures, and so are difficult to work with computationally.
From the perspective of a drawing of a graph, it is easy to see how to model rich
edge types. Each edge in the graph can be drawn with (say) a color that represents
the qualitative kind of relationship (colleague vs. friend) it represents; an arrow
to indicate the directionality of the relationship; and a positive or negative weight
or label to indicate the positive or negative intensity of the relationship. However,
temporal changes are already problematic unless the drawing becomes a video.
Direct renderings of a social network like this also do not scale as the number of nodes and edges increases. Even a small network, say 20 nodes, becomes
a cluttered picture from which conclusions might be hard to draw visually. And
there remains the challenging, and long-studied, problem of how to place the nodes
for maximal effectiveness of the rendering (that is, for maximal interpretability by
human eyes) [95].
For more mathematical analysis, it is conventional to represent a graph by an
adjacency matrix. If the graph contains n nodes, its adjacency matrix is an n × n
structure where the entries are zeros except at positions (i, j) whenever node i has a
connection to node j.
For a simple social network, the i jth entry of the adjacency matrix is set to a
1 to indicate the existence of a connection between nodes i and j. If the edges are
undirected, a connection from node i to node j necessitates a connection from node
j to node i, so that the i jth and jith entries must always be the same. The adjacency
matrix is then said to be symmetric.
It is easy to extend the adjacency matrix representation to allow edges to be
positively or negatively weighted, by using the weight as the value in the corresponding entry of the adjacency matrix.
It is also easy to model directed edges (for then the i jth entry represents the
edge from node i to node j and the jith entry the reverse edge). However, there
is no convenient way to extend the adjacency matrix to represent different kinds
of (weighted) relationships, nor relationships whose intensities change with time.
Tensors (3-dimensional matrices) could be used, with one layer for the adjacency
matrix of each kind or time, but this has not become a popular approach.
Adjacency matrices allow most kinds of social networks to be represented, and
the machinery of linear algebra can be used to manipulate them, and to prove theorems about their properties. However, they do not provide an easy way for humandirected presentation of the graph’s properties,
It is common to get the best of both the computational world and the drawing or
rendering world by using spectral embedding techniques. This family of algorithms
transform an adjacency matrix into one of a family of Laplacian matrices, compute
an eigendecomposition of this Laplacian, and then use a subset of the eigenvectors