Re: [igraph] maximal_cliques_template.h: a way to stop the search?

[Tamas Nepusz]

Hi Szabolcs,

> All this sounds good, but I am a bit uncomfortable with one thing:
> using IGRAPH_INTERRUPTED to signal the stop.
Indeed, you are right - using IGRAPH_INTERRUPTED would mean that it
would be impossible to decide from the main loop (where we iterate
over all the vertices) whether the user pressed Ctrl-C in Python or R
to interrupt the current computation (if we decide to add support for
this), or whether the callback function requested the calculation to
stop. Feel free to define another error code for this purpose.

Best,
T.

___
igraph-help mailing list
igraph-help@nongnu.org
https://lists.nongnu.org/mailman/listinfo/igraph-help

Re: [igraph] maximal_cliques_template.h: a way to stop the search?

[Szabolcs Horvát]

Hi Tamas,

All this sounds good, but I am a bit uncomfortable with one thing:
using IGRAPH_INTERRUPTED to signal the stop.  This error code is used
to signal a user-interrupt checked through
igraph_allow_interruption().  When such an interruption is detected,
there is no expectation for the function to return anything
meaningful, only to free resources (i.e. ensure no memory leak).  The
interruption is handled as a sort of error condition which is passed
up to the calling igraph function.

In this case there would be no error, only a signal to stop the
search.  The top-level clique search function should not indicate an
error to its caller, it should return with IGRAPH_SUCCESS.  The
behaviour should be the same as with igraph_isomorphic_function_vf2()

It must be possible to distinguish between an interactive user
interruption (which is an error condition) and the callback function
requesting a stop (which is not an error).

Of course what you expect would work regardless because the _bk
function does not check for interruptions internally (yet). But what
if in the future someone adds a check there?


On 22 April 2016 at 18:31, Tamas Nepusz  wrote:
> Hi,
>
>> Maximal clique related functions are implemented (mostly) through
>> maximal_cliques_template.h.  There is a RECORD macro where we can
>> define how to record a clique that was found.  Is there a way to
>> signal within this RECORD section that the clique search does not need
>> to continue and the clique search function should now return (after
>> doing all the necessary cleanup)?
> Well, not with the current implementation, but I think it is not too
> hard to modify the existing implementation.
>
> Basically, what you need to do is:
>
> - Formally state that a nonzero return value from
> igraph*_maximal_cliques_bk (the backtracking step) is a request to
> stop the search. (Right now the function always returns zero, but it
> has an int return type, so you can safely return any igraph error code
> there).
>
> - Whenever igraph_*_maximal_cliques_bk is called, you have to check
> whether there was a nonzero value returned and if so, stop the search
> and propagate the error value back to the caller.
>
> - At the topmost level where igraph_*_maximal_cliques_bk is called the
> first time, you need to check the return value and interrupt the
> search accordingly.
>
> By the way, the RECORD macros currently don't do any error checking on
> calls to igraph_vector_ptr_push_back() and alike, so errors from these
> functions may go unnoticed, which is a Bad Thing (TM). I think the
> best would be to:
>
> 1) update all RECORD macros with IGRAPH_CHECK() calls whenever we
> perform an operation that may potentially return an error code
> 2) use the special (and currently undocumented) IGRAPH_INTERRUPTED
> error code from the RECORD macros to signal that the user wants to
> stop the search
> 3) make sure that nonzero return values from
> igraph_*_maximal_cliques_bk are propagated upwards. (Surrounding every
> such call except the topmost one with IGRAPH_CHECK() should suffice).
> 4) at the topmost call to igraph_*_maximal_cliques_bk, check whether
> the error code is IGRAPH_INTERRUPTED; if not, return the error code to
> the caller. Something like:
>
> int ret = igraph_..._maximal_cliques_bk(...);
> if (ret == IGRAPH_INTERRUPTED) {
> /* handle the interruption */
> } else {
> /* let igraph handle the error */
> IGRAPH_CHECK(ret);
> }
>
> T.
>
> ___
> igraph-help mailing list
> igraph-help@nongnu.org
> https://lists.nongnu.org/mailman/listinfo/igraph-help

___
igraph-help mailing list
igraph-help@nongnu.org
https://lists.nongnu.org/mailman/listinfo/igraph-help

Re: [igraph] Performance issue regarding when calculating induced_subgraph and authority_score within a loop

[Tamas Nepusz]

Hi,

I'm suspecting that rbind() is the bottleneck in your for loop because
it always  creates a copy your existing matrix when adding a new row
to it; use lapply() instead:

