Abstract We introduce C lusterix , a novel hybrid visualization model for representing hierarchically clustered networks, which also supports directed and weighted edges. C lusterix offers an integrated view of both the network and its full cluster hierarchy by compactly visualizing the cluster inclusion tree enriched with links of the network. This is achieved through matrix‐based representations at various hierarchy levels, combined with a node‐link style linear layout at the leaf level. To support layout computation based on C lusterix , we propose two algorithmic approaches: an exact Integer Linear Program and a fast heuristic, both aimed at minimizing edge crossings. We present an extensive experimental comparison of these algorithmic approaches to highlight the trade‐offs between efficiency and effectiveness. Moreover, as a proof of concept for our model, we developed an interactive visualization system based on C lusterix and evaluated its performance through case studies and qualitative feedback from experts in different application domains.

We address the problem of computing a dynamic visualization of a geometric graph G as a sequence of frames. Each frame shows only a portion of the graph but their union covers G entirely. The two main requirements of our dynamic visualization are: (i) guaranteeing drawing stability, so to preserve the user’s mental map; (ii) keeping the visual complexity of each frame low. To satisfy the first requirement, we never change the position of the vertices. Regarding the second requirement, we avoid edge crossings in each frame. More precisely, in the first frame we visualize a suitable subset of non-crossing edges; in each subsequent frame, exactly one new edge enters the visualization and all the edges that cross with it are deleted. We call such a sequence of frames a planar story of G. Our goal is to find a planar story whose minimum number of edges contemporarily displayed is maximized (i.e., a planar story that maximizes the minimum frame size). Besides studying our model from a theoretical point of view, we also design and experimentally compare different algorithms, both exact techniques and heuristics. These algorithms provide an array of alternative trade-offs between efficiency and effectiveness, also depending on the structure of the input graph.

The tsNET algorithm adapts the popular dimensional reduction method t-SNE for graph drawing to compute high-quality drawings, preserving the neighborhood and clustering structure. However, its O(nm) runtime results in poor scalability for large graphs. In this poster, we present three fast algorithms for reducing the time complexity of tsNET to O(n log n) time and O(n) time, by integrating new fast methods for computation of high-dimensional probabilities and entropy computation with fast t-SNE algorithms for computation of KL divergence gradient. Specifically, we present two O(n log n)-time algorithms BH-tsNET and FIt-tsNET, incorporating partial BFS-based high-dimensional probability computation and a new quadtree-based entropy computation with fast t-SNE algorithms, and O(n)-time algorithm L-tsNET, introducing a new fast interpolation-based entropy computation. Extensive experiments using benchmark data sets confirm that BH-tsNET, FIt-tsNET, and L-tsNET outperform tsNET, achieving 93.5%, 96%, and 98.6% faster runtime, respectively, while computing similar quality drawings in terms of quality metrics (neighborhood preservation, stress, shape-based metrics, and edge crossing) and visual comparison.

Shape-based metrics measure how faithfully a drawing D of a large graph G shows the structure of the graph by comparing the similarity between G and a proximity graph S computed from D. In this paper, we present new degree-constrained shape-based metrics by introducing new proximity graphs dcGG and dcRNG, which constrain the degree of each vertex v in the proximity graph S to be no greater than the degree of v in G. Extensive experiments demonstrate that our new degree-constrained shape-based metrics QdcRNGand QdcGGcan more accurately measure the shape-faithfulness than the state-of-the-art degree-sensitive shape-based metrics, with on average 29.1% better metrics for highly shape-faithful layouts. Moreover, we present extensive comparison experiments of ten popular graph layouts using our new shape-based metrics QdcRNGand QdcGGto recommend shape-faithful layouts for large and complex graphs. Furthermore, we present a new shape-faithful graph drawing algorithm dcShFR, based on the most popular force-directed algorithm FR, to optimize the new shape-based metrics QdcRNGand QdcGG. Extensive experiments demonstrate that our dcShFR algorithm computes 14.5% higher shape-faithful drawings than FR on average.

We present new metrics and algorithms for connectivity-faithful visualization for dynamic graphs. We first present the SCQ (Sampling Change Quality) framework to evaluate dynamic graph sampling, based on the popular sampling quality metrics for the sampling of static graphs. We introduce the $S C Q_{C L O S E}$ metric as a specific instance of the framework, based on closeness centrality. We next introduce the PCQ (Proxy Change Quality) framework for evaluating the proxy distance change faithfulness of the visualization of dynamic graph sampling. More specifically, we introduce the PDCQ (Proxy Distance Change Quality) metric for proxy distance change faithfulness, i.e., how faithfully the ground-truth change in the shortest path distances of the original dynamic graphs is displayed as the geometric change in Euclidean distances in the drawing of the dynamic graph samples. Finally, we present a dynamic graph sampling algorithm for preserving the connectivity structures of the original dynamic graphs, called DCFNI (Dynamic Connectivity-Faithful NI), based on the well-known NI (Nagamochi-Ibaraki) algorithm for computing a connectivity-faithful sparsification. Extensive experiments on DCFNI, through comparison with the state-of-the-art DSS (Dynamic Spectral Sparsification) which outperforms random sampling methods, demonstrate the effectiveness of DCFNI over DSS: $53 \%$ higher $S C Q_{C L O S E}$ and $13 \%$ higher PDCQ on average, and better preserving the global connectivity of dynamic graphs on visual comparison.

