Package 'sna'

Description

Adds n isolates to the graph (or graphs) in dat.

Usage

add.isolates(dat, n, return.as.edgelist = FALSE)

Arguments

Details

If dat contains more than one graph, the n isolates are added to each member of dat.

Value

The updated graph(s).

Note

Isolate addition is particularly useful when computing structural distances between graphs of different orders; see the above reference for details.

Author(s)

Carter T. Butts [email protected]

References

Butts, C.T., and Carley, K.M. (2001). “Multivariate Methods for Inter-Structural Analysis.” CASOS Working Paper, Carnegie Mellon University.

See Also

isolates

Examples

g<-rgraph(10,5)		#Produce some random graphs

dim(g)			#Get the dimensions of g

g<-add.isolates(g,2)	#Add 2 isolates to each graph in g

dim(g)			#Now examine g
g

Description

Takes posterior draws from Butts' bayesian network accuracy/estimation model for multiple participant/observers (conditional on observed data and priors), using a Gibbs sampler.

Usage

bbnam(dat, model="actor", ...)
bbnam.fixed(dat, nprior=0.5, em=0.25, ep=0.25, diag=FALSE,
    mode="digraph", draws=1500, outmode="draws", anames=NULL,
    onames=NULL)
bbnam.pooled(dat, nprior=0.5, emprior=c(1,11), epprior=c(1,11),
    diag=FALSE, mode="digraph", reps=5, draws=1500, burntime=500, 
    quiet=TRUE, anames=NULL, onames=NULL, compute.sqrtrhat=TRUE)
bbnam.actor(dat, nprior=0.5, emprior=c(1,11), epprior=c(1,11), 
    diag=FALSE, mode="digraph", reps=5, draws=1500, burntime=500,
    quiet=TRUE, anames=NULL, onames=NULL, compute.sqrtrhat=TRUE)

Arguments

Details

The bbnam models a set of network data as reflecting a series of (noisy) observations by a set of participants/observers regarding an uncertain criterion structure. Each observer is assumed to send false positives (i.e., reporting a tie when none exists in the criterion structure) with probability $e^+$, and false negatives (i.e., reporting that no tie exists when one does in fact exist in the criterion structure) with probability $e^-$. The criterion network itself is taken to be a Bernoulli (di)graph. Note that the present model includes three variants:

1. Fixed error probabilities: Each edge is associated with a known pair of false negative/false positive error probabilities (provided by the researcher). In this case, the posterior for the criterion graph takes the form of a matrix of Bernoulli parameters, with each edge being independent conditional on the parameter matrix.

2. Pooled error probabilities: One pair of (uncertain) false negative/false positive error probabilities is assumed to hold for all observations. Here, we assume that the researcher's prior information regarding these parameters can be expressed as a pair of Beta distributions, with the additional assumption of independence in the prior distribution. Note that error rates and edge probabilities are not independent in the joint posterior, but the posterior marginals take the form of Beta mixtures and Bernoulli parameters, respectively.

3. Per observer (“actor”) error probabilities: One pair of (uncertain) false negative/false positive error probabilities is assumed to hold for each observation slice. Again, we assume that prior knowledge can be expressed in terms of independent Beta distributions (along with the Bernoulli prior for the criterion graph) and the resulting posterior marginals are Beta mixtures and a Bernoulli graph. (Again, it should be noted that independence in the priors does not imply independence in the joint posterior!)

By default, the bbnam routine returns (approximately) independent draws from the joint posterior distribution, each draw yielding one realization of the criterion network and one collection of accuracy parameters (i.e., probabilities of false positives/negatives). This is accomplished via a Gibbs sampler in the case of the pooled/actor model, and by direct sampling for the fixed probability model. In the special case of the fixed probability model, it is also possible to obtain directly the posterior for the criterion graph (expressed as a matrix of Bernoulli parameters); this can be controlled by the outmode parameter.

As noted, the taking of posterior draws in the nontrivial case is accomplished via a Markov Chain Monte Carlo method, in particular the Gibbs sampler; the high dimensionality of the problem ($O(n^2+2n)$) tends to preclude more direct approaches. At present, chain burn-in is determined ex ante on a more or less arbitrary basis by specification of the burntime parameter. Eventually, a more systematic approach will be utilized. Note that insufficient burn-in will result in inaccurate posterior sampling, so it's not wise to skimp on burn time where otherwise possible. Similarly, it is wise to employ more than one Markov Chain (set by reps), since it is possible for trajectories to become “trapped” in metastable regions of the state space. Number of draws per chain being equal, more replications are usually better than few; consult Gelman et al. for details. A useful measure of chain convergence, Gelman and Rubin's potential scale reduction ($\sqrt{\hat{R}}$), can be computed using the compute.sqrtrhat parameter. The potential scale reduction measure is an ANOVA-like comparison of within-chain versus between-chain variance; it approaches 1 (from above) as the chain converges, and longer burn-in times are strongly recommended for chains with scale reductions in excess of 1.2 or thereabouts.

Finally, a cautionary concerning prior distributions: it is important that the specified priors actually reflect the prior knowledge of the researcher; otherwise, the posterior will be inadequately informed. In particular, note that an uninformative prior on the accuracy probabilities implies that it is a priori equally probable that any given actor's observations will be informative or negatively informative (i.e., that $i$ observing $j$ sending a tie to $k$ reduces $\Pr(j\to k)$). This is a highly unrealistic assumption, and it will tend to produce posteriors which are bimodal (one mode being related to the “informative” solution, the other to the “negatively informative” solution). Currently, the default error parameter prior is Beta(1,11), which is both diffuse and which renders negatively informative observers extremely improbable (i.e., on the order of 1e-6). Another plausible but still fairly diffuse prior would be Beta(3,5), which reduces the prior probability of an actor's being negatively informative to 0.16, and the prior probability of any given actor's being more than 50% likely to make a particular error (on average) to around 0.22. (This prior also puts substantial mass near the 0.5 point, which would seem consonant with the BKS studies.) For network priors, a reasonable starting point can often be derived by considering the expected mean degree of the criterion graph: if $d$ represents the user's prior expectation for the mean degree, then $d/(N-1)$ is a natural starting point for the cell values of nprior. Butts (2003) discusses a number of issues related to choice of priors for the bbnam model, and users should consult this reference if matters are unclear before defaulting to the uninformative solution.

Value

An object of class bbnam, containing the posterior draws. The components of the output are as follows:

Note

As indicated, the posterior draws are conditional on the observed data, and hence on the data collection mechanism if the collection design is non-ignorable. Complete data (e.g., a CSS) and random tie samples are examples of ignorable designs; see Gelman et al. for more information concerning ignorability.

Author(s)

Carter T. Butts [email protected]

References

Butts, C. T. (2003). “Network Inference, Error, and Informant (In)Accuracy: A Bayesian Approach.” Social Networks, 25(2), 103-140.

Gelman, A.; Carlin, J.B.; Stern, H.S.; and Rubin, D.B. (1995). Bayesian Data Analysis. London: Chapman and Hall.

Gelman, A., and Rubin, D.B. (1992). “Inference from Iterative Simulation Using Multiple Sequences.” Statistical Science, 7, 457-511.

Krackhardt, D. (1987). “Cognitive Social Structures.” Social Networks, 9, 109-134.

See Also

npostpred, event2dichot, bbnam.bf

Examples

#Create some random data
g<-rgraph(5)
g.p<-0.8*g+0.2*(1-g)
dat<-rgraph(5,5,tprob=g.p)

#Define a network prior
pnet<-matrix(ncol=5,nrow=5)
pnet[,]<-0.5
#Define em and ep priors
pem<-matrix(nrow=5,ncol=2)
pem[,1]<-3
pem[,2]<-5
pep<-matrix(nrow=5,ncol=2)
pep[,1]<-3
pep[,2]<-5

#Draw from the posterior
b<-bbnam(dat,model="actor",nprior=pnet,emprior=pem,epprior=pep,
    burntime=100,draws=100)
#Print a summary of the posterior draws
summary(b)

Description

This function uses monte carlo integration to estimate the BFs, and tests the fixed probability, pooled, and pooled by actor models. (See bbnam for details.)

Usage

bbnam.bf(dat, nprior=0.5, em.fp=0.5, ep.fp=0.5, emprior.pooled=c(1, 11),
    epprior.pooled=c(1, 11), emprior.actor=c(1, 11), epprior.actor=c(1, 11), 
    diag=FALSE, mode="digraph", reps=1000)

Arguments

Details

The bbnam model (detailed in the bbnam function help) is a fairly simple model for integrating informant reports regarding social network data. bbnam.bf computes log Bayes Factors (integrated likelihood ratios) for the three error submodels of the bbnam: fixed error probabilities, pooled error probabilities, and per observer/actor error probabilities.

By default, bbnam.bf uses weakly informative Beta(1,11) priors for false positive and false negative rates, which may not be appropriate for all cases. (Likewise, the initial network prior is uniformative.) Users are advised to consider adjusting the error rate priors when using this function in a practical context; for instance, it is often reasonable to expect higher false negative rates (on average) than false positive rates, and to expect the criterion graph density to be substantially less than 0.5. See the reference below for a discussion of this issue.

Value

An object of class bayes.factor.

Note

