NETWORK Procedure

An alternative to community detection for finding cohesive subgroups is a method of extracting k-cores known as core decomposition. Although this method is generally not as powerful as community detection for extracting a detailed community structure, it can provide a coarse approximation of cohesive structure at a very low computational cost. Let define a graph that contains nodes N and links E, and let be an induced subgraph on node set S. The subgraph is a k-core if and only if for every node , the degree of j is greater than or equal to k, and is the maximum subgraph with this property. By definition, the cores are nested. That is, if is a k-core of size k, then is contained in .

In PROC NETWORK, you can invoke core decomposition by using the CORE statement. The options for this statement are described in the section CORE Statement.

The results of the core decomposition algorithm are given in 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 core_out identifies its core number, the highest-order core that contains this node.

The algorithm that is used for core decomposition is based on the work presented in Batagelj and Zaversnik (2003). This algorithm runs in time and therefore should scale to very large graphs.

Core Decomposition of an Undirected Graph

This section illustrates the use of the core decomposition algorithm on the undirected graph G shown in Figure 92.

Figure 92: Undirected Graph

The undirected graph G can be represented using the following nodes data table, mylib.NodeSetIn, and links data table, mylib.LinkSetIn:

data mylib.NodeSetIn;
   input node $ @@;
   datalines;
v1    v2   v3   v4   v5
v6    v7   v8   v9  v10
v11  v12  v13  v14  v15
v16  v17  v18  v19
;

data mylib.LinkSetIn;
   input from $ to $ @@;
   datalines;
v1   v2   v5  v6   v6  v7   v7  v8  v10 v11
v2   v3   v3  v4   v2  v4   v8  v9   v9 v10
v8  v18  v10 v12  v13 v14  v13 v15  v13 v16
v13 v17  v14 v15  v14 v16  v14 v17  v15 v16
v15 v17  v16 v17  v18 v13  v18 v17  v18 v16
v12 v14  v12 v15  v12 v16
;

The following statements calculate the core decomposition and output the results in the data table mylib.NodeSetOut:

proc network
   nodes    = mylib.NodeSetIn
   links    = mylib.LinkSetIn
   outNodes = mylib.NodeSetOut;
   core;
run;

The nodes output data table mylib.NodeSetOut contains the core number (variable core_out) for each node, as shown in Figure 93.

Figure 93: Core Decomposition of an Undirected Graph

node	core_out
v19	0
v1	1
v11	1
v5	1
v6	1
v7	1
v10	2
v2	2
v3	2
v4	2
v8	2
v9	2
v12	3
v18	3
v13	4
v14	4
v15	4
v16	4
v17	4

Figure 94 shows the graph layered by its core number.

Figure 94: Core Decomposition