efficiency: Compute Graph Efficiency Scores

In sna: Tools for Social Network Analysis

Compute Graph Efficiency Scores

Description

efficiency takes one or more graphs (dat) and returns the Krackhardt efficiency scores for the graphs selected by g.

Usage

efficiency(dat, g=NULL, diag=FALSE)

Arguments

dat	one or more graphs.
g	index values for the graphs to be utilized; by default, all graphs are selected.
diag	TRUE if the diagonal contains valid data; by default, diag==FALSE.

Details

Let G= G_1 U ... U G_n be a digraph with weak components G_1,G_2,...,G_n. For convenience, we denote the cardinalities of these components' vertex sets by |V(G)|=N and |V(G_i)|=N_i, for i in 1,...,n. Then the Krackhardt efficiency of G is given by

1 - ( |E(G)| - Sum(N_i-1,i=1,..,n) )/( Sum(N_i(N_i-1) - (N_i-1),i=1,..,n) )

which can be interpreted as 1 minus the proportion of possible “extra” edges (above those needed to weakly connect the existing components) actually present in the graph. A graph which an efficiency of 1 has precisely as many edges as are needed to connect its components; as additional edges are added, efficiency gradually falls towards 0.

Efficiency is one of four measures (connectedness, efficiency, hierarchy, and lubness) suggested by Krackhardt for summarizing hierarchical structures. Each corresponds to one of four axioms which are necessary and sufficient for the structure in question to be an outtree; thus, the measures will be equal to 1 for a given graph iff that graph is an outtree. Deviations from unity can be interpreted in terms of failure to satisfy one or more of the outtree conditions, information which may be useful in classifying its structural properties.

Value

A vector of efficiency scores

Note

The four Krackhardt indices are, in general, nondegenerate for a relatively narrow band of size/density combinations (efficiency being the sole exception). This is primarily due to their dependence on the reachability graph, which tends to become complete rapidly as size/density increase. See Krackhardt (1994) for a useful simulation study.

The violation normalization used before version 0.51 was N(N-1) - Sum(N_i-1,i=1,..,n), based on a somewhat different interpretation of the definition in Krackhardt (1994). The former version gave results which more closely matched those of the cited simulation study, but was less consistent with the textual definition.

Author(s)

Carter T. Butts [e-mail]

References

Krackhardt, David. (1994). “Graph Theoretical Dimensions of Informal Organizations.” In K. M. Carley and M. J. Prietula (Eds.), Computational Organization Theory, 89-111. Hillsdale, NJ: Lawrence Erlbaum and Associates.

See Also

connectedness, efficiency, hierarchy, lubness, gden

Examples

#Get efficiency scores for graphs of varying densities
efficiency(rgraph(10,5,tprob=c(0.1,0.25,0.5,0.75,0.9)))

sna documentation built on Feb. 16, 2023, 9:52 p.m.