ࡱ> +-*bjbjUU >??   0        qssssssLs     s        q  q      ]0    T        ss                  :Resumo A eficincia de processos de difuso de informao em redes complexas depende muito no apenas da estrutura da rede mas tambm dos ns escolhidos para iniciar a difuso, os chamados seeds. Alm disso, em diversos cenrios reais, ns distintos impem custos distintos para iniciar uma difuso, como o caso do marketing viral, onde o custo dos ns correlaciona-se com a estrutura local dos mesmos. O problema conhecido como budgeted influence maximization (BIM) consiste em determinar um conjunto de seeds cuja difuso maximiza o total de ns influenciados, dado que o custo total dos seeds limita-se a um oramento (budget). Este trabalho investiga estrategias eficientes para BIM sob o modelo determinstico de difuso baseado em limiares fixos. Em particular, introduz-se o conceito de extended surrounding sets (conjuntos evolventes estendidos): seeds relativamente baratos que so vizinhos de ns caros porm estruturalmente privilegiados, os quais sero influenciados a custos mais baixos e assim contribuiro para a difuso. De modo a medir o desempenho de maneira mais eficaz, introduzido o conceito de poder de difuso, o qual captura a frao de ns influenciados ao fim do espalhamento descontando-se a frao de seeds. mostrado como essa abordagem pode mudar completamente o entendimento acerca da eficcia de uma dada estratgia. Experimentos numricos com diversas redes complexas de larga escala (oriundas de bases de dados reais) indicam que o mtodo aqui apresentado superior a estratgias que se baseiam na razo centralidade/custo dos ns para escolher os seeds. Uma ideia chave deste trabalho que geralmente obtm-se maior poder de difuso quando considera-se a vizinhana de dois saltos de um vrtice ao cerc-lo, ao invs de considerar-se apenas os seus vizinhos imediatos. Abstract The efficiency of information diffusion processes on complex networks highly depends on the network structure and the nodes chosen to start the diffusion, known as seeds. Moreover, in various realistic scenarios, different nodes have different costs to start a diffusion, such as in viral marketing, where node costs are correlated with their local structure. The budgeted influence maximization (BIM) problem consists of determining a seed set whose diffusion maximizes the total number of nodes influenced, provided that the total cost of the seeds is within a given budget. We investigate efficient seeding strategies for BIM under the deterministic fixed threshold diffusion model. In particular, we introduce the concept of extended surrounding sets: relatively cheap seeds neighboring expensive, yet structurally privileged nodes that will ultimately be influenced at lower costs and thus contribute to the diffusion. In order to measure performance more effectively, it is introduced the concept of diffusion power, which captures the fraction of nodes influenced at the end of the spreading discounting the fraction of seeds. We show how this approach may completely change the understanding around a strategy's effectiveness. Numerical experiments with several large-scale complex networks (from real data social networks) indicate our method outperforms strategies that seed nodes based on their centrality/cost ratios. A key insight from our evaluation is that larger diffusion power is generally attained with the surrounding sets that consider the two hop neighborhood of central nodes, as opposed to their immediate neighbors. > G  Q V q w  6 Z _ a b r s 8=""ǽǭǭǽǭǭǭǭǽǽǭǭǽyh6666666666666666666666666666666666666666666666666hH6666666666666666666666666666666666666666666666666666666666666666662 0@P`p2( 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p8XV~ OJPJQJ_HmHnHsHtHR`R Normal d CJPJ^J_HaJmHsHtH DA D 0Default Paragraph FontRiR 0 Table Normal4 l4a (k ( 0No List PK![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]   VM USummaryInformation(DocumentSummaryInformation8"CompObjy  F'Microsoft Office Word 97-2003 Document MSWordDocWord.Document.89q  F#Documento do Microsoft Office Word MSWordDocWord.Document.89q