What is the best way to identify quasi-cliques in a graph in Mathematica? I don't think it has been implemented, so are there any solutions to do this? Or do I have to export the graph data somehow and do the hard work myself?

EDIT: A quasi-clique is an almost complete subgraph. More formally (from this paper): Given an undirected graph $(V, E)$, and two parameters $\lambda$ and $\gamma$ with $0 \le \lambda \le \gamma \le 1$, the subgraph induced by a subset of the node set $V'\subseteq V$ is a $(\lambda,\gamma)$-quasi-clique if, and only if, the following two conditions hold:

  1. $\forall v \in V':\quad \text{deg}_{V'}(v)\ge \lambda\cdot(|V'|-1)$
  2. $|E'|\ge\gamma\cdot \left(\begin{matrix}|V'|\\2\end{matrix}\right)$

Where $E'=E\cap(V'\times V')$

  • 2
    $\begingroup$ Hi, welcome to Mathematica.SE, please consider taking the tour so you learn the basics of the site. Once you gain enough reputation by making good questions you will be able to vote up and down both questions and answers. The expertise you can find here is varied, and it is helpful to introduce specialist concepts such as quasi-cliques instead of assuming we all will bother doing the necessary research. Please try to make it relevant to others too. $\endgroup$ – rhermans Nov 3 '14 at 8:36
  • $\begingroup$ @rhermans I'm sorry. I'm used to stack-overflow, where specialized concepts are handled by those who have expertise in that area. Should I really edit my post and explain what a quasi-clique is? The people who don't know yet, are probably not the people who can help, anyway. $\endgroup$ – JorenHeit Nov 3 '14 at 9:09
  • $\begingroup$ no need to apologize, its up to you. But with the current question you are limited to answers either such as "no, it's not implemented" or "yes, here is the package". If you break down the problem somebody may take the effort to advance in an implementation. For instance, Are there C libraries that do the job? If yes, Mathematica can link to those and you could build your own implementation using the best of both worlds with the help of the community. Share what you have learned so far about your problem and you are more likely to interest somebody and receive help. $\endgroup$ – rhermans Nov 3 '14 at 9:16
  • $\begingroup$ @rhermans I see :-) I've added the definition of a quasi-clique. I already know that it's not implemented, but I'm simply wondering if there are tricks to accomplish this. I'll go look for some libraries, and if I can find any, I'll try to figure out how to link to it. $\endgroup$ – JorenHeit Nov 3 '14 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.