patternMinor
Densely connected non overlapping subgraph
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
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:
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).
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.