20
Chapter 3. Background
Figure 3.1: The eigendecomposition of the cloud of points corresponding to graph
nodes. Only the first eigenvector reveals anything about the graph’s structure.
It is possible that other eigenvalues at the right-hand end of the spectrum are
zero as well — the number of such zero-valued eigenvalues corresponds to the number of connected components in the graph. We will assume, for simplicity, that the
social networks we consider contain only a single component, and the constructions
we use tend to make the constructed graphs connected anyway.
The rightmost eigenvector corresponding to a non-zero eigenvalue is known as
the Fiedler vector of the graph [34] and represents the best 1-dimensional embedding of the graph, that is an embedding in which the nodes are placed on a line. This
embedding is best in the sense that the distances between the embedded nodes corresponds as closely as possible to the similarities between them (Euclidean distance
is small when nodes are similar).
A k-dimensional embedding can be constructed using the eigenvectors associated with the n − 1 to n − k smallest eigenvalues as coordinates. As before, distances
in this k-dimensional space reflect (dis)similarity. Euclidean distances can be computed between pairs of nodes, whether connected or not, and geometric clustering
algorithms such as K-means, Expectation-Maximization, hierarchical clustering, and
others can be applied to the embedded nodes.
If k = 2 or 3, then direct visualization of the graph can also be carried out.
This will be more accurate, but typically less immediately intelligible, than a graphdrawing algorithm would produce.
Chapter 3. Background
Figure 3.1: The eigendecomposition of the cloud of points corresponding to graph
nodes. Only the first eigenvector reveals anything about the graph’s structure.
It is possible that other eigenvalues at the right-hand end of the spectrum are
zero as well — the number of such zero-valued eigenvalues corresponds to the number of connected components in the graph. We will assume, for simplicity, that the
social networks we consider contain only a single component, and the constructions
we use tend to make the constructed graphs connected anyway.
The rightmost eigenvector corresponding to a non-zero eigenvalue is known as
the Fiedler vector of the graph [34] and represents the best 1-dimensional embedding of the graph, that is an embedding in which the nodes are placed on a line. This
embedding is best in the sense that the distances between the embedded nodes corresponds as closely as possible to the similarities between them (Euclidean distance
is small when nodes are similar).
A k-dimensional embedding can be constructed using the eigenvectors associated with the n − 1 to n − k smallest eigenvalues as coordinates. As before, distances
in this k-dimensional space reflect (dis)similarity. Euclidean distances can be computed between pairs of nodes, whether connected or not, and geometric clustering
algorithms such as K-means, Expectation-Maximization, hierarchical clustering, and
others can be applied to the embedded nodes.
If k = 2 or 3, then direct visualization of the graph can also be carried out.
This will be more accurate, but typically less immediately intelligible, than a graphdrawing algorithm would produce.