Atenção: Todas as denúncias são sigilosas e sua identidade será preservada.
Os campos nome e e-mail são de preenchimento opcional
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Carmo, Renato Jose da Silva, 1965- | - |
Autor(es): dc.contributor | Vignatti, André Luís | - |
Autor(es): dc.contributor | Universidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informática | - |
Autor(es): dc.creator | Melo, Renato Silva de | - |
Data de aceite: dc.date.accessioned | 2019-08-22T00:38:18Z | - |
Data de disponibilização: dc.date.available | 2019-08-22T00:38:18Z | - |
Data de envio: dc.date.issued | 2017-06-02 | - |
Data de envio: dc.date.issued | 2017-06-02 | - |
Data de envio: dc.date.issued | 2016 | - |
Fonte completa do material: dc.identifier | http://hdl.handle.net/1884/44139 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/1884/44139 | - |
Descrição: dc.description | Orientador : Prof. Dr. Renato José da Silva Carmo | - |
Descrição: dc.description | Coorientador : Prof. Dr. André Luís Vignatti | - |
Descrição: dc.description | Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 20/05/2016 | - |
Descrição: dc.description | Inclui referências : f. 63-65 | - |
Descrição: dc.description | Resumo: O problema de maximização de influência em redes sociais, procura pelos vértices que permitam espalhar uma informação para o maior número possível de membros da rede.Um algoritmo guloso proposto por Kempe et al. [19], que escolhe iterativamente os vértices de maior influência, encontra um conjunto resposta cujo alcance da influência é pelo menos1 ? 1/e do ótimo. Mas esta abordagem possui alguns agravantes que comprometem o tempo de execução do algoritmo. Nesta dissertação propomos uma melhoria para o algoritmo guloso de Kempe et al. [19] com foco no tempo de execução deste sobre grafos de lei de potência. A melhoria consiste em fazer uma seleção prévia dos vértices mais promissores. Verificamos por meio de análise experimental que esta pré-seleção reduz expressivamente o tempo de execução, além de manter a qualidade da solução compatível com a do algoritmo guloso de Kempe et al. [19]. A otimização por pré-seleção utiliza propriedades presentes em grafos de lei de potência, explorando a relação de influência social com a distribuição de graus. Esta abordagem reduz em até 58%o tempo de execução do algoritmo Celf [22], que é uma das otimizações mais conhecidas do procedimento deKempe et al. [19]. | - |
Descrição: dc.description | Abstract: The influence maximization problem in social networks, asks for the nodes that allow tospread a information for the highest number of members. A greedy algorithm proposed byKempe et al. [19], that choose iteratively the members of greatest influence, find a solutionset whose the reach of influence is at least 1?1/e of the optimum. But some aggravatinghave affecting the runtime of this approach. In this work we propose improvements forthe algorithm of Kempe et al. [19], with focus on the runtime in power law graphs. Theimprovement consists in make a previous selection of most promising nodes. We haveverified by experimental analysis that this pre selection reduces significantly the runtime,in addition maintaining a quality compatible with the greedy algorithm of Kempe etal. [19]. The optimization by pre selection uses properties present in power law graphs,by exploring the relationship between social influence and the degree distribution. Besides,this approach reduces the runtime of Celf [22] algorithm by up to 58%, which is one ofthe most known optimizations of the algorithm of Kempe et al. [19]. | - |
Formato: dc.format | 95 f. : il. | - |
Formato: dc.format | application/pdf | - |
Formato: dc.format | application/pdf | - |
Relação: dc.relation | Disponível em formato digital | - |
Palavras-chave: dc.subject | Ciência da computação | - |
Palavras-chave: dc.subject | Teoria dos grafos | - |
Palavras-chave: dc.subject | Algoritmos | - |
Palavras-chave: dc.subject | Teses | - |
Título: dc.title | Maximização de influência em grafos lei de potência | - |
Tipo de arquivo: dc.type | livro digital | - |
Aparece nas coleções: | Repositório Institucional - Rede Paraná Acervo |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: