adjacency vs edge list

[jovo]

@gaborcsardi - perhaps you can elaborate a little on something you mentioned in a previous thread. many graph operations that we desire perhaps most naturally operate on adjacency matrices, insofar as they are various linear algebraic routines.

on the other many, many graph operations that we desire perhaps most naturally operate on edge lists, such as triangle counting, locality statistics etc.

it seems to me that you are suggesting that igraph is optimized for in memory operations that operate on edge lists.

if that is the case, what do you suggest with regard to the desired linear algebra routines? convert between internal storage models as necessary? this seems perhaps suboptimal? do you have a different/better suggestion?

[gaborcsardi]

The current igraph data type is optimized for

1. iterating over all edges, and edges incident to a vertex,
2. in sparse graphs that
3. fit into the memory and
4. are mostly static;
5. with an eye on easy embedding into higher level languages.

if that is the case, what do you suggest with regard to the desired linear algebra routines?

Linear algebra software of your choice. Without specifics, I cannot really say more.

convert between internal storage models as necessary?

I don't see how can you get away without it.

this seems perhaps suboptimal?

In what sense? You say we desire perhaps most naturally operate, which suggests that you care about naturally expressing your operations (first), and not about running time, but then you talk about internal storage models. So I am a bit unsure what we are optimizing here.

[jovo]

this seems perhaps suboptimal?

In what sense? You say we desire perhaps most naturally operate, which suggests that you care about naturally expressing your operations (first), and not about running time, but then you talk about internal storage models. So I am a bit unsure what we are optimizing here.

fair question. ideally, what's happening under the hood is hidden from the user, e.g., the nature of the internal storage. and, things go reasonably fast. i realize these are somewhat opposing objectives.

i guess the working model is convert between representations as necessary.

i wonder if it makes to enable commands like:

ase(g), where 'g' is a graph, so that igraph automatically (under the hood) converts it to an adjacency matrix.

but perhaps i'm speaking non-sense?

— Reply to this email directly or view it on GitHubhttps://github.com/igraph/xdata-igraph/issues/43#issuecomment-42261292 .

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

[gaborcsardi]

i wonder if it makes to enable commands like: ase(g), where 'g' is a graph, so that igraph automatically (under the hood) converts it to an adjacency matrix.

No need to convert here, ase is natively implemented on igraph objects, just as (almost) all operations in igraph. ARPACK is not actually working with matrices, either.

[jovo]

No need to convert here, ase is natively implemented on igraph objects, just as (almost) all operations in igraph. ARPACK is not actually working with matrices, either.

ok, perhaps you can explain to me what that means offline, because i don't know enough, i don't think, to understand either of those claims :)

— Reply to this email directly or view it on GitHubhttps://github.com/igraph/xdata-igraph/issues/43#issuecomment-42266876 .

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

[gaborcsardi]

The input of the ase function is an igraph object. It does not convert it to an adjacency matrix internally.

At the implementation level, the input of ARPACK (which is used to calculate the SVD) is not a matrix.

[dpmcsuss]

JOVO: Comparisons on my end showed that igraph ase function are much faster than what we had previously coded using matrices in R.

[gaborcsardi]

@dpmcsuss: I'll actually add another ase implementation based on dense matrices at some point, because for small matrices dense eigenvector/svd algorithms are much faster than ARPACK. Well, most probably, I should measure first, but I am 99% sure. This will also simplify testing.

[jovo]

all good things.

On Thu, May 8, 2014 at 11:42 AM, Gabor Csardi notifications@github.comwrote:

@dpmcsuss https://github.com/dpmcsuss: I'll actually add another aseimplementation based on dense matrices at some point, because for small matrices dense eigenvector/svd algorithms are much faster than ARPACK. Well, most probably, I should measure first, but I am 99% sure. This will also simplify testing.

— Reply to this email directly or view it on GitHubhttps://github.com/igraph/xdata-igraph/issues/43#issuecomment-42565893 .

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