Motivated by the need for decision-making systems that avoid bias and discrimination, the concept of fairness recently gained traction in the broad field of artificial intelligence , stimulating new research also within the information visualization community. In this paper, we introduce a notion of fairness in network visualization, specifically for orthogonal and for straight-line drawings of graphs, two foundational paradigms in the field. We investigate the following research questions: (i) What is the price, in terms of global readability , of incorporating fairness constraints in graph drawings? (ii) How unfair is a graph drawing that does not optimize fairness as a primary objective ? We present both theoretical and empirical results. In particular, we design and implement two optimization algorithms for multi-objective functions, one based on an ILP model for orthogonal drawings, and one based on gradient descent for straight-line drawings. In a nutshell, we experimentally show that it is possible to significantly increase the fairness of a drawing by paying a relatively small amount in terms of reduced global readability. Also, we present a use case in which we qualitatively evaluate our approach on a practical scenario.

Graph and network visualization supports exploration, analysis and communication of relational data arising in many domains: from biological and social networks, to transportation and powergrid systems. With the arrival of AI-based question-answering tools, issues of trustworthiness and explainability of generated answers motivate a significant new role for visualization. In the context of graphs, we see the need for visualizations that can convince a critical audience that an assertion (e. g., from an AI) about the graph under analysis is valid. The requirements for such representations that convey precisely one specific graph property are quite different from standard network visualization criteria which optimize general aesthetics and readability. In this paper, we aim to provide a comprehensive introduction to visual proofs of graph properties and a foundation for further research in the area. We present a framework that defines what it means to visually prove a graph property. In the process, we introduce the notion of a visual certificate, that is, a specialized faithful graph visualization that leverages the viewer's perception, in particular, pre-attentive processing (e. g., via pop-out effects), to verify a given assertion about the represented graph. We also discuss the relationships between visual complexity, cognitive load and complexity theory, and propose a classification based on visual proof complexity. Then, we provide further examples of visual certificates for problems in different visual proof complexity classes. Finally, we conclude the paper with a discussion of the limitations of our model and some open problems.

Not every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyond planarity by considering upward $k$-planar drawings of DAGs in which the edges are monotonically increasing in a common direction and every edge is crossed at most $k$ times for some integer $k \ge 1$. We show that the number of crossings per edge in a monotone drawing is in general unbounded for the class of bipartite outerplanar, cubic, or bounded pathwidth DAGs. However, it is at most two for outerpaths and it is at most quadratic in the bandwidth in general. From the computational point of view, we prove that testing upward-$k$-planarity is NP-complete already for $k=1$ and even for restricted instances for which upward planarity testing is polynomial. On the positive side, we can decide in linear time whether a single-source DAG admits an upward 1-planar drawing in which all vertices are incident to the outer face.

Graph and network visualization supports exploration, analysis and communication of relational data arising in many domains: from biological and social networks, to transportation and powergrid systems. With the arrival of AI-based question-answering tools, issues of trustworthiness and explainability of generated answers motivate a greater role for visualization. In the context of graphs, we see the need for visualizations that can convince a critical audience that an assertion about the graph under analysis is valid. The requirements for such representations that convey precisely one specific graph property are quite different from standard network visualization criteria which optimize general aesthetics and readability. In this paper, we aim to provide a comprehensive introduction to visual proofs of graph properties and a foundation for further research in the area. We present a framework that defines what it means to visually prove a graph property. In the process, we introduce the notion of a visual certificate, that is, a specialized faithful graph visualization that leverages the viewer's perception, in particular, pre-attentive processing (e. g. via pop-out effects), to verify a given assertion about the represented graph. We also discuss the relationships between visual complexity, cognitive load and complexity theory, and propose a classification based on visual proof complexity. Finally, we provide examples of visual certificates for problems in different visual proof complexity classes.

Connectivity is one of the important fundamental structural properties of graphs, and a graph drawing D should faithfully represent the connectivity structure of the underlying graph G. This paper investigates connectivity-faithful graph drawing leveraging the famous Nagamochi-Ibaraki (NI) algorithm, which computes a sparsification G_NI, preserving the k-connectivity of a k-connected graph G. Specifically, we first present CFNI, a divide-and-conquer algorithm, which computes a sparsification G_CFNI, which preserves the global k-connectivity of a graph G and the local h-connectivity of the h-connected components of G. We then present CFGD, a connectivity-faithful graph drawing algorithm based on CFNI, which faithfully displays the global and local connectivity structure of G. Extensive experiments demonstrate that CFNI outperforms NI with 66% improvement in the connectivity-related sampling quality metrics and 73% improvement in proxy quality metrics. Consequently, CFGD outperforms a naive application of NI for graph drawing, in particular with 62% improvement in stress metrics. Moreover, CFGD runs 51% faster than drawing the whole graph G, with a similar quality.

