Algoritmos para o Problema de Particionamento em Grafos

CLEI 2011

Algoritmos para o Problema de Particionamento em Grafos Thiago de Paulo Faleiros1,2 Instituto Federal de Educa¸ca ˜o, Ciˆencia e Tecnologia de Goi´ as Luziˆ ania, Brasil

Eduardo Candido Xavier

3

Instituto de Computa¸c˜ ao Universidade Estadual de Campinas Campinas, Brasil

Resumo Investigamos Problemas de Particionamento de objetos que tˆem rela¸co ˜es de similaridade entre si. Instˆ ancias desses problemas podem ser representados por grafos, em que objetos s˜ ao v´ertices e a similaridade entre dois objetos ´e representada por um valor associado a ` aresta que liga os objetos. Nosso foco ´e o estudo de algoritmos para clusteriza¸ca ˜o em grafos, onde deve-se determinar clusteres tal que arestas ligando v´ertices de clusteres diferentes tenham peso baixo e ao mesmo tempo as arestas entre v´ertices de um mesmo cluster tenham peso alto. No caso geral estes problemas s˜ ao NP-Dif´ıceis. Nosso interesse ´e investigar algoritmos eficientes e que gerem boas solu¸co ˜es, como Heur´ısticas, Meta-heur´ısticas e Algoritmos de Aproxima¸c˜ ao. Dentre os algoritmos estudados, implementamos os mais promissores e fazemos uma compara¸ca ˜o de seus resultados utilizando instˆ ancias geradas computacionalmente. Por fim, propomos um algoritmo que utiliza a metaheur´ıstica GRASP para o problema considerado e mostramos que para as instˆ ancias de testes geradas, nosso algoritmo obt´em melhores resultados. Keywords: Problema de Particionamento, Grafos, Meta-heur´ısticas, Spectral Clustering

1

Introduction

Devido a` dificuldade computacional de se encontrar solu¸co˜es ´otimas para muitos dos problemas de otimiza¸c˜ao combinat´oria, foram elaborados m´etodos que 1 2 3

Este trabalho recebeu aux´ılio financeiro da FAPESP e do CNPq Email: [email protected] Email: [email protected] This paper is electronically published in Electronic Notes in Theoretical Computer Science URL: www.elsevier.nl/locate/entcs

Faleiros, Xavier

abrem m˜ao da otimalidade em troca de solu¸c˜oes consideradas “boas” e que possam ser obtidas eficientemente. Em muitas ocasi˜oes, percebe-se que na falta de uma solu¸ca˜o o´tima do problema, pode-se utilizar a melhor solu¸ca˜o dispon´ıvel. Com isso, m´etodos eficientes que encontrem solu¸co˜es n˜ao necessariamente o´timas, mas suficientemente boas podem ser muito u ´teis. Dentre esses m´etodos, destacamos as heur´ısticas. Os m´etodos heur´ısticos englobam v´arias t´ecnicas de resolu¸ca˜o de problemas que obt´em solu¸co˜es boas mas n˜ao necessariamente o´timas. Dentre as v´arias t´ecnicas, citamos a busca tabu, algoritmos gen´eticos e GRASP. Para mais informa¸co˜es sobre heur´ısticas, veja [11]. Heur´ısticas fornecem solu¸co˜es sem um limite formal de qualidade, ao contr´ario de solu¸c˜oes geradas por algoritmos aproximados. Ainda assim, na pr´atica, o uso de heur´ısticas tem sido promissor para a obten¸c˜ao de solu¸c˜oes de boa qualidade. Neste trabalho temos interesse em investigar m´etodos heur´ısticos para problemas de particionamento. O objetivo desse problema ´e particionar um dado conjunto de objetos de maneira que objetos “similares” perten¸cam a` mesma parte, enquanto objetos em partes distintas sejam menos “similares”. Tais problemas aparecem na literatura de maneira bem variada. Isso ocorre principalmente devido ao grande n´ umero de aplica¸c˜oes existentes, cada uma com uma defini¸ca˜o apropriada da fun¸ca˜o de “similaridade”. Os problemas considerados s˜ao NP-dif´ıceis e, portanto, ´e improv´avel que sejam encontrados algoritmos exatos eficientes. Existem diversas aplica¸c˜oes para problemas de particionamento. Em processamento de imagens, por exemplo, h´a problemas de segmenta¸ca˜o de imagens que podem ser resolvidos atrav´es de problemas de particionamento. Outro problema real que pode ser modelado como um problema de particionamento ´e encontrar subconjuntos de p´aginas da Web que est˜ao relacionadas entre si. Quanto a organiza¸c˜ao deste trabalho, inicialmente, na Se¸ca˜o 2 s˜ao descritas as fun¸co˜es de avalia¸c˜ao de particionamento. Em seguida, na Se¸ca˜o 3, s˜ao mostrados os algoritmos mais promissores para o problema. Na Se¸ca˜o 4, ´e apresentada a abordagem proposta neste trabalho que utiliza GRASP para encontrar solu¸co˜es para o problema de particionamento em grafos. E por fim, na Se¸ca˜o 5, s˜ao analisados os resultados computacionais das execu¸co˜es dos algoritmos. 1.1

Problemas de Clusteriza¸c˜ao e Particionamento

Neste trabalho consideramos o problema de particionamento de um grafo, que tamb´em chamaremos de clusteriza¸c˜ao de um grafo. Como instˆancia do problema, temos um grafo G = (V, E) com pesos nas arestas que indicam a similaridade entre os pares de v´ertices. O objetivo ´e encontrar uma parti¸ca˜o 2

Faleiros, Xavier

dos v´ertices, de forma que cada parte, ou cluster, tenha arestas entre v´ertices internos com peso alto e o peso das arestas entre v´ertices de clusteres diferentes seja baixo. Essa rela¸c˜ao entre os v´ertices internos de um cluster e todos os outros v´ertices, apresenta um paradigma geral para particionamento. Esse paradigma relaciona a densidade intracluster, definida pela soma dos pesos das arestas internas do subgrafo induzido por Ci (cluster), a` esparsidade intercluster, definida pela soma dos pesos das arestas que saem do subgrafo (ou cluster), ou seja, as arestas do corte induzido pelo particionamento. Dessa forma, para modelar o problema como um problema de otimiza¸c˜ao combinat´oria, deve-se ter uma fun¸ca˜o de avalia¸ca˜o cujo o objetivo comum ´e encontrar parti¸c˜oes que maximizem a densidade intracluster e que tamb´em maximizem a esparsidade intercluster.

