ࡱ> ,.+bjbjUU =??   h      lnnnnnn1n$$$n  $$$$  l$$l$$$ !>:k$$X0$$$$4$$$$$$$$nn$$$$$$$$$$$$$$$$$ :Solues eficientes para o Problema de Correlao de Clusters Um dos desafios enfrentados por pesquisadores de redes sociais consiste na avaliao do equilbrio em redes sociais de sinais, onde interaes positivas (amizade) e negativas (antagonismo) esto presentes. O nvel de equilbrio de um grupo social pode ser utilizado como ferramenta de estudo pelos pesquisadores de redes sociais para saber de que forma (e se) determinado grupo evolui para um possvel estado de equilbrio. Neste sentido, uma rede social pode ser representada atravs de um grafo de sinais e a soluo de problemas de clustering definidos sobre grafos de sinais pode ser utilizada como um critrio para medio do nvel de equilbrio em redes sociais. Tal medida pode ser obtida por meio da soluo tima para o Problema de Correlao de Clusters (Correlation Clustering ou CC), assim como uma variao do mesmo, conhecida como Relaxed Correlation Clustering (RCC) problem. Contudo, resolver tais problemas no se traduz em tarefa fcil, especialmente quando necessrio analisar grandes instncias de rede. Este trabalho visa contribuir para a soluo eficiente de ambos os problemas por meio do desenvolvimento de verses sequenciais e paralelas das metaheursticas GRASP e ILS. Ao aplicarmos estes algoritmos, foi possvel realizar, de forma eficiente, a medio do equilbrio estrutural em grandes redes sociais do mundo real. PALAVRAS-CHAVE: Metaheursticas, Grafo de sinais, Correlao de Clusters, Rede Social, Equilbrio Estrutural, GRASP, ILS, MPI, CUDA. >W a = S h)hw16]hw1hFhw15\>?@  $a$$a$gdF ;0P:p. A!"#$% Dpn  666666666666666666666666666666666666666666 6666666666 666666666666 6666666666666666666666666666666666666666666666666666666666666666662 0@P`p2( 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p8XV~$OJPJQJ^J_HmHnHsHtHT`T Normald%B*CJ_HaJmHnHphsHtHHH 0 Heading 1$$x@&CJ(aJ(HH 0 Heading 2$$hx@&CJ aJ RR 0 Heading 3$$@P@&B*CJaJphCCCRR 0 Heading 4$$P@&B*CJaJphfffJJ 0 Heading 5$$P@& B*phfffPP 0 Heading 6$$P@&6B*]phfffDA D 0Default Paragraph FontRiR 0 Table Normal4 l4a (k ( 0No List h/h ^mHeading 1 Char35B*CJ KH OJPJQJ\^JaJ nHphtHj/j ^mHeading 2 Char556B*CJOJPJQJ\]^JaJnHphtHd/d ^mHeading 3 Char/5B*CJOJPJQJ\^JaJnHphtHd/!d ^mHeading 4 Char/5B*CJOJPJQJ\^JaJnHphtHj/1j ^mHeading 5 Char556B*CJOJPJQJ\]^JaJnHphtH\/A\ ^mHeading 6 Char'5B*OJPJQJ\^JnHphtH~/S~ 0 Table Normal1:V4k d%B*CJ_HaJmHnHphsHtH8>8 0Title $$<CJ4aJ4`/q` ^m Title Char35B*CJ KHOJPJQJ\^JaJ nHphtHHJH 0Subtitle $$@B*CJaJphfff\/\ ^m Subtitle Char)B*CJOJPJQJ^JaJnHphtHPK![Content_Types].xmlj0Eжr(΢Iw},-j4 wP-t#bΙ{UTU^hd}㨫)*1P' ^W0)T9<l#$yi};~@(Hu* Dנz/0ǰ $ X3aZ,D0j~3߶b~i>3\`?/[G\!-Rk.sԻ..a濭?PK!֧6 _rels/.relsj0 }Q%v/C/}(h"O = C?hv=Ʌ%[xp{۵_Pѣ<1H0ORBdJE4b$q_6LR7`0̞O,En7Lib/SeеPK!kytheme/theme/themeManager.xml M @}w7c(EbˮCAǠҟ7՛K Y, e.|,H,lxɴIsQ}#Ր ֵ+!,^$j=GW)E+& 8PK!Ptheme/theme/theme1.xmlYOo6w toc'vuر-MniP@I}úama[إ4:lЯGRX^6؊>$ !)O^rC$y@/yH*񄴽)޵߻UDb`}"qۋJחX^)I`nEp)liV[]1M<OP6r=zgbIguSebORD۫qu gZo~ٺlAplxpT0+[}`jzAV2Fi@qv֬5\|ʜ̭NleXdsjcs7f W+Ն7`g ȘJj|h(KD- dXiJ؇(x$( :;˹! I_TS 1?E??ZBΪmU/?~xY'y5g&΋/ɋ>GMGeD3Vq%'#q$8K)fw9:ĵ x}rxwr:\TZaG*y8IjbRc|XŻǿI u3KGnD1NIBs RuK>V.EL+M2#'fi ~V vl{u8zH *:(W☕ ~JTe\O*tHGHY}KNP*ݾ˦TѼ9/#A7qZ$*c?qUnwN%Oi4 =3ڗP 1Pm \\9Mؓ2aD];Yt\[x]}Wr|]g- eW )6-rCSj id DЇAΜIqbJ#x꺃 6k#ASh&ʌt(Q%p%m&]caSl=X\P1Mh9MVdDAaVB[݈fJíP|8 քAV^f Hn- "d>znNJ ة>b&2vKyϼD:,AGm\nziÙ.uχYC6OMf3or$5NHT[XF64T,ќM0E)`#5XY`פ;%1U٥m;R>QD DcpU'&LE/pm%]8firS4d 7y\`JnίI R3U~7+׸#m qBiDi*L69mY&iHE=(K&N!V.KeLDĕ{D vEꦚdeNƟe(MN9ߜR6&3(a/DUz<{ˊYȳV)9Z[4^n5!J?Q3eBoCM m<.vpIYfZY_p[=al-Y}Nc͙ŋ4vfavl'SA8|*u{-ߟ0%M07%<ҍPK! ѐ'theme/theme/_rels/themeManager.xml.relsM 0wooӺ&݈Э5 6?$Q ,.aic21h:qm@RN;d`o7gK(M&$R(.1r'JЊT8V"AȻHu}|$b{P8g/]QAsم(#L[PK-![Content_Types].xmlPK-!֧6 +_rels/.relsPK-!kytheme/theme/themeManager.xmlPK-!Ptheme/theme/theme1.xmlPK-! ѐ' theme/theme/_rels/themeManager.xml.relsPK]  8@0(  P S  ?"_GoBackw141=UF)#|@@@UnknownG*Ax Times New Roman5Symbol3. *Cx Arial7@Cambria7.@CalibriACambria Math"כBכB!02$P#|!xx=Solues eficientes para o Problema de Correlao de ClustersHelioHelioOh+'0, <H l x @Solues eficientes para o Problema de Correlao de ClustersHelioNormal_WordconvHelio2Microsoft Office Outlook@F#@2T.:k@2T.:k՜.+,0, hp   Petrobras >Solues eficientes para o Problema de Correlao de Clusters Title  !"$%&'()*-Root Entry FZ->:k/1Table WordDocument=SummaryInformation(DocumentSummaryInformation8#CompObjy  F'Microsoft Office Word 97-2003 Document MSWordDocWord.Document.89q  F#Documento do Microsoft Office Word MSWordDocWord.Document.89q