In this paper, we introduce the first learning-free model reuse task within the non-Euclidean domain, termed as Deep Graph Mating (Grama). We strive to create a child Graph Neural Network (GNN) that integrates knowledge from pre-trained parent models without requiring re-training, fine-tuning, or annotated labels. To this end, we begin by investigating the permutation invariance property of GNNs, which leads us to develop two vanilla approaches for Grama: Vanilla Parameter Interpolation (VPI) and Vanilla Alignment Prior to Interpolation (VAPI), both employing topology-independent interpolation in the parameter space. However, neither approach has achieved the anticipated results. Through theoretical analysis of VPI and VAPI, we identify critical challenges unique to Grama, including increased sensitivity to parameter misalignment and further the inherent topology-dependent complexities. Motivated by these findings, we propose the Dual-Message Coordination and Calibration (DuMCC) methodology, comprising the Parent Message Coordination (PMC) scheme to optimise the permutation matrices for parameter interpolation by coordinating aggregated messages, and the Child Message Calibration (CMC) scheme to mitigate over-smoothing identified in PMC by calibrating the message statistics within child GNNs. Experiments across diverse domains, including node and graph property prediction, 3D object recognition, and large-scale semantic parsing, demonstrate that the proposed DuMCC effectively enables training-free knowledge transfer, yielding results on par with those of pre-trained models.

The cluster faithfulness metrics CQ measure how faithfully the ground truth clustering of a graph is represented as the geometric clustering in a drawing of the graph. Existing CQ metrics use k-means clustering, which effectively compute a geometric clustering when the cluster sizes are even, resulting in accurate CQ metrics. However, k-means clustering tends to compute clusters of even sizes and thus often fails to compute an accurate geometric clustering when the cluster sizes are uneven, leading to inaccurate CQ metrics.In this paper, we present a new cluster faithfulness metric CQ-HAC, using HAC (Hierarchical Agglomerative Clustering). HAC can compute a more accurate geometric clustering for uneven cluster sizes than k-means clustering. Consequently, CQ-HAC can more accurately measure cluster faithfulness, regardless of whether the sizes of clusters are even or uneven. Moreover, we present two algorithms, Cluster-kmeans and Cluster-HAC, for optimizing cluster faithfulness of graph drawings. Extensive experiments show that in practice, both algorithms always compute perfectly cluster-faithful drawings (i.e., CQ = 1) in our experiments using various graphs with both even and uneven cluster sizes, achieving significant improvement over existing graph layouts, including cluster-focused layouts.

The shape-based metrics evaluate a drawing D of a large and complex graph G, by computing the similarity between G and a proximity graph S computed from D. However, existing metrics using planar proximity graphs, such as the Gabriel proximity graph with at most 3n−8 edges, fail to accurately evaluate drawings of complex dense graphs with Θ(n2) edges.This paper presents new shape-based faithfulness metrics using the β-skeleton proximity graph, which represent the skeleton shape of a set of points in the plane with up to Θ(n2) edges. Specifically, we leverage the effectiveness of the β-skeleton as a shape-based metric, and provide guidelines on the parameter β for various graph classes. Extensive experiments demonstrate that our new β-skeleton shape-based metrics can more accurately measure the faithfulness of drawings of large dense graphs, with a significant improvement of over 67% on average, than the existing Gabriel graph shape-based metrics.

Recent works in graph visualization attempt to reduce the runtime ofrepulsionforce computation of force-directed algorithms using sampling. However, they fail to reduce the runtime forattractionforce computation to sublinear in the number of edges. We present theSubLinearForceframework for a fully sublinear-timeforce computationalgorithm for drawing large complex graphs. More precisely, we present new sublinear-time algorithms for theattraction forcecomputation of force-directed algorithms. We then integrate them with sublinear-time repulsion force computation to give a fully sublinear-time force computation. Extensive experiments show that our algorithms compute layouts on average 80% faster than the existing linear-time force computation algorithm, while obtaining significantly better quality metrics such as edge crossing and shape-based metrics.

In this article, we present new quality metrics for symmetric graph drawing based on group theory. Roughly speaking, the new metrics are faithfulness metrics, i.e., they measure how faithfully a drawing of a graph displays the ground truth (i.e., geometric automorphisms) of the graph as symmetries. More specifically, we introduce two types of automorphism faithfulness metrics for displaying: (1) a single geometric automorphism as a symmetry (axial or rotational), and (2) a group of geometric automorphisms (cyclic or dihedral). We present algorithms to compute the automorphism faithfulness metrics in O(n logn) time. Moreover, we also present efficient algorithms to detect exact symmetries in a graph drawing. We then validate our automorphism faithfulness metrics using deformation experiments. Finally, we use the metrics to evaluate existing graph drawing algorithms to compare how faithfully they display geometric automorphisms of a graph as symmetries.

