[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] Counting number of cliques each vertex is in
From: |
Tamás Nepusz |
Subject: |
Re: [igraph] Counting number of cliques each vertex is in |
Date: |
Fri, 29 Mar 2013 23:51:53 +0100 |
> I'm trying to count the number of cliques that each vertex is in. I couldn't
> find a native igraph function, so I wrote one that works fine using <clique>,
> but is a bit slow.
>
> So, my simple question is whether there is a native igraph function that
> would do the same?
No, there isn't; unfortunately you are on your own here. If you haven't tried
it yet, take a look at the maximal clique enumeration function
(igraph_maximal_cliques in C, maximal.cliques in R, Graph.maximal_cliques() in
Python) and try to make use of the fact that any subgraph of a maximal clique
is also a clique. So, if you find a maximal clique involving vertex v, it means
that v is also contained in every subgraph of that clique. Of course this leads
to another problem: if v is contained by multiple maximal cliques that also
overlap with each other, you will count every clique that consists of vertices
in the overlap multiple times, and you have to take this into account. I'm not
sure whether this is actually simpler in the end or not, but I'm sure that the
clique enumeration part will take a shorter time.
Best,
Tamas