2

Fun¸ c˜ oes de Avalia¸c˜ ao

Nesta se¸c˜ao, vamos definir as fun¸co˜es de avalia¸ca˜o utilizadas para determinar um “bom” particionamento. Antes disso, definiremos a nota¸ca˜o utilizada. Assumiremos que G = (V, E, w) ´e um grafo simples, conexo, n˜ao direcionado e com uma fun¸c˜ao w : E → R+ . Seja |V | = n e C = {C1 , ..., Ck }, Ci ∩Cj = ∅ com i 6= j, uma parti¸ca˜o (tamb´em chamaremos de particionamento/clusteriza¸ca˜o) de V , onde cada Ci ⊆ V corresponde a um cluster e ∪ki=1 Ci = V . Denotaremos por w(C) a soma do peso de todas as arestas P intracluster. Para um subconjunto 0 0 de arestas E ⊆ E, definimos w(E ) = e∈E 0 w(e). O subgrafo induzido pelo subconjunto Ci ser´a denotado por G[Ci ], e denotamos por E(Ci ) as arestas deste subgrafo. Sejam X e Y subconjuntos de V . Denotamos por E(X, Y ) o conjunto de arestas entre v´ertices de X e Y . O somat´orio dos pesos das arestas de E(X, Y ) ser´a denotado por c(X, Y ). A seguir, ser˜ao descritas as fun¸c˜oes de Corte Normalizado e Desempenho (Performance). Corte Normalizado - N Cut: Seja um particionamento C = {C1 , . . . , Ck } com k > 1. O custo do corte normalizado de C ´e definido como N Cut(C) =

k X c(Ci , V \Ci ) i=1

a(Ci )

.

onde a(Ci ) =

XX u∈Ci v∈V

X

w(u, v) = 2

e∈E(Ci )

w(e) +

X

w(e)

e∈E(Ci ,V \Ci )

Note que, quanto menor for o custo do corte normalizado, melhor ser´a o particionamento. 3

Faleiros, Xavier

Desempenho - Performance: A Performance de um particionamento C representa o n´ umero de “pares de v´ertices corretamente interpretados” em um grafo [3]. Informalmente, a Performance ´e uma soma normalizada de contribui¸c˜oes de cada par de v´ertices. Se os dois v´ertices estiverem no mesmo cluster, ent˜ao o par contribui com o peso da aresta entre eles, se houver. Do contr´ario, o par contribui com um valor fixo, descontado o peso da aresta correspondente, quando existir. Seja M o peso m´aximo que uma aresta pode ter. Definimos fun¸co˜es f e g como:

f (C) =

k X

w(E(Ci ))

i=1

g(C) =

k X X

M |{(u, v) ∈ / E|u ∈ Ci , v ∈ Cj }|

i=1 j>i

A fun¸ca˜o f contar´a a contribui¸ca˜o dos pares de v´ertices intracluster, enquanto a fun¸ca˜o g contar´a a contribui¸c˜ao M de cada par de v´ertices n˜ao adjacentes em diferentes clusteres. Para descontar o custo das arestas intercluster, ´e feita a diferen¸ca (M |E(C)| − w(E(C))), onde E(C) ´e o conjunto de arestas intercluster. A f´ormula completa da Performance ´e dada por P erf ormance(C) =

f (C) + g(C) + (M |E(C)| − w(E(C))) . 1 n(n − 1)M 2

Quanto maior for o valor da Performance, melhor ser´a o particionamento.

3

Algoritmos

Nesta se¸ca˜o, s˜ao descritos os algoritmos que tratam o problema de particionamento em grafos. Propriedades de um bom algoritmo, como a baixa complexidade computacional e facilidade de implementa¸ca˜o em aplica¸co˜es pr´aticas, foram consideradas na sele¸ca˜o feita ap´os a revis˜ao bibliogr´afica. Alguns algoritmos utilizam uma matriz normalizada M (G), chamada de matriz de transi¸ca˜o, de um dado grafo com pesos nas arestas n˜ao direcionado G = (V, E, w). Define-se matriz de transi¸ca˜o como M (G) = D(G)−1 × A(G), tal que A(G) ´e a matriz de adjacˆencia do grafo G e D(G)−1 ´e a inversa de uma matriz diagonal D(G). A matriz D(G) possui zeros em todas as posi¸c˜oes exceto na diagonal, onde em cada posi¸ca˜o [v, v] considera-se a soma dos pesos das P arestas incidentes em v, i.e. D(G) = diag(d(V )), onde v ∈ V , d(v) = (v,u)∈E w(v, u). 4

Faleiros, Xavier

3.1

Markov Clustering(MCL)

