I have a problem where I need to split a graph into subgraphs. The conditions for the splitting is as follows:
- Every subgraph must be a complete graph/clique
- No vertex can be part of two or more subgraphs
- Subgraphs that can be merged with other subgraphs while remaining complete cannot exist
- When multiple possible complete subgraphs/cliques are present, chose the one with highest within-clique edge weight
Below is an obvious example. Multiple maximal cliques exists, but it is very clear to the beholder which two should constitute the subgraphs.
Community detection are not a good fit (at least the algorithms I've looked into) because they don't enforce completeness within the communities. Furthermore the graphs that I'm working with are quite small and dense, and community detection algorithms will often just find one large community.
My main approach now is thus to find all maximal cliques, and then somehow remove unwanted cliques based on edge weights but I'm at a loss as to what the best approach for the latter part is...
Edit: This is my current implementation
- Detect maximal cliques in the graph.
- Sort the cliques in descending order based on their minimum edge weight within the clique.
- Iterate over the sorted cliques, adding cliques to my result list if, and only if, its member vertices are not present in any already selected clique.
After iteration see if any vertices in the original graph are present in any of the selected cliques.
- If all vertices are present, exit.
- If not create a subgraph of the original graph containing the missing vertices and repeat 1-4.
This is sort of similar to @kurtosis answer but handles edge weights as well as the case where vertices are left out of the initial iteration.
Edit 2: To clarify what I'm asking (because it might be less obvious after the first edit). My problem remains as described in the first part. After posing the question I've developed a solution as described in the first edit, that seems to get the job done, but it is, in my view, not very elegant. It might be the only way to solve the given problem, but I wouldn't know as graph theory is not my main area. Thus I'm still curious if there are other more efficient approaches to solving the problem.