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 notifications@github.com 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/nipy/brainx/issues/22 .

Cindee Madison Jagust Lab UC Berkeley cindee@berkeley.edu

[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 notifications@github.com 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/nipy/brainx/issues/22#issuecomment-39757473 .

Cindee Madison Jagust Lab UC Berkeley cindee@berkeley.edu

[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 notifications@github.com 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/nipy/brainx/issues/22#issuecomment-39782128 .

Cindee Madison Jagust Lab UC Berkeley cindee@berkeley.edu

[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 notifications@github.com 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/nipy/brainx/issues/22#issuecomment-39798076 .

Cindee Madison Jagust Lab UC Berkeley cindee@berkeley.edu

[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 notifications@github.com 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 notifications@github.com 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 cindee@berkeley.edu

Reply to this email directly or view it on GitHubhttps://github.com/nipy/brainx/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 notifications@github.com 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 notifications@github.com 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 notifications@github.com 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 cindee@berkeley.edu

Reply to this email directly or view it on GitHubhttps://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.

[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 notifications@github.comwrote:

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 notifications@github.com 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 notifications@github.com 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 notifications@github.com 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 cindee@berkeley.edu

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/nipy/brainx/issues/22#issuecomment-39872056 .

Cindee Madison Jagust Lab UC Berkeley cindee@berkeley.edu