Is it possible to speed up code written using Networkx by Cythong

[akshay bhat]

Hello I have implemented a linear time community detection algorithm
called as "Label Propagation algorithm", Is it possible to improve its
speed by using cython?

Has anyone tried cython with networkx?

[akshay bhat]

Thanks

[Aric Hagberg]

Yes, I have experimented with Cython a little. I think Sage
(sagemath.org) is using
it quite extensively including in the parts of NetworkX that are
included there.

Aric

[Fernando Perez]

Hi Akshay,

A few questions regarding this:

- Is this the algorithm you refer to?

Phys. Rev. E 76, 036106 (2007) [11 pages]
Near linear time algorithm to detect community structures in
large-scale networks
http://link.aps.org/doi/10.1103/PhysRevE.76.036106

- Did you make any progress on the cython optimizations?

- Is your code available anywhere, and under a license that would make
it compatible with Networkx for release (i.e. LGPL or BSD)?

I am quite interested in this tool and would be happy to collaborate
with you on cleaning it up and optimizing it for submission into
networkx.

Best regards,

f

[Conrad Lee]

Note that if you're interested in label propagation, you might be interested in a recent paper by Michael Barber that criticizes label propagation by reformulating the algorithm as the solution to an optimization problem.  You could include an implementation of label propagation that takes an objective function as an argument.

Here's the article:

http://arxiv.org/abs/0903.3138

...and here's the abstract:

We investigate the recently proposed label-propagation algorithm (LPA) for identifying network communities. We reformulate the LPA as an equivalent optimization problem, giving an objective function whose maxima correspond to community solutions. By considering properties of the objective function, we identify conceptual and practical drawbacks of the label propagation approach, most importantly the disparity between increasing the value of the objective function and improving the quality of communities found. To address the drawbacks, we modify the objective function in the optimization problem, producing a variety of algorithms that propagate labels subject to constraints; of particular interest is a variant that maximizes the modularity measure of community quality. Performance properties and implementation details of the proposed algorithms are discussed. Bipartite as well as unipartite networks are considered. 

 

Conrad

[Robert Miller]

On Jun 30, 5:41 am, Aric Hagberg <ahagb...@gmail.com> wrote:
> Yes, I have experimented with Cython a little.  I think Sage
> (sagemath.org) is using
> it quite extensively including in the parts of NetworkX that are
> included there.

What is implemented in Sage are two data types, sparse and dense
directed graphs. The sparse graphs support multiple, (int) labeled
edges, and the dense graphs do not. These are offered as alternatives
to NetworkX, which was for a long time the only graph data structure
available in Sage. When I wrote these data types in Cython, I did some
tests which compared (Python) NetworkX with these Cython types, for
basic operations. There were different factors of speedup, from 15-100
or so. I posted a chart here:

http://rlmill.blogspot.com/2008/02/fast-sparse-graphs.html

-- Robert L Miller

[Fernando Perez]

On Tue, Aug 11, 2009 at 12:55 AM, Robert Miller<rlmil...@gmail.com> wrote:
> What is implemented in Sage are two data types, sparse and dense
> directed graphs. The sparse graphs support multiple, (int) labeled
> edges, and the dense graphs do not. These are offered as alternatives
> to NetworkX, which was for a long time the only graph data structure
> available in Sage. When I wrote these data types in Cython, I did some
> tests which compared (Python) NetworkX with these Cython types, for
> basic operations. There were different factors of speedup, from 15-100
> or so. I posted a chart here:
>
> http://rlmill.blogspot.com/2008/02/fast-sparse-graphs.html

That's very nice. I don't know what the NX policy is regarding cython
in the core, but if possible, it would be great if you'd be interested
in pushing your improvements 'upstream', so that both core NX and Sage
could benefit from this great work.

Just a thought from a regular user of both nx and sage, but who
sometimes needs to use these tools as standalone libraries, where I
don't want or have the entire sage machinery.

Cheers,

f

[Robert Miller]

On Aug 11, 12:29 pm, Fernando Perez <fperez....@gmail.com> wrote:
> That's very nice.  I don't know what the NX policy is regarding cython
> in the core, but if possible, it would be great if you'd be interested
> in pushing your improvements 'upstream', so that both core NX and Sage
> could benefit from this great work.

The code is nearly standalone as is, and it would probably only take a
day's work to pull the relevant pieces out of Sage.

> Just a thought from a regular user of both nx and sage, but who
> sometimes needs to use these tools as standalone libraries, where I
> don't want or have the entire sage machinery.

I agree.

[Fernando Perez]

On Tue, Aug 11, 2009 at 3:13 AM, Conrad Lee<conr...@gmail.com> wrote:
> Note that if you're interested in label propagation, you might be interested
> in a recent paper by Michael Barber that criticizes label propagation by
> reformulating the algorithm as the solution to an optimization problem.  You
> could include an implementation of label propagation that takes an objective
> function as an argument.
> Here's the article:
> http://arxiv.org/abs/0903.3138

Thanks a lot for the link. I'm completely new to the literature in
the field, so I appreciate the pointers. I'll have a look now at that
reference.

Regards,

f