O Algoritmo MCL (veja o Algoritmo 1) foi proposto em [13]. A ideia deste algoritmo ´e simular passeios aleat´orios em um grafo. A matriz de transi¸ca˜o ´e utilizada no algoritmo, onde para um par de v´ertices u, v interpretamos os valores M (G)[u, v] como a probabilidade de a partir de u irmos para v. O algoritmo parte do princ´ıpio que em um passeio aleat´orio come¸cando de um v´ertice de um cluster denso (com v´ertices altamente similares) com pouca probabilidade o passeio ir´a deixar o cluster at´e que v´arios v´ertices do cluster sejam visitados. No algoritmo puv corresponde ao valor M (G)[u, v].

Algoritmo 1 Entrada: (G = (V, E, w), parˆ ametro de expans˜ ao e, parˆ ametro de infla¸ca ˜o r) inicio M ← M (G); enquanto (M n˜ ao ´ e imdepotente) fa¸ ca M ← M e; para todo (u ∈ V ) fa¸ ca para todo ( v ∈ V ) fa¸ ca puv ← pruv ; para todo (v ∈ V ) fa¸ ca puv ← P puv p ; w∈V

uv

fim do para fim do enquanto H ← grafo induzido pelas entradas diferentes de zero em M ; C ← parti¸c˜ ao induzida por componentes conexo de H; fim

Algoritmo 1. Markov Clustering (MCL)

Para simular os passos de um passeio dentro do grafo, a matriz de transi¸ca˜o M ´e elevada a uma potˆencia e, obtendo M e . Cada entrada peu,v de M e corresponde a probabilidade de ir de u para v em e passos em um passeio aleat´orio. Na pr´oxima etapa do algoritmo, chamada de infla¸c˜ao, cada entrada peu,v ´e elevada a um valor constante r e re-normalizada logo em seguida. O objetivo ´e que os valores de transi¸c˜oes com alta probabilidade sejam intensificados e transi¸co˜es baixas sejam degradadas. Devido a alternˆancia entre exponencia¸ca˜o e infla¸c˜ao, valores baixos tender˜ao para zero. Assim, as arestas que ligam v´ertices de diferentes subgrafos densos ser˜ao degradadas de forma que no resultado final do algoritmo, cada componente conexo representar´a um particionamento. Na tese de Dongen [13] n˜ao ´e apresentada uma prova formal demonstrando que o processo de alternˆancia entre exponencia¸ca˜o e infla¸c˜ao ir´a levar a “bons” particionamentos. Entretanto, a heur´ıstica que leva para a formula¸ca˜o do algoritmo sugere que bons particionamentos possam ser determinados. 5

Faleiros, Xavier

3.2

Iterative Conductance Cutting (ICC)

Inicialmente, para entender o Algoritmo ICC (veja o Algoritmo 2), definiremos corte de condutˆancia. A condutˆancia de um corte compara o custo do corte e os pesos das arestas internas dos dois subgrafos induzidos. A condutˆancia ϕ(Ci ) de um corte c(Ci , V \Ci ) em G ´e definido como: ϕ(Ci ) =

c(Ci , V \Ci ) . min(a(Ci ), a(V \Ci ))

