Currently, I am working on a research project where I will utilise reinforcement learning for the diversified top-$k$ clique search problem. To train the reinforcement learning algorithm, I need to generate graphs that have similar properties, such as average degree and overlapping cliques, to the ones used in the paper Local search for diversified Top-k clique search problem, which you can find on this website.

What is the diversified top-$k$ clique search problem (DTKC)?

DTKC is a less known combinatorial optimisation problem. The goal of DTKC is to maximise the length of the coverage a found clique set $D=\left \{C_1, C_2, \dots, C_{k-1}, C_k \right \}$ in a given graph $G$. Each $C \in D$ should be a maximal clique, and the set can only contain, at most, $k$ cliques, which means that $ \left | D \right | \leq k$, must always be true. As previously stated, the goal of DTKC is to maximise the coverage of the clique set, which is calculated by: $$ \text{Cov}(D)=\bigcup_{C \in D}C $$ The coverage set $\text{Cov}(D)$ will contain all the unique nodes contained in the cliques. The goal function is then to maximise $|\text{Cov}(D)|$.

What do I need?

At the start of my question, I stated that I needed to generate graphs as training data for my reinforcement learning algorithm. However, I tried several popular models, like the Barabási-Albert and Erdős–Rényi model, which either created too small cliques (with almost all found cliques having 3 to 5 nodes) or the cliques overlapped too much. I am looking for a model that can generate undirected graphs with partially overlapping cliques, up to around 100.000 nodes and an average degree between 10 and 100. With partially overlapping cliques, I mean that two or cliques share a certain amount of nodes. For instance, one of the papers on DTKC describes how the largest maximal cliques in a graph will likely contain most of the same nodes (the paper shows an excellent example figure of this happening, but I am afraid to include it, because of copyright issues).

Any suggestions are welcome about how I should handle the generation. Information that would help is, for instance, proposing lesser-known graph generation models or how to compare graph generation models to real-world data graphs to see which input variables are needed to generate graphs with similar properties to those graphs. I prefer to use already implemented models, like those in Networkx, but I can also implement them myself if needed, of course.

Hopefully, someone can help me with this specific and complex problem, but please do not be afraid to comment if you do not understand DTKC completely. If you know about a graph generator algorithm that can quickly generate graphs with overlapping cliques, it would already be of great help.


Local search for diversified Top-k clique search problem by Jun Wu, Chu-Min Li, Lu Jiang, Junping Zhou, Minghao Yin

Diversified Top-K Clique Search by Long Yuan, Lu Qin, Xuemin Lin, Lijun Chang, and Wenjie Zhang.

  • $\begingroup$ While looking through papers, I found the Lancichinetti–Fortunato–Radicchi benchmark. However, I am a bit struggling with understanding the effects of both power-law distribution parameters, could someone explain in simple terms the impact of them and maybe give suggestions of value ranges, that I should use for both parameters? $\endgroup$
    – Jesse
    Dec 15 '21 at 11:40

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.