invariants

[jovo]

i'm not clear on whether all the invariants from http://www.cis.jhu.edu/~parky/SSP/PCP-JCGS-2010.pdf have been incorporated into igraph.

i know that disa implemented them in Python, as described in this: http://arxiv.org/abs/1312.4318

with code available in here somewhere: https://github.com/openconnectome/MR-connectome/tree/master/MROCPdjango

i recall a discussion between disa, gabor, and others, to perform some benchmarks comparing functions when disa and gabor have both implemented them, and talk of making sure igraph has the best ones, and then disa no longer supporting separate implementations, but i don't recall whether that was all resolved.

for reference, the list of invariants is:

scan-statistic-1 degree eigendecomposition of adjacency matrix local # of triangles clustering coefficient

sorry if this was all resolved long ago...

[gaborcsardi]

This is not exactly the same list as in the cited paper(s), but anyway, I think they are all in igraph. Not necessarily the approximate algorithms, but the exact ones are.

Some of the time complexities in the arxiv paper are definitely better than the implementations in igraph, like for the clustering coefficient and the number of adjacency triangles. (How are these even possible, btw? Don't you need at least O(nk) instead of O(n+k)?)

Anyway, you can do some benchmarks if you like, and then put the best ones in igraph. Just to remind you, you all have commit rights in this repository.....

[jovo]

ok, disa - i'm not sure where this lives on the priority stack for you, but it seems like perhaps near the top? i don't have a strong feeling about this, i just recalled this conversation, so i wanted to know where it stands.

On Monday, December 30, 2013, Gabor Csardi wrote:

This is not exactly the same list as in the cited paper(s), but anyway, I think they are all in igraph. Not necessarily the approximate algorithms, but the exact ones are.

Some of the time complexities in the arxiv paper are definitely better than the implementations in igraph, like for the clustering coefficient and the number of adjacency triangles. (How are these even possible, btw? Don't you need at least O(nk) instead of O(n+k)?)

Anyway, you can do some benchmarks if you like, and then put the best one in igraph. Just to remind you, you all have commit rights in this repository.....

— Reply to this email directly or view it on GitHubhttps://github.com/gaborcsardi/igraph/issues/15#issuecomment-31379895 .

perhaps consider allowing the quest for eudaimonia to guide you openconnecto.me, jovo.me

[disa-mhembere]

Sure - I'll benchmark and let you all know what I get.

On Mon, Dec 30, 2013 at 9:02 PM, joshua vogelstein <notifications@github.com

wrote:

ok, disa - i'm not sure where this lives on the priority stack for you, but it seems like perhaps near the top? i don't have a strong feeling about this, i just recalled this conversation, so i wanted to know where it stands.

On Monday, December 30, 2013, Gabor Csardi wrote:

This is not exactly the same list as in the cited paper(s), but anyway, I think they are all in igraph. Not necessarily the approximate algorithms, but the exact ones are.

Some of the time complexities in the arxiv paper are definitely better than the implementations in igraph, like for the clustering coefficient and the number of adjacency triangles. (How are these even possible, btw? Don't you need at least O(nk) instead of O(n+k)?)

Anyway, you can do some benchmarks if you like, and then put the best one in igraph. Just to remind you, you all have commit rights in this repository.....

— Reply to this email directly or view it on GitHub< https://github.com/gaborcsardi/igraph/issues/15#issuecomment-31379895> .

perhaps consider allowing the quest for eudaimonia to guide you openconnecto.me, jovo.me

—

Reply to this email directly or view it on GitHubhttps://github.com/gaborcsardi/igraph/issues/15#issuecomment-31380441 .

Disa Mhembere Johns Hopkins University disa@jhu.edu

:(){ :|:& };:

[jovo]

excellent, thanks dude!

On Monday, December 30, 2013, Disa Mhembere wrote:

Sure - I'll benchmark and let you all know what I get.

On Mon, Dec 30, 2013 at 9:02 PM, joshua vogelstein < notifications@github.com <javascript:_e({}, 'cvml', 'notifications@github.com');>

wrote:

ok, disa - i'm not sure where this lives on the priority stack for you, but it seems like perhaps near the top? i don't have a strong feeling about this, i just recalled this conversation, so i wanted to know where it stands.

On Monday, December 30, 2013, Gabor Csardi wrote:

This is not exactly the same list as in the cited paper(s), but anyway, I think they are all in igraph. Not necessarily the approximate algorithms, but the exact ones are.

Some of the time complexities in the arxiv paper are definitely better than the implementations in igraph, like for the clustering coefficient and the number of adjacency triangles. (How are these even possible, btw? Don't you need at least O(nk) instead of O(n+k)?)

Anyway, you can do some benchmarks if you like, and then put the best one in igraph. Just to remind you, you all have commit rights in this repository.....

— Reply to this email directly or view it on GitHub< https://github.com/gaborcsardi/igraph/issues/15#issuecomment-31379895> .

perhaps consider allowing the quest for eudaimonia to guide you openconnecto.me, jovo.me

—

Reply to this email directly or view it on GitHub< https://github.com/gaborcsardi/igraph/issues/15#issuecomment-31380441> .

Disa Mhembere Johns Hopkins University disa@jhu.edu <javascript:_e({}, 'cvml', 'disa@jhu.edu');>

:(){ :|:& };:

— Reply to this email directly or view it on GitHubhttps://github.com/gaborcsardi/igraph/issues/15#issuecomment-31381634 .

perhaps consider allowing the quest for eudaimonia to guide you openconnecto.me, jovo.me

[disa-mhembere]

Hey Gabor -- what's the triangle counting function in igraph?

On Mon, Dec 30, 2013 at 11:06 PM, joshua vogelstein < notifications@github.com> wrote:

excellent, thanks dude!

On Monday, December 30, 2013, Disa Mhembere wrote:

Sure - I'll benchmark and let you all know what I get.

On Mon, Dec 30, 2013 at 9:02 PM, joshua vogelstein < notifications@github.com <javascript:_e({}, 'cvml', 'notifications@github.com');>

wrote:

ok, disa - i'm not sure where this lives on the priority stack for you, but it seems like perhaps near the top? i don't have a strong feeling about this, i just recalled this conversation, so i wanted to know where it stands.

On Monday, December 30, 2013, Gabor Csardi wrote:

This is not exactly the same list as in the cited paper(s), but anyway, I think they are all in igraph. Not necessarily the approximate algorithms, but the exact ones are.

Some of the time complexities in the arxiv paper are definitely better than the implementations in igraph, like for the clustering coefficient and the number of adjacency triangles. (How are these even possible, btw? Don't you need at least O(nk) instead of O(n+k)?)

Anyway, you can do some benchmarks if you like, and then put the best one in igraph. Just to remind you, you all have commit rights in this repository.....

— Reply to this email directly or view it on GitHub< https://github.com/gaborcsardi/igraph/issues/15#issuecomment-31379895>

.

perhaps consider allowing the quest for eudaimonia to guide you openconnecto.me, jovo.me

—

Reply to this email directly or view it on GitHub< https://github.com/gaborcsardi/igraph/issues/15#issuecomment-31380441> .

Disa Mhembere Johns Hopkins University disa@jhu.edu <javascript:_e({}, 'cvml', 'disa@jhu.edu');>

:(){ :|:& };:

— Reply to this email directly or view it on GitHub< https://github.com/gaborcsardi/igraph/issues/15#issuecomment-31381634> .

perhaps consider allowing the quest for eudaimonia to guide you openconnecto.me, jovo.me

—

Reply to this email directly or view it on GitHubhttps://github.com/gaborcsardi/igraph/issues/15#issuecomment-31383122 .

[gaborcsardi]

adjacent.triangles

[disa-mhembere]

ok we can close this one. igraph's implementations of all the invariants in question are more efficient than what we run with mrocp. I've attached a few test results. I cleared the cache before each test and ran each 3 times. what you see is the average of the runs. the green is the igraph total time and the orange is mrocp.

results.xlsxhttps://docs.google.com/file/d/0Bz-BhvBcZj6EcWU3elhjUzgwdFE/edit?usp=drive_web

best

On Tue, Dec 31, 2013 at 11:56 AM, Gabor Csardi notifications@github.comwrote:

adjacent.triangles

— Reply to this email directly or view it on GitHubhttps://github.com/gaborcsardi/igraph/issues/15#issuecomment-31401930 .

[jovo]

great! thanks Disa! wanna update our mrocp code to call igraph? also, were you using R, python, or C version of igraph calls?

sent from a tiny miracle cuboid.

On Jan 2, 2014, at 5:52 PM, Disa Mhembere notifications@github.com wrote:

ok we can close this one. igraph's implementations of all the invariants in question are more efficient than what we run with mrocp. I've attached a few test results. I cleared the cache before each test and ran each 3 times. what you see is the average of the runs. the green is the igraph total time and the orange is mrocp.

results.xlsxhttps://docs.google.com/file/d/0Bz-BhvBcZj6EcWU3elhjUzgwdFE/edit?usp=drive_web

best

On Tue, Dec 31, 2013 at 11:56 AM, Gabor Csardi notifications@github.comwrote:

adjacent.triangles

— Reply to this email directly or view it on GitHubhttps://github.com/gaborcsardi/igraph/issues/15#issuecomment-31401930 .

— Reply to this email directly or view it on GitHub.

[disa-mhembere]

wanna update our mrocp code to call igraph?

Sure. I can see python calls for:

• Degree, Transitivity, but

I don't see eigendecomposition, triangles, and scan statistic. These may not have been implemented yet. Gabor please direct me to them if they exist.

also, were you using R, python, or C version of igraph calls?

I was running the R version of igraph calls.

sent from a tiny miracle cuboid.

On Jan 2, 2014, at 5:52 PM, Disa Mhembere notifications@github.com wrote:

ok we can close this one. igraph's implementations of all the invariants in question are more efficient than what we run with mrocp. I've attached a few test results. I cleared the cache before each test and ran each 3 times. what you see is the average of the runs. the green is the igraph total time and the orange is mrocp.

results.xlsx< https://docs.google.com/file/d/0Bz-BhvBcZj6EcWU3elhjUzgwdFE/edit?usp=drive_web>

best

On Tue, Dec 31, 2013 at 11:56 AM, Gabor Csardi notifications@github.comwrote:

adjacent.triangles

— Reply to this email directly or view it on GitHub< https://github.com/gaborcsardi/igraph/issues/15#issuecomment-31401930> .

— Reply to this email directly or view it on GitHub.

— Reply to this email directly or view it on GitHubhttps://github.com/gaborcsardi/igraph/issues/15#issuecomment-31494195 .

[gaborcsardi]

I don't see eigendecomposition, triangles, and scan statistic. These may not have been implemented yet. Gabor please direct me to them if they exist.

Yet? I didn't know that there were any plans for python implementations. I thought xdata plans only included the R package.

[disa-mhembere]

Don't know about xdata plans. I thought eventually everything in igraph ended up in both R and Python. It's fine if this is not true. I can call R directly from Python or write a wrapper myself.

On Fri, Jan 3, 2014 at 11:03 PM, Gabor Csardi notifications@github.comwrote:

I don't see eigendecomposition, triangles, and scan statistic. These may not have been implemented yet. Gabor please direct me to them if they exist.

Yet? I didn't know that there were any plans for python implementations. I thought xdata plans only included the R package.

— Reply to this email directly or view it on GitHubhttps://github.com/gaborcsardi/igraph/issues/15#issuecomment-31570830 .

[jovo]

@dmhembe1 - wanna put the benchmarks in the bottom of this comment and then close it.

[disa-mhembere]

Probably best to just link it rather than duplicate it. Here it is: https://drive.google.com/file/d/0Bz-BhvBcZj6EcWU3elhjUzgwdFE/edit?usp=sharing

[jovo]

http://www.yeppp.info/

is this useful for us ?

sent from a tiny miracle cuboid.