Loading...
| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 325.73 KB | Adobe PDF |
Advisor(s)
Abstract(s)
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.
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.
Description
14º Congresso da APDIO, 7 a 9 de Setembro de 2009, Faculdade de Ciências e Tecnologia - Caparica.
Keywords
Extracção de Conhecimento em Dados Extracção de Conhecimento em Grafos Redes Sociais Data Mining Graph Mining Social Networks
Citation
Cavique, Luis; Mendes, Armando B. e Santos, Jorge M.A. (2009). "Um algoritmo para encontrar a cobertura por k-cliques em redes sociais". In Póvoa, Ana P.B. e Salema, Maria I.G. «Livro de Actas», 14º Congresso da APDIO - IO2009, FCT-UNL: 27-34.
Publisher
FCT-UNL