![]()
Chapter 1: What is a Network?
Injustice anywhere is a threat to justice everywhere. We are caught in an inescapable network of mutuality tied in a single garment of destiny. Whatever affects one directly affects all indirectly.
Martin Luther King Jr., Letter from a Birmingham jail, April 16,1963
LearningObjectives
1. Understand social network terminology.
2. Construct an adjacency matrix.
3. Construct a network from given data.
In the movie, Good Will Hunting, the main character, Will Hunting, played by Matt Damon, is a janitor at a university. As he is mopping floors, he notices a problem posted on a board as a challenge to math students. The solution to the first two parts of the problem uses network analysis.
First Two Parts of the Good Will Hunting Problem
Let G be Figure 1.1 on the right.
- Find the adjacency matrix A of the graph G.
- Find the matrix giving the number of three-step walks for the graph G.
1.1 Basic Network Concepts
A network is a collection of points linked through some type of association. These points can represent any object or subject (e.g., people, places, and resources) and the links can represent any relationship between them (e.g., route, distance, family membership, and reporting structure). The network is graphically illustrated using lines, arcs, and symbols so the viewer can visualize and analyze the structure of the network more easily. A simple network of four points can be seen in Figure 1.1. In this network the points are people and the links are relationships between the people.
A graph is the visual representation of a set of points, frequently called vertices or nodes that are connected by line segments called edges or links. Social networks are graphs that contain a finite set or sets of actors which we call agents and the relation or relations defined between them. A social network would then be comprised of nodes representing people with the corresponding links representing the relationship between the people.
It is important to understand how to navigate through a network graph. The information gained can help us understand how information flow through a network can be used to analyze the placement of nodes within the network and gauge their significance. We will look at how to do this analysis in the next few chapters, but first we need to understand network graph navigation terminology.
Figure 1.1 has four vertices or nodes. Each node is a person. Moving from one node to another along a single edge or link that joins them is a
step. A
walk is a series of steps from one node to another. The number of steps is the
length of the walk. For instance, there is a walk of three steps from node 1 to node 3 using the steps 1 to 4, 4 to 2, and 2 to 3. A
trail is a walk in which all the links are distinct, although some nodes may be included more than once. The length of a trail is the number of links it contains. For example, the length of the trail between nodes 3 and 4 is 2, where 3 to 2 is the first link, and 2 to 4 is the second link. A
path is a walk in which all nodes and links are distinct. Note that every path is a trail and every trail is a walk. In application to social networks, we often focus on paths rather than trails or walks. An important property of a pair of nodes is whether or not there is a path between them. If there is a path between nodes
and
(say nodes 1 and node 4 in
Figure 1.1), then the nodes are said to be
reachable. A walk that begins and ends with the same node is called a
closed walk. A
cycle is a closed walk of at least three nodes. For example, the closed walk 1 to 4, 4 to 2, and 2 to 1 is a cycle as it contains three nodes and begins and ends with node 1. Cycles are important in the study of
balance and
clusterability in signed graphs (a topic we explore later in the book).
1.2 Adjacency Matrices, Graphs, and Notation
We have seen that social networks can be graphically depicted as graphs. Social networks can also be represented mathematically by matrices. For example,
Figure 1.2 is a
friendship graph representing friendship between a group of people. We can record how the people in the graph are related in a mathematical object known as an
adjacency matrix. The adjacency matrix in this case is a square (meaning same number of rows as columns) agent by agent matrix.
Table 1.1 is the adjacency matrix for
Figure 1.2. Mathematically, any network can be represented by an adjacency matrix, denoted by
A, which, in the simplest case, is a
symmetric matrix, where
is the number of vertices or nodes in the network. The adjacency matrix is comprised of elements
We often represent the entire matrix...
