NETWORK Procedure

The (unweighted) degree (valency) of a node j in an undirected graph is the number of links that are incident to node j, with self-links counted twice. The out-degree of a node in a directed graph is the number of out-links incident to that node; the in-degree is the number of in-links incident to that node. For an undirected graph, the terms degree and out-degree are interchangeable. Degree centrality is simply the in- or out-degree of a node and can be interpreted as some form of the node’s relative importance to a network. For example, in a network where nodes are people and you are tracking the flow of a virus, the degree centrality gives some idea of the magnitude of the risk of spreading the virus. People who have a higher out-degree can lead to faster and more widespread transmission. In a friendship network, in-degree often indicates popularity.

The weighted degree of a node is a generalization of degree; it is the sum of the link weights incident to that node. For unweighted graphs, the default weight of each link is 1.

For undirected graphs, degree centrality is

where represents the set of links that are incident to node i, and is the weight of link e.

For directed graphs, out-degree centrality of node i is

where represents the set of outgoing links that are connected from node i.

For directed graphs, in-degree centrality of node i is

where represents the set of incoming links that are connected to node i.

The overall degree centrality for a directed graph is calculated as

Degree centrality is calculated using the value of the DEGREE= option in the CENTRALITY statement. To specify a distributed graph algorithm, you can set DISTRIBUTED=TRUE in the PROC NETWORK statement.

The algorithm that PROC NETWORK uses to compute degree centrality runs in time , and therefore should scale to very large graphs.

proc network
   direction  = directed
   links      = mylib.LinkSetIn
   outNodes   = mylib.NodeSetOut;
   centrality
      degree  = weight;
run;

Influence centrality is a generalization of degree centrality that considers the link and node weights of adjacent nodes () in addition to the link weights of nodes that are adjacent to adjacent nodes (). The metric is referred to as first-order influence centrality, and the metric is referred to as second-order influence centrality.

For undirected graphs, influence centrality is

where represents the set of links that are incident to node i, represents the multiset of neighbors (that is, nodes that are connected by links incident with node i), is the weight of link e, and is the weight of node i.

For directed graphs, influence centrality is

where represents the set of outgoing links that are connected from node i and represents the multiset of out-neighbors (that is, nodes that are connected by outgoing links from node i).

As the name suggests, this metric indicates potential influence, performance, or ability to transfer knowledge. Influence centrality is calculated using the value of the INFLUENCE= option in the CENTRALITY statement.

The algorithm that PROC NETWORK uses to compute influence centrality is a simple traversal, runs in time , and therefore should scale to very large graphs.

proc network
   direction    = directed
   links        = mylib.LinkSetIn
   outNodes     = mylib.NodeSetOut;
   centrality
      influence = unweight;
run;

The local clustering coefficient of a node is the number of links between the nodes within its neighborhood divided by the number of links that could possibly exist between them (their induced complete graph). The local clustering coefficient metric is often referred to as transitivity.

The formula for the clustering coefficient is

when DIRECTION=UNDIRECTED, or

when DIRECTION=DIRECTED, where represents the set of neighbors, excluding node i itself (that is, unique nodes that are connected by links, excluding self-links, incident with node i); represents the set of out-neighbors, excluding node i itself (that is, unique nodes that are connected by outgoing links, excluding self-links, from node i); and specifies whether or not (1 or 0, respectively) a link from node j to node k exists in the link set E, as follows:

The definition of the local clustering coefficient for undirected graphs is closely related to the global triangle count, which is given by

When DIRECTION=UNDIRECTED, this count is reported in the NUM_TRIANGLES term of the macro variable _NETWORK_.

In PROC NETWORK, the calculation of local clustering coefficient considers only binary networks. Weights and multilinks are ignored in the metric.

For a particular node, the clustering coefficient determines how close the subgraph that is induced by its neighbor set is to being a complete subgraph. In social networks, a high clustering coefficient can help predict relationships that might not be known, confirmed, or realized yet. Consider a social network of four people, where person A knows persons B, C, and D, person B knows person C, and person C knows person D. This does not guarantee that person B knows person D, but it is more likely that person B knows person D than that person B knows some random person.

