ISSN 2186-7437

NII Shonan Meeting Report

No. 2016-11

Dynamic Networks Visual Analytics:
Approaches to facilitate visual analysis
of complex and dynamic network data
Takayuki Itoh
Karsten Klein
Giuseppe Liotta
August 1–4, 2016

National Institute of Informatics
2-1-2 Hitotsubashi, Chiyoda-Ku, Tokyo, JapanDynamic Networks Visual Analytics:
Approaches to facilitate visual analysis ofcomplex and dynamic network data
Organizers:
Takayuki Itoh (Ochanomizu University, Tokyo, Japan)
Karsten Klein, (University of Konstanz, Germany)
Beppe Liotta, (University of Perugia, Italy)
August 1–4, 2016

1

Introduction

There is an abundance of complex dynamic data across many domains. Often such data
has a natural interpretation as a network, e.g. for applications in the life sciences, thesocial sciences, telecommunication, finance, energy, and information security. Analysis of these dynamic networks is key to the understanding of complex processes bothin fundamental research and for decision making.
Many of these cases require a human in the loop to make decisions, e.g. in emergency situations, or to allow experts to guide exploration and insight generation forcomplex processes. Lack of sufficient a priori knowledge, in combination with thecomplexity of the dynamics in multi-variate data, hamper the use of purely rule-based
systems for analysis and decision making. Thus, a visual analytics type approach isbest suited for such cases. Efficient tools and methods for the visual analysis of network changes will facilitate the human understanding of dynamic networks, but thecomplexity and the volume of the network dynamics pose a challenge to research.
Several research directions are concerned with the development of methods to support the analysis of such data, including machine learning, information and data visualisation, data analytics and human computer interaction.
Automated analysis methods help to guide the human expert, to filter and selectrelevant parts of the data space, and to detect patterns and trends. Interactive visualizations of both input data and analysis results need to support the user’s perception andreasoning, and can lead to a better understanding and deeper insight. For that to happen, the visualisation and interaction concepts need to allow a faithful representation of
the data and provide intuitive and efficient orientation and navigation in the data space.
While the visual analysis of big and complex static networks already poses a challenge for current research, the temporal aspect of dynamic networks adds a further
difficulty that requires dedicated approaches for visualization, algorithmic treatment,
and interaction. An important aspect that needs to be considered in the development ofefficient concepts for practical applications is that the representations and interactions
need to be tailored towards the actual use-case. In a similar way, network analysis
methods need to be adapted to online streaming scenarios and the potentially huge data1

volumes. Knowledge discovery methods need to cope with large amounts of streaming
data, but also with potential uncertainty and incompleteness of processed data.
The development of efficient methods for dynamic network visual analytics thus
requires a multi-disciplinary approach that spans not only the classical disciplines related to data visualisation and interaction, visual analytics, information visualisation,and graph drawing, but also includes data sciences and network analysis. While researchers in all these fields tackle the problem of dynamic network analysis, we feelthat a concerted effort will be best suited to advance the current state and will leadto new fruitful collaborations. The seminar has the aim to bring together experts inthe listed fields and people from application areas to first have an exchange across thefields on the state of the art and current challenges, and then to state and tackle the mostpressing research questions.
The main aims of the seminar were to• bring together researchers from several communities that can contribute to dynamic network visual analytics research,• identify core challenges based on both ongoing research and real-world examples, e.g. regarding computational efficiency, visual complexity, and interaction,• examine where existing approaches can be extended and where completely new
methods need to be developed to cope with the recent huge rise in complexity,
velocity and volume of dynamic network data,• investigate the embedding of dynamic network data and visualizations into theinterfaces and visualizations commonly used in practice today,• study efficient scalable approaches.

2

Program and Schedule

