Node redundancy vs. clustering coefficient in bipartite graphs?

[Jack]

Hi,

Is there a difference between the results of the two methods when ran on bipartite graphs? Based on their description it seems like they are calculating the same thing.

I also ran it on a toy graph and got identical results (code below).

Can someone please provide a counter example or reference to a theoretical proof that shows those two are actually different (on bipartite graphs)? 

Thanks!

Code:

import networkx as nx

g2 = nx.Graph()

g2.add_node(1)

g2.add_node(2)

g2.add_node(3)

g2.add_node(4)

g2.add_node(5)

g2.add_edge(1,3)

g2.add_edge(1,4)

g2.add_edge(4,2)

g2.add_edge(3,2)

g2.add_edge(1,5)

g2.add_edge(5,2)

nx.draw(g2)

from networkx.algorithms import bipartite

rc = bipartite.node_redundancy(g2)

rc

c = bipartite.clustering(g2)

c

[Jordi Torrents]

Hi jack,

2014-04-12 11:05 GMT+02:00 Jack <wines...@gmail.com>:
> Hi,
>
> Is there a difference between the results of the two methods when ran on
> bipartite graphs? Based on their description it seems like they are
> calculating the same thing.
>
> I also ran it on a toy graph and got identical results (code below).
>
> Can someone please provide a counter example or reference to a theoretical
> proof that shows those two are actually different (on bipartite graphs)?

Yes, there is difference between these two measures. Latapy et al
(2008) paper (referenced in the documentation) explain it well.
Bipartite clustering measures the overlap of a node first order
neighbors with respect to all its second order neighbors (see page 13
of the pdf below). Bipartite redundancy of a node v is the fraction of
pairs of neighbours of v linked to another node than v. In the one
mode projection, these nodes would be linked together even if v were
not there, this is why they call this measure "redundancy" (see page
17 of the pdf below).

www-rp.lip6.fr/~latapy/Publis/socnet07.pdf

However, these two measures are related, and for some bipartite graphs
their value will be the same. This is the case of your example, which
is a complete bipartite graph of 3 nodes on the top and 2 on the
bottom (eg nx.complete_bipartite_graph(3, 2)). If you take the Davis
Souther Woman bipartite graph and compute these measures, you'll see
that they are not the same:

In [29]: G = nx.davis_southern_women_graph()

In [30]: cc = bipartite.clustering(G)

In [31]: rc = bipartite.node_redundancy(G)

In [32]: assert(cc != rc)

Salut!

> Thanks!
>
> Code:
> import networkx as nx
> g2 = nx.Graph()
> g2.add_node(1)
> g2.add_node(2)
> g2.add_node(3)
> g2.add_node(4)
> g2.add_node(5)
> g2.add_edge(1,3)
> g2.add_edge(1,4)
> g2.add_edge(4,2)
> g2.add_edge(3,2)
> g2.add_edge(1,5)
> g2.add_edge(5,2)
> nx.draw(g2)
>
> from networkx.algorithms import bipartite
> rc = bipartite.node_redundancy(g2)
> rc
>
> c = bipartite.clustering(g2)
> c
>

> --
> You received this message because you are subscribed to the Google Groups
> "networkx-discuss" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to networkx-discu...@googlegroups.com.
> To post to this group, send email to networkx...@googlegroups.com.
> Visit this group at http://groups.google.com/group/networkx-discuss.
> For more options, visit https://groups.google.com/d/optout.

[Jack]

Thank you very much Jordi! that was helpful