Hi Tony, Maybe you are looking for clique decomposition - I’m not that familiar with the subject but googling for “clique decomposition” seems to yield a bunch of potentially useful papers:
http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190180412/abstract http://link.springer.com/article/10.1007%2FBF01212981 -- T. On Monday, 18 November 2013 at 19:25, Tony Larson wrote: > Sorry, my error in my first post. I've since re-checked my large dataset and > although there are partial duplications between some vectors output from > maximal.cliques(), there are no cases where the entire contents of one vector > is the subset of another. So no bug - just a bug in my understanding!! > > But I'm still scratching my head in how to solve my problem. I need to > extract clusters where all within-cluster members are completely connected > and a member can only exist in one cluster. Maybe it's a community detection > solution ? > > > On 18 November 2013 17:54, Gábor Csárdi <[email protected] > (mailto:[email protected])> wrote: > > On Mon, Nov 18, 2013 at 12:46 PM, Tony Larson <[email protected] > > (mailto:[email protected])> 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 <[email protected] > > > (mailto:[email protected])> wrote: > > >> > > >> On Mon, Nov 18, 2013 at 11:57 AM, Tony Larson <[email protected] > > >> (mailto:[email protected])> > > >> 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 > > >> [email protected] (mailto:[email protected]) > > >> 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 (tel:%2B44%280%291904%20328%20826) (office) > > > Tel: +44(0)7833 471 685 (tel:%2B44%280%297833%20471%20685) (mobile) > > > Fax: +44(0)1904 328 762 (tel:%2B44%280%291904%20328%20762) > > > E-mail: [email protected] (mailto:[email protected]) > > > *************************************** > > > > > > 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 > > > [email protected] (mailto:[email protected]) > > > https://lists.nongnu.org/mailman/listinfo/igraph-help > > > > > > > _______________________________________________ > > igraph-help mailing list > > [email protected] (mailto:[email protected]) > > 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: [email protected] (mailto:[email protected]) > *************************************** > > 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 > [email protected] (mailto:[email protected]) > https://lists.nongnu.org/mailman/listinfo/igraph-help > >
_______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
