Ticket #498 (needinfo enhancement)

Opened 3 years ago

Last modified 3 years ago

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

degree_seq.patch (2.0 KB) - added by anonymous 3 years ago.

Change History

Changed 3 years ago by anonymous

comment:1 Changed 3 years ago by aric

  • Status changed from new to needinfo

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"

comment:2 Changed 3 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 3 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 3 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 3 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 3 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 3 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 3 years ago by aric

Here is another paper that explains the issue and gives an alternate solution:

http://arxiv.org/abs/0912.0685v3

comment:9 Changed 3 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).

Note: See TracTickets for help on using tickets.