structdist: Find the Structural Distances Between Two or More Graphs

In sna: Tools for Social Network Analysis

Find the Structural Distances Between Two or More Graphs

Description

structdist returns the structural distance between the labeled graphs g1 and g2 in stack dat based on Hamming distance for dichotomous data, or else the absolute (manhattan) distance. If normalize is true, this distance is divided by its dichotomous theoretical maximum (conditional on |V(G)|).

Usage

structdist(dat, g1=NULL, g2=NULL, normalize=FALSE, diag=FALSE,
    mode="digraph", method="anneal",  reps=1000, prob.init=0.9,
    prob.decay=0.85, freeze.time=25, full.neighborhood=TRUE,
    mut=0.05, pop=20, trials=5, exchange.list=NULL)

Arguments

dat	one or more input graphs.
g1	a vector indicating which graphs to compare (by default, all elements of dat).
g2	a vector indicating against which the graphs of g1 should be compared (by default, all graphs).
normalize	divide by the number of available dyads?
diag	boolean indicating whether or not the diagonal should be treated as valid data. Set this true if and only if the data can contain loops. diag is FALSE by default.
mode	string indicating the type of graph being evaluated. "digraph" indicates that edges should be interpreted as directed; "graph" indicates that edges are undirected. mode is set to "digraph" by default.
method	method to be used to search the space of accessible permutations; must be one of "none", "exhaustive", "anneal", "hillclimb", or "mc".
reps	number of iterations for Monte Carlo method.
prob.init	initial acceptance probability for the annealing routine.
prob.decay	cooling multiplier for the annealing routine.
freeze.time	freeze time for the annealing routine.
full.neighborhood	should the annealer evaluate the full neighborhood of pair exchanges at each iteration?
mut	GA Mutation rate (currently ignored).
pop	GA population (currently ignored).
trials	number of GA populations (currently ignored).
exchange.list	information on which vertices are exchangeable (see below); this must be a single number, a vector of length n, or a nx2 matrix.

Details

The structural distance between two graphs G and H is defined as

d_S\left(G,H \left| L_G,L_H\right.\right) = \min_{L_G,L_H} d\left(\ell\left(G\right),\ell\left(H\right)\right)

where L_G is the set of accessible permutations/labelings of G, and \ell(G) is a permuation/relabeling of the vertices of G (\ell(G) \in L_G). The set of accessible permutations on a given graph is determined by the theoretical exchangeability of its vertices; in a nutshell, two vertices are considered to be theoretically exchangeable for a given problem if all predictions under the conditioning theory are invariant to a relabeling of the vertices in question (see Butts and Carley (2001) for a more formal exposition). Where no vertices are exchangeable, the structural distance becomes the its labeled counterpart (here, the Hamming distance). Where all vertices are exchangeable, the structural distance reflects the distance between unlabeled graphs; other cases correspond to distance under partial labeling.

The accessible permutation set is determined by the exchange.list argument, which is dealt with in the following manner. First, exchange.list is expanded to fill an nx2 matrix. If exchange.list is a single number, this is trivially accomplished by replication; if exchange.list is a vector of length n, the matrix is formed by cbinding two copies together. If exchange.list is already an nx2 matrix, it is left as-is. Once the nx2 exchangeabiliy matrix has been formed, it is interpreted as follows: columns refer to graphs 1 and 2, respectively; rows refer to their corresponding vertices in the original adjacency matrices; and vertices are taken to be theoretically exchangeable iff their corresponding exchangeability matrix values are identical. To obtain an unlabeled distance (the default), then, one could simply let exchange.list equal any single number. To obtain the Hamming distance, one would use the vector 1:n.

Because the set of accessible permutations is, in general, very large (o(n!)), searching the set for the minimum distance is a non-trivial affair. Currently supported methods for estimating the structural distance are hill climbing, simulated annealing, blind monte carlo search, or exhaustive search (it is also possible to turn off searching entirely). Exhaustive search is not recommended for graphs larger than size 8 or so, and even this may take days; still, this is a valid alternative for small graphs. Blind monte carlo search and hill climbing tend to be suboptimal for this problem and are not, in general recommended, but they are available if desired. The preferred (and default) option for permutation search is simulated annealing, which seems to work well on this problem (though some tinkering with the annealing parameters may be needed in order to get optimal performance). See the help for lab.optimize for more information regarding these options.

Structural distance matrices may be used in the same manner as any other distance matrices (e.g., with multidimensional scaling, cluster analysis, etc.) Classical null hypothesis tests should not be employed with structural distances, and QAP tests are almost never appropriate (save in the uniquely labeled case). See cugtest for a more reasonable alternative.

Value

A structural distance matrix

Warning

The search process can be very slow, particularly for large graphs. In particular, the exhaustive method is order factorial, and will take approximately forever for unlabeled graphs of size greater than about 7-9.

Note

Consult Butts and Carley (2001) for advice and examples on theoretical exchangeability.

Author(s)

Carter T. Butts [e-mail]

References

Butts, C.T. and Carley, K.M. (2005). “Some Simple Algorithms for Structural Comparison.” Computational and Mathematical Organization Theory, 11(4), 291-305.

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

See Also

hdist, sdmat

Examples

#Generate two random graphs
g<-array(dim=c(3,5,5))
g[1,,]<-rgraph(5)
g[2,,]<-rgraph(5)

#Copy one of the graphs and permute it
g[3,,]<-rmperm(g[2,,])

#What are the structural distances between the labeled graphs?
structdist(g,exchange.list=1:5)

#What are the structural distances between the underlying unlabeled 
#graphs?
structdist(g,method="anneal", prob.init=0.9, prob.decay=0.85, 
    freeze.time=50, full.neighborhood=TRUE)

sna documentation built on Sept. 11, 2024, 8:45 p.m.