The vulnerability of smartphones to cyber attacks has been a serious concern to users arising from the integrity of installed applications (mobile apps). These apps are to provide legitimate and diversified on-the-go services. However, some have uncovered ways to penetrate smartphones for malicious behaviors. While some development and distribution regulations, such as Google Play Protect are in place, their effectiveness is often limited due primarily to falling behind the emergence of new malware. This paper presents an Analytic-based deep neural network Android Malware detection (ADAM) to detect potentially dangerous apps based on a set of features and patterns, i.e., application fingerprints, extracted from mobile apps. In particular, ADAM uses these features and patterns to train feature-specific DNNs to have consensus on the application labels when their ground truth is unknown. In addition, ADAM leverages the transfer learning technique to obtain its adjustability to new applications across smartphones. This is done by reusing the pre-trained model(s) and making them more adaptable by model personalization and federated learning (FL) techniques. This adjustability facilitates collaborative detection and independent labeling across smartphones, assisted by FL guards, which protect ADAM against poisoning attacks through model analysis. ADAM relies on a diverse dataset containing more than 153000 applications with over 41000 extracted features for DNNs training. ADAM’s feature-specific DNNs, on average, achieved more than 98% accuracy compared to Play Protect and antivirus software, resulting in an outstanding performance against data manipulation attacks.

Shape-based metrics measure how faithfully a drawing D of a large graph G shows the structure of graph, by comparing the similarity between G and a proximity graph S computed from D. Although these metrics can successfully evaluate drawings of large graphs, they are limited to relatively sparse graphs, since existing metrics use planar proximity graphs GG (Gabriel Graph) and RNG (Relative Neighbourhood Graph). This paper presents new shape-based faithfulness metrics for evaluating drawings of large and complex graphs, using high-order prox-imity graphs k-GG and k-RNG. Extensive experiments demonstrate that our new shape-based metrics using degree-based proximity graphs dGG and dRNG can more accurately measure the faithful-ness of drawings of large and complex graphs, with a significant improvement of over 100% better, on average, than the existing shape-based metrics using GG and RNG. Moreover, we present a new shape change faithfulness metric DSC for evaluating drawings of dynamic graphs, by measuring how proportional the geometric shape change in the drawings of dynamic graphs is to the ground truth change in dynamic graphs. Validation using deformation experiments support that DSC can accurately measure shape change faithfulness in dynamic graph drawing. Furthermore, we present extensive comparison experiments of ten popular graph layouts using our new shape-based metrics dGG, dRNG and DSC, to recommend which layouts can give a better shape-faithful graph drawing for large and complex graphs.

Mobile applications (apps) on smartphones have become a primary means to bring a wide variety of services on the go. These apps are provided by third-party developers and service providers. These apps are increasingly diverse, so as are malware. As a result, current signature-based protection approaches are ineffective against new malware. This poses privacy and security risks, increasing smartphones' vulnerability to cyber attacks. In this paper, we present a novel Deep neural network-based On-device Malware Detection (DOM) that employs model personalization and transfer learning for enhancing real-time ondevice detection performance. DOM consists of two on-device machine learning models referred to as generic and personalized models and dynamically analyzes applications to extract a comprehensive set of features. The generic model is a fine-tuned deep neural network (DNN) for labeling applications whose ground truth is not available. In contrast, the personalized model is a lightweight trainable model created by retaining the majority of the generic DNN layers and trainable parameters and adding a new lightweight neural network. The personalized model is further improved with the help of federated learning, which aggregates the personalized model parameters. We have used over 32000 real-world applications from different repositories to train and evaluate DOM. Experiments show that the generic DNN model achieves 98.41% accuracy, and the personalized model has also demonstrated outstanding performance detection with an accuracy of 87%. DOM is very lightweight and uses less than 4% memory consumption.

Finding a shortest path for a given pair of vertices in a graph drawing is one of the fundamental tasks for qualitative evaluation of graph drawings. In this paper, we present the first machine learning approach to predict human shortest path task performance, including accuracy, response time, and mental effort. To predict the shortest path task performance, we utilize correlated quality metrics and the ground truth data from the shortest path experiments. Specifically, we introduce path faithfulness metrics and show strong correlations with the shortest path task performance. Moreover, to mitigate the problem of insufficient ground truth training data, we use the transfer learning method to pre-train our deep model, exploiting the correlated quality metrics. Experimental results using the ground truth human shortest path experiment data show that our models can successfully predict the shortest path task performance. In particular, model MSP achieves an MSE (i.e., test mean square error) of 0.7243 (i.e., data range from −17.27 to 1.81) for prediction.