auth_scr <- lapply(clust, function(x) {
authority_score(induced_subgraph(g, x))$vector })

T.


On Sat, Apr 23, 2016 at 10:55 AM, Roland Sztaho  wrote:
> Hello Guys,
>
> I would like to prepare some stats based on clusters made by
> cluster_label_prop() method. When I use authority_score() and
> induced_subgraph() within a loop, it shows weak performance and I am looking
> for a workaround to speed up the code. My network contains approx. 3.000.000
> edges and 250.000 clusters. I think calculation of these measure for the
> clusters without the loop could be a good point, however I didn't find a way
> in the docs for this.
>
> R version 3.2.5 (2016 04 14)
> igraph package version 1.0.1
> OS: windows 7 64bit
>
> Here is what I have so far:
>
> library("igraph")
> library("plyr")
> setwd("C:/Projects/R/igraph")
>
> g_in = read.csv("my_network.csv", sep=" ")
> g = graph.data.frame(g_in, directed=FALSE)
>
> clust = groups(cluster_label_prop(g, weights=E(g)$weight))
> clust_count <- length(clust)
> clustm <- as.matrix(ldply((clust), data.matrix))
> clustm1 <- clustm[clustm[, ".id"] == 1, 2]
>
> g_sub = induced_subgraph(g, clustm1)
> auth_scr = as.matrix(authority_score(g_sub)$vector)
> for (i in 2:clust_count) {
> g_sub = induced_subgraph(g, clustm[clustm[, ".id"] == i, 2])
> auth_scr = rbind(as.matrix(auth_scr),
> as.matrix(authority_score(g_sub)$vector))
> }
>
> Any suggestions would be great!
>
> Thanks,
> Roland
>
> ___
> igraph-help mailing list
> igraph-help@nongnu.org
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>

___
igraph-help mailing list
igraph-help@nongnu.org
https://lists.nongnu.org/mailman/listinfo/igraph-help

Re: [igraph] Maximum graph size that Python igraph can handle

[Tamas Nepusz]

Also, re the original question: there is no built-in constraint for
the sizes of the graphs apart from the fact that vertex and edge IDs
are typically stored as long integers, so you won't be able to have
more than 2 billion vertices or edges.  But, if you have that many
vertices or edges then you probably have bigger problems anyway ;)
T.


On Mon, Apr 25, 2016 at 11:11 AM, Tamas Nepusz  wrote:
> Hi,
>
> Storing this graph should not be a problem for igraph. As for further
> analysis - it depends on what you want to do with it. Some algorithms
> might work while others would be infeasible to try; for instance, edge
> betweenness community detection probably wouldn't work, but the
> Louvain method (a.k.a. multilevel community detection) probably would
> (given enough time).
>
> All the best,
> T.
>
>
> On Sun, Apr 24, 2016 at 4:41 AM, Pablo Moriano  
> wrote:
>> Hi,
>>
>> I was wondering if there exist any constraint with the size of a graph in 
>> Python graph. I need to manipulate a graph of approximately 21 M nodes and 
>> 60 M edges. I could assign until 64gb of RAM to this task. Thank you.
>> ___
>> igraph-help mailing list
>> igraph-help@nongnu.org
>> https://lists.nongnu.org/mailman/listinfo/igraph-help

___
igraph-help mailing list
igraph-help@nongnu.org
https://lists.nongnu.org/mailman/listinfo/igraph-help

Re: [igraph] Maximum graph size that Python igraph can handle

[Tamas Nepusz]

Hi,

Storing this graph should not be a problem for igraph. As for further
analysis - it depends on what you want to do with it. Some algorithms
might work while others would be infeasible to try; for instance, edge
betweenness community detection probably wouldn't work, but the
Louvain method (a.k.a. multilevel community detection) probably would
(given enough time).

All the best,
T.


On Sun, Apr 24, 2016 at 4:41 AM, Pablo Moriano  wrote:
> Hi,
>
> I was wondering if there exist any constraint with the size of a graph in 
> Python graph. I need to manipulate a graph of approximately 21 M nodes and 60 
> M edges. I could assign until 64gb of RAM to this task. Thank you.
> ___
> igraph-help mailing list
> igraph-help@nongnu.org
> https://lists.nongnu.org/mailman/listinfo/igraph-help

___
igraph-help mailing list
igraph-help@nongnu.org
https://lists.nongnu.org/mailman/listinfo/igraph-help