The clustering coefficient is calculated when you specify the CLUSTERINGCOEFFICIENT option in the CENTRALITY statement.

The algorithm that PROC NETWORK uses to compute the clustering coefficient runs in time . Therefore, this algorithm is not expected to scale to very large graphs.

Clustering Coefficient of an Undirected Graph

Consider the three undirected graphs on four nodes shown in Figure Three Undirected Graphs.

Figure 58: Three Undirected Graphs

Graph 1	Graph 2	Graph 3

Define the three links data tables as follows:

data mylib.LinkSetInCC1;
   input from $ to $ @@;
   datalines;
A B  A C  A D
B C  B D  C D
;

data mylib.LinkSetInCC2;
   input from $ to $ @@;
   datalines;
A B  A C  A D
C D
;

data mylib.LinkSetInCC3;
   input from $ to $ @@;
   datalines;
A B  A C  A D
;

The following statements use three calls to PROC NETWORK to calculate the clustering coefficients of each graph:

proc network
   links     = mylib.LinkSetInCC1
   outNodes  = mylib.NodeSetOut1;
   centrality
      clusteringCoef;
run;

proc network
   links     = mylib.LinkSetInCC2
   outNodes  = mylib.NodeSetOut2;
   centrality
      clusteringCoef;
run;

proc network
   links     = mylib.LinkSetInCC3
   outNodes  = mylib.NodeSetOut3;
   centrality
      clusteringCoef;
run;

The nodes data tables provide the clustering coefficients for each node of each input graph, as shown in Figure 59 through Figure 61.

Figure 59: Clustering Coefficient of an Undirected Graph 1

node	centr_cluster
A	1
B	1
C	1
D	1

Figure 60: Clustering Coefficient of an Undirected Graph 2

node	centr_cluster
C	1.00000
D	1.00000
A	0.33333
B	0.00000

Figure 61: Clustering Coefficient of an Undirected Graph 3

node	centr_cluster
A	0
B	0
C	0
D	0

Closeness centrality is the reciprocal of the average of the shortest path (geodesic) distances from a particular node to all other nodes. Closeness can be thought of as a measure of how long it takes information to spread from a particular node to other nodes in the network. The higher the closeness value of a particular node, the faster the information will spread from that node to other nodes.

Define to be the shortest path distance from node i to node j, with link weight defined by the AUXWEIGHT= option in the LINKSVAR statement. If the auxiliary link weight is not specified, then the link weight defaults to , where w represents the weight assigned by the WEIGHT= option in the LINKSVAR statement. By default, this means that a higher link weight implies a stronger relationship between its nodes (similar to other centrality metrics).

Closeness Centrality for an Undirected Graph

For an undirected graph, is the set of reachable nodes from node i. The set of unreachable nodes from node i is . The CLOSENOPATH= option specifies how to handle unreachable nodes.

For the special case in which all nodes are unreachable from node i, the closeness centrality is defined as 0. Otherwise, closeness centrality is calculated as

where p defines a penalty parameter for unreachable nodes, defines the number of nodes that are considered in calculating the average, and is a scaling factor, as shown in Table 11.

Table 11: Formulas for CLOSENOPATH= Option for Undirected Graphs

CLOSENOPATH=	p
DIAMETER			1
NNODES			1
ZERO	0

Closeness Centrality for a Directed Graph

For a directed graph, is the set of reachable nodes from node i, whereas is the set of nodes from which there is a finite path to node i. The set of unreachable nodes from node i is , whereas the set of nodes from which there is no finite path to node i is .

For the special case in which all nodes are unreachable from node i, the out-closeness centrality is defined as 0. Otherwise, out-closeness centrality is calculated as

where defines the number of nodes that are considered in calculating the average and is a scaling factor, as shown in Table 12.

For the special case in which node i is unreachable from all the other nodes, the in-closeness centrality is defined as 0. Otherwise, in-closeness centrality is calculated as

where defines the number of nodes that are considered in calculating the average and is a scaling factor, as shown in Table 12.

Table 12: Formulas for CLOSENOPATH= Option for Directed Graphs

CLOSENOPATH=
DIAMETER		1		1
NNODES		1		1
ZERO

The overall closeness centrality for directed graphs is calculated as

Harmonic Centrality

Harmonic centrality, as described in Rochat (2009), is a variant of closeness centrality that attempts to simplify the treatment of unreachable nodes by calculating the average of the reciprocal of the shortest path distances from a particular node to all the other nodes. The formula for harmonic centrality is

To enable the calculation of harmonic centrality, use the CLOSENOPATH=HARMONIC option.

Closeness centrality is calculated using the value of the CLOSE= option in the CENTRALITY statement. If CLOSE=WEIGHT (or BOTH), then the shortest paths are calculated with respect to the weighted graph. Because the metric uses shortest paths to determine closeness, the weight and the closeness metric are inversely related. In general, the lower the weight, the higher the contribution to the closeness metric.

The algorithm that PROC NETWORK uses to compute closeness centrality relies on calculating shortest paths for all source-sink pairs and runs in time . Therefore, this algorithm is not expected to scale to very large graphs. Because the shortest path calculations can be computed independently (for each source node), the algorithm uses multiple threads and multiple machines (depending on your session configuration and license).

proc network
   direction  = directed
   links      = mylib.LinkSetIn
   outNodes   = mylib.NodeSetOut;
   centrality
      close   = both;
run;

Betweenness centrality counts the number of times a particular node (or link) occurs in shortest paths between other nodes. Betweenness can be thought of as a measure of the control that a node (or link) has over the communication flow through the rest of the network. In this sense, the nodes (or links) that have high betweenness are the gatekeepers of information, because of their relative location in the network.

The formula for node betweenness centrality is

when DIRECTION=UNDIRECTED, or

when DIRECTION=DIRECTED, where is the number of shortest paths from s to t and is the number of shortest paths from s to t that pass through node i. As with closeness centrality, the shortest path is calculated with respect to the link weight that is defined by the AUXWEIGHT= option in the LINKSVAR statement. If the auxiliary link weight is not specified, then the link weight defaults to , where w represents the weight that is assigned by the WEIGHT= option in the LINKSVAR statement. By default, this means that a higher link weight implies a stronger relationship between the link’s nodes.

By default, this metric is normalized by dividing by , the number of links in the complete graph on node set . You can disable this normalization by using the BETWEENNORM= option.

The formula for link betweenness centrality is

when DIRECTION=UNDIRECTED, or

when DIRECTION=DIRECTED, where is the number of shortest paths from s to t that pass through link .

By default, this metric is normalized by dividing by , the number of links in the complete graph on node set N. You can disable this normalization by using the BETWEENNORM= option.

For directed graphs, because the paths are directed, only the out-betweenness is computed. To get the in-betweenness, you must reverse all the directions of the graph and run the procedure again. You can accomplish this by simply using the LINKSVAR statement to reverse the interpretation of from and to.

Betweenness centrality is calculated using the value of the BETWEEN= option in the CENTRALITY statement. As with closeness centrality, if BETWEEN=WEIGHT (or BETWEEN=BOTH), then the calculation of shortest paths is performed using the weighted graph.

The algorithm that PROC NETWORK uses to compute betweenness centrality relies on calculating shortest paths for all source-sink pairs and runs in time . Therefore, it is not expected to scale to very large graphs. As with closeness centrality, because shortest path computations can be calculated independently (for each source node), the algorithm uses multiple threads and multiple machines (depending on your session configuration and license). When closeness and betweenness centrality are run together, PROC NETWORK calculates both metrics in one pass.

You can compute an approximation of betweenness centrality by using the SAMPLEPERCENT= option in the CENTRALITY statement (AlGhamdi et al. 2017). The value that you specify for this option (p) defines the percentage of source nodes to use in calculating shortest paths. In this case the algorithm runs in time . If , then PROC NETWORK computes betweenness centrality exactly.