Understanding what graph layout human prefer and why they prefer such graph layout is significant and challenging due to the highly complex visual perception and cognition system in human brain. In this paper, we present the first machine learning approach for predicting human preference for graph layouts.In general, the data sets with human preference labels are limited and insufficient for training deep networks. To address this, we train our deep learning model by employing the transfer learning method, e.g., exploiting the quality metrics, such as shape-based metrics, edge crossing and stress, which are shown to be correlated to human preference on graph layouts. Experimental results using the ground truth human preference data sets show that our model can successfully predict human preference for graph layouts. To our best knowledge, this is the first approach for predicting qualitative evaluation of graph layouts using human preference experiment data.

This paper presents a new visual representation of graphs, inspired by the dot painting style of Central Australia. This painting style is established as a powerful medium for communicating information with abstraction, and has a long history of supporting storytelling.We propose a general framework GDot to visually represent in-formation as dot paintings. We describe computational techniques as well as the rendering effects to produce painterly representations of graphs and networks. We present visualization examples with various networks from diverse domains, from pure mathematics to social systems. Further, we briefly describe the extension of our dot painting visualization style to multi-dimensional data, dynamic data and geo-referenced data.

The multi-level graph drawing is a popular approach to visualize large and complex graphs. It recursively coarsens a graph and then uncoarsens the drawing using layout refinement. In this paper, we leverage the Louvain community detection algorithm for the multi-level graph drawing paradigm.More specifically, we present the Louvain-based multi-level graph drawing algorithm, and compare with other community detection algorithms such as Label Propagation and Infomap clustering. Experiments show that Louvain-based multi-level algorithm performs best in terms of efficiency (i.e., fastest runtime), while Label Propagation and Infomap-based multi-level algorithms perform better in terms of effectiveness (i.e., better visualization in quality metrics).

Recent works in graph visualization attempt to reduce the runtime of repulsion force computation of force-directed algorithms using sampling, however they fail to reduce the runtime for attraction force computation to sublinear in the number of edges.We present new sublinear-time algorithms for the attraction force computation of force-directed algorithms and integrate them with sublinear-time repulsion force computation.Extensive experiments show that our algorithms, operated as part of a fully sublinear-time force computation framework, compute graph layouts on average 80% faster than existing linear-time force computation algorithm, with surprisingly significantly better quality metrics on edge crossing and shape-based metrics.

We present algorithms reducing the runtime of the stress minimization iteration of stress-based layouts to sublinear in the number of vertices and edges. Specifically, we use vertex sampling to further reduce the number of vertex pairs considered in stress minimization iterations. Moreover, we use spectral sparsification to reduce the number of edges considered in stress minimization computations to sublinear in the number of edges, esp. for dense graphs.Specifically, we present new pivot selection methods using importance-based sampling. Then, we present two variations of sublinear-time stress minimization method on two popular stress-based layouts, Stress Majorization and Stochastic Gradient Descent.Experimental results demonstrate that our sublinear-time algorithms run, on average, about 35% faster than the state-of-art linear-time algorithms, while obtaining similar quality drawings based on stress and shape-based metrics.

Subgraph query processing (also known as subgraph search) and subgraph matching are fundamental graph problems in many application domains. A lot of efforts have been made to develop practical solutions for these problems. Despite the efforts, existing algorithms showed limited running time and scalability in dealing with large and/or many graphs. In this paper, we propose a new subgraph search algorithm using equivalences of vertices in order to reduce search space: (1) static equivalence of vertices in a query graph that leads to an efficient matching order of the vertices, and (2) dynamic equivalence of candidate vertices in a data graph, which enables us to capture and remove redundancies in search space. These techniques for subgraph search also lead to an improved algorithm for subgraph matching. Experiments show that our approach outperforms state-of-the-art subgraph search and subgraph matching algorithms by up to several orders of magnitude with respect to query processing time.

Recent methods for visualizing graphs have used a map metaphor: vertices are represented as regions in the plane, and proximity between regions represents edges between vertices.In many real world applications, the data changes over time, resulting in a dynamic map. This paper introduces new methods for representing dynamic graphs with map animation. More specifically, we present three different animation methods: MDSV (Multidimensional scaling - Voronoi), TV (Tutte - Voronoi) and TD (Tutte - dual). These methods support operations such as addition and deletion of vertices and edges. Each of our methods uses a kind of matrix interpolation.

In this paper, we present a framework for quality metrics that measure symmetry, that is, how faithfully a drawing of a graph displays the ground truth geometric automorphisms as symmetries. The quality metrics are based on group theory as well as geometry. More specifically, we introduce two types of symmetry quality metrics for displaying: (1) a single geometric automorphism as a symmetry (axial or rotational) and (2) a group of geometric automorphisms (cyclic or dihedral). We also present algorithms to compute the symmetry quality metrics in O(n log n) time. We validate our symmetry quality metrics using deformation experiments. We then use the metrics to evaluate existing graph layouts to compare how faithfully they display geometric automorphisms of a graph as symmetries.

