Extracting Multiscale Backbone of Complex Weighted Networks

[Brian Keegan]

Has anyone implemented or know of a Pythonic implementation of the edge-weight filter proposed in [1] within NetworkX?

Best,

Brian

[1] Serrano, Boguna, & Vespignani (2009) http://www.pnas.org/content/106/16/6483.abstract

-- 
Brian C. Keegan
Ph.D. Student - Media, Technology, & Society
School of Communication, Northwestern University

Science of Networks in Communities, Laboratory for Collaborative Technology

[Brian Keegan]

I'm not sure if this is exactly right (i.e., translating math to code), but it appears to accomplish the intended result. Thanks to Michael Conover at Indiana for help with it. 

Does this correspond to what you are using Qian?

def extract_backbone(g, alpha):

  backbone_graph = nx.Graph()

  for node in g:

      k_n = len(g[node])

      if k_n > 1:

          sum_w = sum( g[node][neighbor]['weight'] for neighbor in g[node] )

          for neighbor in g[node]:

              edgeWeight = g[node][neighbor]['weight']

              pij = float(edgeWeight)/sum_w

              if (1-pij)**(k_n-2) < alpha: # equation 2

                  backbone_graph.add_edge( node,neighbor, weight = edgeWeight)

  return backbone_graph

On Wed, Jun 20, 2012 at 10:05 AM, Qian <zhangqi...@gmail.com> wrote:

i have a python version for directed weighted networks (without using networkx), and a matlab version for undirected ones.

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To view this discussion on the web visit https://groups.google.com/d/msg/networkx-discuss/-/3W6bYRFIqJkJ.
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.

[Qian]

i am not sure why you calculate equation 2 with (1-pij)**(k_n-2) <
alpha. Maybe it is an approximation? I did not calculate if this
approximation is correct. But if you are sure, it is ok.

what i did is 1 - (k-1)*integrate.quad(f, 0, p)[0] < alpha
(from scipy import integrate)

btw, Michael is my friend and we were in the same program :)

> >> [1] Serrano, Boguna, & Vespignani (2009)http://www.pnas.org/**
> >> content/106/16/6483.abstract<http://www.pnas.org/content/106/16/6483.abstract>

[Brian Keegan]

Wasn't an approximation, probably me just doing it wrong. Using your approach, should the code look like this?

def extract_backbone(g, alpha):

  backbone_graph = nx.Graph()

  for node in g:

      k_n = len(g[node])

      if k_n > 1:

          sum_w = sum( g[node][neighbor]['weight'] for neighbor in g[node] )

          for neighbor in g[node]:

              edgeWeight = g[node][neighbor]['weight']

              pij = float(edgeWeight)/sum_w

              f = lambda p,k: (1-p)**(k-2)

              x = 1-(k_n-1)*integrate.quad(f,0.,pij,args=(k_n))[0] # equation 2

              if x < alpha: 

                  backbone_graph.add_edge( node,neighbor, weight = edgeWeight)

  return backbone_graph

[Qian]

I would say,
f = lambda x: (1-x)**(k_n-2)
alpha_ij = 1 - (k_n-1)*integrate.quad(f, 0, pij)[0]

On Jun 20, 12:14 pm, Brian Keegan <bkee...@northwestern.edu> wrote:
> Wasn't an approximation, probably me just doing it wrong. Using your
> approach, should the code look like this?
>
> def extract_backbone(g, alpha):
>   backbone_graph = nx.Graph()
>   for node in g:
>       k_n = len(g[node])
>       if k_n > 1:
>           sum_w = sum( g[node][neighbor]['weight'] for neighbor in g[node] )
>           for neighbor in g[node]:
>               edgeWeight = g[node][neighbor]['weight']
>               pij = float(edgeWeight)/sum_w
>               f = lambda p,k: (1-p)**(k-2)
>               x = 1-(k_n-1)*integrate.quad(f,0.,pij,args=(k_n))[0] #
> equation 2
>               if x < alpha:
>                   backbone_graph.add_edge( node,neighbor, weight =
> edgeWeight)
>   return backbone_graph
>