The seminar’s schedule reflected the main goals of the meeting, with introductory talks
to give an overview on the research fields and application areas covered by the participants. However, most time was devoted to discussions in small groups focusing toinvestigate the research questions and challenges of dynamic network analytics. The
participants defined topics for working groups in an open discussion, and afterwards
selected working groups based on their personal preference. Thus, the main part ofthe seminar time was used for the work in those groups, with a few general discussion
sessions in between working group sessions, see Table 1.
The following overview talks were given:• Daniel Archambault talked about animation, small multiples, and the mental map
in dynamic graphs.
• Fabian Beck and Michael Burch presented the state of the art in visualizing dynamic graphs based on their STAR report on the topic.
• Ken Wakita presented an approach on how to fill the gap between theory and
code.

2

Sunday
Day 1:

10:00:
10:30:
12:00:
13:30:
14:30:
15:00:
15:30:
18:00:

Check-in and welcome reception
Seminar start, welcome, introductory presentations, and working
groupsOpening, seminar overview by the organizers, and individual selfintroductions by participants
Break
Invited Talks (Fabian Beck, Michael Burch, Ken Wakita)
Lunch
Invited Talk (Daniel Archambault)
Plenary discussion - formulation of challenges and research questions
Break
Plenary discussion
DinnerDay2:
09:00:
09:15:
10:30:
11:00:
12:00:
14:00:
15:30:
16:00:
18:00:

Working groups, discussions and presentations
Lightning talks
Breakout groups - tackling selected topics
Break
Working groups
Lunch
Working groups
BreakWorking groups and group reports
DinnerDay3:
09:00:
10:30:
11:00:
12:00:
13:30:
19:00:

Working groups, discussions, and excursion
Working groups
BreakWorking groups
Lunch
Excursion
BanquetDay4:
09:00:
11:00:
12:00:

Working groups and wrap-up
Working groups
Final group feedback and wrap up
Lunch – end of the seminar

09:00:

Table 1: Seminar schedule

3

Working Group Reports

3.1

Visual Analytics

Participants: Fabian Beck, Maxime Cordeil, Leszek Gasieniec,
˛
Carsten Görg,
Masahiko Itoh, Kwan-Liu Ma, Tobias Schreck, and Ken Wakita
Summary. Visual analytics integrates visualization approaches with algorithmic solutions and embeds them into highly interactive tools. This facilitates computer-supported,3

but still interactive analysis methods and makes data analysis more scalable. Whilevarious visualization techniques have been proposed for dynamic graph visualization
already (Beck et al. 2016 [3]), very few visual analytics systems incorporate thesetechniques. In this working group, we analyzed existing approaches and developed avisual analytics process that could form the basis for a new generation of approaches
to visually analyze dynamic graphs. We discussed a set of three realistic application
scenarios and identified main research challenges for instantiating the process in thesescenarios.
Previous Work. Traditionally, dynamic graph visualization techniques focus on graphlayout and the visual encoding of the graph and time information. Only recently, someapproaches have started to study interaction techniques and semi-automatic analysis
methods in the context of dynamic graphs. Abello et al. (2013) [1] use interactively
controllable degree-of-interest (DOI) functions to filter down a larger dynamic network(in particular, a co-author network). Liao et al. (2013) [5] detect anomalies in dynamic
graphs leveraging a set of overview and detail visualizations. Li et al. (2013) [4] visualize the dynamic propagation of microblog messages through a network of users bydifferent interactive temporal node-link visualizations. Some approaches also cluster
similar subsequent time steps to simplify the time dimension (Bach et al. 2015 [2], vonLandesberger et al. 2016 [6]).
Visual Analysis Process. In a realistic setting, graphs are often too large to be visualized as a whole especially if they undergo dynamic changes. However, when solving
a specific task, there usually exists a natural focus that allows reducing the data to asmaller size. Hence, we want to leverage this natural focus to interactively filter thedata according to the current needs of the analyst. In particular, a visual analysis system should support the following generic process, with the fourth step as an optional
extension:
1. Define a specific (structural and temporal) pattern.
2. Browse the detected results in an overview visualization.
3. Select one result and view a focused dynamic graph visualization.
4. hChange the data and predict the impact of the changes.i
This process is different from most related interactive analysis approaches, where usually the full graph is visualized as part of an aggregated overview and then interactively
explored without support for detecting patterns. The approach by Abello et al. (2013)
is most related, but the analyst cannot browse different results of the analysis individually. Figure 1 illustrates this process in a broader setting. The user is in control of theprocess, in particular, the dynamic graph data that might be aggregated from different
data sources, the algorithmic analysis that helps retrieve patterns and trends, and theresulting dynamic graph visualization. Detected patterns set a focus in the analysis,
while the full, but partially aggregated data provides a context for the visualization.
Specific tasks that an analyst has to perform as part of the process are, among
others,• to visually seek patterns or to interactively define them, to set a focus or points
of interest in the data,• to detect and explain trends, abnormal situations, outliers, temporal paths, orinformation propagation through the network,4