In large-scale distributed systems, such as clouds, failures are rather the norm than the exception. These failures include job failures, server failures, network outage and power failure. Among them, server failures are most common. With the wide adoption of cloud computing, the impact of server failures in clouds is far greater than that in traditional computer clusters as jobs of different tenants are often co-located (multi-tenancy). In this paper, we address the problem of robust scheduling, with realistic failure modeling, to minimize such impact on the execution of (co-located) jobs. To this end, we develop four online failure-aware (FA) scheduling algorithms, FAFF-WJ, FAFF-FC, FABF-WJ and FABF-FC, considering the availability and reliability of servers. In particular, FF (First-Fit) and BF (Best-Fit) indicate how the availability of servers is checked while WJ (Waiting Job) and FC (Failure Count) differ primarily in whether the reliability is measured from job's perspective or server's perspective. All four algorithms are designed essentially by combining these availability and reliability check methods. We evaluate our scheduling algorithms with failures generated based on our failure modeling of six real-world server failure traces. Our evaluation results show the effectiveness of our scheduling algorithms in robust job execution, with respect to both performance and cost.

We introduce and study the 1-planar packing problem: Given $k$ graphs with $n$ vertices $G_1, \dots, G_k$, find a 1-planar graph that contains the given graphs as edge-disjoint spanning subgraphs. We mainly focus on the case when each $G_i$ is a tree and $k=3$. We prove that a triple consisting of three caterpillars or of two caterpillars and a path may not admit a 1-planar packing, while two paths and a special type of caterpillar always have one. We then study 1-planar packings with few crossings and prove that three paths (resp. cycles) admit a 1-planar packing with at most seven (resp. fourteen) crossings. We finally show that a quadruple consisting of three paths and a perfect matching with $n \geq 12$ vertices admits a 1-planar packing, while such a packing does not exist if $n \leq 10$.

Abstract In this paper, we present a new framework for sublinear time force computation for visualization of big complex graphs. Our algorithm is based on the sampling of vertices for computing repulsion forces and edge sparsification for attraction force computation. More specifically, for vertex sampling, we present three types of sampling algorithms, including random sampling, geometric sampling, and combinatorial sampling, to reduce the repulsion force computation to sublinear in the number of vertices. We utilize a spectral sparsification approach to reduce the number of attraction force computations to sublinear in the number of edges for dense graphs. We also present a smart initialization method based on radial tree drawing of the BFS spanning tree rooted at the center. Experiments show that our new sublinear time force computation algorithms run quite fast, while producing good visualization of large and complex networks, with significant improvements in quality metrics such as shape‐based and edge crossing metrics.

Supergraph search is one of fundamental graph query processing problems in many application domains. Given a query graph and a set of data graphs, supergraph search is to find all the data graphs contained in the query graph as subgraphs. In existing algorithms, index construction or filtering approaches are computationally expensive, and search methods can cause redundant computations. In this paper, we introduce four new concepts to address these limitations: (1) DAG integration, (2) dynamic programming between integrated DAG and graph, (3) active-first search, and (4) relevance-size order, which together lead to a much faster and scalable algorithm for supergraph search. Extensive experiments with real datasets show that our approach outperforms state-of-the-art algorithms by up to orders of magnitude in terms of indexing time and query processing time.

Distributed (computing) systems come in various sizes and scale. They range from a single workstation computer with several processors, a cluster of compute nodes (servers) to a federation of geographically distributed data centres with millions of servers. Job scheduling is a fundamental aspect for data centre efficiency. In this paper, we present ds-viz as a visualisation aid for ds-sim, a recently developed distributed systems simulator. In particular, ds-viz significantly helps leverage the evaluation and analysis of scheduling algorithms that ds-sim facilitates to design. We show the effectiveness of these tools with some examples.

In large-scale distributed systems, such as data centers resource failures are the norm rather than an exception. In this paper, we propose a holistic approach to study resource failures from resource failure modelling to distributed system simulation to failure-aware scheduling algorithm design. In particular, we present (1) a simple and yet practical way to model resource failures using real-world failure traces, (2) a new distributed systems simulator and (3) two failure-aware scheduling algorithms. These scheduling algorithms are designed primarily to validate (1) and (2). Our evaluation results demonstrate the feasibility and effectiveness of our holistic approach.

