A Graph-theoretic Framework for Multi-layered k-community Clique Relaxation

Abstract

In network-based data mining, clique percolation brings an attractive feature for finding communities in a graph as well as the overlapping areas of these communities. Despite complete clique formalization, some of the properties of clique structure have been relaxed to investigate more effective and efficient manners to identify the community structure in large and sparse network. In this paper, it is proposed the idea that how to take advantages of the clique relaxation concept of k-community, introduced by Verma and Butenko (2013), with some modifications in clustering cohesive groups. In addition, we intend to promote the quality of the cluster by means of new multi-layered consideration.