Um algoritmo para encontrar a cobertura por k-cliques em redes sociais

• Autor(es): Mendes, Armando B. ; Cavique, Luís ; Santos, Jorge M. A.
• Data: 2009
• Identificador Persistente: http://hdl.handle.net/10400.3/2154
• Origem: Repositório da Universidade dos Açores
• Assunto(s): Extracção de Conhecimento em Dados; Extracção de Conhecimento em Grafos; Redes Sociais; Data Mining; Graph Mining; Social Networks
• Tipo de Documento: Parte ou capítulo de livro
• Idioma: Português

Descrição

14º Congresso da APDIO, 7 a 9 de Setembro de 2009, Faculdade de Ciências e Tecnologia - Caparica. Na análise de redes sociais, uma k-clique é a relaxação de uma clique, i.e., uma k-clique é um quase sub-grafo completo. Um k-clique num grafo é um sub-grafo onde a distancia entre quaisquer par de vértices não é maior que k. A visualização de um pequeno número de vértices é fácil de obter. Contudo, quando o número de vértices aumenta a visualização torna-se incompreensível. Nesta comunicação, propomos uma nova abordagem na extracção de conhecimento em grafos, utilizando k-cliques. O conceito que clique relaxado é estendido para todo o grafo, de forma a ter uma visão geral, ao cobrir a rede com k-cliques. Sequências de coberturas de k-cliques são apresentadas combinando o conceito dos "pequenos mundos" com estruturas com coesão. Resultados computacionais e exemplos são apresentados. ABSTRACT: In social network analysis, a k-clique is a relaxed clique, i.e., a k-clique 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 easy to perform 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 whole the 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.