proc network
   direction  = directed
   links      = mylib.LinkSetIn
   outLinks   = mylib.LinkSetOut
   outNodes   = mylib.NodeSetOut;
   centrality
      between = both;
run;

Eigenvector centrality is an extension of degree centrality in which centrality points are awarded for each neighbor. However, not all neighbors are equally important. Intuitively, a connection to an important node should contribute more to the centrality score than a connection to a less important node. This is the basic idea behind eigenvector centrality. The eigenvector centrality of a node is defined to be proportional to the sum of the scores of all nodes that are connected to it. Mathematically, it is represented as

when DIRECTION=UNDIRECTED, or

when DIRECTION=DIRECTED, where is the eigenvector centrality of node i, is the sum of the weights of links from node i to node j, and is a constant.

The right eigenvector equation in matrix form can be written as:

where, for an undirected graph, represents the (symmetric) adjacency matrix that corresponds to the link weights in E, or for a directed graph, , represents the adjacency matrix that corresponds to the outgoing link weights in E. To calculate the left eigenvector, which corresponds to the incoming link weights, switch the orientation of the from and to variables in the data table by using the LINKSVAR= statement. In constructing the matrix , the weights of multilinks are aggregated. Eigenvector centrality is defined as the principal eigenvector that corresponds to the largest eigenvalue .

To solve this eigenvector problem, PROC NETWORK provides two algorithms: the Jacobi-Davidson algorithm and the power method. You can use the EIGENALGORITHM= option in the CENTRALITY statement to specify which algorithm to use. EIGENALGORITHM=JACOBIDAVIDSON, which is the default, specifies the Jacobi-Davidson algorithm for solving large-scale eigenvalue problems (Sleijpen and van der Vorst 2000). The power method is one of the standard algorithms for solving eigenvalue problems, but it converges slowly for certain problems.

Eigenvector centrality is calculated using the value that you specify in the EIGEN= option in the CENTRALITY statement.

Eigenvector Centrality of an Undirected Graph

The following example illustrates the use of eigenvector centrality on the undirected graph G shown in Figure 65.

Figure 65: Eigenvector Centrality Example of an Undirected Graph

The graph can be represented by the following links data table, mylib.LinkSetIn:

data mylib.LinkSetIn;
   input from $ to $ @@;
   datalines;
A D  B C  B D  B E  B F
B I  B J  E F  E G  E H
;

The following statements compute the eigenvector centrality:

proc network
   links      = mylib.LinkSetIn
   outNodes   = mylib.NodeSetOut;
   centrality
      eigen   = unweight;
run;

The output data table mylib.NodeSetOut now contains the eigenvector centrality of each node, as shown in Figure 66.

Figure 66: Eigenvector Centrality Output

node	centr_eigen_unwt
B	1.00000
E	0.75919
F	0.61981
D	0.40226
I	0.35233
J	0.35233
C	0.35233
G	0.26749
H	0.26749
A	0.14173

Even though nodes F and D both have the same degree of 2, node F has a higher eigenvector centrality than node D. This is because node F links to two important nodes (B and E), whereas node D links to one important node (B) and one unimportant node (A).

For a more detailed example, see Example 2.5: Eigenvector Centrality for Word Sense Disambiguation.

Hub and authority centrality was originally developed by Kleinberg (1998) to rank the importance of web pages. Certain web pages (called hubs) are important in the sense that they point to many important pages. On the other hand, some web pages (called authorities) are important because they are pointed to by many important pages. In other words, a good hub node is one that points to many good authorities, and a good authority node is one that is pointed to by many good hub nodes. This idea can be applied to many other types of graphs besides web pages. For example, you can apply it to a citation network for journal articles. A review article that cites many good authority papers has a high hub score, whereas a paper that is referenced by many other papers has a high authority score. The section Authority in US Supreme Court Precedent presents a similar example.

The authority centrality of a node is proportional to the sum of the hub centrality of nodes that point to it. Similarly, the hub centrality of a node is proportional to the sum of the authorities of nodes that it points to. That is,

where is the authority centrality of node i, is the hub centrality of node j, is the sum of the weights of links from node i to node j, and and are constants.

