Multilevel Coarsening for Interactive Visualization of Large Bipartite Networks

Author(s)

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

• Document type: Journal article
• Source: FRONTIERS IN RESEARCH METRICS AND ANALYTICS; v. 7, p. 18-pg., 2022-06-16.

Abstract

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)

• FAPESP's process: 19/07665-4 - Center for Artificial Intelligence
• Grantee: Fabio Gagliardi Cozman
• Support Opportunities: Research Grants - Research Program in eScience and Data Science - Research Centers in Engineering Program
• FAPESP's process: 19/14429-5 - Visual analytics of heterogeneous brain networks using multilevel methods
• Grantee: Alan Demétrius Baria Valejo
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• FAPESP's process: 15/50122-0 - Dynamic phenomena in complex networks: basics and applications
• Grantee: Elbert Einstein Nehrer Macau
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 17/05838-3 - Visual analytics: applications and a conceptual investigation
• Grantee: Maria Cristina Ferreira de Oliveira
• Support Opportunities: Regular Research Grants
• FAPESP's process: 18/22214-6 - Towards a convergence of technologies: from sensing and biosensing to information visualization and machine learning for data analysis in clinical diagnosis
• Grantee: Osvaldo Novais de Oliveira Junior
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 13/07375-0 - CeMEAI - Center for Mathematical Sciences Applied to Industry
• Grantee: Francisco Louzada Neto
• Support Opportunities: Research Grants - Research, Innovation and Dissemination Centers - RIDC