Comparing clustering and partitioning strategies

• Autor(es): Afonso, Carlos ; Ferreira, Fábio ; Exposto, José ; Pereira, Ana I.
• Data: 2012
• Identificador Persistente: http://hdl.handle.net/10198/10800
• Origem: Biblioteca Digital do IPB
• Assunto(s): Clustering; Partitioning; Web graph
• Tipo de Documento: Parte ou capítulo de livro
• Idioma: Inglês

Descrição

In this work we compare balance and edge-cut evaluation metrics to measure the performance of two well-known graph data-grouping algorithms applied to four web and social network graphs. One of the algorithms employs a partitioning technique using Kmetis tool, and the other employs a clustering technique using Scluster tool. Because clustering algorithms use a similarity measure between each graph node and partitioning algorithms use a dissimilarity measure (weight), it was necessary to apply a normalized function to convert weighted graphs to similarity matrices. The numerical results show that partitioning algorithms behave clearly better than to the clustering counterparts when applied to these types of graphs.