It is important to be aware that the model parameter priors are essential components of the models to be compared; inappropriate parameter priors will result in misleading Bayes Factors.

Author(s)

Carter T. Butts [email protected]

References

Butts, C. T. (2003). “Network Inference, Error, and Informant (In)Accuracy: A Bayesian Approach.” Social Networks, 25(2), 103-140.

Robert, C. (1994). The Bayesian Choice: A Decision-Theoretic Motivation. Springer.

See Also

bbnam

Examples

#Create some random data from the "pooled" model
g<-rgraph(7)
g.p<-0.8*g+0.2*(1-g)
dat<-rgraph(7,7,tprob=g.p)

#Estimate the log Bayes Factors
b<-bbnam.bf(dat,emprior.pooled=c(3,5),epprior.pooled=c(3,5),
    emprior.actor=c(3,5),epprior.actor=c(3,5))
#Print the results
b

Description

betweenness takes one or more graphs (dat) and returns the betweenness centralities of positions (selected by nodes) within the graphs indicated by g. Depending on the specified mode, betweenness on directed or undirected geodesics will be returned; this function is compatible with centralization, and will return the theoretical maximum absolute deviation (from maximum) conditional on size (which is used by centralization to normalize the observed centralization score).

Usage

betweenness(dat, g=1, nodes=NULL, gmode="digraph", diag=FALSE,
    tmaxdev=FALSE, cmode="directed", geodist.precomp=NULL, 
    rescale=FALSE, ignore.eval=TRUE)

Arguments

Details

The shortest-path betweenness of a vertex, $v$, is given by

$C_B(v) = \sum_{i,j : i \neq j, i \neq v, j \neq v} \frac{g_{ivj}}{g_{ij}}$

where $g_{ijk}$ is the number of geodesics from $i$ to $k$ through $j$. Conceptually, high-betweenness vertices lie on a large number of non-redundant shortest paths between other vertices; they can thus be thought of as “bridges” or “boundary spanners.”

Several variant forms of shortest-path betweenness exist, and can be selected using the cmode argument. Supported options are as follows:

directed

Standard betweenness (see above), calculated on directed pairs. (This is the default option.)

undirected

Standard betweenness (as above), calculated on undirected pairs (undirected graphs only).

endpoints

Standard betweenness, with direct connections counted towards ego's score. This expresses the intuition that individuals' control over their own direct contacts should be considered in their total score (e.g., when betweenness is interpreted as a measure of information control).

proximalsrc

Borgatti's proximal source betweenness, given by

$C_B(v) = \sum_{i,j : i \neq v, i\neq j, j \to v} \frac{g_{ivj}}{g_{ij}}.$

This variant allows betweenness to accumulate only for the last intermediating vertex in each incoming geodesic; this expresses the notion that, by serving as the “proximal source” for the target, this particular intermediary will in some settings have greater influence or control than other intervening parties.

proximaltar

Borgatti's proximal target betweenness, given by

$C_B(v) = \sum_{i,j : i \neq v, i\to v, i\neq j} \frac{g_{ivj}}{g_{ij}}.$

This counterpart to proximal source betweenness (above) allows betweenness to accumulate only for the first intermediating vertex in each outgoing geodesic; this expresses the notion that, by serving as the “proximal target” for the source, this particular intermediary will in some settings have greater influence or control than other intervening parties.

proximalsum

The sum of Borgatti's proximal source and proximal target betweenness scores (above); this may be used when either role is regarded as relevant to the betweenness calculation.

lengthscaled

Borgetti and Everett's length-scaled betweenness, given by

$C_B(v) = \sum_{i,j : i \neq j, i \neq v, j \neq v} \frac{1}{d_{ij}}\frac{g_{ivj}}{g_{ij}},$

where $d_{ij}$ is the geodesic distance from $i$ to $j$. This measure adjusts the standard betweenness score by downweighting long paths (e.g., as appropriate in circumstances for which such paths are less-often used).

linearscaled

Geisberger et al.'s linearly-scaled betweenness:

$C_B(v) = \sum_{i,j : i \neq j, i \neq v, j \neq v} \frac{1}{d_{ij}}\frac{g_{ivj}}{g_{ij}}.$

This variant modifies the standard betweenness score by giving more weight to intermediaries which are closer to their targets (much like proximal source betweenness, above). This may be of use when those near the end of a path have greater direct control over the flow of influence or resources than those near its source.

See Brandes (2008) for details and additional references. Geodesics for all of the above can be calculated using valued edges by setting ignore.eval=TRUE. Edge values are interpreted as distances for this purpose; proximity data should be transformed accordingly before invoking this routine.

Value

A vector, matrix, or list containing the betweenness scores (depending on the number and size of the input graphs).

Warning

Rescale may cause unexpected results if all actors have zero betweenness.

Note

Judicious use of geodist.precomp can save a great deal of time when computing multiple path-based indices on the same network.

Author(s)

Carter T. Butts [email protected]

References

Borgatti, S.P. and Everett, M.G. (2006). “A Graph-Theoretic Perspective on Centrality.” Social Networks, 28, 466-484.

Brandes, U. (2008). “On Variants of Shortest-Path Betweenness Centrality and their Generic Computation.” Social Networks, 30, 136–145.

Freeman, L.C. (1979). “Centrality in Social Networks I: Conceptual Clarification.” Social Networks, 1, 215-239.