Figure 1: Visual analysis process• to consider structural and temporal uncertainty of the analysis, and• to predict future states of the graph.
Special examples of the process could implicate additional tasks, for instance, in scenarios like collaborative analysis and crowdsourcing as well as in-situ analysis (i.e.,
on-the-fly analysis of big data). Application Scenarios To concretize and specify thevisual analysis process further, we discussed the following three realistic applications,
including online scenarios where data is visualized in real time and offline scenarios
where a retrospective analysis allows an in-depth investigation.
• Traffic data: Analyzing real-time traffic data such as passengers of a metro system requires online investigation of dynamic traffic flow through a network. In
particular, during outstanding events such as the breakdown of a line, the operator of the traffic system relies on an effective visualization of the current situationand its evolution.
• Social media and co-author networks: The analysis of text documents and messages could help estimate impact of key players, specific events, or topics. For
example, the visualization of a dynamic co-author graph would enable hiring
committees and research managers to evaluate researchers and research meetings.
• Software engineering: Dependencies in a software system might violate design
rules and could hinder an effective maintenance of the system, for example, unwanted cyclic dependencies. Identifying these patterns and understanding theircreation by investigating their evolution would help improve the architecture of
the software.
In these scenarios, the data is sufficiently large and complex that it often cannot be
visualized as a whole. Hence, they would particularly profit from our visual analytics
process that interactively filters and queries the data to smaller subsets.
Research Challenges. Based on the specified visual analysis process and discussed
application scenarios, we derived central research challenges that will be important fordeveloping novel visual analytics approaches for dynamic graphs.
• How to interactively specify patterns in a dynamic graph? – The basis for the
exploration process is the interactive specification of temporal and structural patterns in dynamic graphs. While the design space of such patterns is large, first5

meaningful patterns can be derived from conceptual patterns described in different application areas, for instance, bad smells in software engineering, types ofresearchers in scientometrics, or social network metrics in social sciences.
• How to visualize a dynamic graph with (temporal/structural) focus-context anduncertainty? – A specific pattern sets a temporal and structural focus within thegraph. When visualizing this, also some structural context needs to be provided
on a coarser level. Hierarchical graph aggregation can be leveraged for summarizing the context. Visual comparison of related graphs could illustrate similar
results or uncertain information.
• How to control time (real-time data + analysis time) in an online scenario? – Theinteractive analysis introduces a second time dimension. If information comesin too quickly in an online scenario, the update process could be stopped. This
would simplify the problem to an offline scenario that can be handed over froman online operator to an offline analyst. Alternatively, an automatic approachmonitors the real-time data, detects importants events, and notifies an analyst
when further analysis is required. The appropriate automatic detection of interesting events in a dynamic graph may also allow to temporally compress (orabstract) the dynamic graph, or implement dynamic focus+context techniques.
Depending on the chosen application scenarios, all three challenges or a subset of themneeds to be addressed to come up with an effective visual analysis approach. Apartfrom the relevance and quality of the proposed methods, we are also interested in thedesign of time and memory efficient algorithmic solutions.
Conclusion and Future Work. The group developed a generic analytics process fora new generation of visual analytics systems to study dynamic graphs. We describedpromising application scenarios and research challenges that might form the basis ofsuch novel approaches. Group members plan to collaborate on developing such approaches and potentially refining the general visual analysis scenario.
References[1] James Abello, Steffen Hadlak, Heidrun Schumann, and Hans-Jörg Schulz. A
modular degree-of-interest specification for the visual analysis of large dynamic networks. IEEE Transactions on Visualization and Computer Graphics,
20(3):337–350, 2014.
[2] B. Bach, N. Henry-Riche, T. Dwyer, T. Madhyastha, J-D. Fekete, andT. Grabowski. Small multipiles: Piling time to explore temporal patterns in dynamic networks. Computer Graphics Forum, 34(3):31–40, 2015.
[3] Fabian Beck, Michael Burch, Stephan Diehl, and Daniel Weiskopf. A taxonomy
and survey of dynamic graph visualization. Computer Graphics Forum, 2016.
[4] Quan Li, Huamin Qu, Li Chen, Robert Wang, Junhai Yong, and Detan Si. Visual analysis of retweeting propagation network in a microblogging platform. In
Proceedings of the 6th International Symposium on Visual Information Communication and Interaction, VINCI ’13, pages 44–53, New York, NY, USA, 2013.
ACM.
[5] Q. Liao, L. Shi, and C. Wang. Visual analysis of large-scale network anomalies.
IBM Journal of Research and Development, 57(3/4):13:1–13:12, May 2013.
6[6] T. von Landesberger, F. Brodkorb, P. Roskosch, N. Andrienko, G. Andrienko,
and A. Kerren. Mobilitygraphs: Visual analysis of mass mobility dynamics via
spatio-temporal graphs and clustering. IEEE Transactions on Visualization andComputer Graphics, 22(1):11–20, Jan 2016.

