World's most popular travel blog for travel bloggers.

# [Answers] Densely connected non overlapping subgraph

, ,
Problem Detail:

I'm trying to detect quasi cliques in an undirected graph. My problem is that I don't want any overlap between cluster.

I'm currently trying to detect community using Louvain algorithm, but it detects subgraphs with a low clustering coefficient (0.60) and when I detect maximal or quasi cliques they tend to overlap.

How can I compute a clique decomposition of an undirected graph with no overlap between clusters ? Is there an algorithm with an implementation of it which can deal with my problem ?

Thanks

If you want to find cliques, or quasi-cliques, don't expect non-overlapping communities, as their definitions imply that there might be overlap between clusters. When it comes to community detection or clustering, you need to make a formal definition of a community or cluster (in this case it is a clique). There are two types of definitions:

Non-overlapping definitions - There are some definitions that do not allow any overlap between communities such as \$k\$-cores. Basically, the following properties prevent \$k\$-cores of being overlapping:

1. \$k\$-cores are maximal
2. Union of two \$k\$-cores is a \$k\$-core.

There are lots of different techniques such as modularity optimization, seed expansion, etc. If you are looking for stricter non-overlapping community definitions, you can dig further in this paper (and the sequence of other papers) and find the one ghat works well on coefficient clustering score:

Fortunato, Santo. "Community detection in graphs." Physics reports 486.3 (2010): 75-174.

Overlapping definitions - However, some definitions such as cliques or quasi-cliques, allow overlap between clusters, even though you consider maximality. Below, I show a simple example where few maximal cliques overlap with each other (link for image).