Comparing clustering and partitioning strategies

• Author(s): Afonso, Carlos ; Ferreira, Fábio ; Exposto, José ; Pereira, Ana I.
• Date: 2012
• Persistent ID: http://hdl.handle.net/10198/10800
• Origin: Biblioteca Digital do IPB
• Subject(s): Clustering; Partitioning; Web graph
• Document Type: Part of book or chapter of book
• Language: English

Description

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.