3.2

Scalability

Participants: Daniel Archambault, Michael Burch, Markus Chimani, Peter Eades,
Hiroshi Hosobe, Karsten Klein, Kazuo Misue, Hsiang-Yun Wu, Xiaru Yuan
Summary. Due to the volume, velocity, and complexity of today’s data sets in practicalapplications, scalability is an important aspect in the development of visual analytics
approaches for dynamic graph analysis. Scalability poses a big challenge for current
research and for applications in practice. For many applications, e.g. from the life sciences, it is impossible with current methods to even process the complete data stream,
or to solve analysis problems to optimality.
In this working group we analyzed the characteristics of scalability in the dynamic
graph context, tried to define dimensions of it, discussed requirements from application
areas, and finally focused on selected challenges.
Discussion. A large part of the discussions was centered around the definition of aspects or dimensions of scalability. There are some commonalities of the general big
data characterisation and dynamic networks scalability. Our first approach contained
four main dimensions that we thought might be necessary to characterise dynamic data
for a discussion of scalability issues.
• Mass - defined on the graph structure and the data annotations, e.g. number ofnodes and edges• Momentum - the relative size of the change, or mass ∗ velocity• Potential - similar to the concept in computational complexity, the potential wasmeant to measure some amortized complexity of the data over several updates• Velocity - the speed at which changes happen, i.e. ∆G∆tAfter some discussion we dropped ‘potential’ again as it didn’t seem to fit as areasonable dimension and probably would have to be adapted to a particular use-case.
We agreed that there needs to be a distinction of visual and processing scalability tocover the difference in computational and human capabilities. While hardware andsoftware improvements can advance the limits of what is computationally tractable,
the limitations of e.g. human perception represent a much stricter constraint for visual
analytics approaches.
A further focus was on what we called "phase transitions" in complexity dimensions, were we would expect rifts in the efficiency and efficacy of methods for visualization and analysis, such that visual analytics concepts need to be adapted to handle
data in a different way depending on the area of the data space it belongs to. In particular, we looked at the relation between velocity and mass of the dynamic data, andinvestigated the regions of the mass-velocity coordinate system with regard to the applicability of visualisation and analysis techniques. Our hypothesis is that, while there
is no simple mapping of techniques to locations in the coordinate system, there is asweet spot that enables good visualisation, i.e. where common approaches might already be sufficient. For the other areas dedicated solutions will be required that depend7