Geisberger, R., Sanders, P., and Schultes, D. (2008). “Better Approximation of Betweenness Centrality.” In Proceedings of the 10th Workshop on Algorithm Engineering and Experimentation (ALENEX'08), 90-100. SIAM.

See Also

centralization, stresscent, geodist

Examples

g<-rgraph(10)     #Draw a random graph with 10 members
betweenness(g)    #Compute betweenness scores

Description

bicomponent.dist returns the bicomponents of an input graph, along with size distribution and membership information.

Usage

bicomponent.dist(dat, symmetrize = c("strong", "weak"))

Arguments

Details

The bicomponents of undirected graph G are its maximal 2-connected vertex sets. bicomponent.dist calculates the bicomponents of $G$, after first coercing to undirected form using the symmetrization rule in symmetrize. In addition to bicomponent memberships, various summary statistics regarding the bicomponent distribution are returned; see below.

Value

A list containing

Note

Remember that bicomponents can intersect; when this occurs, the relevant vertices' entries in the membership vector are assigned to one of the overlapping bicomponents on an arbitrary basis. The members element of the return list is the safe way to recover membership information.

Author(s)

Carter T. Butts [email protected]

References

Brandes, U. and Erlebach, T. (2005). Network Analysis: Methodological Foundations. Berlin: Springer.

See Also

component.dist, cutpoints, symmetrize

Examples

#Draw a moderately sparse graph
g<-rgraph(25,tp=2/24,mode="graph")

#Compute the bicomponents
bicomponent.dist(g)

Description

Given a set of equivalence classes (in the form of an equiv.clust object, hclust object, or membership vector) and one or more graphs, blockmodel will form a blockmodel of the input graph(s) based on the classes in question, using the specified block content type.

Usage

blockmodel(dat, ec, k=NULL, h=NULL, block.content="density", 
    plabels=NULL, glabels=NULL, rlabels=NULL, mode="digraph", 
    diag=FALSE)

Arguments

Details

Unless a vector of classes is specified, blockmodel forms its eponymous models by using cutree to cut an equivalence clustering in the fashion specified by k and h. After forming clusters (roles), the input graphs are reordered and blockmodel reduction is applied. Currently supported reductions are:

1. density: block density, computed as the mean value of the block

2. meanrowsum: mean row sums for the block

3. meancolsum: mean column sums for the block

4. sum: total block sum

5. median: median block value

6. min: minimum block value

7. max: maximum block value

8. types: semi-intelligent coding of blocks by “type.” Currently recognized types are (in order of precedence) “NA” (i.e., blocks with no valid data), “null” (i.e., all values equal to zero), “complete” (i.e., all values equal to 1), “1 covered” (i.e., all rows/cols contain a 1), “1 row-covered” (i.e., all rows contain a 1), “1 col-covered” (i.e., all cols contain a 1), and “other” (i.e., none of the above).

Density or median-based reductions are probably the most interpretable for most conventional analyses, though type-based reduction can be useful in examining certain equivalence class hypotheses (e.g., 1 covered and null blocks can be used to infer regular equivalence classes). Once a given reduction is performed, the model can be analyzed and/or expansion can be used to generate new graphs based on the inferred role structure.

Value

An object of class blockmodel.

Author(s)

Carter T. Butts [email protected]

References

Doreian, P.; Batagelj, V.; and Ferligoj, A. (2005). Generalized Blockmodeling. Cambridge: Cambridge University Press.

White, H.C.; Boorman, S.A.; and Breiger, R.L. (1976). “Social Structure from Multiple Networks I: Blockmodels of Roles and Positions.” American Journal of Sociology, 81, 730-779.

See Also

equiv.clust, blockmodel.expand

Examples

#Create a random graph with _some_ edge structure
g.p<-sapply(runif(20,0,1),rep,20)  #Create a matrix of edge 
                                   #probabilities
g<-rgraph(20,tprob=g.p)            #Draw from a Bernoulli graph 
                                   #distribution

#Cluster based on structural equivalence
eq<-equiv.clust(g)

#Form a blockmodel with distance relaxation of 10
b<-blockmodel(g,eq,h=10)
plot(b)                            #Plot it

Description

blockmodel.expand takes a blockmodel and an expansion vector, and expands the former by making copies of the vertices.

Usage

blockmodel.expand(b, ev, mode="digraph", diag=FALSE)

Arguments

Details

The primary use of blockmodel expansion is in generating test data from a blockmodeling hypothesis. Expansion is performed depending on the content type of the blockmodel; at present, only density is supported. For the density content type, expansion is performed by interpreting the interclass density as an edge probability, and by drawing random graphs from the Bernoulli parameter matrix formed by expanding the density model. Thus, repeated calls to blockmodel.expand can be used to generate a sample for monte carlo null hypothesis tests under a Bernoulli graph model.

Value

An adjacency matrix, or stack thereof.

Note

Eventually, other content types will be supported.

Author(s)

Carter T. Butts [email protected]

References

Doreian, P.; Batagelj, V.; and Ferligoj, A. (2005). Generalized Blockmodeling. Cambridge: Cambridge University Press.

White, H.C.; Boorman, S.A.; and Breiger, R.L. (1976). “Social Structure from Multiple Networks I: Blockmodels of Roles and Positions.” American Journal of Sociology, 81, 730-779.

See Also

blockmodel

Examples

#Create a random graph with _some_ edge structure
g.p<-sapply(runif(20,0,1),rep,20)  #Create a matrix of edge 
                                   #probabilities
g<-rgraph(20,tprob=g.p)            #Draw from a Bernoulli graph 
                                   #distribution

#Cluster based on structural equivalence
eq<-equiv.clust(g)

#Form a blockmodel with distance relaxation of 15
b<-blockmodel(g,eq,h=15)

#Draw from an expanded density blockmodel
g.e<-blockmodel.expand(b,rep(2,length(b$rlabels)))  #Two of each class
g.e

Description

Fits a biased net model to an input graph, using moment-based or maximum pseudolikelihood techniques.

Usage

bn(dat, method = c("mple.triad", "mple.dyad", "mple.edge", 
    "mtle"), param.seed = NULL, param.fixed = NULL, 
    optim.method = "BFGS", optim.control = list(), 
    epsilon = 1e-05)

Arguments

Details

The biased net model stems from early work by Rapoport, who attempted to model networks via a hypothetical "tracing" process. This process may be described loosely as follows. One begins with a small "seed" set of vertices, each member of which is assumed to nominate (generate ties to) other members of the population with some fixed probability. These members, in turn, may nominate new members of the population, as well as members who have already been reached. Such nominations may be "biased" in one fashion or another, leading to a non-uniform growth process. Specifically, let $e_{ij}$ be the random event that vertex $i$ nominates vertex $j$ when reached. Then the conditional probability of $e_{ij}$ is given by

$\Pr(e_{ij}|T) = 1-\left(1-\Pr(B_e)\right) \prod_k \left(1-\Pr(B_k|T)\right)$

where $T$ is the current state of the trace, $B_e$ is the a Bernoulli event corresponding to the baseline probability of $e_{ij}$, and the $B_k$ are "bias events." Bias events are taken to be independent Bernoulli trials, given $T$, such that $e_{ij}$ is observed with certainty if any bias event occurs. The specification of a biased net model, then, involves defining the various bias events (which, in turn, influence the structure of the network).

Although other events have been proposed, the primary bias events employed in current biased net models are the "parent bias" (a tendency to return nominations); the "sibling bias" (a tendency to nominate alters who were nominated by the same third party); and the "double role bias" (a tendency to nominate alters who are both siblings and parents). These bias events, together with the baseline edge events, are used to form the standard biased net model. It is standard to assume homogeneity within bias class, leading to the four parameters $\pi$ (probability of a parent bias event), $\sigma$ (probability of a sibling bias event), $\rho$ (probability of a double role bias event), and $d$ (probability of a baseline event).

Unfortunately, there is no simple expression for the likelihood of a graph given these parameters (and hence, no basis for likelihood based inference). However, Skvoretz et al. have derived a class of maximum pseudo-likelihood estimators for the the biased net model, based on local approximations to the likelihood at the edge, dyad, or triad level. These estimators may be employed within bn by selecting the appropriate MPLE for the method argument. Alternately, it is also possible to derive expected triad census rates for the biased net model, allowing an estimator which maximizes the likelihood of the observed triad census (essentially, a method of moments procedure). This last may be selected via the argument mode="mtle". In addition to estimating model parameters, bn generates predicted edge, dyad, and triad census statistics, as well as structure statistics (using the Fararo-Sunshine recurrence). These can be used to evaluate goodness-of-fit.

print, summary, and plot methods are available for bn objects. See rgbn for simulation from biased net models.

Value

An object of class bn.

Note

Asymptotic properties of the MPLE are not known for this model. Caution is strongly advised.

Author(s)

Carter T. Butts [email protected]

References

Fararo, T.J. and Sunshine, M.H. (1964). “A study of a biased friendship net.” Syracuse, NY: Youth Development Center.

Rapoport, A. (1957). “A contribution to the theory of random and biased nets.” Bulletin of Mathematical Biophysics, 15, 523-533.

Skvoretz, J.; Fararo, T.J.; and Agneessens, F. (2004). “Advances in biased net theory: definitions, derivations, and estimations.” Social Networks, 26, 113-139.

See Also

rgbn, structure.statistics

Examples

#Generate a random graph
g<-rgraph(25)

#Fit a biased net model, using the triadic MPLE
gbn<-bn(g)

#Examine the results
summary(gbn)
plot(gbn)

#Now, fit a model containing only a density parameter
gbn<-bn(g,param.fixed=list(pi=0,sigma=0,rho=0))
summary(gbn)
plot(gbn)

Description

bonpow takes one or more graphs (dat) and returns the Boncich power centralities of positions (selected by nodes) within the graphs indicated by g. The decay rate for power contributions is specified by exponent (1 by default). This function is compatible with centralization, and will return the theoretical maximum absolute deviation (from maximum) conditional on size (which is used by centralization to normalize the observed centralization score).

Usage

bonpow(dat, g=1, nodes=NULL, gmode="digraph", diag=FALSE,
    tmaxdev=FALSE, exponent=1, rescale=FALSE, tol=1e-07)

Arguments

Details

Bonacich's power centrality measure is defined by $C_{BP}\left(\alpha,\beta\right)=\alpha\left(\mathbf{I}-\beta\mathbf{A}\right)^{-1}\mathbf{A}\mathbf{1}$, where $\beta$ is an attenuation parameter (set here by exponent) and $\mathbf{A}$ is the graph adjacency matrix. (The coefficient $\alpha$ acts as a scaling parameter, and is set here (following Bonacich (1987)) such that the sum of squared scores is equal to the number of vertices. This allows 1 to be used as a reference value for the “middle” of the centrality range.) When $\beta \rightarrow 1/\lambda_{\mathbf{A}1}$ (the reciprocal of the largest eigenvalue of $\mathbf{A}$), this is to within a constant multiple of the familiar eigenvector centrality score; for other values of $\beta$, the behavior of the measure is quite different. In particular, $\beta$ gives positive and negative weight to even and odd walks, respectively, as can be seen from the series expansion $C_{BP}\left(\alpha,\beta\right)=\alpha \sum_{k=0}^\infty \beta^k \mathbf{A}^{k+1} \mathbf{1}$ which converges so long as $|\beta| < 1/\lambda_{\mathbf{A}1}$. The magnitude of $\beta$ controls the influence of distant actors on ego's centrality score, with larger magnitudes indicating slower rates of decay. (High rates, hence, imply a greater sensitivity to edge effects.)

Interpretively, the Bonacich power measure corresponds to the notion that the power of a vertex is recursively defined by the sum of the power of its alters. The nature of the recursion involved is then controlled by the power exponent: positive values imply that vertices become more powerful as their alters become more powerful (as occurs in cooperative relations), while negative values imply that vertices become more powerful only as their alters become weaker (as occurs in competitive or antagonistic relations). The magnitude of the exponent indicates the tendency of the effect to decay across long walks; higher magnitudes imply slower decay. One interesting feature of this measure is its relative instability to changes in exponent magnitude (particularly in the negative case). If your theory motivates use of this measure, you should be very careful to choose a decay parameter on a non-ad hoc basis.

Value

A vector, matrix, or list containing the centrality scores (depending on the number and size of the input graphs).

Warning

Singular adjacency matrices cause no end of headaches for this algorithm; thus, the routine may fail in certain cases. This will be fixed when I get a better algorithm. bonpow will not symmetrize your data before extracting eigenvectors; don't send this routine asymmetric matrices unless you really mean to do so.

Note

The theoretical maximum deviation used here is not obtained with the star network, in general. For positive exponents, at least, the symmetric maximum occurs for an empty graph with one complete dyad (the asymmetric maximum is generated by the outstar). UCINET V seems not to adjust for this fact, which can cause some oddities in their centralization scores (thus, don't expect to get the same numbers with both packages).

Author(s)

Carter T. Butts [email protected]

References

Bonacich, P. (1972). “Factoring and Weighting Approaches to Status Scores and Clique Identification.” Journal of Mathematical Sociology, 2, 113-120.

Bonacich, P. (1987). “Power and Centrality: A Family of Measures.” American Journal of Sociology, 92, 1170-1182.

See Also

centralization, evcent

Examples

#Generate some test data
dat<-rgraph(10,mode="graph")
#Compute Bonpow scores
bonpow(dat,exponent=1,tol=1e-20)
bonpow(dat,exponent=-1,tol=1e-20)

Description

Performs the brokerage analysis of Gould and Fernandez on one or more input graphs, given a class membership vector.

Usage

brokerage(g, cl)

Arguments

Details

Gould and Fernandez (following Marsden and others) describe brokerage as the role played by a social actor who mediates contact between two alters. More formally, vertex $v$ is a broker for distinct vertices $a$ and $b$ iff $a \to v \to b$ and $a \not\to b$. Where actors belong to a priori distinct groups, group membership may be used to segment brokerage roles into particular types. Let $A \to B \to C$ denote the two-path associated with a brokerage structure, such that some vertex from group $B$ brokers the connection from some vertex from group $A$ to a vertex in group $C$. The types of brokerage roles defined by Gould and Fernandez (and their accompanying two-path structures) are then defined in terms of group membership as follows:

• $w_I$: Coordinator role; the broker mediates contact between two individuals from his or her own group. Two-path structure: $A \to A \to A$

• $w_O$: Itinerant broker role; the broker mediates contact between two individuals from a single group to which he or she does not belong. Two-path structure: $A \to B \to A$

• $b_{OI}$: Gatekeeper role; the broker mediates an incoming contact from an out-group member to an in-group member. Two-path structure: $A \to B \to B$

• $b_{IO}$: Representative role; the broker mediates an outgoing contact from an in-group member to an out-group member. Two-path structure: $A \to A \to B$

• $b_O$: Liaison role; the broker mediates contact between two individuals from different groups, neither of which is the group to which he or she belongs. Two-path structure: $A \to B \to C$

• $t$: Total (cumulative) brokerage role occupancy. (Any of the above two-paths.)

The brokerage score for a given vertex with respect to a given role is the number of ordered pairs having the appropriate group membership(s) brokered by said vertex. brokerage computes the brokerage scores for each vertex, given an input graph and vector of class memberships. Aggregate scores are also computed at the graph level, which correspond to the total frequency of each role type within the network structure. Expectations and variances of the brokerage scores conditional on size and density are computed, along with approximate $z$-tests for incidence of brokerage. (Note that the accuracy of the normality assumption is not known in the general case; see Gould and Fernandez (1989) for details. Simulation-based tests may be desirable as an alternative.)

Value

An object of class brokerage, containing the following elements:

Author(s)

Carter T. Butts [email protected]

References

Gould, R.V. and Fernandez, R.M. 1989. “Structures of Mediation: A Formal Approach to Brokerage in Transaction Networks.” Sociological Methodology, 19: 89-126.

See Also

triad.census, gtrans

Examples

#Draw a random network with 3 groups
g<-rgraph(15)
cl<-rep(1:3,5)

#Compute a brokerage object
b<-brokerage(g,cl)
summary(b)

Description

Returns the central graph of a set of labeled graphs, i.e. that graph in which i->j iff i->j in >=50% of the graphs within the set. If normalize==TRUE, then the value of the i,jth edge is given as the proportion of graphs in which i->j.

Usage

centralgraph(dat, normalize=FALSE)

Arguments

Details

The central graph of a set of graphs S is that graph C which minimizes the sum of Hamming distances between C and G in S. As such, it turns out (for the dichotomous case, at least), to be analogous to both the mean and median for sets of graphs. The central graph is useful in a variety of contexts; see the references below for more details.

Value

A matrix containing the central graph (or mean matrix)

Note

0.5 is used as the cutoff value regardless of whether or not the data is dichotomous (as is tacitly assumed). The routine is unaffected by data type when normalize==TRUE.

Author(s)

Carter T. Butts [email protected]

References

Banks, D.L., and Carley, K.M. (1994). “Metric Inference for Social Networks.” Journal of Classification, 11(1), 121-49.

See Also

hdist

Examples

#Generate some random graphs
dat<-rgraph(10,5)
#Find the central graph
cg<-centralgraph(dat)
#Plot the central graph
gplot(cg)
#Now, look at the mean matrix
cg<-centralgraph(dat,normalize=TRUE)
print(cg)

Description

Centralization returns the centralization GLI (graph-level index) for a given graph in dat, given a (node) centrality measure FUN. Centralization follows Freeman's (1979) generalized definition of network centralization, and can be used with any properly defined centrality measure. This measure must be implemented separately; see the references below for examples.

Usage

centralization(dat, FUN, g=NULL, mode="digraph", diag=FALSE, 
    normalize=TRUE, ...)

Arguments

Details

The centralization of a graph G for centrality measure $C(v)$ is defined (as per Freeman (1979)) to be:

$C^*(G) = \sum_{i \in V(G)} \left|\max_{v \in V(G)}(C(v))-C(i)\right|$

Or, equivalently, the absolute deviation from the maximum of C on G. Generally, this value is normalized by the theoretical maximum centralization score, conditional on $|V(G)|$. (Here, this functionality is activated by normalize.) Centralization depends on the function specified by FUN to return the vector of nodal centralities when called with dat and g, and to return the theoretical maximum value when called with the above and tmaxdev==TRUE. For an example of such a centrality routine, see degree.

Value

The centralization of the specified graph.

Note

See cugtest for null hypothesis tests involving centralization scores.

Author(s)

Carter T. Butts [email protected]

References

Freeman, L.C. (1979). “Centrality in Social Networks I: Conceptual Clarification.” Social Networks, 1, 215-239.

Wasserman, S., and Faust, K. (1994). Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press.

See Also

cugtest

Examples

#Generate some random graphs
dat<-rgraph(5,10)
#How centralized is the third one on indegree?
centralization(dat,g=3,degree,cmode="indegree")
#How about on total (Freeman) degree?
centralization(dat,g=3,degree)

Description

clique.census computes clique census statistics on one or more input graphs. In addition to aggregate counts of maximal cliques, results may be disaggregated by vertex and co-membership information may be computed.

Usage

clique.census(dat, mode = "digraph", tabulate.by.vertex = TRUE,
    clique.comembership = c("none", "sum", "bysize"), enumerate = TRUE,
    na.omit = TRUE)

Arguments

Details

A (maximal) clique is a maximal set of mutually adjacenct vertices. Cliques are important for their role as cohesive subgroups, but show up in many other contexts as well.

A subgraph census statistic is a function which, for any given graph and subgraph, gives the number of copies of the latter contained in the former. A collection of subgraph census statistics is referred to as a subgraph census; widely used examples include the dyad and triad censuses, implemented in sna by the dyad.census and triad.census functions (respectively). Likewise, kpath.census and kcycle.census compute a range of census statistics related to $k$-paths and $k$-cycles. clique.census provides similar functionality for the census of maximal cliques, including:

• Aggregate counts of maximal cliques by size.

• Counts of cliques to which each vertex belongs (when tabulate.byvertex==TRUE).

• Counts of clique co-memberships, potentially disaggregated by size (when the appropriate co-membership argument is set to bylength).

These calculations are intrinsically expensive (clique enumeration is NP hard in the general case), and users should be aware that computing the census can be impractical on large graphs (unless they are very sparse). On the other hand, the algorithm employed here (a variant of Makino and Uno (2004)) is generally fast enough to suport enumeration for even dense graphs of several hundred vertices on a typical desktop computer.

Calling this function with mode=="digraph", forces and initial symmetrization step, which can be avoided with mode=="graph". While incorrectly employing the default is harmless (except for the relatively small cost of verifying symmetry), setting mode=="graph" incorrectly may result in problematic behavior. When in doubt, stick with the default.

Value

A list with the following elements:

Warning

The computational cost of calculating cliques grows very sharply in size and network density. It is possible that the expected completion time for your calculation may exceed your life expectancy (and those of subsequent generations).

Author(s)

Carter T. Butts [email protected]

References

Wasserman, S. and Faust, K. (1994). Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press.

Makino, K. and Uno, T. (2004.) “New Algorithms for Enumerating All Maximal Cliques.” In T. Hagerup and J. Katajainen (eds.), SWAT 2004, LNCS 3111, 260-272. Berlin: Springer-Verlag.

See Also

dyad.census, triad.census, kcycle.census, kpath.census

Examples

#Generate a fairly dense random graph
g<-rgraph(25)

#Obtain cliques by vertex, with co-membership by size
cc<-clique.census(g,clique.comembership="bysize")
cc$clique.count                             #Examine clique counts
cc$clique.comemb[1,,]                       #Isolate co-membership is trivial
cc$clique.comemb[2,,]                       #Co-membership for 2-cliques
cc$clique.comemb[3,,]                       #Co-membership for 3-cliques
cc$cliques                                  #Enumerate the cliques

Description

closeness takes one or more graphs (dat) and returns the closeness centralities of positions (selected by nodes) within the graphs indicated by g. Depending on the specified mode, closeness on directed or undirected geodesics will be returned; this function is compatible with centralization, and will return the theoretical maximum absolute deviation (from maximum) conditional on size (which is used by centralization to normalize the observed centralization score).

Usage

closeness(dat, g=1, nodes=NULL, gmode="digraph", diag=FALSE, 
    tmaxdev=FALSE, cmode="directed", geodist.precomp=NULL, 
    rescale=FALSE, ignore.eval=TRUE)

Arguments

Details

The closeness of a vertex v is defined as

$C_C(v) = \frac{\left|V\left(G\right)\right|-1}{\sum_{i : i \neq v} d(v,i)}$

where $d(i,j)$ is the geodesic distance between i and j (where defined). Closeness is ill-defined on disconnected graphs; in such cases, this routine substitutes Inf. It should be understood that this modification is not canonical (though it is common), but can be avoided by not attempting to measure closeness on disconnected graphs in the first place! Intuitively, closeness provides an index of the extent to which a given vertex has short paths to all other vertices in the graph; this is one reasonable measure of the extent to which a vertex is in the “middle” of a given structure.

An alternate form of closeness (apparently due to Gil and Schmidt (1996)) is obtained by taking the sum of the inverse distances to each vertex, i.e.

$C_C(v) = \frac{\sum_{i : i \neq v} \frac{1}{d(v,i)}}{\left|V\left(G\right)\right|-1}.$

This measure correlates well with the standard form of closeness where both are well-defined, but lacks the latter's pathological behavior on disconnected graphs. Computation of alternate closeness may be performed via the argument cmode="suminvdir" (directed case) and cmode="suminvundir" (undirected case). The corresponding arguments cmode="directed" and cmode="undirected" return the standard closeness scores in the directed or undirected cases (respectively). Although treated here as a measure of closeness, this index was originally intended to capture power or efficacy; in its original form, the Gil-Schmidt power index is a renormalized version of the above. Specifically, let $R(v,G)$ be the set of vertices reachable by $v$ in $V\setminus v$. Then the Gil-Schmidt power index is defined as

$C_{GS}(v) = \frac{\sum_{i \in R(v,G)} \frac{1}{d(v,i)}}{|R(v,G)|}.$

with $C_{GS}$ defined to be 0 for vertices with no outneighbors. This may be obtained via the argument cmode="gil-schmidt".

Value

A vector, matrix, or list containing the closeness scores (depending on the number and size of the input graphs).

Note

Judicious use of geodist.precomp can save a great deal of time when computing multiple path-based indices on the same network.

Author(s)

Carter T. Butts, [email protected]

References

Freeman, L.C. (1979). “Centrality in Social Networks I: Conceptual Clarification.” Social Networks, 1, 215-239.

Gil, J. and Schmidt, S. (1996). “The Origin of the Mexican Network of Power”. Proceedings of the International Social Network Conference, Charleston, SC, 22-25.

Sinclair, P.A. (2009). “Network Centralization with the Gil Schmidt Power Centrality Index” Social Networks, 29, 81-92.

See Also

centralization

Examples

g<-rgraph(10)     #Draw a random graph with 10 members
closeness(g)      #Compute closeness scores

Description

James Coleman (1964) reports research on self-reported friendship ties among 73 boys in a small high school in Illinois over the 1957-1958 academic year. Networks of reported ties for all 73 informants are provided for two time points (fall and spring).

Usage

data(coleman)

Format

An adjacency array containing two directed, unvalued 73-node networks:

Details

Both networks reflect answers to the question, “What fellows here in school do you go around with most often?” with the presence of an $(i,j,k)$ edge indicating that $j$ nominated $k$ in time period $i$. The data are unvalued and directed; although the self-reported ties are highly reciprocal, unreciprocated nominations are possible.

It should be noted that, although this data is usually described as “friendship,” the sociometric item employed might be more accurately characterized as eliciting “frequent elective interaction.” This should be borne in mind when interpreting this data.

References

Coleman, J. S. (1964). Introduction to Mathermatical Sociology. New York: Free Press.

Examples

data(coleman)

#Plot showing edges by time point
gplot(coleman[1,,]|coleman[2,,],edge.col=2*coleman[1,,]+3*coleman[2,,])

Description

component.dist returns a list containing a vector of length n such that the ith element contains the number of components of graph $G$ having size i, and a vector of length n giving component membership (where n is the graph order). Component strength is determined by the connected parameter; see below for details.

component.largest identifies the component(s) of maximum order within graph G. It returns either a logical vector indicating membership in a maximum component or the adjacency matrix of the subgraph of $G$ induced by the maximum component(s), as determined by result. Component strength is determined as per component.dist.

Usage

component.dist(dat, connected=c("strong","weak","unilateral",
     "recursive"))

component.largest(dat, connected=c("strong","weak","unilateral",
     "recursive"), result = c("membership", "graph"), return.as.edgelist =
     FALSE)

Arguments

Details

Components are maximal sets of mutually connected vertices; depending on the definition of “connected” one employs, one can arrive at several types of components. Those supported here are as follows (in increasing order of restrictiveness):

1. weak: $v_1$ is connected to $v_2$ iff there exists a semi-path from $v_1$ to $v_2$ (i.e., a path in the weakly symmetrized graph)

2. unilateral: $v_1$ is connected to $v_2$ iff there exists a directed path from $v_1$ to $v_2$ or a directed path from $v_2$ to $v_1$

3. strong: $v_1$ is connected to $v_2$ iff there exists a directed path from $v_1$ to $v_2$ and a directed path from $v_2$ to $v_1$

4. recursive: $v_1$ is connected to $v_2$ iff there exists a vertex sequence $v_a,\ldots,v_z$ such that $v_1,v_a,\ldots,v_z,v_2$ and $v_2,v_z,\ldots,v_a,v_1$ are directed paths

Note that the above definitions are distinct for directed graphs only; if dat is symmetric, then the connected parameter has no effect.

Value

For component.dist, a list containing:

If multiple input graphs are given, the return value is a list of lists.

For component.largest, either a logical vector of component membership indicators or the adjacency matrix/edgelist of the subgraph induced by the largest component(s) is returned. If multiple graphs were given as input, a list of results is returned.

Note

Unilaterally connected component partitions may not be well-defined, since it is possible for a given vertex to be unilaterally connected to two vertices that are not unilaterally connected with one another. Consider, for instance, the graph $a \rightarrow b \leftarrow c \rightarrow d$. In this case, the maximal unilateral components are $ab$ and $bcd$, with vertex $b$ properly belonging to both components. For such graphs, a unique partition of vertices by component does not exist, and we “solve” the problem by allocating each “problem vertex” to one of its components on an essentially arbitrary basis. (component.dist generates a warning when this occurs.) It is recommended that the unilateral option be avoided where possible.

Do not make the mistake of assuming that the subgraphs returned by component.largest are necessarily connected. This is usually the case, but depends upon the uniqueness of the largest component.

Author(s)

Carter T. Butts [email protected]

References

West, D.B. (1996). Introduction to Graph Theory. Upper Saddle River, N.J.: Prentice Hall.

See Also

components, symmetrize, reachability geodist

Examples

g<-rgraph(20,tprob=0.06)   #Generate a sparse random graph

#Find weak components
cd<-component.dist(g,connected="weak")
cd$membership              #Who's in what component?
cd$csize                   #What are the component sizes?
                           #Plot the size distribution
plot(1:length(cd$cdist),cd$cdist/sum(cd$cdist),ylim=c(0,1),type="h")  
lgc<-component.largest(g,connected="weak")  #Get largest component
gplot(g,vertex.col=2+lgc)  #Plot g, with component membership
                           #Plot largest component itself 
gplot(component.largest(g,connected="weak",result="graph"))

#Find strong components
cd<-component.dist(g,connected="strong")
cd$membership              #Who's in what component?
cd$csize                   #What are the component sizes?
                           #Plot the size distribution
plot(1:length(cd$cdist),cd$cdist/sum(cd$cdist),ylim=c(0,1),type="h")
lgc<-component.largest(g,connected="strong")  #Get largest component
gplot(g,vertex.col=2+lgc)  #Plot g, with component membership
                           #Plot largest component itself 
gplot(component.largest(g,connected="strong",result="graph"))

Description

This function computes the component structure of the input network, and returns a vector whose $i$th entry is the size of the component to which $i$ belongs. This is useful e.g. for studies of diffusion or similar applications.

Usage

component.size.byvertex(dat, connected = c("strong", "weak", 
    "unilateral", "recursive"))

Arguments

Details

Component sizes are here computed using component.dist; see this function for additional information.

In an undirected graph, the size of $v$'s component represents the maximum number of nodes that can be reached by a diffusion process along the edges of the graph originating with node $v$; the expectation of component sizes by vertex (rather than the mean component size) is thus one measure of the maximum average diffusion potential of a graph. Because this quantity is monotone with respect to edge addition, it can be bounded using Bernoulli graphs (see Butts (2011)). In the directed case, multiple types of components are possible; see component.dist for details.

Value

A vector of length equal to the number of vertices in dat, whose $i$th element is the number of vertices in the component to which the $i$th vertex belongs.

Author(s)

Carter T. Butts [email protected]

References

West, D.B. (1996). Introduction to Graph Theory. Upper Saddle River, N.J.: Prentice Hall.

Butts, C.T. (2011). “Bernoulli Bounds for General Random Graphs.” Sociological Methodology, 41, 299-345.

See Also

component.dist

Examples

#Generate a random undirected graph
g<-rgraph(100,tprob=1.5/99,mode="graph",return.as.edgelist=TRUE)

#Get the component sizes for each vertex
cs<-component.size.byvertex(g)
cs

Description

Returns the number of components within dat, using the connectedness rule given in connected.

Usage

components(dat, connected="strong", comp.dist.precomp=NULL)

Arguments

Details

The connected parameter corresponds to the rule parameter of component.dist. By default, components returns the number of strong components, but other component types can be returned if so desired. (See component.dist for details.) For symmetric matrices, this is obviously a moot point.

Value

A vector containing the number of components for each graph in dat

Author(s)

Carter T. Butts [email protected]

References

West, D.B. (1996). Introduction to Graph Theory. Upper Saddle River, NJ: Prentice Hall.

See Also

component.dist, symmetrize

Examples

g<-rgraph(20,tprob=0.05)   #Generate a sparse random graph

#Find weak components
components(g,connected="weak")

#Find strong components
components(g,connected="strong")

Description

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

Usage

connectedness(dat, g=NULL)

Arguments

Details

Krackhardt's connectedness for a digraph $G$ is equal to the fraction of all dyads, $\{i,j\}$, such that there exists an undirected path from $i$ to $j$ in $G$. (This, in turn, is just the density of the weak reachability graph of $G$.) Obviously, the connectedness score ranges from 0 (for the null graph) to 1 (for weakly connected graphs).

Connectedness 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 containing the connectedness 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.

Author(s)

Carter T. Butts [email protected]

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, reachability

Examples

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

Description

consensus estimates a central or consensus structure given multiple observations, using one of several algorithms.

Usage

consensus(dat, mode="digraph", diag=FALSE, method="central.graph", 
    tol=1e-06, maxiter=1e3, verbose=TRUE, no.bias=FALSE)

Arguments

Details

The term “consensus structure” is used by a number of authors to reflect a notion of shared or common perceptions of social structure among a set of observers. As there are many interpretations of what is meant by “consensus” (and as to how best to estimate it), several algorithms are employed here:

1. central.graph: Estimate the consensus structure using the central graph. This corresponds to a “median response” notion of consensus.

2. single.reweight: Estimate the consensus structure using subject responses, reweighted by mean graph correlation. This corresponds to an “expertise-weighted vote” notion of consensus.

3. iterative.reweight: Similar to single.reweight, but the consensus structure and accuracy parameters are estimated via an iterated proportional fitting scheme. The implementation employed here uses both bias and competency parameters.

4. romney.batchelder: Fits a Romney-Batchelder informant accuracy model using IPF. This is very similar to iterative.reweight, but can be interpreted as the result of a process in which each informant report is correct with a probability equal to the informant's competency score, and otherwise equal to a Bernoulli trial with parameter equal to the informant's bias score.

5. PCA.reweight: Estimate the consensus using the (scores on the) first component of a network PCA. This corresponds to a “shared theme” or “common element” notion of consensus.

6. LAS.intersection: Estimate the consensus structure using the locally aggregated structure (intersection rule). In this model, an i->j edge exists iff i and j agree that it exists.

7. LAS.union: Estimate the consensus structure using the locally aggregated structure (union rule). In this model, an i->j edge exists iff i or j agree that it exists.

8. OR.row: Estimate the consensus structure using own report. Here, we take each informant's outgoing tie reports to be correct.

9. OR.col: Estimate the consensus structure using own report. Here, we take each informant's incoming tie reports to be correct.

Note that the results returned by the single weighting algorithms are not dichotomized by default; since some algorithms thus return valued graphs, dichotomization may be desirable prior to use.

It should be noted that a model for estimating an underlying criterion structure from multiple informant reports is provided in bbnam; if your goal is to reconstruct an “objective” network from informant reports, this (or the R-B model) may prove more useful than the ad-hoc solutions.

Value

An adjacency matrix representing the consensus structure

Author(s)

Carter T. Butts [email protected]

References

Banks, D.L., and Carley, K.M. (1994). “Metric Inference for Social Networks.” Journal of Classification, 11(1), 121-49.

Butts, C.T., and Carley, K.M. (2001). “Multivariate Methods for Inter-Structural Analysis.” CASOS Working Paper, Carnegie Mellon University.

Krackhardt, D. (1987). “Cognitive Social Structures.” Social Networks, 9, 109-134.

Romney, A.K.; Weller, S.C.; and Batchelder, W.H. (1986). “Culture as Consensus: A Theory of Culture and Informant Accuracy.” American Anthropologist, 88(2), 313-38.

See Also

bbnam, centralgraph

Examples

#Generate some test data
g<-rgraph(5)
g.pobs<-g*0.9+(1-g)*0.5
g.obs<-rgraph(5,5,tprob=g.pobs)

#Find some consensus structures
consensus(g.obs)                           #Central graph
consensus(g.obs,method="single.reweight")  #Single reweighting
consensus(g.obs,method="PCA.reweight")     #1st component in network PCA

Description

cug.test takes an input network and conducts a conditional uniform graph (CUG) test of the statistic in FUN, using the conditioning statistics in cmode. The resulting test object has custom print and plot methods.

Usage

cug.test(dat, FUN, mode = c("digraph", "graph"), cmode = c("size", 
    "edges", "dyad.census"), diag = FALSE, reps = 1000, 
    ignore.eval = TRUE, FUN.args = list())

Arguments

Details

cug.test is an improved version of cugtest, for use only with univariate CUG hypotheses. Depending on cmode, conditioning on the realized size, edge count (or exact edge value distribution), or dyad census (or dyad value distribution) can be selected. Edges are treated as unvalued unless ignore.eval=FALSE; since the latter setting is less efficient for sparse graphs, it should be used only when necessary.

A brief summary of the theory and goals of conditional uniform graph testing can be found in the reference below. See also cugtest for a somewhat informal description.

Value

An object of class cug.test.

Author(s)

Carter T. Butts [email protected]

References

Butts, Carter T. (2008). “Social Networks: A Methodological Introduction.” Asian Journal of Social Psychology, 11(1), 13–41.

See Also

cugtest

Examples

#Draw a highly reciprocal network
g<-rguman(1,15,mut=0.25,asym=0.05,null=0.7)

#Test transitivity against size, density, and the dyad census
cug.test(g,gtrans,cmode="size")
cug.test(g,gtrans,cmode="edges")
cug.test(g,gtrans,cmode="dyad.census")

Description

cugtest tests an arbitrary GLI (computed on dat by FUN) against a conditional uniform graph null hypothesis, via Monte Carlo simulation. Some variation in the nature of the conditioning is available; currently, conditioning only on size, conditioning jointly on size and estimated tie probability (via expected density), and conditioning jointly on size and (bootstrapped) edge value distributions are implemented. Note that fair amount of flexibility is possible regarding CUG tests on functions of GLIs (Anderson et al., 1999). See below for more details.

Usage

cugtest(dat, FUN, reps=1000, gmode="digraph", cmode="density", 
    diag=FALSE, g1=1, g2=2, ...)

Arguments

Details

The null hypothesis of the CUG test is that the observed GLI (or function thereof) was drawn from a distribution equivalent to that of said GLI evaluated (uniformly) on the space of all graphs conditional on one or more features. The most common “features” used for conditioning purposes are order (size) and density, both of which are known to have strong and nontrivial effects on other GLIs (Anderson et al., 1999) and which are, in many cases, exogenously determined. (Note that maximum entropy distributions conditional on expected statistics are not in general correctly referred to as “conditional uniform graphs”, but have been described as such for independent-dyad models; this is indeed the case for this function, although such terminology is not really proper. See cug.test for CUG tests with exact conditioning.) Since theoretical results regarding functions of arbitrary GLIs on the space of graphs are not available, the standard approach to CUG testing is to approximate the quantiles of the observed statistic associated with the null hypothesis using Monte Carlo methods. This is the technique utilized by cugtest, which takes appropriately conditioned draws from the set of graphs and computes on them the GLI specified in FUN, thereby accumulating an approximation to the true quantiles.

The cugtest procedure returns a cugtest object containing the estimated distribution of the test GLI under the null hypothesis, the observed GLI value of the data, and the one-tailed p-values (estimated quantiles) associated with said observation. As usual, the (upper tail) null hypothesis is rejected for significance level alpha if p>=observation is less than alpha (or p<=observation, for the lower tail). Standard caveats regarding the use of null hypothesis testing procedures are relevant here: in particular, bear in mind that a significant result does not necessarily imply that the likelihood ratio of the null model and the alternative hypothesis favors the latter.

Informative and aesthetically pleasing portrayals of cugtest objects are available via the print.cugtest and summary.cugtest methods. The plot.cugtest method displays the estimated distribution, with a reference line signifying the observed value.

Value

An object of class cugtest, containing

Note

This function currently conditions only on expected statistics, and is somewhat cumbersome. cug.test is now recommended for univariate CUG tests (and will eventually supplant this function).

Author(s)

Carter T. Butts [email protected]

References

Anderson, B.S.; Butts, C.T.; and Carley, K.M. (1999). “The Interaction of Size and Density with Graph-Level Indices.” Social Networks, 21(3), 239-267.

See Also

cug.test, qaptest, gliop

Examples

#Draw two random graphs, with different tie probabilities
dat<-rgraph(20,2,tprob=c(0.2,0.8))
#Is their correlation higher than would be expected, conditioning 
#only on size?
cug<-cugtest(dat,gcor,cmode="order")
summary(cug)
#Now, let's try conditioning on density as well.
cug<-cugtest(dat,gcor)
summary(cug)

Description

cutpoints identifies the cutpoints of an input graph. Depending on mode, either a directed or undirected notion of “cutpoint” can be used.

Usage

cutpoints(dat, mode = "digraph", connected = c("strong","weak","recursive"),
    return.indicator = FALSE)

Arguments

Details

A cutpoint (also known as an articulation point or cut-vertex) of an undirected graph, $G$ is a vertex whose removal increases the number of components of $G$. Several generalizations to the directed case exist. Here, we define a strong cutpoint of directed graph $G$ to be a vertex whose removal increases the number of strongly connected components of $G$ (see component.dist). Likewise, weak and recursive cutpoints of G are those vertices whose removal increases the number of weak or recursive cutpoints (respectively). By default, strong cutpoints are used; alternatives may be selected via the connected argument.

Cutpoints are of particular interest when seeking to identify critical positions in flow networks, since their removal by definition alters the connectivity properties of the graph. In this context, cutpoint status can be thought of as a primitive form of centrality (with some similarities to betweenness).

Cutpoint computation is significantly faster for the undirected case (and for the weak/recursive cases) than for the strong directed case. While calling cutpoints with mode="digraph" on an undirected graph will give the same answer as mode="graph", it is thus to one's advantage to use the latter form. Do not, however, employ mode="graph" with directed data, unless you enjoy unpredictable behavior.

Value

A vector of cutpoints (if return.indicator==FALSE), or else a logical vector indicating cutpoint status for each vertex.

Author(s)

Carter T. Butts [email protected]

References

Berge, Claude. (1966). The Theory of Graphs. New York: John Wiley and Sons.

See Also

component.dist, bicomponent.dist, betweenness

Examples

#Generate some sparse random graph
gd<-rgraph(25,tp=1.5/24)                               #Directed
gu<-rgraph(25,tp=1.5/24,mode="graph")                  #Undirected

#Calculate the cutpoints (as an indicator vector)
cpu<-cutpoints(gu,mode="graph",return.indicator=TRUE)
cpd<-cutpoints(gd,return.indicator=TRUE)

#Plot the result
gplot(gu,gmode="graph",vertex.col=2+cpu)
gplot(gd,vertex.col=2+cpd)

#Repeat with alternate connectivity modes
cpdw<-cutpoints(gd,connected="weak",return.indicator=TRUE)
cpdr<-cutpoints(gd,connected="recursive",return.indicator=TRUE)

#Visualize the difference
gplot(gd,vertex.col=2+cpdw)
gplot(gd,vertex.col=2+cpdr)

Description

Degree takes one or more graphs (dat) and returns the degree centralities of positions (selected by nodes) within the graphs indicated by g. Depending on the specified mode, indegree, outdegree, or total (Freeman) degree will be returned; this function is compatible with centralization, and will return the theoretical maximum absolute deviation (from maximum) conditional on size (which is used by centralization to normalize the observed centralization score).

Usage

degree(dat, g=1, nodes=NULL, gmode="digraph", diag=FALSE,
    tmaxdev=FALSE, cmode="freeman", rescale=FALSE, ignore.eval=FALSE)

Arguments

Details

Degree centrality is the social networker's term for various permutations of the graph theoretic notion of vertex degree: for unvalued graphs, indegree of a vertex, $v$, corresponds to the cardinality of the vertex set $N^+(v)=\{i \in V(G) : (i,v) \in E(G)\}$; outdegree corresponds to the cardinality of the vertex set $N^-(v)=\{i \in V(G) : (v,i) \in E(G)\}$; and total (or “Freeman”) degree corresponds to $\left|N^+(v)\right| + \left|N^-(v)\right|$. (Note that, for simple graphs, indegree=outdegree=total degree/2.) Obviously, degree centrality can be interpreted in terms of the sizes of actors' neighborhoods within the larger structure. See the references below for more details.

When ignore.eval==FALSE, degree weights edges by their values where supplied. ignore.eval==TRUE ensures an unweighted degree score (independent of input). Setting gmode=="graph" forces behavior equivalent to cmode=="indegree" (i.e., each edge is counted only once); to obtain a total degree score for an undirected graph in which both in- and out-neighborhoods are counted separately, simply use gmode=="digraph".

Value

A vector, matrix, or list containing the degree scores (depending on the number and size of the input graphs).

Author(s)

Carter T. Butts [email protected]

References

Freeman, L.C. (1979). “Centrality in Social Networks I: Conceptual Clarification.” Social Networks, 1, 215-239.

See Also

centralization

Examples

#Create a random directed graph
dat<-rgraph(10)
#Find the indegrees, outdegrees, and total degrees
degree(dat,cmode="indegree")
degree(dat,cmode="outdegree")
degree(dat)

Description

Returns the input graphs, with the diagonal entries removed/replaced as indicated.

Usage

diag.remove(dat, remove.val=NA)

Arguments

Details

diag.remove is simply a convenient way to apply diag to an entire collection of adjacency matrices/network objects at once.

Value

The updated graphs.

Author(s)

Carter T. Butts [email protected]

See Also

diag, upper.tri.remove, lower.tri.remove

Examples

#Generate a random graph stack
g<-rgraph(3,5)
#Remove the diagonals
g<-diag.remove(g)

Description

dyad.census computes a Holland and Leinhardt dyad census on the graphs of dat selected by g.

Usage

dyad.census(dat, g=NULL)

Arguments

Details

Each dyad in a directed graph may be in one of four states: the null state ($a \not\leftrightarrow b$), the complete or mutual state ($a \leftrightarrow b$), and either of two asymmetric states ($a \leftarrow b$ or $a \rightarrow b$). Holland and Leinhardt's dyad census classifies each dyad into the mutual, asymmetric, or null categories, counting the number of each within the digraph. These counts can be used as the basis for null hypothesis tests (since their distributions are known under assumptions such as constant edge probability), or for the generation of random graphs (e.g., via the U|MAN distribution, which conditions on the numbers of mutual, asymmetric, and null dyads in each graph).

Value

A matrix whose three columns contain the counts of mutual, asymmetric, and null dyads (respectively) for each graph

Author(s)

Carter T. Butts [email protected]

References

Holland, P.W. and Leinhardt, S. (1970). “A Method for Detecting Structure in Sociometric Data.” American Journal of Sociology, 76, 492-513.

Wasserman, S., and Faust, K. (1994). “Social Network Analysis: Methods and Applications.” Cambridge: Cambridge University Press.

See Also

mutuality, grecip, rguman triad.census, kcycle.census, kpath.census

Examples

#Generate a dyad census of random data with varying densities
dyad.census(rgraph(15,5,tprob=c(0.1,0.25,0.5,0.75,0.9)))

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

Details

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

$1-\frac{|E(G)| - \sum_{i=1}^n \left(N_i-1\right)}{\sum_{i=1}^n \left(N_i \left(N_i-1\right)-\left(N_i-1\right)\right)}$

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\left(N-1\right) \sum_{i=1}^n \left(N_i-1\right)$, 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 [email protected]

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)))

