Chapter 2
The core model
In this chapter, we introduce the key technique that we will develop and use to analyze social networks with rich semantics for the relationships between nodes. This
will include all of the possibilities mentioned in the previous chapter: qualitatively
different types of relationships, asymmetric relationship intensities, positive and negative relationships, and relationships that vary with time.
2.1 Representing networks to understand their
structures
As we mentioned in Chapter 1, there are two main ways in which a social network,
captured as a graph, can be understood. These methods can handle graphs whose
edges are positively weighted and undirected — adding other features is already
beyond their capabilities.
The first main way to understand a graph is graph drawing, collections of algorithmic ways to display, visualize, or render a graph in a way that humans can directly
and easily understand. Graph drawing algorithms try to place the nodes so that any
groupings that might be present are made obvious, so that nodes do not obscure one
another, and so that edges are as uncluttered as possible. A simple intuition gives
the flavor of these algorithms. Suppose that the nodes of the graph are connected
by elastic bands whose pull is proportional to the weight of the corresponding edge
(relationship) and that a gentle uniform outward pull is applied from all directions
at once. The positions at which the outward pull on each node exactly balances the
pulls from all of the other nodes are probably a good approximation to the structure of the graph. These positions can then be tweaked locally to remove occlusions
and clutter. Of course, these algorithms work best for graphs that are close to planar, which many real-world graphs are, for example power grids and transportation
networks. They perform less well when the graph is naturally high dimensional.
The problem with the graph-drawing approach is: in how many dimensions
9
The core model
In this chapter, we introduce the key technique that we will develop and use to analyze social networks with rich semantics for the relationships between nodes. This
will include all of the possibilities mentioned in the previous chapter: qualitatively
different types of relationships, asymmetric relationship intensities, positive and negative relationships, and relationships that vary with time.
2.1 Representing networks to understand their
structures
As we mentioned in Chapter 1, there are two main ways in which a social network,
captured as a graph, can be understood. These methods can handle graphs whose
edges are positively weighted and undirected — adding other features is already
beyond their capabilities.
The first main way to understand a graph is graph drawing, collections of algorithmic ways to display, visualize, or render a graph in a way that humans can directly
and easily understand. Graph drawing algorithms try to place the nodes so that any
groupings that might be present are made obvious, so that nodes do not obscure one
another, and so that edges are as uncluttered as possible. A simple intuition gives
the flavor of these algorithms. Suppose that the nodes of the graph are connected
by elastic bands whose pull is proportional to the weight of the corresponding edge
(relationship) and that a gentle uniform outward pull is applied from all directions
at once. The positions at which the outward pull on each node exactly balances the
pulls from all of the other nodes are probably a good approximation to the structure of the graph. These positions can then be tweaked locally to remove occlusions
and clutter. Of course, these algorithms work best for graphs that are close to planar, which many real-world graphs are, for example power grids and transportation
networks. They perform less well when the graph is naturally high dimensional.
The problem with the graph-drawing approach is: in how many dimensions
9