A condutˆancia ϕ(G) de um grafo G ´e o valor da condutˆancia m´ınima dentre todos poss´ıveis cortes de G: ϕ(G) = minCi ⊂V ϕ(Ci ) Note que a fun¸c˜ao de condutˆancia relaciona bem o paradigma principal deste trabalho, que ´e encontrar subconjuntos de v´ertices com alto peso nas arestas internas e peso baixo nas arestas que ligam diferentes subconjuntos de v´ertices (arestas externas). Dessa forma, a id´eia do Algoritmo ICC (proposto por [9]) ´e que em um bom particionamento {C1 , ..., Ck } do grafo, cada Ci tem o valor do corte de condutˆancia ϕ(Ci ) baixo e, ao mesmo tempo, o valor de condutˆancia de G[Ci ] (ϕ(G[Ci ]) n˜ao ´e baixo. Inicialmente o algoritmo considera como particionamento apenas uma parti¸ca˜o que cont´em todos os v´ertices, i.e., C = {V }. A cada itera¸ca˜o o algoritmo verifica se existe uma parti¸ca˜o C ⊂ C que possa ser separada em duas novas parti¸co˜es tal que o valor da condutˆancia destas duas novas parti¸co˜es seja baixo. Para encontrar estas duas novas parti¸co˜es o algoritmo considera o subgrafo induzido G[C] e acha um corte com condutˆancia m´ınima aproximada. O algoritmo procede enquanto houver parti¸co˜es que possam ser divididas. Algoritmo 2 Entrada: (G = (V, E, w), limiar de condutˆ ancia 0 < α∗ < 1) inicio C ← {V }; enquanto (∃ C ∈ C com ϕ(G[C]) < α∗ ) fa¸ ca x ← autovetor de M (G[C]) associado ao segundo maior autovalor; S ← {S ⊂ C | maxv∈S (xv ) < minw∈C\S (xw )}; C 0 ← arg min SS∈S (ϕ(S)); C ← (C\{C}) {C’, C\C’}; fim enquanto fim

Algoritmo 2. Iterative Conductance Cutting (ICC)

O problema de encontrar o corte de condutˆancia m´ınima ´e N P -Dif´ıcil [9]. Dessa forma, o Algoritmo ICC utiliza uma heur´ıstica que retorna uma aproxima¸ca˜o para o corte de condutˆancia m´ınima. A heur´ıstica para aproximar o 6

Faleiros, Xavier

corte de condutˆancia m´ınima pode ser descrita da seguinte forma: primeiramente calcula-se o autovetor x ∈ Rn relativo ao segundo maior autovalor λ2 da matriz M (G[C]), onde G[C] ´e o grafo induzido do subconjunto de v´ertices C; a partir dos valores de x = {x1 , ..., xk } orden´a-los em ordem crescente, tal que xi1 ≤ xi2 ≤ ... ≤ xik e em seguida encontrar o valor t que minimize a condutˆancia ϕ({xi1 , ..., xit }), 1 ≤ t ≤ k. No trabalho de [9] ´e provado um limite superior para a aproxima¸ca˜o com a seguinte rela¸c˜ao: φ(G)2 (1) ϕ(G) ≥ 1 − λ2 ≥ 2 onde φ(G) ´e o valor do corte de condutˆancia encontrado pelo algoritmo aproximado que utiliza a heur´ıstica do segundo autovetor λ2 . 3.3

Geometric MST Clustering (GMC)

A ideia do Algoritmo GMC [3] (veja o Algoritmo 3) ´e imergir um grafo G no espa¸co Rn e atribuir peso a`s arestas. Os valores dos pesos ser˜ao dados pela rela¸ca˜o de distˆancia entre v´ertices. Em seguida, ´e criada uma a´rvore geradora m´ınima (Minimum Spanning Tree - MST) com os novos pesos das arestas de G. Seja T uma MST gerada com os novos pesos. Para encontrar os clusteres, s˜ao removidas arestas de T com peso superior a um limiar τ . Chamaremos de F (T, τ ) a floresta induzida por todas as arestas de T com peso no m´aximo τ . Para cada limiar τ , os componentes conexos de F (T, τ ) gerar˜ao uma solu¸ca˜o com clusteres que denotamos por C(τ ). A solu¸ca˜o final ´e determinada pelo limiar τ que otimiza a fun¸c˜ao de qualidade (ver Se¸ca˜o 2) aplicada sobre C(τ ). Veja o Algoritmo 3 para a descri¸ca˜o em pseudoc´odigo do Algoritmo GMC. Algoritmo 3 Entrada: (G = (V, E, w), n´ umero de dimens˜ oes para imers˜ ao d , fun¸c˜ ao de avalia¸ca ˜o de clusteres q) inicio (1, λ2 , ..., λd+1 ) ← d + 1 maiores autovalores de M (G); d0 ← max{i|1 ≤ i ≤ d, λi > 0}; x1 , ..., xd0 ← autovetores de M (G) associados com λ1 , ..., λd0 respectivamente; para todo (e = (u, v) ∈ E) fa¸ ca d0 X w0 (e) ← |xi [u] − xi [v]|; i=1

fim do para T ←a ´rvore geradora m´ınima de G em rela¸c˜ ao a w0 ; Dentre todos τ ∈ {w(e)| ∈ T }, devolva C(τ ) que otimiza q(C(τ )); fim

Algoritmo 3. Geometric MST Clustering (GMC)

O Algoritmo GMC cria a matriz de transi¸c˜ao do grafo de entrada e seleciona os autovetores u ´teis para fazer a imers˜ao do grafo no espa¸co. Uma imers˜ao do grafo G no espa¸co ´e constru´ıda a partir de d autovetores {x1 , x2 , ..., xd } da 7

Faleiros, Xavier

matriz de transi¸ca˜o M (G) que est˜ao associados aos maiores autovalores menores ou iguais a um. Formalmente, podemos enunciar o problema da imers˜ao de um grafo G no espa¸co d-dimensional da seguinte forma: Problem 3.1 (Imers˜ ao no Espa¸co) [6] Dado como entrada um grafo G = (V, E) com n v´ertices – sem perda de generalidade assumimos que V = {1, 2, ..., n} – e uma fun¸c˜ao de custo g : Rn×d → R, onde d representa o n´ umero de dimens˜oes. O objetivo ´e determinar uma fun¸c˜ao % : V → Rd tal que, se a fun¸c˜ao de custo g tem um m´ınimo global, ent˜ao o valor de g(A) ´e o m´ınimo com a matriz A constru´ıda como   %(1)    ..  A =  . .   %(n) Note que no algoritmo a imers˜ao para cada v´ertice v ´e dada por %(v) = (x1 [v], x2 [v], . . . , xd0 [v]). Para ilustrarmos o processo de imers˜ao de um grafo e a sua rela¸c˜ao com clusteres, tomaremos como exemplo um grafo (ver Figura 1) e aplicaremos o processo descrito pelo Algoritmo GMC. Para simplificar a ilustra¸ca˜o, ser´a considerada a imers˜ao do grafo G0 em uma reta (d = 1). Sejam o grafo G0 = (V 0 , E 0 ), representado pela Figura 1, e x1 o autovetor associado ao segundo maior autovalor de M (G0 ).

Figura 1. Grafo G0 dado como entrada para o exemplo de imers˜ ao no espa¸co Rn .

Neste caso % ´e dado pelo u ´nico autovetor x1 , e ´e uma fun¸c˜ao que atribui um valor real a cada v´ertice. A representa¸c˜ao ´e dada pela Figura 2.

Figura 2. Reta com a imers˜ ao dos v´ertices do grafo G1 .

8

Faleiros, Xavier

Note que os pontos {e, g, d, f } est˜ao posicionados pr´oximos um dos outros e distantes dos pontos {c, b, a}. Para o grafo G0 , que ´e um grafo com poucos v´ertices, ´e poss´ıvel perceber que os clusteres s˜ao os conjuntos de v´ertices {e, g, d, f } e {c, b, a} apenas com o aux´ılio dessa imers˜ao. Quanto ao tempo de execu¸ca˜o, o Algoritmo GMC ´e dominado pelo tempo de calcular os autovetores da matriz de transi¸ca˜o e o tempo da cria¸ca˜o da a´rvore geradora m´ınima.

4

GRASP para o problema de Particionamento

Nesta se¸ca˜o, ´e apresentada uma nova abordagem que utiliza a meta-heur´ıstica GRASP para tratar o problema de particionamento em grafos. GRASP (Greedy Randomized Adaptive Search Procedure) ´e uma meta-heur´ıstica iterativa, desenvolvida por Feo e Resende [4], em que a cada itera¸c˜ao duas fases a s˜ao executadas: constru¸ca˜o e busca local. Na fase de constru¸c˜ao, uma solu¸c˜ao vi´avel ´e criada progressivamente a partir do zero. Em cada itera¸c˜ao, apenas um elemento ´e adicionado a solu¸c˜ao. A sele¸ca˜o do pr´oximo elemento ´e guiado por uma fun¸ca˜o gulosa-aleat´oria que mede o benef´ıcio que o mais recente elemento escolhido concede para a solu¸ca˜o at´e ent˜ao constru´ıda. Na busca local, o objetivo ´e tentar melhorar a solu¸c˜ao inicial S de maneira iterativa. A cada itera¸ca˜o, ´e gerado um conjunto de solu¸co˜es vizinhas de S, denotado por N (S). Este conjunto ´e gerado atrav´es de pequenas modifica¸c˜oes na solu¸ca˜o atual S. A melhor solu¸c˜ao em N (S) ´e escolhida para ser a solu¸ca˜o atual, se esta melhorar o custo da fun¸ca˜o objetivo em rela¸c˜ao a S. O processo ´e repetido at´e encontrarmos um m´ınimo local, quando a solu¸ca˜o atual n˜ao pode ser melhorada. Para descrever a utiliza¸ca˜o da meta-heur´ıstica GRASP para tratar o problema de particionamento em grafos, deve-se ater em dois passos importantes. Primeiro, como construir uma solu¸ca˜o inicial vi´avel para o problema de particionamento em grafos e, em seguida, como gerar os vizinhos para realizar a busca local. 4.1

Constru¸c˜ao da Solu¸c˜ao Inicial

Foram elaboradas v´arias estrat´egias para a fase de constru¸ca˜o. Para cada estrat´egia, considera-se um grafo G = (V, E, w) dado como entrada. Abaixo s˜ao descritas as estrat´egias: Classifica¸c˜ ao gulosa utilizando centroides: Seja R um subconjunto com k v´ertices de V . Chamaremos cada v´ertice ri ∈ R, para i = 1, . . . , |R|, de centro. Cada centro ri corresponder´a a um cluster Ci do particionamento C, 9

Faleiros, Xavier

onde 1 ≤ i ≤ k. A estrat´egia ´e atribuir cada v´ertice ao cluster mais similar de forma que a soma dos pesos das arestas para outros clusteres seja baixa. Em outras palavras, um v´ertice v ∈ V ser´a atribu´ıdo ao cluster Ci (correspondente ao centro ri ) que tenha o menor valor para q(v, Ci ) =

1 + w(v, ri ) + 

X

w(v, u),

(2)

{u∈Cj |i6=j}

onde  ´e uma constante, tal que 0 <  ≤ 1. Para encontrar o conjunto R com os centros iniciais resolvemos o problema do k-centro ou k-means. Embora ambos sejam N P -Dif´ıceis, existem algoritmos aproximados r´apidos com bom fator de aproxima¸ca˜o e heur´ısticas que retornam bons resultados [8] [7] [10]. Antes de buscar o conjunto R de centros de um grafo G, devemos construir uma representa¸ca˜o do grafo no espa¸co d-dimensional. Para construir a representa¸c˜ao, ´e feito o processo de imers˜ao no espa¸co (veja o Problema 3.1). Veja o Algoritmo 4 para a constru¸ca˜o da imers˜ao. O Algoritmo 4 utiliza o mesmo princ´ıpio de imers˜ao utilizado pelo algoritmo GMC. Uma representa¸c˜ao do v´ertice u ∈ V no espa¸co corresponder´a a um vetor linha %(u) de R, onde a matriz R ´e formada pelos autovetores x1 , ..., xd de M correspondente aos d maiores autovalores 1, λ2 , ..., λd . Algoritmo 4 Entrada (G = (V, E, w) com n v´ ertices, d ´ e o n´ umero de dimens˜ oes para imers˜ ao) inicio Represente cada v´ ertice de V como um inteiro de 1 at´ e n; Construa a matriz de transi¸c˜ ao de probabilidade M (G); (1, λ2 , ..., λd ) ← d maiores autovalores de M (G); x1 , ..., xd ← autovetores de M (G) associado com 1, λ2 , ..., λd ; para todo (i de 1 at´ e n) fa¸ ca %(i) ← (x1 [i], ..., xd+1 [i]); retorne a representa¸c˜ ao %; fim

Algoritmo 4. imersao – Algoritmo para imers˜ ao no espa¸co

O algoritmo guloso-aleat´orio utilizado pelo GRASP para a constru¸ca˜o de uma solu¸ca˜o inicial vi´avel ´e descrito no Algoritmo 5. Inicialmente, o algoritmo cria uma representa¸c˜ao dos v´ertices do grafo no espa¸co e busca o conjunto de centros da representa¸ca˜o. Na descri¸ca˜o do Algoritmo 5, utilizamos o m´etodo kcentros para encontrar esse conjunto. Entretanto, nos testes computacionais, utilizamos tamb´em o algoritmo k-means. Cada centro ser´a atribu´ıdo a um cluster diferente. Em seguida, escolhemos aleatoriamente um conjunto T 0 com um n´ umero x v´ertices. Cada v´ertice desse conjunto ´e atribu´ıdo ao cluster que minimiza a fun¸ca˜o q definida em (2). O algoritmo para quando todos os v´ertices forem atribu´ıdos a algum dos k clusteres. 10

Faleiros, Xavier Algoritmo 5 Entrada: (grafo G = (V, E, w) , valor constante x, n´ umero k de clusteres) inicio % ← imersao(G); R ← k − center(%); Atribua cada v´ ertice de R a um diferente cluster Ci , onde 1 ≤ i ≤ k; T ← V \R; enquanto (T 6= ∅) fa¸ ca Escolha aleatoriamente um subconjunto T 0 ⊆ T tal que |T 0 | ≤ x; para todo (p ∈ T 0 ) fa¸ ca {p} ∪ argminri ∈R q(Ci ); T ← T − T 0; fim do enquanto Retorne o particionamento {C1 , . . . , Ck }; fim

Algoritmo 5. Algoritmo Aleat´ orio Guloso para constru¸ca ˜o de uma solu¸ca ˜o do problema de particionamento.

Classifica¸c˜ ao Gulosa Aleat´ oria: Elaboramos uma outra forma mais simples de construir uma solu¸ca˜o inicial vi´avel. Seja R um subconjunto de V com k centros escolhidos aleatoriamente. Cada cluster ser´a formado incrementalmente, escolhendo a aresta de maior peso que sai de um v´ertice pertencente a um cluster e unindo esse cluster ao v´ertice da aresta. Inicialmente, ser˜ao criados k clusteres C1 , . . . , Ck com apenas um v´ertice de R em cada um. A cada passo do algoritmo, escolhemos a aresta de maior peso que liga um v´ertice v ainda n˜ao associado a um v´ertice de algum cluster Ci , 1 ≤ i ≤ k, e adicionamos v a Ci . Solu¸c˜ oes iniciais de heur´ısticas: Outra forma de construir solu¸c˜oes iniciais ´e aproveitar o particionamento retornado por outras heur´ısticas como o ICC e MCL, que podem ser usados para gerar a solu¸ca˜o inicial. 4.2

Busca Local

Nesta se¸ca˜o descrevemos como gerar uma vizinhan¸ca para uma dada solu¸c˜ao. A partir de uma solu¸c˜ao inicial C, uma solu¸ca˜o vizinha C 0 ∈ N (C) ´e obtida pela opera¸c˜ao de “movimento”. Essa opera¸ca˜o corresponde a mover alguns v´ertices de um cluster Ci ∈ C para outro cluster Cj ∈ C. Seja G0 = (Ci , E 0 , w) o subgrafo induzido pelos v´ertices de Ci ; aplicamos o corte m´ınimo em G0 e obtemos os subconjuntos S e S, separados pelo corte. Dentre S e S considere o de menor tamanho, digamos S. Um movimento corresponde a atribui¸c˜ao de todos os v´ertices de S para um outro cluster Cj . Para cada atribui¸c˜ao teremos uma uma nova solu¸ca˜o que ser´a uma solu¸ca˜o vizinha de C. Seja k o n´ umero de clusteres. Em cada itera¸ca˜o da busca local, ser˜ao feitos k cortes m´ınimos e k(k − 1) movimentos. As opera¸co˜es de movimentos tem complexidade O(n), restando o corte m´ınimo como a opera¸c˜ao mais onerosa. 11

Faleiros, Xavier

A forma tradicional de resolver o problema de corte m´ınimo ´e por meio de sua rela¸c˜ao com o problema de fluxo m´aximo. Ford e Fulkerson [5] mostraram a dualidade entre o fluxo m´aximo de s para t e o corte (s, t) m´ınimo (minimun (s, t)-cut). No problema de corte (s, t) m´ınimo, s e t s˜ao dois v´ertices que devem ser separados por um corte m´ınimo. Encontrar um corte m´ınimo de um grafo pode ser resolvido encontrando-se o corte de custo m´ınimo dentre os cortes (s, t) m´ınimos entre um v´ertice fixo s e cada outro v´ertice t ∈ V \{s}. O algoritmo mais r´apido para se resolver o problema do corte m´ınimo usando fluxo tem complexidade de tempo O(n3 ) [1]. Neste trabalho, utilizamos um algoritmo determin´ıstico simples e r´apido, com complexidade de tempo O(n3 ) [12].

5

Resultados Computacionais

Nesta se¸ca˜o, apresentamos uma compara¸ca˜o entre os algoritmos escolhidos, analisando os resultados aplicando as fun¸c˜oes N Cut e Performance. Quanto aos recursos utilizados nos testes, todos os experimentos foram executados em um computador Intel XEON 2.40GHz com 1GB de RAM utilizando o sistema operacional LINUX vers˜ao 2.6. As implementa¸c˜oes dos algoritmos foram escritas em Java (1.6.0). Foi utilizada a biblioteca LAPACK que provˆe rotinas para resolver problemas de a´lgebra linear (principalmente decomposi¸ca˜o em autovetores e autovalores) [2]. 5.1

As Instˆancias

Seguindo o processo de gera¸ca˜o aleat´oria de grafos descrita por Brandes et al [3], criamos um gerador aleat´orio de grafos com n v´ertices e com clusteres de tamanho quase uniformes. Um gerador P (n, s, v) determina uma parti¸c˜ao C = (C1 , . . . , Ck ) de {1, . . . , n} com |Ci | sendo uma vari´avel aleat´oria com valor esperado s e desvio padr˜ao vs . O valor de k depende da escolha de n, s e v. Dada uma parti¸ca˜o C = P (n, s, v) e probabilidades pin e pout , um grafo G ´e gerado. Os pesos das arestas do grafo G s˜ao definidos da seguinte forma: para uma aresta cujos v´ertices est˜ao em um mesmo cluster Ci , o peso ´e um valor escolhido aleatoriamente no intervalo [pin , 1]; para uma aresta cujos os v´ertices est˜ao em clusteres diferentes, o peso ´e um valor escolhido aleatoriamente no intervalo [0, pout ]. Caso o grafo gerado n˜ao seja conexo, arestas adicionais com peso pout s˜ao adicionadas. Para nosso experimento, os parˆametros (n, s, v), pin e pout s˜ao definidos a seguir. Tomamos v = 4 e escolhemos s por meio de uma distribui¸ca˜o uniforme √ aleat´oria de { nl | log n ≤ l ≤ n}. Experimentos s˜ao executados para n = 500. Todas as combina¸co˜es de probabilidades de pin e pout que distam de 0.05 s˜ao consideradas desde que o valor de probabilidade pin seja maior que o valor 12

Faleiros, Xavier

de pout (pin > pout ). Com isso, foram criadas 171 instˆancias. As instˆancias com probabilidade pin alta e pout baixa s˜ao “f´aceis” de se encontrar um “bom” particionamento. Chamaremos essas instˆancias “f´aceis” de instˆancias esparsas. Chamaremos de instˆancias “densas” aquelas com probabilidade pout alta. 5.2

Parˆametros e Implementa¸c˜ao dos Algoritmos

Os parˆametros do Algoritmo MCL foram definidos com e = 2 e r = 2, como sugerido no trabalho [6]. No Algoritmo GMC, os melhores resultados foram encontrados para o parˆametro d = 5. No Algoritmo ICC, para que ele pudesse encontrar o particionamento em todas as instˆancias, iniciamos os testes com α = 0.4. Caso o Algoritmo ICC tenha encontrado um particionamento com apenas um cluster, incrementamos α em 0.01 e aplicamos o ICC novamente. Sucessivas execu¸c˜oes do ICC com α incrementado foram feitas at´e que o resultado fosse um particionamento com mais de um cluster. Modificamos o Algoritmo GMC para que ele gerasse particionamentos cujo n´ umero de clusteres estivesse entre um limite inferior e um limite superior. No processo realizado pelo Algoritmo GMC modificado, ap´os a constru¸ca˜o da a´rvore geradora m´ınima T (ver Algoritmo 3 ), o particionamento ´e calculado somente se o n´ umero de componentes desconexos da floresta induzida F (T, τ ) for maior que 2 e menor que 40. Usamos o limite inferior 2 para que nunca fosse gerado o particionamento trivial e o limite superior 40 para que o algoritmo n˜ao gerasse particionamentos que extrapolam a quantidade de clusteres esperados. Na meta-heur´ıstica GRASP, o n´ umero m´aximo de itera¸co˜es executadas ´e 15. Al´em disso, inclu´ımos na busca local a capacidade de ser interrompida se, ap´os v´arias buscas nas solu¸co˜es vizinhas, n˜ao ocorrer uma melhora significativa na solu¸c˜ao. Isso foi feito na implementa¸ca˜o para diminuir o tempo de convergˆencia. Foram feitos v´arios testes para encontrar qual a porcentagem de melhora considerada significativa. Notamos que, se em 10 itera¸c˜oes da busca local, em cada itera¸c˜ao a solu¸ca˜o vizinha melhora menos de 0, 5% em rela¸ca˜o a solu¸c˜ao corrente, a convergˆencia para o o´timo local ser´a bastante lenta. 5.3

Os resultados

Os resultados s˜ao apresentados para cada fun¸c˜ao de avalia¸ca˜o. Para mostrar de forma resumida os resultados dos testes sobre as 171 instˆancias, agrupamos os resultados em rela¸ca˜o ao valor de pout . Para cada valor fixo de pout ´e mostrada a m´edia dos resultados para todos os valores de pin . Al´em disso, para o grupo pout foi constru´ıdo quatro gr´aficos, dois para apresentarem os valores das fun¸co˜es de avalia¸ca˜o e outros dois, um para cada fun¸ca˜o de avalia¸ca˜o, com os tempos de processamento dos algoritmos. Os itens que s˜ao apresentados nos gr´aficos s˜ao os seguintes: grasp (icc) – com solu¸c˜oes iniciais geradas pelos algoritmos ICC, MCL, k-centro, k-means, 13

Faleiros, Xavier

classifica¸ca˜o gulosa utilizando centroides e classifica¸ca˜o gulosa aleat´oria; grasp – Algoritmo GRASP sem a utiliza¸ca˜o do resultado do Algoritmo ICC para solu¸ca˜o inicial; mcl – Algoritmo MCL; icc – Algoritmo ICC; gmc – Algoritmo GMC; result – que corresponde aos particionamentos gerados por P (n, s, v) e utilizados nas constru¸co˜es das instˆancias de testes. As figuras 3 e 5 mostram os resultados obtidos pelos algoritmos considerando as fun¸co˜es de N Cut e Performance e os resultados agrupados pelo valor de probabilidade pout (o eixo x representa pout ). Os resultados obtidos pelos algoritmos grasp e grasp (icc) s˜ao praticamente idˆenticos. Isso mostra que, mesmo sem uma solu¸c˜ao inicial dada pelo ICC, a busca local ainda converge de forma eficiente. Note que o Algoritmo mcl n˜ao encontrou nas instˆancias densas (com pout > 0.2) particionamentos com mais de dois clusteres. Por outro lado, o Algoritmo gmc encontrou particionamento para todas as instˆancias, mas com o valor de Performance menor do que o do particionamento gerador result. Considerando a fun¸ca˜o de N Cut, o Algoritmo icc encontrou bons particionamentos apenas para instˆancias com grafos esparsos. Considerando a fun¸ca˜o de Performance, o Algoritmo icc encontrou “bons” particionamentos.

Figura 3. Compara¸ca ˜o dos particionamentos obtidos com o particionamento gerador (Avaliados por N Cut e agrupados por pout ).

As Figuras 4 e 6 apresentam o tempo de execu¸ca˜o dos algoritmos para as fun¸c˜oes de N Cut e P erf ormance. Podemos notar que os algoritmos mcl e gmc apresentam poucas varia¸co˜es no tempo de execu¸ca˜o. Temos que o tempo de execu¸c˜ao do gmc ´e significantemente menor do que qualquer outro algoritmo testado. O Algoritmo icc apresenta uma piora no tempo a medida que o grafo se torna mais denso, que ´e justificado pelos sucessivos incrementos no parˆametro α. Os algoritmos grasp e grasp (icc) possuem tempo bastante vari´avel, porque a busca local depende da qualidade da solu¸c˜ao inicial para chegar a um o´timo local. Por outro lado os algoritmos grasp e grasp (icc) s˜ao os u ´nicos algoritmos que apresentam resultados muito pr´oximos de result para 14

Faleiros, Xavier

Figura 4. Compara¸ca ˜o dos tempos de execu¸c˜ ao dos algoritmos (N Cut como fun¸ca ˜o objetivo e os dados agrupados por pout ).

ambas as fun¸c˜oes de avalia¸c˜ao consideradas neste trabalho.

Figura 5. Compara¸ca ˜o dos particionamentos obtidos com o particionamento gerador (Avaliados por Performance e agrupados por pout ).

Figura 6. Compara¸ca ˜o dos tempos de execu¸ca ˜o dos algoritmos (Performance como fun¸c˜ ao objetivo e os dados agrupados por pout ).

15

Faleiros, Xavier

6

Conclus˜ ao

Neste trabalho apresentamos algoritmos para o problema de particionamento em grafos e propomos uma nova heur´ıstica GRASP para o problema. Para as fun¸co˜es de avalia¸ca˜o de qualidade consideradas, a heur´ıstica GRASP apresentou uma significativa melhora na qualidade das solu¸c˜oes geradas. Outro ponto relevante obtido com os resultados foi a valida¸c˜ao da t´ecnica de imers˜ao do grafo no espa¸co. Gra¸cas a essa t´ecnica fomos capazes de aplicar algoritmos de clusteriza¸ca˜o, como o k-means e k-center, em dados representados por grafos. Al´em disso, a simplicidade dos algoritmos aqui descritos motiva a sua utiliza¸c˜ao em aplica¸co˜es pr´aticas.

Referˆ encias [1] R. K. Ahuja, J. B. Orlin, and R. E. Tarjan. Improved time bounds for the maximum flow problem. SIAM J. Comput., 18(5):939–954, 1989. [2] E. Anderson, Z. Bai, J. Dongarra, A. Greenbaum, A. McKenney, J. Du Croz, S. Hammerling, J. Demmel, C. Bischof, and D. Sorensen. Lapack: a portable linear algebra library for high-performance computers. In Supercomputing ’90: Proceedings of the 1990 ACM/IEEE conference on Supercomputing, pages 2–11, Los Alamitos, CA, USA, 1990. IEEE Computer Society Press. [3] U. Brandes, M. Gaertler, and D. Wagner. Engineering graph clustering: Models and experimental evaluation. ACM Journal on Experimental Algorithm, 12(1):1–26, June 2008. [4] T. Feo and M. Resende. A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters, 8(2):67 – 71, 1989. [5] L.R. Ford and D.R. Fulkerson. Mathematics, 8:399–404, 1956.

Maximal flow through a network.

Canadian Journal of

[6] M. Gaertler. Clustering with spectral methods. Diplomarbeit, fachbereich informatik und informationswissenschaft, Universitat Konstanz, March 2002. [7] T. Gonzalez. Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci., 38:293–306, 1985. [8] D.S. Hochbaum and D.B. Shmoys. A best possible heuristic for the k-center problem. Mathematics of Operations Research, 10:180–184, 1985. [9] R. Kannan, S. Vempala, and A. Vetta. On clusterings: Good, bad and spectral. J. ACM, 51(3):497–515, 2004. [10] T. Kanungo, D. Mount, N. Netanyahu, C. Piatko, R. Silverman, and A. Wu. A local search approximation algorithm for k-means clustering. In SCG ’02: Proceedings of the eighteenth annual symposium on Computational geometry, pages 10–18, New York, NY, USA, 2002. ACM. [11] Z. Michalewicz and D. B. Fogel. How to Solve It: Modern Heuristics. Springer, 2004. [12] M. Stoer and F. Wagner. A simple min cut algorithm. In ESA ’94: Proceedings of the Second Annual European Symposium on Algorithms, pages 141–147, London, UK, 1994. SpringerVerlag. [13] S. van Dongen. Graph Clustering by Flow Simulation. PhD thesis, University of Utrecht, May 2000.

16