Description

ego.extract takes one or more input graphs (dat) and returns a list containing the egocentric networks centered on vertices named in ego, using adjacency rule neighborhood to define inclusion.

Usage

ego.extract(dat, ego = NULL, neighborhood = c("combined", "in",
    "out"))

Arguments

Details

The egocentric network (or “ego net”) of vertex $v$ in graph $G$ is defined as $G[v \cup N(v)]$ (i.e., the subgraph of $G$ induced by $v$ and its neighborhood). The neighborhood employed by ego.extract is selected by the eponymous argument: "in" selects in-neighbors, "out" selects out-neighbors, and "combined" selects all neighbors. In the event that one of the vertices selected by ego has no qualifying neighbors, ego.extract will return a degenerate (1 by 1) adjacency matrix containing that individual's diagonal entry.

Vertices within the returned matrices are maintained in their original order, save for ego (who is always listed first). The ego nets themselves are returned in the order specified in the ego parameter (or their vertex order, if no value was specified).

ego.extract is useful for finding local properties associated with particular vertices. To compute functions of neighbors' covariates, see gapply.

Value

A list containing the adjacency matrices for the ego nets of each vertex in ego.

Author(s)

Carter T. Butts [email protected]

References

Wasserman, S. and Faust, K. (1994). Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press.

