simulated annealing directed graph?

[rsblume]

Hi team,
I accidentally passed a digraph to mod.simulated_annealing(). The algo is currently churning away without throwing up an warning or error. Is this desirable?

[cindeem]

Hi Rob,

There is a hidden behavior in networkx

#define directed adj matrix
In [121]: jnk
Out[121]:
array([[ 0., 0., 1.],
[ 0., 0., 0.],
[ 1., 1., 0.]])

create a graph object

In [125]: graph = nx.from_numpy_matrix(jnk)

get back adj matrix

In [126]: nx.adjacency_matrix(graph)
Out[126]:
matrix([[ 0., 0., 1.],
[ 0., 0., 1.],
[ 1., 1., 0.]])

Note it is now undirected.

when you created your graph, if you dont explicitly create a digraph, it
will treat it as undirected.
somewhat unexpected and may be worth adding in an error??

Can you confirm that this is what occurred, or did you explicitly pass a
DiGraph object?

--Cindee

On Fri, Apr 4, 2014 at 4:03 PM, rsblume [email protected] wrote:

Hi team,
I accidentally passed a digraph to mod.simulated_annealing(). The algo is
currently churning away without throwing up an warning or error. Is this
desirable?

Reply to this email directly or view it on GitHubhttps://github.com//issues/22
.

Cindee Madison
Jagust Lab
UC Berkeley
[email protected]

[rsblume]

Hi Cindee:
I passed it a digraph explicitly:
from my notebook:
In [4]:
#load data
filestub=('C:\Users\Robert\gitrepos\cocomac-tools-rsblume\applications\ModhaSingh_PFC\modha\lowest_full_g.pck')
whole_low=pickle.load(open(filestub, "rb"))

In [9]: whole_low
Out[9]: <networkx.classes.digraph.DiGraph at 0x5c1ed30>

In [10]: whole_low_sim_part=mod.simulated_annealing(whole_low)

it produced an output.... seems funky... 268 nodes in 1 module and 3 in the second but could be my data.

[cindeem]

okay...

the result should be funky, do not trust it...
I will add an exception when a directed graph is passed, I do not think the
algorithm can support it....

im meetings most of today will try to send a fix this afternoon/evening
--Cindee

On Mon, Apr 7, 2014 at 10:17 AM, rsblume [email protected] wrote:

Hi Cindee:
I passed it a digraph explicitly:
from my notebook:
In [4]:
#load data

filestub=('C:\Users\Robert\gitrepos\cocomac-tools-rsblume\applications\ModhaSingh_PFC\modha\lowest_full_g.pck')
whole_low=pickle.load(open(filestub, "rb"))

In [9]: whole_low
Out[9]:

In [10]: whole_low_sim_part=mod.simulated_annealing(whole_low)

it produced an output.... seems funky... 268 nodes in 1 module and 3 in
the second but could be my data.

Reply to this email directly or view it on GitHubhttps://github.com//issues/22#issuecomment-39757473
.

Cindee Madison
Jagust Lab
UC Berkeley
[email protected]

[rsblume]

I can confirm that the partition of the digraph and the partition of the graph via sim. anneal. are different. I think I am the only user so far who has directed graphs...

[cindeem]

one quick question,
do the nodes in your graph have self links?
This would be a problem with our current implementation....

On Mon, Apr 7, 2014 at 1:53 PM, rsblume [email protected] wrote:

I can confirm that the partition of the digraph and the partition of the
graph via sim. anneal. are different. I think I am the only user so far who
has directed graphs...

Reply to this email directly or view it on GitHubhttps://github.com//issues/22#issuecomment-39782128
.

Cindee Madison
Jagust Lab
UC Berkeley
[email protected]

[rsblume]

no
In [39]: whole_low_undirected.number_of_selfloops()
Out[39]: 0

Thanks

[cindeem]

Hi Rob,

So without self loops, code as structured should detect communities, Ill
look a little more today to make sure I have not missed anything, but
algorithm should return meaningful communities
C

On Mon, Apr 7, 2014 at 4:58 PM, rsblume [email protected] wrote:

no
In [39]: whole_low_undirected.number_of_selfloops()
Out[39]: 0

Thanks

Reply to this email directly or view it on GitHubhttps://github.com//issues/22#issuecomment-39798076
.

Cindee Madison
Jagust Lab
UC Berkeley
[email protected]

[rsblume]

