Re: [igraph] Rewire probabilities question
Hi, Q1: Does the code below identify properly the new edges in the rewired > graph in comparison to the original? > Well, the code is more or less correct -- it does not account for corner cases like when an edge ends up being rewired twice or more (in such cases, the edge may even end up being identical with some other edge from the original one), but for large graphs, the probability of such corner cases is negligible. Also, the function currently relies on the fact that the order of edges is not changed during rewire, i.e. edge i in the original graph ends up being edge i in the rewired graph -- the documentation does not guarantee this so it may break in future releases. Q2: Why is it that, with a rewire of approx p=.30, I get approx 50% new > edges (given the way I’ve defined new below). > It is because p is not equal to the probability of selecting an edge for rewiring. I am not sure about the documentation of the R interface of igraph; it may not be stated there, but the documentation of the C core says that "each endpoint of each edge is rewired to a uniformly randomly chosen vertex with constant probability". Since an edge in an undirected graph has two endpoints, each edge gets *two* chances to be rewired -- therefore, the probability of an edge _not_ being rewired is equal to (1 - 0.3) * (1 - 0.3) = 0.49. T. ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
[igraph] Rewire probabilities question
Hi All, I’m using rewire(g,each_edge(p=x)). One of my needs is to identify which of the edges in the rewired graph are rewires from the original graph for which I’ve written a piece of code below. (SEE SIMPLE EXAMPLE BELOW).I have two questions for which I would be very appreciative of an answer from the group. I’m not well versed in C code, so the git repository doesn’t really help me in figuring this out. Q1: Does the code below identify properly the new edges in the rewired graph in comparison to the original? Q2: Why is it that, with a rewire of approx p=.30, I get approx 50% new edges (given the way I’ve defined new below). Any help very much appreciated. Thanks, Mark #BEGIN rm(list=ls()) #MAKE ORIGINAL AND REWIRED GRAPH--tested with ring then watts... #g.1 <- graph.ring(1) g.1 <- watts.strogatz.game(dim=1,size=1,nei=2,p=0) g.2 <- rewire(g.1,each_edge(prob=.29)) #COMBINE EDGE LISTS INTO DATA FRAME FOR COMPARISON g.1.edgeframe <- data.frame(get.edgelist(g.1)) g.2.edgeframe <- data.frame(get.edgelist(g.2)) g.comb <- cbind(g.1.edgeframe,g.2.edgeframe) names(g.comb) <- c("g1.a","g1.b","g2.a","g2.b") #ASSESS REWIRED EDGES g.comb$new <- 1 g.comb$new[g.comb$g1.a==g.comb$g2.a & g.comb$g1.b==g.comb$g2.b] <- 0 #CALCULATE PROPORTION NEW print(mean(g.comb$new)) #EOF --- Mark Orr Research Associate Professor Social and Decision Analytics Laboratory Biocomplexity Institute of Virginia Tech 900 North Glebe Rd. Arlington, VA 22203 p: 571-858-3116 f: 571-858-3015 mo...@vt.edu ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
Re: [igraph] rewire
> > (2) If I set niter = 100, does it mean 100 edge pairs will be rewired? >> > > No, it means that 100 attempts will be made. Some may be unsuccessful. > Correct. > Is there a probability that controls whether to rewire each selected edge >> pairs? >> > No, there isn't - each edge is selected with equal probability for a rewiring attempt. You can control the probability indirectly by specifying the number of trials. For instance, if the number of trials is equal to half the number of edges, then each edge is expected to be selected for rewiring once (although of course this is not guaranteed). Some times a randomly selected edge pair can not be rewired, will this >> counted a trial or only successfully rewired ones will be counted as a >> trail? >> > > "Trial" means "attempt". Not all attempts will be successful. > Correct. > (3) Sometimes, the rewired network will be divided into several >> components, even when the original network is one connected component. Is >> there is a way to control the rewire process make the network connected? >> > No, there isn't - this would involve checking whether the network stays connected after each rewiring attempt, and this is costly. You can do this yourself, however: 1. make a copy of your graph 2. perform 1000 rewiring attempts, check whether the graph is connected 3. if the graph is connected, go to step 1 and continue rewiring. 4. if the graph is not connected, take the last copy of your graph and continue from step 2. You could of course perform only one attempt in step 2, but this would probably be slow because the implementation of igraph_rewire first converts the graph to an alternative representation where rewiring is faster, and then converts it back. Therefore, the more attempts you perform in a single batch, the faster it will be - although of course you risk performing more trials unnecessarily before you realize that the graph became disconnected. Rewiring many times creates a random graph with the same degree sequence as > your starting point. You can check out the degree sequence game function > with the Viger-Latapy method, which creates connected graphs. > This is a very good point - in many cases, you are not actually interested in rewiring the graph, you just want to get another graph with the same degree sequence. The Viger-Latapy method in the degree sequence game does exactly this, and it also ensures connectedness. Best, T. ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
Re: [igraph] rewire
On 10 September 2015 at 15:21, Qunawei Zhang wrote: > Hello: > > I have some questions about rewire, would you please explain to me? Thanks > (1) Each iteration, two edges are randomly selected right? And the new > edges (which generated by the rewiring) can also be selected and to be > rewire again? > The following is based on my understanding, and may not be fully accurate. The igraph authors will correct me if necessary. In each step you select two disjoint edges and swap the endpoints if possible. E.g., A-B, C-D can be swapped to A-C, B-D or to A-D, B-C, if those edges do not already exist. > (2) If I set niter = 100, does it mean 100 edge pairs will be rewired? > No, it means that 100 attempts will be made. Some may be unsuccessful. > Is there a probability that controls whether to rewire each selected edge > pairs? > Sorry, I don't understand this question. > Some times a randomly selected edge pair can not be rewired, will this > counted a trial or only successfully rewired ones will be counted as a > trail? > "Trial" means "attempt". Not all attempts will be successful. Ensuring that precisely 100 swaps will be performed is rather problematic to implement in a useful (and fast) way because it would involve checking whether any edges can be swapped at all. (3) Sometimes, the rewired network will be divided into several components, > even when the original network is one connected component. Is there is a > way to control the rewire process make the network connected? I tried to > just selected the connected random network, but I can only get a few from > 1000 random network, and I need much more. > Rewiring many times creates a random graph with the same degree sequence as your starting point. You can check out the degree sequence game function with the Viger-Latapy method, which creates connected graphs. > > rewire(graph, mode = c("simple", "loops"), niter = 100) > niter > > Number of rewiring trials to perform. > > > Thanks. > > Best > Quanwei > > ___ > igraph-help mailing list > igraph-help@nongnu.org > https://lists.nongnu.org/mailman/listinfo/igraph-help > > ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
[igraph] rewire
Hello: I have some questions about rewire, would you please explain to me? Thanks (1) Each iteration, two edges are randomly selected right? And the new edges (which generated by the rewiring) can also be selected and to be rewire again? (2) If I set niter = 100, does it mean 100 edge pairs will be rewired? Is there a probability that controls whether to rewire each selected edge pairs? Some times a randomly selected edge pair can not be rewired, will this counted a trial or only successfully rewired ones will be counted as a trail? (3) Sometimes, the rewired network will be divided into several components, even when the original network is one connected component. Is there is a way to control the rewire process make the network connected? I tried to just selected the connected random network, but I can only get a few from 1000 random network, and I need much more. rewire(graph, mode = c("simple", "loops"), niter = 100) niterNumber of rewiring trials to perform. Thanks. Best Quanwei ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
Re: [igraph] rewire vs. degree.sequence.game
> One of the graphs I am using currently only has ~1e2 edges, so I think 1e4 > may be enough. I remember reading a paper citing that 10*|E| is sufficient, > but will have to look again. I think ~1e4 should be enough hen, especially if you are using the graph as a starting point for a Markov chain. T. ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
Re: [igraph] rewire vs. degree.sequence.game
Thank you for the response. One of the graphs I am using currently only has ~1e2 edges, so I think 1e4 may be enough. I remember reading a paper citing that 10*|E| is sufficient, but will have to look again. Additionally, I will be using a Markov Chain method to rewire graphs so that they match the transitivity of my graph of interest (in addition to the degree distribution). I was mainly wondering if using 'rewire' with ~1e4 iterations would create a graph that is "random enough" from which to start the Markov Chain process. Thanks, Chris On Fri, Jul 4, 2014 at 5:48 AM, Tamás Nepusz wrote: > > Hello, > > > I was wondering how different the functions 'rewire' and > 'degree.sequence.game' are. > degree.sequence.game() constructs a graph from scratch, while rewire() > rewires an existing graph. This means that you must "guesstimate" the > number of rewiring attempts to perform in case of your particular graph to > ensure that you do enough rewires so that the starting point (i.e. the > original graph) becomes irrelevant. I think there are some theoretical > results (or at least rules of thumb) in the literate about the optimal > number of rewiring attempts, but I cannot cite any off the top of my head. > In general, the number of rewiring attempts is usually chosen so that every > edge of the graph is attempted to be rewired at least k times on average -- > choosing the right k is then up to you. > > > Would there be a problem with calling rewire with, e.g. 1e4 iterations? > It depends on the size of your graph. If your graph contains, say, 1e6 > edges, then using only 1e4 rewiring attempts is not enough because it will > touch only 2e4 edges out of the 1e6 -- and even then it is not guaranteed > that every rewiring attempt is successful. > > You might also try static.fitness.game(), which generates networks where > the probability of an edge between two vertices is proportional to some > fitness scores of the endpoints. It can be shown that the _expected_ > degrees of the vertices are then proportional to the fitness scores (but > not the _actual_ degrees) if we allow loop and multiple edges. (Banning > loop and multiple edges introduces some bias, but it might not be > noticeable for your graphs so it's worth trying if you don't need to match > the degrees of the original graph *exactly* but only on average). > > Best, > T. > ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
Re: [igraph] rewire vs. degree.sequence.game
Hello, > I was wondering how different the functions 'rewire' and > 'degree.sequence.game' are. degree.sequence.game() constructs a graph from scratch, while rewire() rewires an existing graph. This means that you must "guesstimate" the number of rewiring attempts to perform in case of your particular graph to ensure that you do enough rewires so that the starting point (i.e. the original graph) becomes irrelevant. I think there are some theoretical results (or at least rules of thumb) in the literate about the optimal number of rewiring attempts, but I cannot cite any off the top of my head. In general, the number of rewiring attempts is usually chosen so that every edge of the graph is attempted to be rewired at least k times on average -- choosing the right k is then up to you. > Would there be a problem with calling rewire with, e.g. 1e4 iterations? It depends on the size of your graph. If your graph contains, say, 1e6 edges, then using only 1e4 rewiring attempts is not enough because it will touch only 2e4 edges out of the 1e6 -- and even then it is not guaranteed that every rewiring attempt is successful. You might also try static.fitness.game(), which generates networks where the probability of an edge between two vertices is proportional to some fitness scores of the endpoints. It can be shown that the _expected_ degrees of the vertices are then proportional to the fitness scores (but not the _actual_ degrees) if we allow loop and multiple edges. (Banning loop and multiple edges introduces some bias, but it might not be noticeable for your graphs so it's worth trying if you don't need to match the degrees of the original graph *exactly* but only on average). Best, T. ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
[igraph] rewire vs. degree.sequence.game
(sorry if this is double posted) Hello, I was wondering how different the functions 'rewire' and 'degree.sequence.game' are. In some data I'm using, degree.sequence.game takes prohibitively long to find a solution (I use the option 'simple.no.multiple'; I cannot use 'vl' because the graph in question is unconnected). Would there be a problem with calling rewire with, e.g. 1e4 iterations? Thanks, Chris ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
[igraph] rewire vs. degree.sequence.game
Hello, I was wondering how different the functions 'rewire' and 'degree.sequence.game' are. In some data I'm using, degree.sequence.game takes prohibitively long to find a solution (I use the option 'simple.no.multiple'; I cannot use 'vl' because the graph in question is unconnected). Would there be a problem with calling rewire with, e.g. 1e4 iterations? Thanks, Chris ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
Re: [igraph] rewire till assortivity.degree reaches certain value.
thanks for your reply. your solution for 1,2,3 step worked for me and it reaches desired value for assortivity.degree in few seconds. Thanks & Regards Suvir On Tue, Apr 23, 2013 at 12:22 AM, Tamás Nepusz wrote: > > How to i make it to move in one direction(either towards more positive or > > more negative) of values? > Well, you write your own rewiring function that strives to increase or > decrease assortativity explicitly ;) The degree-preserving rewiring > implemented in igraph does not care about assortativity at all. > > A (probably) slow way of doing what you want would be as follows: > > 1. Calculate the assortativity of your current graph. > 2. Rewire your original graph using a small value for the "niter" > parameter of rewire(); maybe try with niter=10 first. > 3. Calculate the assortativity of the rewired graph. If it went in the > desired direction, keep the rewired graph and go back to the previous step > to keep on rewiring. Otherwise, keep the original graph before the last > rewiring step and try again from step 2. > > The reason why I'm saying that it's probably slow is because there is a > constant overhead associated with the rewire() call since it makes a copy > of your graph (this is the standard way of doing things in R). If your > graph is large, the cost of copying will dominate the cost of making a > single rewiring step. > > -- > T. > ___ > igraph-help mailing list > igraph-help@nongnu.org > https://lists.nongnu.org/mailman/listinfo/igraph-help > ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
Re: [igraph] rewire till assortivity.degree reaches certain value.
> How to i make it to move in one direction(either towards more positive or > more negative) of values? Well, you write your own rewiring function that strives to increase or decrease assortativity explicitly ;) The degree-preserving rewiring implemented in igraph does not care about assortativity at all. A (probably) slow way of doing what you want would be as follows: 1. Calculate the assortativity of your current graph. 2. Rewire your original graph using a small value for the "niter" parameter of rewire(); maybe try with niter=10 first. 3. Calculate the assortativity of the rewired graph. If it went in the desired direction, keep the rewired graph and go back to the previous step to keep on rewiring. Otherwise, keep the original graph before the last rewiring step and try again from step 2. The reason why I'm saying that it's probably slow is because there is a constant overhead associated with the rewire() call since it makes a copy of your graph (this is the standard way of doing things in R). If your graph is large, the cost of copying will dominate the cost of making a single rewiring step. -- T. ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
Re: [igraph] rewire till assortivity.degree reaches certain value.
Hi, I'm doing this.original assortivity is -0.08167785 for (i in 1:100) { jg <- rewire(jg, mode = c("loops"), 1) print(assortativity.degree(jg)) } with top ten values in loop as : [1] 0.03132712 [1] -0.0562163 [1] -0.00841146 [1] -0.01359139 [1] -0.03106399 [1] -0.005318964 [1] -0.01219977 [1] 0.009112685 [1] 0.01743665 [1] -0.02284311 With both positive and negative values. How to i make it to move in one direction(either towards more positive or more negative) of values? i don't know what is the relation between iterations here with assortive.degree. Thanks & Regards Suvir On Mon, Apr 22, 2013 at 11:16 PM, Tamás Nepusz wrote: > > i want to do degree preserving rewire till degree > correlation(assortivity.degree) reaches certain value. > > Should i keep doing this in a loop,chehcking everytime > assortivity.degree value or is there any better way? > Just use a loop -- I am not aware of any better way, at least not in > igraph. I would probably also perform rewire() with a high number of > iterations between consecutive checks of assortativity.degree, because > rewiring is quite an expensive operation with igraph's current data > structures. Based on the difference between the _current_ value of > assortativity.degree and the desired one, you can also "guesstimate" the > number of iterations to make things faster. > > > Also,is there any IRC channel for igraph? > No, there isn't. > > Best, > Tamas > > > ___ > igraph-help mailing list > igraph-help@nongnu.org > https://lists.nongnu.org/mailman/listinfo/igraph-help > ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
Re: [igraph] rewire till assortivity.degree reaches certain value.
> i want to do degree preserving rewire till degree > correlation(assortivity.degree) reaches certain value. > Should i keep doing this in a loop,chehcking everytime assortivity.degree > value or is there any better way? Just use a loop -- I am not aware of any better way, at least not in igraph. I would probably also perform rewire() with a high number of iterations between consecutive checks of assortativity.degree, because rewiring is quite an expensive operation with igraph's current data structures. Based on the difference between the _current_ value of assortativity.degree and the desired one, you can also "guesstimate" the number of iterations to make things faster. > Also,is there any IRC channel for igraph? No, there isn't. Best, Tamas ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
[igraph] rewire till assortivity.degree reaches certain value.
Hi, i want to do degree preserving rewire till degree correlation(assortivity.degree) reaches certain value. Should i keep doing this in a loop,chehcking everytime assortivity.degree value or is there any better way? Also,is there any IRC channel for igraph? Thanks & Regards Suvir ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
Re: [igraph] Rewire in general
Hi Nina, > I was just reading some requests to change the rewire-function: I am also in > trouble because I need a fast rewiring method that maintains the (directed) > degree distribution and AVOIDS self-loops. I noticed that in November 2012 > somebody actually wanted the rewiring to include self-loops, and you fixed > that > 'bug', but actually I do not think it is a bug if self-loops cannot be > created. > In my opinion, it would be very nice to have a Boolean that allows switching > the > creation of self-loops on or off. Do not worry, both methods are still in there; the rewire function will offer a "mode" argument where you can specify whether you want to allow the creation of self-loops or not. > Another thing I noticed: The verbal description of the rewire-function does > not > make clear whether the permutation of undirected graphs is correct, i.e., > whether edges can be "picked" in both directions. Thanks for the suggestion; the release process of igraph 0.6.4 has already started so we cannot add this to the documentation of 0.6.4 but we will include it in 0.6.5 or 0.7, whichever comes first. All the best, Tamas ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
[igraph] Rewire in general
Hi Tamás, thanks for the work all of you put into igraph. I was just reading some requests to change the rewire-function: I am also in trouble because I need a fast rewiring method that maintains the (directed) degree distribution and AVOIDS self-loops. I noticed that in November 2012 somebody actually wanted the rewiring to include self-loops, and you fixed that 'bug', but actually I do not think it is a bug if self-loops cannot be created. In my opinion, it would be very nice to have a Boolean that allows switching the creation of self-loops on or off. (In case self-loops are wanted, the fasted way would be to use r2dtables, as they easily create matrices with fixed marginals and self-loops). In any case it would be helpful if the way you handle self-loops would become more clear. Another thing I noticed: The verbal description of the rewire-function does not make clear whether the permutation of undirected graphs is correct, i.e., whether edges can be "picked" in both directions. A small test on the rewire function quickly revealed that this is actually the case, but maybe the documentation could be a bit more verbose there. Thanks again, Nina ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
Re: [igraph] rewire() and self loops
Hi Dov, I have recently fixed this in the development branch. If you wanna give it a go and don't mind compiling it yourself, check out the nightly build tomorrow: http://code.google.com/p/igraph/downloads/list Revision 3006 of the 0.7-main tree should include all the changes -- this will be uploaded around 6am GMT tomorrow. Best, -- T. On Thursday, 11 October 2012 at 21:43, Gábor Csárdi wrote: > Hi Dov, > > I think this is simply a bug. He have this in the C code for rewire: > > if (!igraph_vector_search(neis[0], 0, d, NULL) && > !igraph_vector_search(neis[1], 0, b, NULL) && > b!=c && a!=d && a!=b && c!=d) { > do the rewiring here > } > > So, yes, if a=b or a=d, or b=c or c=d, the rewiring is not performed, > I am not sure why. I have submitted a bug report for this: > https://bugs.launchpad.net/igraph/+bug/1065681 > > Thanks, Best, > Gabor > > > On Thu, Oct 11, 2012 at 3:29 PM, Dov Pechenick (mailto:dapec...@gmail.com)> wrote: > > Hello, > > > > I'm using igraph in R, and I'm trying to randomize the edges of directed > > graphs while preserving in- and out-degree distributions. Since my graphs > > are directed, I don't use degree.sequence.game(). Instead, I've been using > > rewire(). This function correctly preserves the degree distribution, > > however as far as I can tell it completely ignores self loop edges during > > the rewiring process. That is to say, every single self loop in my original > > network is also preserved in all my rewired networks. I did not expect this > > based on the documentation: > > > > "simple rewiring algorithm which chooses two arbitrary edges in each step > > (namely (a,b) and (c,d)) and substitutes them with (a,d) and (c,b) if they > > don't yet exist" > > > > While true that self loops aren't explicitly mentioned, the most general > > form of the algorithm allows a==b and c==d. Thus, this algorithm should > > allow for the generation and destruction of self-loops. For example, a->a > > and b->b can be replaced with a->b and b->a if they don't yet exist. The > > reverse should also be a valid swap. I tested this on the following > > networks, just to be sure: > > > > a <- graph(c(0,0,1,1,2,2,3,3)) # 4 nodes, only self loops > > b <- graph(c(0,1,1,0,2,3,3,2,0,2,2,0,0,3,3,0,1,2,2,1,1,3,3,1)) # 4 node > > complete graph, no self loops > > > > Rewiring using rewire() does nothing to the above graphs. For a, self loops > > are never destroyed, and for b, they are never created. If I am missing > > something, please let me know. Otherwise, is there a way to rewire directed > > graphs that both preserves degree distribution and allows for the generation > > and destruction of self-loops? (Ideally it would be the same function, with > > an option to allow self-loops.) > > > > Thanks! > > Dov > > > > ___ > > igraph-help mailing list > > igraph-help@nongnu.org (mailto:igraph-help@nongnu.org) > > https://lists.nongnu.org/mailman/listinfo/igraph-help > > > > > > -- > Gabor Csardi mailto:csa...@rmki.kfki.hu)> MTA KFKI RMKI > > ___ > igraph-help mailing list > igraph-help@nongnu.org (mailto:igraph-help@nongnu.org) > https://lists.nongnu.org/mailman/listinfo/igraph-help ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
Re: [igraph] rewire() and self loops
Hi Dov, I think this is simply a bug. He have this in the C code for rewire: if (!igraph_vector_search(neis[0], 0, d, NULL) && !igraph_vector_search(neis[1], 0, b, NULL) && b!=c && a!=d && a!=b && c!=d) { do the rewiring here } So, yes, if a=b or a=d, or b=c or c=d, the rewiring is not performed, I am not sure why. I have submitted a bug report for this: https://bugs.launchpad.net/igraph/+bug/1065681 Thanks, Best, Gabor On Thu, Oct 11, 2012 at 3:29 PM, Dov Pechenick wrote: > Hello, > > I'm using igraph in R, and I'm trying to randomize the edges of directed > graphs while preserving in- and out-degree distributions. Since my graphs > are directed, I don't use degree.sequence.game(). Instead, I've been using > rewire(). This function correctly preserves the degree distribution, > however as far as I can tell it completely ignores self loop edges during > the rewiring process. That is to say, every single self loop in my original > network is also preserved in all my rewired networks. I did not expect this > based on the documentation: > > "simple rewiring algorithm which chooses two arbitrary edges in each step > (namely (a,b) and (c,d)) and substitutes them with (a,d) and (c,b) if they > don't yet exist" > > While true that self loops aren't explicitly mentioned, the most general > form of the algorithm allows a==b and c==d. Thus, this algorithm should > allow for the generation and destruction of self-loops. For example, a->a > and b->b can be replaced with a->b and b->a if they don't yet exist. The > reverse should also be a valid swap. I tested this on the following > networks, just to be sure: > > a <- graph(c(0,0,1,1,2,2,3,3)) # 4 nodes, only self loops > b <- graph(c(0,1,1,0,2,3,3,2,0,2,2,0,0,3,3,0,1,2,2,1,1,3,3,1)) # 4 node > complete graph, no self loops > > Rewiring using rewire() does nothing to the above graphs. For a, self loops > are never destroyed, and for b, they are never created. If I am missing > something, please let me know. Otherwise, is there a way to rewire directed > graphs that both preserves degree distribution and allows for the generation > and destruction of self-loops? (Ideally it would be the same function, with > an option to allow self-loops.) > > Thanks! > Dov > > ___ > igraph-help mailing list > igraph-help@nongnu.org > https://lists.nongnu.org/mailman/listinfo/igraph-help > -- Gabor Csardi MTA KFKI RMKI ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
[igraph] rewire() and self loops
Hello, I'm using igraph in R, and I'm trying to randomize the edges of directed graphs while preserving in- and out-degree distributions. Since my graphs are directed, I don't use degree.sequence.game(). Instead, I've been using rewire(). This function correctly preserves the degree distribution, however as far as I can tell it completely ignores self loop edges during the rewiring process. That is to say, every single self loop in my original network is also preserved in all my rewired networks. I did not expect this based on the documentation: "simple rewiring algorithm which chooses two arbitrary edges in each step (namely (a,b) and (c,d)) and substitutes them with (a,d) and (c,b) if they don't yet exist" While true that self loops aren't explicitly mentioned, the most general form of the algorithm allows a==b and c==d. Thus, this algorithm should allow for the generation and destruction of self-loops. For example, a->a and b->b can be replaced with a->b and b->a if they don't yet exist. The reverse should also be a valid swap. I tested this on the following networks, just to be sure: a <- graph(c(0,0,1,1,2,2,3,3)) # 4 nodes, only self loops b <- graph(c(0,1,1,0,2,3,3,2,0,2,2,0,0,3,3,0,1,2,2,1,1,3,3,1)) # 4 node complete graph, no self loops Rewiring using rewire() does nothing to the above graphs. For a, self loops are never destroyed, and for b, they are never created. If I am missing something, please let me know. Otherwise, is there a way to rewire directed graphs that both preserves degree distribution and allows for the generation and destruction of self-loops? (Ideally it would be the same function, with an option to allow self-loops.) Thanks! Dov ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help