on the actual velocity and mass values. These solutions will include preprocessing
methods that allow to transform the input data such that it is ‘shifted’ towards the visualisation sweet spot, e.g. by means of aggregation of time like subdivision, clustering,or interval aggregation.
Finally, we listed specific challenges, including the ‘shape’ of a clustering, the characterisation of ‘temporal motifs’, and how changes can be clustered, and addressed
them for the remainder of the working group discussions. We discussed possible approaches for clustering of changes as well as time filtering and distortion, e.g. with a"time lens"-based approach.
For future work, we plan to work on one of those challenges in more detail in orderto develop a model and method that can be applied in practice.

3.3

Real World Applications

Participants: Takayuki Itoh, Stephen Kobourov, Björn Sommer Guest participants: Kwan-Liu Ma, Xiaoru Yuan
Summary. The smallest group of the Shonan meeting on “Dynamic Networks Visual
Analytics” discussed a number of application areas and related topics.
Topic. The main topic for this group was to discuss real-world applications which
require visualization of dynamic networks. We identified several areas: Biomedicine,
Co-Authorships, Computer communication/relation, Human communication/relation,
Financial Transaction, Retweet Maps/Microblog, Surveillance, Transportation/Traffic.
For more information, please see the application areas overview list below.
Application Areas Overview.
• Biomedical networks– Neuronal Networks– Health-related Network– Cell Networks– Biomolecular Networks• Co-Authorship Networks (growing-only)• Computer communication/relation Networks– eCommunication Crimes/Online Fraud Networks– Internet Security Networks– Supercomputer Communication Networks• Financial Transactions Networks– Bitcoin Network– Stock market• Human communication/relation Network– Development of Keywords (growing-only)– Conference analysis, change in paper topics
8

– Wordle• Retweets Maps/Microblog (China) Diffusion Map (growing-only)– Social networks• Surveillance Networks– International travel data
– Movement of humans recorded by sensors• Transportation/Traffic Networks– Airplane trajectories
We also discussed some specific goals for dynamic network visualizations, as well
as specific tasks one might perform with dynamic network visualizations. Examples ofsuch goals include present, explore, monitor, compare, and verify hypothesis. Examples of such tasks include find patterns, find correlations, find outliers, find trends, findstructural changes, and find temporal changes.
Attributes. In addition we started to identify a list of attributes which apply to a number or all of the aforementioned areas, namely Structural Changes, Temporal Changes,
Fixed Layout, Statistics, and Simulations. By discussing the different associated application areas, we found out that one attribute which all areas have in common are theTemporal Changes. On the other hand, the attribute Fixed Layout seems to be quite
specific for Transport/Traffic N., and might be also interesting for Biomedicine andHuman communication/relation N. Please see the complete table of dynamic network
application areas in Figure 2.

