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.

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.