Similar to eigenvector centrality, the definitions of authority and hub centrality can be written in matrix form as

where represents the adjacency matrix that corresponds to the outgoing link weights in E and represents the adjacency matrix that corresponds to the incoming link weights in E. In constructing the matrices and , the weights of multilinks are aggregated.

Combining the two equations results in

where . Thus, the authority and hub centralities are the principal eigenvectors of and , respectively.

To solve this eigenvector problem, PROC NETWORK provides two algorithms: the Jacobi-Davidson algorithm and the power method. You can use the EIGENALGORITHM= option in the CENTRALITY statement to specify which algorithm to use. EIGENALGORITHM=JACOBIDAVIDSON, which is the default, specifies the Jacobi-Davidson algorithm for solving large-scale eigenvalue problems (Sleijpen and van der Vorst 2000). The power method is one of the standard algorithms for solving eigenvalue problems, but it converges slowly for certain problems.

Hub and Authority Centrality of a Directed Graph

The following example illustrates the use of hub and authority scoring on the directed graph G shown in Figure 67. Each node represents a web page. If web page i has a hyperlink that points to web page j, then there is a directed link from i to j.

Figure 67: Hub and Authority Centrality Example of a Directed Graph

The graph can be represented by the following links data table, mylib.LinkSetIn:

data mylib.LinkSetIn;
   input from $ to $ @@;
   datalines;
B C  C B  D A  D B  E B
E D  E F  F B  F E  G E
H E  I E  I B  J E  J B
K B  K E
;

The following statements compute hub and authority centrality:

proc network
   direction   = directed
   links       = mylib.LinkSetIn
   outNodes    = mylib.NodeSetOut;
   centrality
      hub      = unweight
      auth     = unweight;
run;

The output data table mylib.NodeSetOut now contains the hub and authority scores of each node, as shown in Figure 68.

Figure 68: Hub and Authority Centrality Output

node	centr_hub_unwt	centr_auth_unwt
K	1.00000	0.00000
F	1.00000	0.11466
I	1.00000	0.00000
J	1.00000	0.00000
E	0.66549	0.84725
D	0.59703	0.11466
C	0.54135	0.00000
G	0.45865	0.00000
H	0.45865	0.00000
A	0.00000	0.10287
B	0.00000	1.00000

The output shows that nodes B and E have high authority scores because they have many incoming links. Nodes F, I, J, and K have high hub scores because they all point to good authority nodes B and E.

PageRank centrality, named after Google’s cofounder Larry Page, was originally proposed for the application of ranking web pages in a search engine.

The PageRank algorithm models the stationary distribution of a Markov process, assuming that each node is a web page and each link is a hyperlink from one page to another. A web surfer might choose a random link on every page or might jump to a random page on the whole web with some probability. The PageRank of a web page is the percentage of time the surfer spends on the page. Mathematically, it is defined as

where is the PageRank score of node i, is the sum of the weights of links from node i to node j, is a damping factor, and

is the sum of the outbound link weights from node i.

For the calculation of PageRank centrality, PROC NETWORK implements a version of the power method, as described in Langville and Meyer (2006). The damping factor , which you can specify in the PAGERANKALPHA= option in the CENTRALITY statement, is an important concept in the PageRank algorithm. In the PageRank equation, represents the probability of jumping to a random page. Without the damping factor, pages that have no incoming links would have a PageRank score of zero, so these pages cannot be distinguished by PageRank scores. The damping factor also affects the convergence of the power method. Typically, many more iterations are required as the damping factor is set closer to 1.

When the PageRank algorithm is applied to undirected graphs, each undirected link is treated as two directed links that go in both directions.

proc network
   direction   = directed
   links       = mylib.LinkSetIn
   outNodes    = mylib.NodeSetOut;
   centrality
      pagerankAlpha = 0.85
      pagerank      = unweight;
run;

proc network
   direction   = directed
   links       = mylib.LinkSetIn
   outNodes    = mylib.NodeSetOut;
   centrality
      pagerankAlpha = 0.999
      pagerank      = unweight;
run;