Recent work for visualizing big graphs uses a proxy graph approach: the original graph is replaced by a proxy graph, which is much smaller than the original graph. The challenge for the proxy graph approach is to ensure that the proxy graph is a good representation of the original graph. However, previous work to compute proxy graphs using graph sampling techniques often fails to preserve connectivity and important global skeletal structure in the original graph. This paper introduces two new families of proxy graph methods BCP-W and BCP-E, tightly integrating graph sampling methods with the BC (Block Cut-vertex) tree, which represents the decomposition of a graph into biconnected components. Experimental results using graph sampling quality metrics show that our new BC treebased proxy graph methods produce significantly better results than existing sampling-based proxy graph methods: 25% improvement by BCP-W and 15% by BCP-E on average. We also present DBCP, a BC tree-based proxy graph method for distributed environment. Experiments on the Amazon Cloud EC2 demonstrate that DBCP is scalable for big graph data sets; runtime speed-up of 77% for distributed 5-server on average. Visual comparison using a graph layout method and the proxy quality metrics confirm that our new BC tree-based proxy graph methods are significantly better than existing sampling-based proxy graph method. Our main results lead to guidelines for computing sampling-based proxy graphs for visualization of big graphs.

Data quality management, especially data cleansing, has been extensively studied for many years in the areas of data management and visual analytics. In the paper, we first review and explore the relevant work from the research areas of data management, visual analytics and human-computer interaction. Then for different types of data such as multimedia data, textual data, trajectory data, and graph data, we summarize the common methods for improving data quality by leveraging data cleansing techniques at different analysis stages. Based on a thorough analysis, we propose a general visual analytics framework for interactively cleansing data. Finally, the challenges and opportunities are analyzed and discussed in the context of data and humans.

We present a new multi-level graph drawing algorithm based on the k-core coarsening, a well-known cohesive subgroup analysis method in social network analysis. The k-core of a graph is also known as the degeneracy in graph theory, and can be computed in linear time. Our k-core based multi-level algorithm also includes a new concentric circle placement and a variation of force-directed layout to display the structure of graphs effectively. Experiments with real-world networks suggest that our algorithm performs well for visualization of large and complex scale-free networks, with a power-law degree distribution, a short diameter and a high clustering coefficient. Comparison with other multi-level algorithms shows that our method is fast and effective, in particular performs better than Walshaw [26] and FM3[15].

This paper introduces a new kind of geometric graph, called the degree-sensitive neighbourhood graph (dNNG), for a more precise modelling of neighbourhoods. Based on dNNG, we define better shape-based metrics and then propose a neighbourhood-driven force-directed algorithm, called NEFO, for neighbourhood faithfulness. Our evaluation on both real-world and randomly generated graphs shows that the dNNG gives more effective shape-based measures when compared to existing geometric graphs. The NEFO algorithm is shown to be effective for improving neighbourhood faithfulness of graph drawings.

Data sampling has been extensively studied for large scale graph mining. Many analyses and tasks become more efficient when performed on graph samples of much smaller size. The use of proxy objects is common in software engineering for analysis and interaction with heavy objects or systems. In this paper, we coin the term 'proxy graph' and empirically investigate how well a proxy graph visualization can represent a big graph. Our investigation focuses on proxy graphs obtained by sampling; this is one of the most common proxy approaches. Despite the plethora of data sampling studies, this is the first evaluation of sampling in the context of graph visualization. For an objective evaluation, we propose a new family of quality metrics for visual quality of proxy graphs. Our experiments cover popular sampling techniques. Our experimental results lead to guidelines for using sampling-based proxy graphs in visualization.

Curves have long been used for graph visualization with increased popularity in recent years. Curves are mainly used for two purposes: one is to increase readability and the other is to enhance visual aesthetic pleasingness. Although curves can be visually pleasing, the introduction of curves in graph drawing does not increase readability automatically. Attempts have been made to investigate the usability of curved drawings. However, the results on the effect of curves per se on human graph comprehension has not been conclusive. This paper presents a user study that is to examine the effect of curves when they are introduced to remove crossings. Twenty-six participants were recruited to perform typical graph reading tasks. Task performance and user preference data were collected for analysis. The results indicate that curves can be a useful alternative when crossings are to be present in straight-line drawings. The findings of the study are also discussed along with some of our future research activities in this paper.

Modern-day social networks are often dynamic and multi-relational, however there is currently little being studied on how to incorporate both aspects simultaneously to support visual analytic tasks for such complex social networks. We present a visual analytic framework for dynamic multi-relational networks and a prototype implementation, called the MultiStory system, which includes two new visualisation methods, AlterCluster and InterArc, designed for dynamic networks with multiple relations. The system is evaluated with two case studies using social networks from the MIT Reality Commons to demonstrate the effectiveness of the system to support a variety of visual analytical tasks on dynamic multi-relational networks.