See Also

gapply

Examples

#Generate a sample network
g<-rgraph(10,tp=1.5/9)

#Extract some ego nets
g.in<-ego.extract(g,neighborhood="in")
g.out<-ego.extract(g,neighborhood="out")
g.comb<-ego.extract(g,neighborhood="in")

#View some networks
g.comb

#Compare ego net size with degree
all(sapply(g.in,NROW)==degree(g,cmode="indegree")+1)    #TRUE
all(sapply(g.out,NROW)==degree(g,cmode="outdegree")+1)  #TRUE
all(sapply(g.comb,NROW)==degree(g)/2+1)        #Usually FALSE!

#Calculate egocentric network density
ego.size<-sapply(g.comb,NROW)
if(any(ego.size>2))
  sapply(g.comb[ego.size>2],function(x){gden(x[-1,-1])})

Description

equiv.clust uses a definition of approximate equivalence (equiv.fun) to form a hierarchical clustering of network positions. Where dat consists of multiple relations, all specified relations are considered jointly in forming the equivalence clustering.

Usage

equiv.clust(dat, g=NULL, equiv.dist=NULL, equiv.fun="sedist",
   method="hamming", mode="digraph", diag=FALSE, 
   cluster.method="complete", glabels=NULL, plabels=NULL, ...)

