Multi-Level Graph Representation for Big Data Arising in Science Mapping

Motivation

For centuries, cartographic maps have guided human exploration. While being rather imperfect initially, they helped explorers find promised lands and return home safely. Recent advances in data, algorithms, and computing infrastructures make it possible to map humankind's collective scholarly knowledge and technology expertise by using topic maps on which “continents” represent major areas of science (e.g., mathematics, physics, or medicine) and zooming reveals successively more detailed subareas. Basemaps of science and technology are generated by analyzing citations links between millions of publications and/or patents. “Data overlays” (e.g., showing all publications by one scholar, institution, or country or the career trajectory of a scholar as a pathway) are generated by science-locating relevant publication records based on topical similarity. Despite the demonstrated utility of such maps, current approaches do not scale to the hundreds of millions of data records now available. The main challenge is designing efficient and effective methods to visualize and interact with more than 100 million scholarly publications at multiple levels of resolution.

This Dagstuhl Seminar will bring together researchers in cartography, information visualization, science of science, and graph drawing to discuss novel graph mining and layout algorithms and their application to the development of science mapping standards and services. We will also organize an exhibition of art contributed by scientists and science maps contributed by artists, and use this to stimulate discussion.

One of our main goals is to create a special journal issue on the topics related to the development of the next generation science map, SciMap2020. Among others, we will aim to answer:

1. What data is most robust to design SciMap2020?
2. What information should the nodes and link encode in SciMap2020?
3. What user experience metaphors, functionality, and interactive user interfaces are best?
4. What user studies should be run to compare options and study knowledge gains?

On the algorithmic front, specific research problems include:

1. Construct a hierarchy of graphs, so that each represents the underlying large graph well
2. Study the complexity of underlying problem: computing multi-level graph sketches
3. Design efficient algorithms for computing multi-level graph sketches and clustering
4. Design graph layout algorithms, driven by multi-level sketches and clustering

We look forward to a stimulating week that brings together world-leading experts to tackle these research challenges.