The NETWORK Procedure

A biconnected component (or block) of a graph is a connected subgraph that you cannot break into disconnected pieces by deleting any single node (and its incident links). An articulation point (or cut point) of a graph is a node whose removal would cause an increase in the number of connected components. Articulation points can be important when you analyze any graph that represents a communications network. Consider an articulation point that, if removed, breaks the graph into two components, and . All paths in G between some nodes in and some nodes in must pass through node i. In this sense, articulation points are critical to communication. Examples where articulation points are important include airline hubs, electric circuits, network wires, protein bonds, traffic routers, and many other industrial applications.

In PROC NETWORK, you can find biconnected components and articulation points of an input graph by using the BICONNECTEDCOMPONENTS statement. This algorithm works only with undirected graphs.

The results of the biconnected components algorithm are written to the output links data table that you specify in the OUTLINKS= option in the PROC NETWORK statement. For each link in the links data table, the variable biconcomp identifies its component. The component identifiers are numbered sequentially, starting from the value of the INDEXOFFSET= option in the PROC NETWORK statement. The results of the articulation points are written to the output nodes data table that you specify in the OUTNODES= option in the PROC NETWORK statement. For each node in the nodes data table, the variable artpoint is either 1 (if the node is an articulation point) or 0 (otherwise).

The block-cut tree of a given connected graph is an abstract representation of that graph in the form of a tree, where biconnected components, or blocks, are connected through articulation points, or cut points.

The nodes and links information of the block-cut tree is written to two data tables that you specify in the OUTBCTREENODES= and OUTBCTREELINKS= options in the BICONNECTEDCOMPONENTS statement. Additionally, a map from the nodes in the original graph to the nodes in the block-cut tree is written to the bcTree_node column of the OUTNODES= data table.

The algorithm that PROC NETWORK uses to compute biconnected components is a variant of the depth-first search algorithm (Tarjan 1972). This algorithm runs in time and therefore should scale to very large graphs.

Biconnected Components of an Undirected Graph

This section illustrates the use of the biconnected components algorithm on the undirected graph G that is shown in Figure 39.

Figure 39: Undirected Graph G

The undirected graph G can be represented by the following links data table, mycas.LinkSetInBiCC:

data mycas.LinkSetInBiCC;
   input from $ to $ @@;
   datalines;
A B  A F  A G  B C  B D
B E  C D  E F  G I  G H
H I
;

The following statements calculate the biconnected components and articulation points for G and output the results in the data tables mycas.LinkSetOut, mycas.NodeSetOut, and mycas.BiConCompOut:

proc network
   links    = mycas.LinkSetInBiCC
   outLinks = mycas.LinkSetOut
   outNodes = mycas.NodeSetOut;
   biconnectedComponents
      out   = mycas.BiConCompOut;
run;

The output data table mycas.LinkSetOut contains the biconnected components of the input graph, as shown in Figure 40.

Figure 40: Biconnected Components of an Undirected Graph

from	to	biconcomp
A	B	1
A	F	1
B	E	1
E	F	1
A	G	2
B	C	3
B	D	3
C	D	3
G	H	4
G	I	4
H	I	4

The output data table mycas.NodeSetOut contains the articulation points of the input graph, as shown in Figure 41.

Figure 41: Articulation Points of an Undirected Graph

node	artpoint
A	1
B	1
C	0
D	0
E	0
F	0
G	1
H	0
I	0

The output data table mycas.BiConCompOut contains the number of links in each biconnected component of the input graph, as shown in Figure 42.

Figure 42: Summary for the Biconnected Components of an Undirected Graph

biconcomp	links
1	4
2	1
3	3
4	3

The biconnected components are shown graphically in Figure 43 and Figure 44.

Figure 43: Biconnected Components and

Figure 44: Biconnected Components and

For a more detailed example, see Example 2.1: Articulation Points in a Terrorist Network.

Block-Cut Tree of an Undirected Graph

Consider again the undirected graph in Figure 39, which is represented by the links data table mycas.LinkSetInBiCC. The following statements calculate the block-cut tree and output the results in the data tables mycas.BCTreeNodesOut and mycas.BCTreeLinksOut. To indicate the mapping to the original node labels, the bcTree_node variable is added to the mycas.NodeSetOut data table.

proc network
   links    = mycas.LinkSetInBiCC
   outLinks = mycas.LinkSetOut
   outNodes = mycas.NodeSetOut;
   biconnectedComponents
      outBCTreeNodes  = mycas.BCTreeNodesOut
      outBCTreeLinks  = mycas.BCTreeLinksOut;
run;

The mycas.BCTreeNodesOut output data table contains the nodes in the block-cut tree, as shown in Figure 45.

Figure 45: Block-Cut Tree Nodes Data Table

node	artpoint
a_1	A
a_2	B
a_3	G
b_1
b_2
b_3
b_4

The mycas.BCTreeLinksOut output data table contains the links in the block-cut tree, as shown in Figure 46.

Figure 46: Block-Cut Tree Links Data Table

from	to
a_1	b_1
a_1	b_2
a_2	b_1
a_2	b_3
a_3	b_2
a_3	b_4

The mycas.NodeSetOut output data table contains the articulation points of the input graph as well as the bcTree_node variable, which indicates the map from nodes in the original graph to nodes in the block-cut tree, as shown in Figure 47.

Figure 47: Articulation Points and Block-Cut Tree Node Mappings

node	artpoint	bcTree_node
A	1	a_1
B	1	a_2
C	0	b_3
D	0	b_3
E	0	b_1
F	0	b_1
G	1	a_3
H	0	b_4
I	0	b_4

The block-cut tree is shown graphically in Figure 48.

Figure 48: Block-Cut Tree of the Undirected Graph G