Chapter 3
Background
Having provided some intuition for the kinds of constructions we will be using, we
now introduce the mathematical notation and constructions more formally.
3.1 Graph theory background
A graph G = (V, E) consists of a set of vertices V = {v 1 , ..., v n } and edges E =
{e 1 , ..., e k }, where e x = {v i , v j }, that connect pairs of vertices. Vertices can also be
called nodes, a more common usage in the social network literature.
There are various special kinds of graphs:
Undirected graph: A graph is undirected when the edges between vertices have no
orientation, so that if {v i , v j } exists, so does {v j , v i }. These are often called undirected edges.
Directed graph: A graph is directed when the existence of {v i , v j } does not necessarily imply the existence of {v j , v i }. Such an edge is called a directed edge.
Unweighted graph: A graph is unweighted when the only property of an edge is its
existence. The edge is typically modelled as having weight 1 if it exists and weight
0 if it does not.
Weighted graph: A graph is weighted when each edge has an associated positive
numerical value representing, in some way, an intensity associated with that edge.
Signed graph: A weighted graph is signed when its edge weights can also be negative numerical values, representing an intensity associated with antipathy or opposition.
Simple graph: A graph is simple when it has no self-loops (edges that start and end
at the same vertex) and no more than one edge between any two different vertices.
Multigraph: A graph is a multigraph when self-loops and multiple edges between
the same pair of vertices are allowed. A directed graph is not normally considered
a multigraph since multiple edges between the same pair of nodes go in different
directions, but a signed graph must implicitly be a multigraph because it is possible
17
Background
Having provided some intuition for the kinds of constructions we will be using, we
now introduce the mathematical notation and constructions more formally.
3.1 Graph theory background
A graph G = (V, E) consists of a set of vertices V = {v 1 , ..., v n } and edges E =
{e 1 , ..., e k }, where e x = {v i , v j }, that connect pairs of vertices. Vertices can also be
called nodes, a more common usage in the social network literature.
There are various special kinds of graphs:
Undirected graph: A graph is undirected when the edges between vertices have no
orientation, so that if {v i , v j } exists, so does {v j , v i }. These are often called undirected edges.
Directed graph: A graph is directed when the existence of {v i , v j } does not necessarily imply the existence of {v j , v i }. Such an edge is called a directed edge.
Unweighted graph: A graph is unweighted when the only property of an edge is its
existence. The edge is typically modelled as having weight 1 if it exists and weight
0 if it does not.
Weighted graph: A graph is weighted when each edge has an associated positive
numerical value representing, in some way, an intensity associated with that edge.
Signed graph: A weighted graph is signed when its edge weights can also be negative numerical values, representing an intensity associated with antipathy or opposition.
Simple graph: A graph is simple when it has no self-loops (edges that start and end
at the same vertex) and no more than one edge between any two different vertices.
Multigraph: A graph is a multigraph when self-loops and multiple edges between
the same pair of vertices are allowed. A directed graph is not normally considered
a multigraph since multiple edges between the same pair of nodes go in different
directions, but a signed graph must implicitly be a multigraph because it is possible
17