HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Densely connected non overlapping subgraph

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
nonoverlappingconnectedsubgraphdensely

Problem

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

Solution

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:

  • $k$-cores are maximal



  • 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).

Context

StackExchange Computer Science Q#57773, answer score: 3

Revisions (0)

No revisions yet.