Arguments

Details

This routine is essentially a joint front-end to hclust and various positional distance functions, though it defaults to structural equivalence in particular. Taking the specified graphs as input, equiv.clust computes the distances between all pairs of positions using equiv.fun (unless distances are supplied in equiv.dist), and then performs a cluster analysis of the result. The return value is an object of class equiv.clust, for which various secondary analysis methods exist.

Value

An object of class equiv.clust

Note

See sedist for an example of a distance function compatible with equiv.clust.

Author(s)

Carter T. Butts [email protected]

References

Breiger, R.L.; Boorman, S.A.; and Arabie, P. (1975). “An Algorithm for Clustering Relational Data with Applications to Social Network Analysis and Comparison with Multidimensional Scaling.” Journal of Mathematical Psychology, 12, 328-383.

Burt, R.S. (1976). “Positions in Networks.” Social Forces, 55, 93-122.

Wasserman, S., and Faust, K. Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press.

See Also

sedist, blockmodel

Examples

#Create a random graph with _some_ edge structure
g.p<-sapply(runif(20,0,1),rep,20)  #Create a matrix of edge 
                                   #probabilities
g<-rgraph(20,tprob=g.p)            #Draw from a Bernoulli graph 
                                   #distribution

#Cluster based on structural equivalence
eq<-equiv.clust(g)
plot(eq)

