birewire.rewire.undirected: Efficient rewiring of undirected graphs

In BiRewire: High-performing routines for the randomization of a bipartite graph (or a binary event matrix), undirected and directed signed graph preserving degree distribution (or marginal totals)

Description

Optimal implementation of the switching algorithm. It returns the rewired version of the initial undirected graph or its adjacency matrix.

Usage

birewire.rewire.undirected(adjacency, max.iter="n",accuracy=0.00005,
verbose=TRUE,MAXITER_MUL=10,exact=FALSE)

Arguments

adjacency	An igraph undirected graph g or its adjacency matrix (can be extracted from g using get.adjacency). Since 3.6.0, if the matrix is provided, such matrix can contain also NAs and the position of such entries will be preserved by the SA
max.iter	"n" (default) the number of switching steps to be performed (or if exact==TRUE the number of successful switching steps). If equal to "n" then this number is considered equal to the analytically derived lower bound presented in Gobbi et al. (see References): N={e}/{(2d^3-6d^2+2d+2)} \ln{(e-de)} if exact is FALSE, N={e(1-d)}/{2} \ln{((e-de)/δ)} otherwise , where e is the number of edges of g and d its edge density . This bound is much lower than the empirical one proposed in Milo et al. 2003 (see References);
accuracy	0.00005 (default) is the desired level of accuracy reflecting the average distance between the Jaccard index at the N-th step and its analytically derived fixed point in terms of fracion of common edges;
verbose	TRUE (default) boolean value. If TRUE print a processing bar during the rewiring algorithm.
MAXITER_MUL	10 (default). If exact==TRUE in order to prevent a possible infinite loop the program stops anyway after MAXITER_MUL*max.iter iterations;
exact	FALSE (default). If TRUE the program performs max.iter swithcing steps, otherwise the program will count also the not-performed swithcing steps;

Details

Performs at most max.iter number of rewiring steps producing a rewired version of an initial undirected graph.

Value

Adjacency matrix of the rewired graph or the relative igraph object depending on the input type.

Author(s)

Andrea Gobbi
Maintainer: Andrea Gobbi <[e-mail]>
Special thanks to:Davide Albanese

References

Gobbi, A. and Iorio, F. and Dawson, K. J. and Wedge, D. C. and Tamborero, D. and Alexandrov, L. B. and Lopez-Bigas, N. and Garnett, M. J. and Jurman, G. and Saez-Rodriguez, J. (2014) Fast randomization of large genomic datasets while preserving alteration counts Bioinformatics 2014 30 (17): i617-i623 doi: 10.1093/bioinformatics/btu474.

Iorio, F. and and Bernardo-Faura, M. and Gobbi, A. and Cokelaer, T.and Jurman, G.and Saez-Rodriguez, J. (2016) Efficient randomization of biologicalnetworks while preserving functionalcharacterization of individual nodes Bioinformatics 2016 1 (17):542 doi: 10.1186/s12859-016-1402-1.

Gobbi, A. and Jurman, G. (2013) Theoretical and algorithmic solutions for null models in network theory (Doctoral dissertation) http://eprints-phd.biblio.unitn.it/1125/
R. Milo, N. Kashtan, S. Itzkovitz, M. E. J. Newman, U. Alon (2003), On the uniform generation of random graphs with prescribed degree sequences, eprint arXiv:cond-mat/0312028

Examples

library(igraph)
library(BiRewire)
g <- erdos.renyi.game(1000,0.1)
##gets the incidence matrix of g
 m<-as.matrix(get.adjacency(graph=g,sparse=FALSE))

## sets parameters
step=1000
max=100*length(E(g))

##rewiring 
m2=birewire.rewire.undirected(m,100*length(E(g))) 
##creates the corresponding bipartite graph 
g2<-graph.adjacency(m2,mode="undirected")

BiRewire documentation built on Nov. 8, 2020, 8:09 p.m.