Reciprocal links in DiGraph
Tony Hirst
I'm new to networkx, still finding my way around both it particular,
and social network analysis in general, and I was wondering:
- given a digraph, D, what's an efficient way of generating an
undirected graph, G, where an undirected edge A-B only exists between
nodes A and B if A->B and B->A in D.
thanks
tony
Moritz Beber
at the moment I can't think of a better way than iterating over the
edges and checking whether a bidirectional link exists. If you have an
extremely large number of (bidirectional) edges you might gain something
from using a list and checking the head of the list, then slice away the
head and throw away the edge in the other direction if it exists. So you
do not double check. But since these are quite extensive operations
simply iterating over the edges will in most cases be faster. Sorry,
these seem to be really crude techniques, probably someone else has a
better idea.
Best,
Moritz
Aric Hagberg
There is no "built-in" way to do this (but we could add that - see below).
The straightforward way is to check the edge directions. e.g.
import networkx as nx
D=nx.DiGraph()
D.add_path([1,2,3,4])
D.add_path([2,1])
# keep original graph
G=D.to_undirected() # copy
for (u,v) in D.edges():
if not D.has_edge(v,u):
G.remove_edge(u,v)
print G.edges()
# modify original graph
for (u,v) in D.edges():
if not D.has_edge(v,u):
D.remove_edge(u,v)
D=nx.Graph(D) # switch to undirected
print D.edges()
If this is a common operation we could consider adding a keyword
argument to DiGraph.to_undirected(), say "reciprocal=False" to
indicate whether the resulting Graph should have an edge if the digraph
has an edge in either direction (False) or both directions (True).
Aric
Moritz Beber
Is there a particular reason why you would choose to remove edges rather
than only add them if the bidirectional edge exists? (That's for the
case when you want to keep your original graph.)
Just curious,
Moritz
Aric Hagberg
>>
> Is there a particular reason why you would choose to remove edges rather
> than only add them if the bidirectional edge exists? (That's for the case
> when you want to keep your original graph.)
No - either way would clearly work. This way showed that there wasn't
much difference in the code if you didn't want to keep the original graph.
Neither is probably optimal for speed - but a faster version would require
modifying the underlying data structure directly.
Aric
Tony Hirst
The approach I would have guessed at was along lines of looking at
each node in D, finding the nodes it links out to in D, checking to
see if those nodes link back, and if they do writing a new edge on G.
In addition, each time an edge is checked and seen to exist in D,
remove it from D so it doesn't have to be checked again as later nodes
are inspected.
As this request seems not to be a common one, the use case is looking
at the structure of friends networks in twitter (in particular, the
connections between a persons friends, or between the members of a
list).
eg http://blog.ouseful.info/2010/09/27/initial-thoughts-on-profiling-dirdigengs-friends-network-on-twitter/
At the moment, A->B is A has declared B a friend (ie A follows B).
What I want is a view over the graph just showing people who follow
and are followed by each other, My suspicion being that in some
communities the network under this view is likely to fragment into
separate or very loosely coupled groupings
tony
Moritz Beber
iterator over the edges in that graph.
Aric Hagberg
> Thanks all for the advice...
>
> The approach I would have guessed at was along lines of looking at
> each node in D, finding the nodes it links out to in D, checking to
> see if those nodes link back, and if they do writing a new edge on G.
> In addition, each time an edge is checked and seen to exist in D,
> remove it from D so it doesn't have to be checked again as later nodes
> are inspected.
>
> As this request seems not to be a common one, the use case is looking
> at the structure of friends networks in twitter (in particular, the
> connections between a persons friends, or between the members of a
> list).
>
> eg http://blog.ouseful.info/2010/09/27/initial-thoughts-on-profiling-dirdigengs-friends-network-on-twitter/
I added a ticket with a suggested patch that would implement this
using a keyword,
i.e. D.to_undirected(reciprocal=True) .
https://networkx.lanl.gov/trac/ticket/441
If it is interesting enough I'll write some tests and we can include it.
Aric
>
> At the moment, A->B is A has declared B a friend (ie A follows B).
> What I want is a view over the graph just showing people who follow
> and are followed by each other, My suspicion being that in some
> communities the network under this view is likely to fragment into
> separate or very loosely coupled groupings
>
>
> tony
>
> On Sep 28, 3:06 am, Aric Hagberg <ahagb...@gmail.com> wrote:
>> On Mon, Sep 27, 2010 at 6:59 PM, Moritz Beber
>>
>>
>>
>> > Is there a particular reason why you would choose to remove edges rather
>> > than only add them if the bidirectional edge exists? (That's for the case
>> > when you want to keep your original graph.)
>>
>> No - either way would clearly work. This way showed that there wasn't
>> much difference in the code if you didn't want to keep the original graph.
>> Neither is probably optimal for speed - but a faster version would require
>> modifying the underlying data structure directly.
>>
>> Aric
>
> --
> You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
> To post to this group, send email to networkx...@googlegroups.com.
> To unsubscribe from this group, send email to networkx-discu...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/networkx-discuss?hl=en.
>
>