Description

Evaluates a given function on an input graph with and without a specified edge, returning the difference between the results in each case.

Usage

eval.edgeperturbation(dat, i, j, FUN, ...)

Arguments

Details

Although primarily a back-end utility for pstar, eval.edgeperturbation may be useful in any circumstance in which one wishes to assess the stability of a given structural index with respect to single edge perturbations. The function to be evaluated is calculated first on the input graph with all marked edges set to present, and then on the same graph with said edges absent. (Obviously, this is sensible only for dichotomous data.) The difference is then returned.

In pstar, calls to eval.edgeperturbation are used to construct a perturbation effect matrix for the GLM.

Value

The difference in the values of FUN as computed on the perturbed graphs.

Note

length(i) and length(j) must be equal; where multiple edges are specified, the row and column listings are interpreted as pairs.

Author(s)

Carter T. Butts [email protected]

References

Anderson, C.; Wasserman, S.; and Crouch, B. (1999). “A p* Primer: Logit Models for Social Networks. Social Networks, 21,37-66.

See Also

pstar

Examples

#Create a random graph
g<-rgraph(5)

#How much does a one-edge change affect reciprocity?
eval.edgeperturbation(g,1,2,grecip)

Description

evcent takes one or more graphs (dat) and returns the eigenvector centralities of positions (selected by nodes) within the graphs indicated by g. This function is compatible with centralization, and will return the theoretical maximum absolute deviation (from maximum) conditional on size (which is used by centralization to normalize the observed centralization score).