The articles in this special issue present extended versions of the five best papers from the 2013 IEEE Pacific Visualization Symposium (PacificVis'13) which was held in Sydney, Australia from February 26 to March 1, 2013. The objective of this symposium series is to foster greater exchange between visualization researchers and practitioners, with a focus on the Asia-Pacific region.

Readability criteria have been commonly used to measure the quality of graph visualizations. In this paper we argue that readability criteria, while necessary, are not sufficient. We propose a new kind of criterion, generically termed faithfulness, for evaluating graph layout methods. We propose a general model for quantifying faithfulness, and contrast it with the well established readability criteria. We use examples of multidimensional scaling, edge bundling and several other visualization metaphors (including matrix-based and map-based visualizations) to illustrate faithfulness.

Dynamic Social network visualization transforms dynamic information in a social network into geometric representations. Most previous work in this field mainly focuses on the evolution of the overall network.

Many automatic graph drawing algorithms implement only one or two aesthetic criteria since most aesthetics conflict with each other. Empirical research has shown that although those algorithms are based on different aesthetics, drawings produced by them have comparable effectiveness. The comparable effectiveness raises a question about necessity of choosing one algorithm against another for drawing graphs when human performance is a main concern. In this paper, we argue that effectiveness can be improved when algorithms are designed by making compromises between aesthetics, rather than trying to satisfy one or two of them to the fullest. In particular, this paper presents a user study. The study compares effectiveness of drawings produced by two different force-directed methods, Classical spring algorithm and BIGANGLE. BIGANGLE produces drawings with a few aesthetics being improved at the same time. The experimental results indicate that BIGANGLE induces significantly better performance of humans in perceiving shortest paths between two nodes.

The end result of graph visualization is that people read the graph and understand the data. To make this effective, it is essential to construct visualizations based on how people read graphs. Despite the popularity and importance of graph usage in a variety of application domains, little is known about how people read graphs. The lack of this knowledge has severely limited the effectiveness of graph visualizations. In attempts to understand how people read graphs, we previously observed that people have geodesic-path tendency based on subjective eye tracking data. This paper presents two controlled experiments. One is to approve the existence of the geodesic-path tendency. The other is to examine the effects of this tendency on people in reading graphs. The results show that in performing path search tasks, when eyes encounter a node that has more than one link, links that go toward the target node are more likely to be searched first. The results also indicate that when graphs are drawn with branch links on the path leading away from the target node, graph reading performance can be significantly improved.

This paper investigates a new problem of visualizing a set of overlapping networks. We present two methods for constructing visualization of two and three overlapping networks in three dimensions. Our methods aim to achieve both drawing aesthetics (or conventions) for each individual network and exposing the common nodes between the overlapping networks. We evaluated our approaches using biological networks including protein interaction network, metabolic network, and gene regulatory network, from the bacterium Escherichia coli and crop plants to demonstrate their usefulness to support biological analysis.

In visualizing graphs as node-link diagrams, it is commonly accepted and employed as a general rule that the number of link crossings should be minimized whenever possible. However, little attention has been paid to how to handle the remaining crossings in the visualization. The study presented in this paper examines the effects of crossing angles on performance of path tracing tasks. It was found that the effect varied with the size of crossing angles. In particular, task response time decreased as the crossing angle increased. However, the rate of the decrease tended to level off when the angle was close to 90 degrees. One of the implications of this study in graph visualization is that just minimizing the crossing number is not sufficient to reduce the negative impact to the minimum. The angles of remaining crossings should be maximized as well.

Visualising large graphs faces the challenges of both data complexity and visual complexity. This paper presents a framework for visualising large graphs that reduces data complexity using the clustered graph model and provides users with navigational approaches for browsing clustered graphs. A key design task of such a system is to define a strategy for generating logical abstractions of a clustered graph during navigation. An appropriate abstraction strategy should represent a clustered graph well and avoid visual overload. The semantic fisheye view of a clustered graph is proposed for such a purpose. Two case studies were investigated, and the experiment results show that during navigation the first-order fisheye view of a clustered graph conserves visual complexity at a constant level.

Scale-free networks appear in many application domains such as social and biological networks [BA99, BB03, BO04]. Roughly speaking, scale-free networks have power-law degree distribution, ultra-short average path length and high clustering coefficient [BA99, BB03, BO04]. This paper presents new methods for visualising scale-free networks in three dimensions. To make effective use of the third dimension and minimise occlusion, we produce graph visulaisations with nodes constrained to lie on parallel planes or on the surface of spheres. We implement the algorithms using a variation of a fast force-directed graph layout method [QE00]. Results with real world data sets such as IEEE InfoVis citation and collaboration networks and a protein-protein interaction network show that our method can be useful for visual analysis of large and complex scale-free networks. We also discuss the issue of visualisation of evolving networks and network integration.

Visualizing software architecture faces the challenges of both data complexity and visual complexity. This paper presents an approach for visualizing software architecture, which reduces data complexity using the clustered graph model and navigates pictures of clustered graphs with constant visual complexity. A graph drawing algorithm is introduced to generate visualizations of clustered graphs. A semantic fisheye view of a clustered graph is proposed for conserving constant visual complexity. Animation is used to present smooth transition of visualizations. A case study is investigated to navigate the architecture of the Compiler c488.

This video describes an implementation of a three dimensional drawing algorithm for trees. The algorithm draws trees with as much symmetry as possible.