• 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
 
 
Thèse de Doctorat
DOI
https://doi.org/10.11606/T.55.2020.tde-06012020-174051
Document
Auteur
Nom complet
Alan Demetrius Baria Valejo
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Carlos, 2019
Directeur
Jury
Lopes, Alneu de Andrade (Président)
Cesar Junior, Roberto Marcondes
Macau, Elbert Einstein Nehrer
Travieso, Gonzalo
Titre en anglais
Multilevel method in bipartite networks
Mots-clés en anglais
Bipartite networks
Complex networks
Large-scale networks
Multilevel method
Network coarsening
Resumé en anglais
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.
Titre en portugais
Método multinível em redes bipartidas
Mots-clés en portugais
Contração de redes
Método multinível
Redes bipartidas
Redes Complexas
Redes de grande escala
Resumé en portugais
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.
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Date de Publication
2020-01-06
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
CeTI-SC/STI
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2020. Tous droits réservés.