An Algorithm to Discover the k-Clique Cover in Networks.

• Author(s): Cavique, Luís ; Mendes, Armando B. ; Santos, Jorge M. A.
• Date: 2009
• Persistent ID: http://hdl.handle.net/10400.3/2148
• Origin: Repositório da Universidade dos Açores
• Subject(s): Data Mining; Graph Mining; Social Networks
• Document Type: Part of book or chapter of book
• Language: English

Description

14th Portuguese Conference on Artificial Intelligence, EPIA 2009, Aveiro, Portugal, October 12-15, 2009. In social network analysis, a k-clique is a relaxed clique, i.e., a kclique is a quasi-complete sub-graph. A k-clique in a graph is a sub-graph where the distance between any two vertices is no greater than k. The visualization of a small number of vertices can be easily performed in a graph. However, when the number of vertices and edges increases the visualization becomes incomprehensible. In this paper, we propose a new graph mining approach based on k-cliques. The concept of relaxed clique is extended to the whole graph, to achieve a general view, by covering the network with k-cliques. The sequence of k-clique covers is presented, combining small world concepts with community structure components. Computational results and examples are presented.