Re: [igraph] maximal.cliques returns duplicates

[Gábor Csárdi]

On Mon, Nov 18, 2013 at 12:46 PM, Tony Larson <address@hidden> wrote:
> Hmmm - I think I am misunderstanding fundamentally what maximal.cliques() is
> doing - I assumed there should be no overlap but of course there will be as
> vertices can be shared amongst cliques!  What I am trying to achieve is
> effectively clustering by pulling out complete subgraphs, but vertices
> should appear uniquely in the final set of clusters.  Can you suggest a way
> of doing this?

I guess what makes sense depends on your application. In general
cliques will overlap, so just taking the maximal or largest cliques is
definitely not good.

Overlap is one thing, but in your first email you had a reported
maximal clique that was a subset of another reported maximal clique.
If this happens, then it is a bug. So if you could reproduce it, that
would be great, even if the maximal clique finder was rewritten from
scratch in our development version, and it is unlikely that we'll have
the same error form version 0.7.

Gabor

>  One thought I had was to recursively calculate the largest.cliques(),
> delete the associated vertices,  and continue until there are no vertices
> left.  However, I am still stuck with the problem that  largest.cliques()
> can return more than one clique (if vector lengths are equal) and these can
> contain overlapping vertices, so there still has to be a choice made of
> which vertices to use...
>
>
> On 18 November 2013 17:23, Gábor Csárdi <address@hidden> wrote:
>>
>> On Mon, Nov 18, 2013 at 11:57 AM, Tony Larson <address@hidden>
>> wrote:
>> > OK,
>> > Here's a toy example (and on the latest igraph) - still not behaving as
>> > expected??
>>
>> You need to set the random seed to make this example reproducible.
>>
>> >> mat <- matrix(sample(c(0,1), 100 * 100, replace = TRUE, prob = c(0.8,
>> >> 0.2)), 100, 100)
>> >> g <- graph.adjacency(mat, mode = "undirected", weighted = TRUE, diag =
>> >> FALSE)
>> >> mc <- maximal.cliques(g)
>> >> any(duplicated(unlist(mc)))
>>
>> No, this is not good, you just create a long vector from all clique
>> vertices, and there will be duplicates if there is overlap.... you
>> need to check whether one is a subset of any of the others.
>>
>> G.
>>
>> [...]
>>
>> _______________________________________________
>> igraph-help mailing list
>> address@hidden
>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
>
>
>
> --
> ***************************************
> Dr. Tony R. Larson
> CNAP
> Department of Biology, Area 7
> University of York
> Wentworth Way
> Heslington
> York YO10 5DD
> UK
>
> Tel: +44(0)1904 328 826 (office)
> Tel: +44(0)7833 471 685 (mobile)
> Fax: +44(0)1904 328 762
> E-mail: address@hidden
> ***************************************
>
> Times Higher Education University of the Year 2010
>
>
> Disclaimer: This email and any
> attachment(s) are strictly confidential
> and contain information intended only
> for the use of the individual(s) named
> above.  If you are not the intended
> recipients please delete this message
> from your system, do not use or
> disclose the information in any way and
> notify us by return e-mail.
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>