Opened 5 years ago
Last modified 5 years ago
#498 needinfo enhancement
double_edge_swap for directed graphs
Reported by: | anonymous | Owned by: | aric |
---|---|---|---|
Priority: | normal | Milestone: | networkx-future |
Component: | networkx | Version: | |
Severity: | normal | Keywords: | |
Cc: |
Description
Currently, double_edge_swap doesn't work for DiGraph?. I have attached the patch for degree_seq.py that should make double_edge_swap work for directed graphs.
Attachments (1)
Change History (10)
Changed 5 years ago by anonymous
comment:1 Changed 5 years ago by aric
- Status changed from new to needinfo
comment:2 Changed 5 years ago by anonymous
The Havel-Hakimi algorithm is biased so it is not good for estimating the null distributions of graph features. Does the patch do something that makes it unbiased and so should not be included. In other words, is there reason to believe that the double_edge_swap should not work for directed graphs?
comment:3 Changed 5 years ago by aric
I thought Theorem 7 (in Section 4) implied that you need to also consider 3-edge swaps for directed graphs.
comment:4 follow-up: ↓ 5 Changed 5 years ago by anonymous
He mentions 2-edge and 3-edge swaps, but I am not sure which transformations this implementation does not do. As far as I can see the microscopic reversibility is maintained, and as long as the all sample space is reachable, it should be fine.
comment:5 in reply to: ↑ 4 Changed 5 years ago by aric
Replying to anonymous:
and as long as the all sample space is reachable, it should be fine.
I think that is the issue. I haven't read enough of the details to understand the paper.
comment:6 Changed 5 years ago by anonymous
This discussion seems to answer the question of what sort of 3-node swaps are needed to sample directed graphs. Integrating this shouldn't be very hard.
comment:7 Changed 5 years ago by moritz.beber
I was not aware of the triple edge swapping methods until now. I have implemented a method myself that distinguishes unidirectional edges and bidirectional edges as two categories of links. It lacks a bit of documentation and testing otherwise I would attach it here.
What would an acceptable test look like?
comment:8 Changed 5 years ago by aric
Here is another paper that explains the issue and gives an alternate solution:
comment:9 Changed 5 years ago by moritz.beber
That's the working group my flatmate is in =P He's of the opinion that mixing with just two edges is good enough if one is interested in raw few-node subgraph counts. I'll look into it, though, when I have a bit more time (one or two weeks from now).
This was discussed in ticket #447 where I recommended to look at this paper: http://www.combinatorics.org/Volume_17/PDF/v17i1r66.pdf "A simple Havel–Hakimi type algorithm to realize graphical degree sequences of directed graphs"