• 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
 
 
Tesis Doctoral
DOI
https://doi.org/10.11606/T.55.2020.tde-06012020-174051
Documento
Autor
Nombre completo
Alan Demetrius Baria Valejo
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Carlos, 2019
Director
Tribunal
Lopes, Alneu de Andrade (Presidente)
Cesar Junior, Roberto Marcondes
Macau, Elbert Einstein Nehrer
Travieso, Gonzalo
Título en inglés
Multilevel method in bipartite networks
Palabras clave en inglés
Bipartite networks
Complex networks
Large-scale networks
Multilevel method
Network coarsening
Resumen en inglés
Bipartite networks comprise a particular class of network models in which the vertex set is split into two disjoint and independent subsets, with edges connecting only vertices placed in different subsets. They provide a powerful representation of the relationships in many realworld systems and have been widely employed to model data-intensive problems. In a related scenario, multilevel methods have been previously applied to handle computationally expensive optimization problems defined in networks. The strategy aims at reducing the cost of executing an expensive algorithm or task by exploiting a hierarchy of coarsened versions of the original network. There is a growing interest in multilevel methods in networked systems, motivated mostly by their capability of handling large-scale networks and applicability to a variety of problems, most notably community detection and network drawing. Despite their potential, existing approaches are not directly applicable to bipartite networks and, to the best of our knowledge, the multilevel strategy had not been considered in this context so far, opening a vast space for scientific exploration. This gap motivated this research project, which introduces a study on multilevel methods applicable to bipartite networks. In order to overcome the aforementioned limitations, this thesis presents two novel multilevel frameworks for handling bipartite structures, named OPM and MOb. OPM analyzes the bipartite network based on its one-mode projections, allowing the reuse of classical and already established solutions from the literature. MOb (and its Mdr, CSV and CSL variations) operate directly on the bipartite representation to execute the multilevel method, providing a cost-effective implementation. Empirical results obtained on a set of synthetic and real-world networks on diverse applications indicate a considerable speed up with no significant loss in the quality of the solutions obtained in the coarsened networks as compared to those obtained in the original network (i.e., conventional approaches). The potential applicability and reliability of the proposed methods have been illustrated in multiple scenarios, namely optimization, community detection, dimensionality reduction and visualization. Furthermore, the results provide empirical evidence that the proposed methods can foster novel applications of the multilevel method in bipartite networks, e.g. link prediction and trajectory mining and, therefore, that this thesis brings a relevant contribution to the field.
Título en portugués
Método multinível em redes bipartidas
Palabras clave en portugués
Contração de redes
Método multinível
Redes bipartidas
Redes Complexas
Redes de grande escala
Resumen en portugués
As redes bipartidas compreendem uma classe particular das redes complexas, na qual vértices são divididos em dois subconjuntos separados e independentes e as arestas conectam apenas vértices de conjuntos diferentes. Tais redes fornecem uma poderosa representação para a modelagem de muitos sistemas complexos do mundo real e têm sido amplamente empregadas em problemas caracterizados pelo alto custo computacional e uso intensivo de dados. Nessa linha, os chamados métodos multinível têm sido empregados para tratar problemas computacionalmente custosos e descrevem uma estratégia escalável que explora (e cria) uma hierarquia de versões reduzidas, ou simplificadas, da rede original. Nos últimos anos, houve um crescente interesse em métodos multinível motivado, principalmente, por sua capacidade de manipular redes de larga escala, bem como sua aplicabilidade em diversos problemas, como detecção de comunidades e visualização. Apesar de seu potencial, as abordagens atuais não são diretamente aplicáveis às redes bipartites e, até onde sabemos, a estratégia multinível não havia sido considerada neste contexto anteriormente, abrindo um vasto espaço para exploração científica. Essa lacuna motivou este projeto de pesquisa, o qual introduz um estudo sobre métodos multinível aplicáveis às redes bipartidas. Para superar as limitações mencionadas, esta tese apresenta duas novas estratégias direcionadas às redes bipartidas, denominadas OPM e MOb. O OPM analisa a rede bipartida em suas projeções unipartidas e permite a reutilização de algoritmos multinível clássicos e já estabelecidos na literatura. O MOb (e suas variações Mdr, CSV e CSL) considera diretamente a estrutura bipartida para executar o método multinível e fornecer uma implementação eficiente e eficaz. Os resultados empíricos obtidos em conjuntos de redes reais e sintéticas, em uma variedade de aplicações, demonstram uma redução considerável no tempo de processamento sem perda significativa na qualidade da solução obtida na rede reduzida, quando comparada aos resultados obtidos na rede original. A potencial aplicabilidade e confiabilidade dos métodos propostos foram ilustradas em múltiplos cenários, a saber: otimização, detecção de comunidades, redução de dimensionalidade e visualização. Além disso, os resultados fornecem evidências empíricas de que os métodos propostos podem fomentar novas aplicações do método multinível em redes bipartidas, por exemplo, na predição de arestas e mineração de trajetórias, e evidenciam que este estudo gerou contribuições relevantes para a área.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2020-01-06
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2020. Todos los derechos reservados.