Usage

evcent(dat, g=1, nodes=NULL, gmode="digraph", diag=FALSE,
    tmaxdev=FALSE, rescale=FALSE, ignore.eval=FALSE, tol=1e-10,
    maxiter=1e5, use.eigen=FALSE)

Arguments

Details

Eigenvector centrality scores correspond to the values of the first eigenvector of the graph adjacency matrix; these scores may, in turn, be interpreted as arising from a reciprocal process in which the centrality of each actor is proportional to the sum of the centralities of those actors to whom he or she is connected. In general, vertices with high eigenvector centralities are those which are connected to many other vertices which are, in turn, connected to many others (and so on). (The perceptive may realize that this implies that the largest values will be obtained by individuals in large cliques (or high-density substructures). This is also intelligible from an algebraic point of view, with the first eigenvector being closely related to the best rank-1 approximation of the adjacency matrix (a relationship which is easy to see in the special case of a diagonalizable symmetric real matrix via the $S \Lambda S^{-1}$ decomposition).)

By default, a sparse-graph power method is used to obtain the principal eigenvector. This procedure scales well, but may not converge in some cases. In the event that the convergence objective set by tol is not obtained, evcent will return a warning message. Correctives in this case include increasing maxiter, or setting use.eigen to TRUE. The latter will cause evcent to use R's standard eigen method to calculate the principal eigenvector; this is far slower for sparse graphs, but is also more robust.

The simple eigenvector centrality is generalized by the Bonacich power centrality measure; see bonpow for more details.

Value

A vector, matrix, or list containing the centrality scores (depending on the number and size of the input graphs).

WARNING

evcent will not symmetrize your data before extracting eigenvectors; don't send this routine asymmetric matrices unless you really mean to do so.

Note

The theoretical maximum deviation used here is not obtained with the star network, in general. For symmetric data, the maximum occurs for an empty graph with one complete dyad; the maximum deviation for asymmetric data is generated by the outstar. UCINET V seems not to adjust for this fact, which can cause some oddities in their centralization scores (and results in a discrepancy in centralizations between the two packages).

Author(s)

Carter T. Butts [email protected]

References

Bonacich, P. (1987). “Power and Centrality: A Family of Measures.” American Journal of Sociology, 92, 1170-1182.

Katz, L. (1953). “A New Status Index Derived from Sociometric Analysis.” Psychometrika, 18, 39-43.

See Also

centralization, bonpow

Examples

#Generate some test data
dat<-rgraph(10,mode="graph")
#Compute eigenvector centrality scores
evcent(dat)

Description

Given one or more valued adjacency matrices (possibly derived from observed interaction “events”), event2dichot returns dichotomized equivalents.

Usage

event2dichot(m, method="quantile", thresh=0.5, leq=FALSE)

Arguments

Details

The methods used for choosing dichotomization thresholds are as follows:

1. quantile: specified quantile over the distribution of all edge values

2. rquantile: specified quantile by row

3. cquantile: specified quantile by column

4. mean: grand mean

5. rmean: row mean

6. cmean: column mean

7. absolute: the value of thresh itself

8. rank: specified rank over the distribution of all edge values

9. rrank: specified rank by row

10. crank: specified rank by column

Note that when a quantile, rank, or value is said to be “specified,” this refers to the value of thresh.

Value

The dichotomized data matrix (or matrices)

Author(s)

Carter T. Butts [email protected]

References

Wasserman, S. and Faust, K. (1994). Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press.

Examples

#Draw a matrix of normal values
n<-matrix(rnorm(25),nrow=5,ncol=5)

#Dichotomize by the mean value
event2dichot(n,"mean")

#Dichotomize by the 0.95 quantile
event2dichot(n,"quantile",0.95)

Description

flowbet takes one or more graphs (dat) and returns the flow betweenness scores of positions (selected by nodes) within the graphs indicated by g. Depending on the specified mode, flow betweenness on directed or undirected geodesics will be returned; this function is compatible with centralization, and will return the theoretical maximum absolute deviation (from maximum) conditional on size (which is used by centralization to normalize the observed centralization score).

Usage

flowbet(dat, g = 1, nodes = NULL, gmode = "digraph", diag = FALSE,
    tmaxdev = FALSE, cmode = "rawflow", rescale = FALSE, 
    ignore.eval = FALSE)

Arguments

Details

The (“raw,” or unnormalized) flow betweenness of a vertex, $v \in V(G)$, is defined by Freeman et al. (1991) as

$C_F(v) = \sum_{i,j : i \neq j, i \neq v, j \neq v} \left(f(i,j,G) - f(i,j,G\setminus v)\right),$

where $f(i,j,G)$ is the maximum flow from $i$ to $j$ within $G$ (under the assumption of infinite vertex capacities, finite edge capacities, and non-simultaneity of pairwise flows). Intuitively, unnormalized flow betweenness is simply the total maximum flow (aggregated across all pairs of third parties) mediated by $v$.

The above flow betweenness measure is computed by flowbet when cmode=="rawflow". In some cases, it may be desirable to normalize the raw flow betweenness by the total maximum flow among third parties (including $v$); this leads to the following normalized flow betweenness measure:

$C'_F(v) = \frac{\sum_{i,j : i \neq j, i \neq v, j \neq v} \left(f(i,j,G) - f(i,j,G\setminus v)\right)}{\sum_{i,j : i \neq j, i \neq v, j \neq v} f(i,j,G)}.$

This variant can be selected by setting cmode=="normflow".

Finally, it may be noted that the above normalization (from Freeman et al. (1991)) is rather different from that used in the definition of shortest-path betweenness, which normalizes within (rather than across) third-party dyads. A third flow betweenness variant has been suggested by Koschutzki et al. (2005) based on a normalization of this type:

$C''_F(v) = \sum_{i,j : i \neq j, i \neq v, j \neq v} \frac{ \left(f(i,j,G) - f(i,j,G\setminus v)\right)}{f(i,j,G)}$