Métodos de partição e reordenação para grafos

5 dezembro 2011, 08:00 • Alexandre Francisco

Comunidades em grafos, clustering e reordenação de vértices (cont.). Problemas e limitações. Métodos baseados em propagação de labels. Modularidade e optimização gananciosa. Métodos multi-level, coarsening e refinamento. Cortes minimos como abordagem à partição de grafos e optimização de clusters.

Referências complementares: S. Fortunato: Community detection in graphs, Physics Reports 486:75-174, 2010; Boldi et al.: Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks, WWW'2011; Abou-rjeili and Karypis: Multilevel Algorithms for Partitioning Power-Law Graphs, TR 05-034, CSE Dept, University of Minnesota, 2005; Flake et al: Graph Clustering and Minimum Cut Trees, Internet Mathematics Vol. 1, No. 4: 385-408.