> On Wed, Jun 20, 2012 at 11:07 AM, Brian Keegan <bkee...@northwestern.edu>wrote:
>
>
>
>
>
>
>
>
>
> > I'm not sure if this is exactly right (i.e., translating math to code),
> > but it appears to accomplish the intended result. Thanks to Michael Conover
> > at Indiana for help with it.
>
> > Does this correspond to what you are using Qian?
>
> > def extract_backbone(g, alpha):
> >   backbone_graph = nx.Graph()
> >   for node in g:
> >       k_n = len(g[node])
> >       if k_n > 1:
> >           sum_w = sum( g[node][neighbor]['weight'] for neighbor in g[node]
> > )
> >           for neighbor in g[node]:
> >               edgeWeight = g[node][neighbor]['weight']
> >               pij = float(edgeWeight)/sum_w
> >               if (1-pij)**(k_n-2) < alpha: # equation 2
> >                   backbone_graph.add_edge( node,neighbor, weight =
> > edgeWeight)
> >   return backbone_graph
>

> > On Wed, Jun 20, 2012 at 10:05 AM, Qian <zhangqian.r...@gmail.com> wrote:
>
> >> i have a python version for directed weighted networks (without using
> >> networkx), and a matlab version for undirected ones.
>
> >> On Tuesday, June 5, 2012 3:19:47 PM UTC-4, Brian Keegan wrote:
>
> >>> Has anyone implemented or know of a Pythonic implementation of the
> >>> edge-weight filter proposed in [1] within NetworkX?
>
> >>> Best,
>
> >>> Brian
>

> >>> [1] Serrano, Boguna, & Vespignani (2009)http://www.pnas.org/**
> >>> content/106/16/6483.abstract<http://www.pnas.org/content/106/16/6483.abstract>

[clayadavis]

I realize this thread is super dead, but it is still the first Google search result for "networkx backbone extraction", so hopefully I can prevent some mistakes.

If you do the math, Qian's solution

f = lambda x: (1-x)**(k_n-2) 
alpha_ij =  1 - (k_n-1)*integrate.quad(f, 0, pij)[0]

if x < alpha: 

is equivalent to this:

if (1-pij)**(k_n-1):

 

This is close to, but not quite Bryan's originally proposed 

if (1-pij)**(k_n-2) < alpha: # equation 2

which has the wrong exponent.

For completeness, here is the proper code in its entirety:

def extract_backbone(g, alpha):

  backbone_graph = nx.Graph()

  for node in g:

      k_n = len(g[node])

      if k_n > 1:

          sum_w = sum( g[node][neighbor]['weight'] for neighbor in g[node] )

          for neighbor in g[node]:

              edgeWeight = g[node][neighbor]['weight']

              pij = float(edgeWeight)/sum_w

              if (1-pij)**(k_n-1) < alpha: # equation 2

                  backbone_graph.add_edge( node,neighbor, weight = edgeWeight)

  return backbone_graph

-CAD

[amitabh sharma]

CAD, can we use this code for undirected also ? If I get it right, this will give me the backbone of a big Network to visualize ?

thanks

A

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/groups/opt_out.

[Brian Keegan]

I've posted this code as a gist here (https://gist.github.com/brianckeegan/8846206) and will update it now with acknowledgement to Clay Davis.

[amitabh sharma]

Hi Brian,

How to run on unweighted network ?

thanks
A

[Brian Keegan]

The algorithm is only defined for weighted networks. 

You may want to consider methods that look for edge betweenness to extract backbones for unweighted networks:

http://link.springer.com/article/10.1140/epjb/e2006-00066-4

http://prl.aps.org/abstract/PRL/v96/i1/e018701

[amitabh sharma]

Thanks Brian,

A

[jallepalli deepthi]

i have an issue regarding executing networkx and python code togther....

when i saw this post containnig the same structure ......i would like to know how did you run this code as a whole(not typing one statement at atime)????