A regularized graph layout framework for dynamic network visualization

DOI10.1007/S10618-012-0286-6zbMATH Open1298.68282arXiv1202.6042OpenAlexW2001557365WikidataQ114827258 ScholiaQ114827258MaRDI QIDQ468664FDOQ468664

Mark Kliger, Kevin S. Xu, Alfred O. III Hero

Publication date: 7 November 2014

Published in: Data Mining and Knowledge Discovery (Search for Journal in Brave)

Abstract: Many real-world networks, including social and information networks, are dynamic structures that evolve over time. Such dynamic networks are typically visualized using a sequence of static graph layouts. In addition to providing a visual representation of the network structure at each time step, the sequence should preserve the mental map between layouts of consecutive time steps to allow a human to interpret the temporal evolution of the network. In this paper, we propose a framework for dynamic network visualization in the on-line setting where only present and past graph snapshots are available to create the present layout. The proposed framework creates regularized graph layouts by augmenting the cost function of a static graph layout algorithm with a grouping penalty, which discourages nodes from deviating too far from other nodes belonging to the same group, and a temporal penalty, which discourages large node movements between consecutive time steps. The penalties increase the stability of the layout sequence, thus preserving the mental map. We introduce two dynamic layout algorithms within the proposed framework, namely dynamic multidimensional scaling (DMDS) and dynamic graph Laplacian layout (DGLL). We apply these algorithms on several data sets to illustrate the importance of both grouping and temporal regularization for producing interpretable visualizations of dynamic networks.

Full work available at URL: https://arxiv.org/abs/1202.6042

zbMATH Keywords

regularizationvisualizationmultidimensional scalingdynamic networkgraph Laplaciangraph layoutmental mapspectral layout

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Distributed systems (68M14)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Modern multidimensional scaling. Theory and applications.
• Ridge Regression: Biased Estimation for Nonorthogonal Problems
• Empirical Analysis of an Evolving Social Network
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• Drawing graphs by eigenvectors: theory and practice
• An Interior Point Algorithm for Large-Scale Nonlinear Programming
• An algorithm for drawing general undirected graphs
• Nonlinear Dimensionality Reduction
• An r-Dimensional Quadratic Placement Algorithm
• Graph Drawing
• Supervised multidimensional scaling for visualization, classification, and bipartite ranking
• A Quantitative Comparison of Stress-Minimization Approaches for Offline Dynamic Graph Drawing
• Navigating Clustered Graphs Using Force-Directed Methods
• Dynamic Spectral Layout with an Application to Small Worlds

Cited In (3)

• HOTVis: Higher-Order Time-Aware Visualisation of Dynamic Graphs
• Visualizing the effects of a changing distance on data using continuous embeddings
• PLANET: a radial layout algorithm for network visualization

Uses Software

• superMDS
• SoNIA
• visone
• Colibri
• GenLouvain
• PMA

This page was built for publication: A regularized graph layout framework for dynamic network visualization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q468664)