- 1 Introduction
- 2 Graph Theory
- 3 Ties and Graphs
- 4 Matrices
- 4.1 From Graph to Matrix
- 4.2 Relationship Matrices
- 4.3 The Symmetric Adjacency Matrix
- 4.4 The Asymmetric Adjacency Matrix
- 4.5 The Valued Adjacency Matrix
- 4.6 The Reachability Matrix
- 4.7 The Distance Matrix
- 4.8 The Shortest Paths Matrix
- 4.9 The Neighborhood Overlap Matrix
- 4.10 Matrix Operations
- 4.11 Matrix Powers
- 4.12 Practice Problems

- 5 Graph Metrics
- 6 Centrality
- 7 Ego Nets Metrics
- 8 Affiliation Nets
- 8.1 Affiliations and Bipartite Graphs
- 8.2 Unipartite Projections of Bipartite Graphs
- 8.3 The Affiliation Matrix
- 8.4 Group and Person Centralities
- 8.5 The Affiliation Matrix Transpose
- 8.6 The Person and Group Overlap Matrices
- 8.7 One Mode Projections of Two Mode Networks
- 8.8 Advanced Centrality Notions
- 8.9 Advanced Node Overlap Notions

Consider the graph shown in Figure 2.4 again. If all the actors that you are interested in studying are included here, we would refer to it as the **whole network**. However, sometimes, even when we collect data on a large number of actors we may be interested in analyzing not the whole network, but only some parts of it. How do we do that?

Figure 2.5: A subgraph of an undirected graph

Well, good thing that a graph is actually a set of two sets. If you remember your high school set theory, you can always take a set and consider only a **subset** of the original members.

Since graphs are sets, we can do the same thing. A subset of the original nodes (or edges) of a graph, is called a **subgraph**. So if \(G =\{E,V\}\) is the original graph, the subgraph \(G' = \{E',V'\}\) is a subset of \(G\), which is written \(G \subset G'\), with the understanding that \(E' \subset E\) and \(V' \subset V\).

Figure 2.6: Another subgraph of an undirected graph

For instance, let’s say we were interested in just analyzing actors *A*, *B*, *D*, and *F* in the graph shown in 2.4. They seem to be a close-knit group of people. In that case, as noted earlier, if we call the original graph \(G\) with vertex and edge sets \(\{E, V\}\)we can define a new subgraph \(G'\), whose node subset \(V'\) only includes the actors we are interested in studying, in this case \(V' = \{A, B, D, F\}\), where \(V' \subset V\).

The subgraph \(G'\) is shown in Figure 2.5. It looks exactly like we wanted, capturing the relations between an inter-connected subgroup of actors in the original graph.8 As we will see later, well-connected subgroups of actors of an original graph are called a **cohesive subset**. Note that the edge set of the subgraph \(E'\) only includes those edges that are incident to the other nodes in the subgraph and omits those in the original graph that connect to nodes that are not in the subgraph, so \(E' \subset E\).

Additionally, for any graph, we can define a subgraph based on *any* old random subset of the original node set. It is completely up to us. For instance, we could define a new subgraph \(G''\) of the original graph shown in Figure 2.4, that includes the node set \(V'' = \{C, E, F\}\). That is shown in Figure 2.6. That subgraph is weird and probably not very useful, but it is a subgraph of the original graph anyways!

There is an important difference between the subgraphs shown in Figures 2.5 and 2.6 that will prove important in later discussions. In particular, note that every node in the subgraph shown in Figure 2.5 is linked to the other nodes. When a subgraph of a graph has this property, we say that it is a **connected subgraph** of the original graph. This is the not case for the subgraph shown in Figure 2.6 where node *C* is isolated from (not adjacent to) nodes *E* and *F*. So this subgraph is a **disconnected subgraph** of the original graph.

Just like we can define subgraphs based on the node set of a graph, we can define subgraphs based on subsets of the original edge set. For instance, we could pick the edges \(E' = \{AB, AC, AF\}\) and define a subgraph based on them, which will necessarily include node set \(V' = \{A, B, C, F\}\).

When a subgraph is defined according to a subset of nodes, which is the more common case, it is called a **node induced subgraph** of the original graph. When a subgraph is defined by picking a subset of edges, it is called (you guessed it) an **edge induced subgraph** of the original graph.

A common reason for defining subgraphs in social network analysis is when we wonder what a network would look like if were to get rid of one actor in it. Sometimes this is useful, when we want to get a sense of how important an actor is for holding the network together. So it is possible to define a subgraph by *deleting* a node (or an edge). This is written \(G' = G - i\), where *i* is the name of the node we are deleting. So this says “give me a subgraph *G’* that is equal to the original graph *G* minus node *i*.”

Figure 2.7: Yet another subgraph of an undirected graph

For instance, Figure 2.7, shows the subgraph that results when we delete node *A* from the graph in Figure 2.4: \(G' = G-A\). This is called a **vertex-deleted subgraph** of the original graph. If we had defined the subgraph by removing a single-edge instead (\(G' = G - ij\)), then it would be called an **edge-deleted subgraph** of the original graph.

As we will see later, subgraphs (as well as vertex and edge deletion) are a useful concept for discussing levels at an “in-between” levels, above the node level but “below” the whole network level (see Figure 1.9 in Chapter 1): Communities, groups, and motifs. However, subgraphs are also useful for network concepts at the node level, because there is a special type of subgraph, called the **ego graph** that is defined by picking a central node and the nodes that are connected to it.