Figure 2: A tabular overview of discussed application areas. (X - regular attributes, (X)- optional attributes
Target Audience. Another important topic during the discussion were the different
target groups - from a qualitative and quantitative point of view. We identified threegroups: domain experts, general scientists, and the general public. Whereas the domain
expert should be able to edit the data, the general scientist should be able to use dynamic networks visualization in discussions, publications and presentations, and finallythe general public should be able to read and interpret the presented data. Dependingon the target group, the design of the dynamic networks could differ dramatically. In
addition, the quantitative perspective can be very important: are the dynamic network
visualizations directed towards a large or small audience? This might be especially9relevant in terms of performance issues and interaction (e.g., comment function) withthe data.
Generating dynamic networks and a tool to visualize them. Another topic whichmight be interesting for future collaboration is the development of a new tool to generate personal dynamic graphs - available especially to the general public. We consideredseveral ideas for different types of personal data that can be visualized with dynamic
networks, such as personal web activity (visited pages, visit duration, temporal as well
as structural patterns). Another possibilty would be to extract dynamic networks fromcelebrities (e.g., retweet networks, topics over time, etc.)
Future Work. A better understanding of the real-world need for dynamic network
visualization can help in writing convincing research proposals. A tool for generating
personalized dynamic networks will raise awareness and spur more work in this area.

4

Dynamic Approaches for Hybrid Visualizations

Participants: Vladimir Batagelj, Emilio Di Giacomo, Walter Didimo, Michael
Kaufmann, Giuseppe Liotta, Maurizio Patrignani
Summary. Hybrid Visualization is a paradigm invented to support the visual analysisof large and complex networks. It mixes node-link diagrams and matrix-based representations in a single visualization. Dense subgraphs are visualized with a matrixbased representation, while sparse subgraphs or high-level views are shown by meansof a node-link diagram. An example of a hybrid visualization taken from the seminal
paper of Henry et al. [15] is shown in Figure 3a.

(a)

(b)

Figure 3: Two examples of hybrid visualizations: (a) NodeTrix (b) VHyXY.
In a subsequent paper, Batagelj et al. [8] proposed an algorithmic framework called(X, Y )-clustering and describe a hybrid visualization system called VHyXY based on
this approach (see Figure 3b for an example of a visualization created by VHyXY).
An (X, Y )-clustering of a graph G is a clustering of G such that the graph induced byeach cluster belongs to a given family X and the inter-cluster graph belongs to anothergiven family Y . The inter-cluster graph is represented as a node-link diagram (for10

example it could be a planar drawing if Y is the family of planar graphs), while eachcluster is represented as a matrix or again as a node-link diagram, depending on its
density or user’s preference. Given this framework, the concept of k-cores is exploited
to define the clusters of a given graph G; the k-core of G is the largest subgraph of G
such that all the nodes in such a subgraph have degree at least k (with 0 ≤ k < |V |).
For each node v in G, the core number of v denotes the largest k such that a k-coreexists and contains v. Each connected component of the k-core of G is called a kcore component of G. Batagelj et al. [8] use the k-core components of G to define
the clusters of G. Each cluster (i.e., each k-core component) can then be recursively
decomposed by using larger values of k. The clustering of G computed in this way iscalled a k-core decomposition of G, and the tree that describes such a decomposition iscalled a k-core decomposition tree. An example of a k-core decomposition of a graphis shown in Figure 4.

1
3

2

4

3

5
1

4

4

2

4
5

Figure 4: A k-core decomposition of a graph and the corresponding k-core decomposition tree.
We recall that the notion of k-core was introduced by Seidman in 1983 [19], andused in several application areas for the decomposition and the analysis of large graphs,
especially in the field of social networks and biology (see, e.g., [9, 11, 13, 14, 17, 20]).
A linear-time algorithm to compute the core number of each vertex of a given graphhas been proposed by Batagelj and Zaveršnik [10]. We finally remark that hybrid
visualizations have been recently studied from a theoretical point of view by Da Lozzo
et al. [12].
Our algorithmic problem. We studied the problem of efficiently updating the kcore decomposition tree under edge insertions and deletions. This is a key algorithmic
problem for the design and implementation of a hybrid visualization system based on
the k-core decomposition where the visualized network can change dynamically. We
concentrated on the following questions: (i) Is it possible to guarantee sub-linear time
per operation (asymptotically speaking, according to a worst-case analysis)? (ii) If
linear-time is required in the worst case, can we design techniques to speed-up thecomputation in practice?
The problem of efficiently updating the core numbers of the vertices dynamically,has been recently studied in various papers [7, 16, 18, 21]. It is worth remarking thatthe algorithms presented in these papers do not guarantee sub-linear time per operation,
but are fast in practice. On the other hand, they only concentrate on updating the corenumbers of the vertices, while we want to keep the k-core decomposition tree updated.
Indeed, the dynamic maintenance of the different connected components of every k-

11core, seems to be a more challenging problem
We devised a possible algorithm for our problem. The main idea is to use a suitabledata structure to efficiently find the components that are affected by the edge addition/removal and to locally change the k-core decomposition tree to keep it updated.
The worst-case time complexity is still linear but we hope that the algorithm could befaster in practice. We plan to further refine the algorithm and to experimentally test
it to evaluate its performance. Moreover, we would like to design a dynamic hybrid
visualization system based on our algorithm.
References[7] Sabeur Aridhi, Martin Brugnara, Alberto Montresor, and Yannis Velegrakis. Distributed k-core decomposition and maintenance in large dynamic graphs. In Proceedings of the 10th ACM International Conference on Distributed and Eventbased Systems, DEBS ’16, pages 161–168, New York, NY, USA, 2016. ACM.
[8] V. Batagelj, F. J. Brandenburg, W. Didimo, G. Liotta, P. Palladino, and M. Patrignani. Visual analysis of large graphs using (X, Y )-clustering and hybrid
visualizations. IEEE Transactions on Visualization and Computer Graphics,
17(11):1587–1598, Nov 2011.
[9] Vladimir Batagelj, Andrej Mrvar, and Matjaž Zaveršnik. Partitioning approach
to visualization of large graphs. In Jan Kratochvíl, editor, Graph Drawing: 7thInternational Symposium, GD’99 Štiřín Castle, Czech Republic September 15–
19, 1999 Proceedings, pages 90–97, Berlin, Heidelberg, 1999. Springer Berlin
Heidelberg.
[10] Vladimir Batagelj and Matjaž Zaveršnik. Fast algorithms for determining (generalized) core groups in social networks. Advances in Data Analysis and Classification, 5(2):129–145, 2011.
[11] G. J. Baxter, S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes. k-coreorganization in complex networks. In T. My Thai and M. Panos Pardalos, editors,
Handbook of Optimization in Complex Networks: Theory and Applications, pages
229–252. Springer US, Boston, MA, 2012.
[12] Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, and Maurizio Patrignani. Computing nodetrix representations of clustered graphs. In Nöllenburg
Martin and Yifan Hu, editors, Graph Drawing and Network Visualization: 24th
International Symposium, GD 2016. Springer International Publishing. to appear.
[13] Marco Gaertler and Maurizio Patrignani. Dynamic analysis of the autonomous
system graph. In International Workshop on Inter-domain Performance and Simulation (IPS), pages 13–24, 2004.
[14] A. V. Goltsev, S. N. Dorogovtsev, and J. F. F. Mendes. k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects. Phys. Rev.
E, 73:056101, May 2006.
[15] N. Henry, J. D. Fekete, and M. J. McGuffin. Nodetrix: a hybrid visualization ofsocial networks. IEEE Transactions on Visualization and Computer Graphics,
13(6):1302–1309, Nov 2007.

12

[16] R. H. Li, J. X. Yu, and R. Mao. Efficient core maintenance in large dynamic
graphs. IEEE Transactions on Knowledge and Data Engineering, 26(10):2453–
2465, Oct 2014.
[17] Tomasz Łuczak. Size and connectivity of the k-core of a random graph. Discrete
Mathematics, 91(1):61 – 68, 1991.
[18] Ahmet Erdem Saríyüce, Buğra Gedik, Gabriela Jacques-Silva, Kun-Lung Wu,
and Ümit V. Çatalyürek. Streaming algorithms for k-core decomposition. Proc.
VLDB Endow., 6(6):433–444, April 2013.
[19] Stephen B. Seidman. Network structure and minimum degree. Social Networks,
5(3):269 – 287, 1983.
[20] Stefan Wuchty and Eivind Almaas. Peeling the yeast protein network. PROTEOMICS, 5(2):444–449, 2005.
[21] Yikai Zhang, Jeffrey Xu Yu, Ying Zhang, and Lu Qin. A fast order-based approach for core maintenance. CoRR, abs/1606.00200, 2016.

5

Participants• Takayuki Itoh, Ochanomizu University• Karsten Klein, University of Konstanz• Giuseppe Liotta, University of Perugia• Daniel Archambault, Swansea University• Vladimir Batagelj, University of Ljubljana• Fabian Beck, VISUS, University of Stuttgart• Michael Burch, Stuttgart University• Markus Chimani, Osnabrück University• Maxime Cordeil, Monash University• Walter Didimo, University of Perugia• Emilio Di Giacomo, University of Perugia• Peter Eades, The University of Sydney• Leszek Gasieniec, University of Liverpool• Carsten Goerg, University of Colorado• Hiroshi Hosobe, Hosei University• Masahiko Itoh, University of Tokyo• Michael Kaufmann, Eberhard Karls University, Tübingen• Stephen Kobourov, University of Arizona13• Kwan-Liu Ma, University of California• Kazuo Misue, University of Tsukuba• Maurizio Patrignani, Roma Tre University• Huamin Qu, Hong Kong University of Science and Technology• Tobias Schreck, Graz University of Technology• Bjoern Sommer, Konstanz University• Ken Wakita, Tokyo Institute of Technology• Hsiang-Yun Wu, Keio University• Xiaoru Yuan, Peking University• Hsu-Chun Yen, National Taiwan University

6

Overview of Talks

There were three invited talks, giving rather broad overviews on different aspects ofthe visual analytics challenges, see the abstracts below. In addition, two lightning talks
were given.

Daniel Archambault
Animation, Small Multiples, and the Mental Map in Dynamic Graphs
Visualising dynamic graphs is important for many application areas. For social
media networks, these visualisations can help us understand the interaction and interests of users online. In biology, they can illustrate the interactions between genes andbiological processes. Understanding and designing effective visualisation methods for
dynamic network data is fundamental to these areas as well as many others. In the talkpresented at Shonan, the results of three experiments was presented covering the effective presentation of dynamic networks. In particular, results with respect to animation(presentation of interactive movies of the data), small multiples (presenting the data
through several linked windows like a comic book), and drawing stability (the visualstability of the data presentation).
Given the evidence provided by these three experiments, some guidelines for theeffective presentation of dynamic graphs were drawn. The mental map, or drawing
stability, is important when a large number of objects could be of interest to the task
and highlighting of these objects (via colour or other means) is difficult or not possible. Stable drawings help users orient themselves in dynamic data (to find specificlocations in the graph or to follow specific paths) and do not necessarily improve readability. Animation can be useful if changes are over a short time period (two to threetimeslices), the data is not stable in terms of spatial position (many objects must move),and highlighting is not possible by other means. Otherwise, static presentations, likesmall multiples, have significant advantages in terms of the time it takes to used them.
They often have significantly faster response times with no significant differences interms of error rate. For long time series, there is a significant research opportunity forthe design and implementation of visualisation methods that effectively scale to longtime series.
14

Ken Wakita
Filling the gap between theory and code
The problem of finding a good layout for graphs, including dynamic graphs, is understood as optimization of objective functions that encodes visual cosmetics, meeting
various constraints. The cause of the complexity of maintaining software implementation of graph layout algorithms is primarily due to semantic gap between the high-level,
mathematical description of the layout problem and low-level description of the software using programming languages. The talk addresses this problem by describing
the algorithm using computational algebra system and automatically synthesizing thesoftware and its documentation from the description.

Fabian Beck, Michael Burch
Title: The State of the Art in Visualizing Dynamic Graphs
Visualizing changes in graphs and networks is a growing area of research with avariety of approaches to encode the graph structure and its temporal evolution. We
report the state of the art in the field by introducing a taxonomy that structures existing techniques. The representation of time as animation (time-to-time mapping) ortimeline (time-to-space mapping) forms the first discriminating feature of the hierarchically structured taxonomy. In the talk, we present the structure of the taxonomy andprovide examples for every taxonomy category. Furthermore, we discuss main resultsof conducted user evaluations and promising future directions of research.
Lightning talks
Carsten Goerg: Matching the user’s mental map Traditionally, researchers areconcerned about preserving the user’s mental map when drawing dynamic graphs.
They try to keep the parts of the layout for which the underlying graph doesn’t change
stable, and only change the parts of the layout for which there are changes in the underlying graph. In some domain applications there exist a similar challenge, even for
static graphs. Sometimes, a user already has a mental map for a network that represents
a specific set of relationships. In these scenarios, it is important that the generated layouts match the user’s mental map to minimize the user’s efforts of understanding thevisualization. I present such a scenario in the biomedical domain and propose a semiautomatic layout approach that can address the problem of matching the user’s mental
map.

Huamin Qu: Overview on recent research
Acknowledgments. The organizers would like to thank all participants, NII, and the
Shonan staff for all their contributions. We hope that the research during the seminar,
as well as the exchange between the participants, will lead to new successful collaborations and research findings in the future.

15