• 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
 
 
Doctoral Thesis
DOI
https://doi.org/10.11606/T.55.2020.tde-06012020-174051
Document
Author
Full name
Alan Demetrius Baria Valejo
Institute/School/College
Knowledge Area
Date of Defense
Published
São Carlos, 2019
Supervisor
Committee
Lopes, Alneu de Andrade (President)
Cesar Junior, Roberto Marcondes
Macau, Elbert Einstein Nehrer
Travieso, Gonzalo
Title in English
Multilevel method in bipartite networks
Keywords in English
Bipartite networks
Complex networks
Large-scale networks
Multilevel method
Network coarsening
Abstract in English
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.
Title in Portuguese
Método multinível em redes bipartidas
Keywords in Portuguese
Contração de redes
Método multinível
Redes bipartidas
Redes Complexas
Redes de grande escala
Abstract in Portuguese
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.
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
2020-01-06
 
WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2020. All rights reserved.