Multilevel Coarsening for Interactive Visualization of Large Bipartite Networks

Autor(es)

Valejo, Alan Demetrius Baria ; Fabbri, Renato ; Lopes, Alneu de Andrade ; Zhao, Liang ; de Oliveira, Maria Cristina Ferreira

• Tipo de documento: Artigo Científico
• Fonte: FRONTIERS IN RESEARCH METRICS AND ANALYTICS; v. 7, p. 18-pg., 2022-06-16.

Resumo

Bipartite networks are pervasive in modeling real-world phenomena and play a fundamental role in graph theory. Interactive exploratory visualization of such networks is an important problem, and particularly challenging when handling large networks. In this paper we present results from an investigation on using a general multilevel method for this purpose. Multilevel methods on networks have been introduced as a general approach to increase scalability of community detection and other complex optimization algorithms. They employ graph coarsening algorithms to create a hierarchy of increasingly coarser (reduced) approximations of an original network. Multilevel coarsening has been applied, e.g., to the problem of drawing simple ("unipartite") networks. We build on previous work that extended multilevel coarsening to bipartite graphs to propose a visualization interface that uses multilevel coarsening to compute a multi-resolution hierarchical representation of an input bipartite network. From this hierarchy, interactive node-link drawings are displayed following a genuine route of the "overview first, zoom and filter, details on demand" visual information seeking mantra. Analysts may depart from the coarsest representation and select nodes or sub-graphs to be expanded and shown at greater detail. Besides intuitive navigation of large-scale networks, this solution affords great flexibility, as users are free to select different coarsening strategies in different scenarios. We illustrate its potential with case studies involving real networks on distinct domains. The experimental analysis shows our strategy is effective to reveal topological structures, such as communities and holes, that may remain hidden in a conventional node-link layout. It is also useful to highlight connectivity patterns across the bipartite layers, as illustrated in an example that emphasizes the correlation between diseases and genes in genetic disorders, and in a study of a scientific collaboration network of authors and papers. (AU)

• Processo FAPESP: 19/07665-4 - Centro de Inteligência Artificial
• Beneficiário: Fabio Gagliardi Cozman
• Modalidade de apoio: Auxílio à Pesquisa - Programa eScience e Data Science - Centros de Pesquisa em Engenharia
• Processo FAPESP: 19/14429-5 - Análise visual de redes cerebrais heterogêneas usando métodos multilíveis
• Beneficiário: Alan Demétrius Baria Valejo
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 15/50122-0 - Fenômenos dinâmicos em redes complexas: fundamentos e aplicações
• Beneficiário: Elbert Einstein Nehrer Macau
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 17/05838-3 - Visual analytics: aplicações e uma investigação conceitual
• Beneficiário: Maria Cristina Ferreira de Oliveira
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 18/22214-6 - Rumo à convergência de tecnologias: de sensores e biossensores à visualização de informação e aprendizado de máquina para análise de dados em diagnóstico clínico
• Beneficiário: Osvaldo Novais de Oliveira Junior
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 13/07375-0 - CeMEAI - Centro de Ciências Matemáticas Aplicadas à Indústria
• Beneficiário: Francisco Louzada Neto
• Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs