• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
10.11606/D.55.2013.tde-05062013-104308
Documento
Autor
Nome completo
Jorge Carlos Valverde Rebaza
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Carlos, 2013
Orientador
Banca examinadora
Lopes, Alneu de Andrade (Presidente)
Hruschka Júnior, Estevam Rafael
Liang, Zhao
Título em português
Predição de links em redes complexas utilizando informações de estruturas de comunidades
Palavras-chave em português
Detecção de comunidades
Predição de links
Redes complexas
Resumo em português
Diferentes sistemas do mundo real podem ser representados por redes. As redes são estruturas nas quais seus vértices (nós) representam entidades e links representam relações entre essas entidades. Além disso, as redes caracterizam-se por ser estruturas dinâmicas, o que implica na rápida aparição e desaparição de entidades e seus relacionamentos. Nesse cenário, um dos problemas importantes a serem enfrentados no contexto das redes, é da predição de links, isto é, prever a ocorrência futura de um link ainda não existente entre dois vértices com base nas informações já existentes. A importância da predição de links deve-se ao fato de ter aplicações na recuperação de informação, identificação de interações espúrias e, ainda, na avaliação de mecanismos de evolução das redes. Para enfrentar o problema da predição de links, a maioria dos métodos utiliza informações da vizinhança topológica das redes para atribuir um valor que represente a probabilidade de conexão futura entre um par de vértices analisados. No entanto, recentemente têm aparecido métodos híbridos, caracterizados por usar outras informações além da vizinhança topológica, sendo as informações das comunidades as normalmente usadas, isso, devido ao fato que, ao serem grupos de vértices densamente ligados entre si e esparsamente ligados com vértices de outros grupos, fornecem informações que podem ser úteis para determinar o comportamento futuro das redes. Assim, neste trabalho são apresentadas duas propostas na linha dos métodos baseados nas informações das comunidades para predição de links. A primeira proposta consiste em um novo índice de similaridade que usa as informações dos vértices pertencentes a mesma comunidade na vizinhança de um par de vértices analisados, bem como as informações dos vértices pertencentes a diferentes comunidades nessa mesma vizinhança. A segunda proposta consiste de um conjunto de índices obtidos a partir da reformulação de algumas propostas já existentes, porém, inserindo neles informações dos vértices pertencentes unicamente à mesma comunidade na vizinhança topológica de um par de vértices analisados. Experimentos realizados em dez redes complexas de diferentes domínios demonstraram que, em geral, os índices propostos obtiveram desempenho superior às abordagens usuais
Título em inglês
Link prediction in complex networks using community structure information
Palavras-chave em inglês
Community detection
Complex netwoprks
Link prediction
Resumo em inglês
Different real-world systems can be represented as networks. Networks are structures in which vertices (nodes) represent entities and links represent relationships between these entities. Moreover, networks are dynamic structures, which implies rapid appearance and disappearance of entities and their relationships. In this scenario, the link prediction problem attempts to predict the future existence of a link between a pair of vertices considering existing information. The link prediction importance is due to the fact of having different applications in areas such as information retrieval, identification of spurious interactions, as well as for understanding mechanisms of network evolution. To address the link prediction problem, many proposals use topological information to assign a value that represents the likelihood of a future connection between a pair of vertices. However, hybrid methods have appeared recently. These methods use additional information such as community information. Communities are groups of vertices densely connected among them and sparsely connected to vertices from other groups, providing useful information to determinate the future behavior of networks. So, this research presents two proposals for link prediction based on communities information. The first proposal consists of a new similarity index that uses information about the communities that the vertices in the neighborhood of a analyzed pair of vertices belong. The second proposal is a set of indices obtained from the reformulation of various existing proposals, however, using only the information from vertices belonging to the same community in the neighborhood of a pair of vertices analyzed. Experiments conducted in ten complex networks of different fields show the proposals outperform traditional approaches
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
dissertacao.pdf (1.90 Mbytes)
Data de Publicação
2013-06-05
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
Centro de Informática de São Carlos
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2020. Todos os direitos reservados.