Thanks Cindee,
Sim annealing did return a partition on the directed version of the graph,
but the it was very different than the partition for the undirected. If
memory serves, Newman/modularity was only meant for undirected graphs.
There is another community detection algorithm that Fernando, Dan Bliss and
I played with called Infomap (
http://igraph.sourceforge.net/doc-0.6/html/ch22s08.html) that is meant for
directed graphs. We never got reasonable/usable partitions from infomap
using our graphs. Maybe I am wrong though and modularity is perfectly
appropriate for directed graphs. Thoughts from others in the group?
-Rob

On Tue, Apr 8, 2014 at 7:08 AM, cindeem [email protected] wrote:

Hi Rob,

So without self loops, code as structured should detect communities, Ill
look a little more today to make sure I have not missed anything, but
algorithm should return meaningful communities
C

On Mon, Apr 7, 2014 at 4:58 PM, rsblume [email protected] wrote:

no
In [39]: whole_low_undirected.number_of_selfloops()
Out[39]: 0

Thanks

Reply to this email directly or view it on GitHub<
https://github.com/nipy/brainx/issues/22#issuecomment-39798076>

.

Cindee Madison
Jagust Lab
UC Berkeley
[email protected]

Reply to this email directly or view it on GitHubhttps://github.com//issues/22#issuecomment-39851760
.

Robert Blumenfeld, Ph.D.
Assistant Adjunct Professor
Brain Circuits Laboratory
University of California, Irvine

[mb3152]

Modularity is certainly a reasonable thing for directed graphs, but I don’t think the jury is out on how to handle the directed edges, as directed edges let you measure flow in the graph, which should be taken into account while partitioning the graph; this might get you a more realistic partition than simply treating the graph as undirected and ignoring how the direction of edges dictate flow in the graph. Here are a couple papers proposing methods to handle it. They also discuss overlapping communities, which we might want to start doing as well.

http://arxiv.org/pdf/0904.3940.pdf
http://arxiv.org/pdf/0801.1647.pdf

On Apr 8, 2014, at 9:30 AM, rsblume [email protected] wrote:

Thanks Cindee,
Sim annealing did return a partition on the directed version of the graph,
but the it was very different than the partition for the undirected. If
memory serves, Newman/modularity was only meant for undirected graphs.
There is another community detection algorithm that Fernando, Dan Bliss and
I played with called Infomap (
http://igraph.sourceforge.net/doc-0.6/html/ch22s08.html) that is meant for
directed graphs. We never got reasonable/usable partitions from infomap
using our graphs. Maybe I am wrong though and modularity is perfectly
appropriate for directed graphs. Thoughts from others in the group?
-Rob

On Tue, Apr 8, 2014 at 7:08 AM, cindeem [email protected] wrote:

Hi Rob,

So without self loops, code as structured should detect communities, Ill
look a little more today to make sure I have not missed anything, but
algorithm should return meaningful communities
C

On Mon, Apr 7, 2014 at 4:58 PM, rsblume [email protected] wrote:

no
In [39]: whole_low_undirected.number_of_selfloops()
Out[39]: 0

Thanks

Reply to this email directly or view it on GitHub<
https://github.com/nipy/brainx/issues/22#issuecomment-39798076>

.

Cindee Madison
Jagust Lab
UC Berkeley
[email protected]

Reply to this email directly or view it on GitHubhttps://github.com//issues/22#issuecomment-39851760
.

Robert Blumenfeld, Ph.D.
Assistant Adjunct Professor
Brain Circuits Laboratory
University of California, Irvine
—
Reply to this email directly or view it on GitHub.

[cindeem]

Thanks Maxwell
It is also useful to take a look at
http://journals.aps.org/pre/pdf/10.1103/PhysRevE.80.056117

On Tue, Apr 8, 2014 at 9:44 AM, Maxwell Bertolero
[email protected]:

Modularity is certainly a reasonable thing for directed graphs, but I
don't think the jury is out on how to handle the directed edges, as
directed edges let you measure flow in the graph, which should be taken
into account while partitioning the graph; this might get you a more
realistic partition than simply treating the graph as undirected and
ignoring how the direction of edges dictate flow in the graph. Here are a
couple papers proposing methods to handle it. They also discuss overlapping
communities, which we might want to start doing as well.

http://arxiv.org/pdf/0904.3940.pdf
http://arxiv.org/pdf/0801.1647.pdf

On Apr 8, 2014, at 9:30 AM, rsblume [email protected] wrote:

Thanks Cindee,
Sim annealing did return a partition on the directed version of the
graph,
but the it was very different than the partition for the undirected. If
memory serves, Newman/modularity was only meant for undirected graphs.
There is another community detection algorithm that Fernando, Dan Bliss
and
I played with called Infomap (
http://igraph.sourceforge.net/doc-0.6/html/ch22s08.html) that is meant
for
directed graphs. We never got reasonable/usable partitions from infomap
using our graphs. Maybe I am wrong though and modularity is perfectly
appropriate for directed graphs. Thoughts from others in the group?
-Rob

On Tue, Apr 8, 2014 at 7:08 AM, cindeem [email protected]
wrote:

Hi Rob,

So without self loops, code as structured should detect communities,
Ill
look a little more today to make sure I have not missed anything, but
algorithm should return meaningful communities
C

On Mon, Apr 7, 2014 at 4:58 PM, rsblume [email protected]
wrote:

no
In [39]: whole_low_undirected.number_of_selfloops()
Out[39]: 0

Thanks

Reply to this email directly or view it on GitHub<
https://github.com/nipy/brainx/issues/22#issuecomment-39798076>

.

Cindee Madison
Jagust Lab
UC Berkeley
[email protected]

Reply to this email directly or view it on GitHub<
https://github.com/nipy/brainx/issues/22#issuecomment-39851760>
.

Robert Blumenfeld, Ph.D.
Assistant Adjunct Professor
Brain Circuits Laboratory

University of California, Irvine

Reply to this email directly or view it on GitHub.

Reply to this email directly or view it on GitHubhttps://github.com//issues/22#issuecomment-39872056
.

Cindee Madison
Jagust Lab
UC Berkeley
[email protected]