Network Science

2Subnetwork Analysis

2.1 Introduction

An important concept in graph theory is the concept assigned to subgraphs. A subgraph of a graph is a smaller portion of that original graph. For example, if H is a subgraph of G and i and j are nodes of H, by the definition of a subgraph, the nodes i and j are also nodes of the original graph G. However, a critical concept in subgraphs needs to be highlighted. If the nodes i and j are adjacent in G, which means that they are connected by a link between them, then the definition of a subgraph does not necessarily require that the link joining the nodes i and j in G is also a link of H. If the subgraph H has the property that whenever two of its nodes are connected by a link in G, this link is also a link in H, then the subgraph H is called an induced subgraph.

For example, the three graphs shown in Figure 2.1 describe (a) a graph, (b) a subgraph, and (c) an induced subgraph.

Notice that the subgraphs in (b) and (c) have the same subset of nodes. However, the subgraph (b) misses all the links between their nodes. Subgraph (c) has the original links between the subset of nodes from the original graph. For that reason, the subgraph (c) is an induced subgraph.

The idea of working with subgraphs is simple and straightforward. If all the nodes and links we are interested in analyzing are in the graph, we have the whole network to perform the analysis. However, from the entire data collected to perform the network analysis, we may often be interested ...