A Taxonomy and Survey of Dynamic Graph Visualization

Dynamic graph visualization focuses on the challenge of representing the evolution of relationships between entities in readable, scalable and effective diagrams. This work surveys the growing number of approaches in this discipline. We derive a hierarchical taxonomy of techniques by systematically categorizing and tagging publications. While static graph visualizations are often divided into node‐link and matrix representations, we identify the representation of time as the major distinguishing feature for dynamic graph visualizations: either graphs are represented as animated diagrams or as static charts based on a timeline. Evaluations of animated approaches focus on dynamic stability for preserving the viewer's mental map or, in general, compare animated diagrams to timeline‐based ones. A bibliographic analysis provides insights into the organization and development of the field and its community. Finally, we identify and discuss challenges for future research. We also provide feedback from experts, collected with a questionnaire, which gives a broad perspective of these challenges and the current state of the field.     

Distance‐based control of formations with hybrid communication topology

In this paper, we focus on the control of multiagent formations with hybrid communication topology through a distance‐based approach. By saying hybrid topology, we mean that the communication topology contains both undirected and directed links, or the underlying graph of the formation contains both undirected and directed edges. A new type of graph, ie, hybrid graph, is introduced. We discuss the persistence of hybrid graphs and present the persistence verification strategy for hybrid graphs. It is proved that all the minimally persistent hybrid graphs can be obtained from persistent directed graphs by the operation of edge transformation. As the main result, it is shown that multiagent formations modeled by acyclic persistent hybrid graphs can be stabilized locally under distance‐based controllers.     

Visualization for Knowledge Graph Based on Education Data

Knowledge graph, also known as scienti c knowledge graph, can reveal the dynamic development rules in complex knowledge elds. How to clearly present the internal structure of knowledge graph is particularly important, however, the current visualization research based on knowledge graph is rare. In this paper, varieties of data related to education are mined from massive web data, and are fused together. Then knowledge graph which is centered on educational events is constructed utilizing extracted named entities and entity relations. We construct a visual analysis platform for education knowledge graph, EduVis, which can support users to do associated analysis of education, and enable users to obtain the public opinions. In EduVis, we design and implement a) a word cloud treemap to provide an overview of education knowledge graph, b) a layout of events relation network graph based on topological structure and timeline to explore in details, c) a click tracking path to record the history of users'' clicks and help users to backtrack. The case studies show that the aforementioned visual analysis methods for our knowledge graph can meet users'' demands for data analysis tasks.     

Visualizing the Evolution of Community Structures in Dynamic Social Networks

Social network analysis is the study of patterns of interaction between social entities. The field is attracting increasing attention from diverse disciplines including sociology, epidemiology, and behavioral ecology. An important sociological phenomenon that draws the attention of analysts is the emergence of communities, which tend to form, evolve, and dissolve gradually over a period of time. Understanding this evolution is crucial to sociologists and domain scientists, and often leads to a better appreciation of the social system under study. Therefore, it is imperative that social network visualization tools support this task. While graph‐based representations are well suited for investigating structural properties of networks at a single point in time, they appear to be significantly less useful when used to analyze gradual structural changes over a period of time. In this paper, we present an interactive visualization methodology for dynamic social networks. Our technique focuses on revealing the community structure implied by the evolving interaction patterns between individuals. We apply our visualization to analyze the community structure in the US House of Representatives. We also report on a user study conducted with the participation of behavioral ecologists working with social network datasets that depict interactions between wild animals. Findings from the user study confirm that the visualization was helpful in providing answers to sociological questions as well as eliciting new observations on the social organization of the population under study.     

基于快照的大规模动态图相似节点查询算法

动态图拓扑结构演进过程中,为了量化在一定时间域内节点间联系的变化情况,定义了一种泛相似节点的概念,通过衡量其与当前节点的联系是否频繁、分布是否均匀来确定与当前节点的泛相似程度,并提出了一种基于快照的大规模动态图泛相似节点查询处理算法。具体包括:图动态演进过程的快照集表示,即演进动态图;图动态演进过程中的节点泛相似的语义及其形式化表示方式,从联系的频繁程度与分布的均匀程度对节点的相似程度进行了刻画;节点泛相似语义的矩阵表示及处理方式;针对这种语义的泛相似节点查询处理算法。真实数据集和合成数据集上的实验结果均表明算法能够处理大规模动态图上泛相似节点的查询问题,并在实际应用中运用实现。     

Controllability of discrete‐time multiagent systems with switching topology

The current theoretical investigation on the controllability of switched multiagent systems mainly focuses on fixed connected topology or union graph without nonaccessible nodes. However, for discrete‐time multiagent systems with switching topology, it is still unknown whether the existing results are valid or not under the condition of arbitrary topology. Based on graph distance partitions and Wonham's geometric approach, we provide the lower and upper bounds for the dimension of controllable subspaces of discrete‐time multiagent systems. Unlike the existing results of controllability with switching topology, the proposed results have the advantage of being applicable to multiagent systems with arbitrary graphic topologies, union graph (strongly connected or not), and coupling weights. We also provide 2 algorithms for computing the lower and upper bounds for the dimension of controllable subspaces, respectively. Furthermore, as a remarkable application, we present how the proposed lower bound can be utilized for achieving the targeted controllability if the dimension of the controllable subspace of the switched system satisfies certain conditions.     

大规模网络安全数据协同可视分析方法研究

网络安全可视化是近年来网络安全研究的热点,它通过提供有效的信息可视化工具,提升网络安全分析师在解决网络安全问题过程中的感知和认知能力,从而发现模式、识别异常和掌握趋势。为了应对大规模、多数据源的网络安全协同可视分析需求,研究了基于统一格式的事件元组和统计元组的数据融合模型,并提出了擅长事件关联分析的雷达图和擅长统计时序对比分析的对比堆叠流图的设计方法。最后使用该原型系统对2013国际可视分析挑战赛（visual analytics science and technology challenge,VAST Challenge）中网络安全数据可视分析竞赛提供的数据集进行了分析,通过实验和讨论验证了该网络安全数据协同可视分析方法的有效性。     

多视角融合的时空动态图卷积网络城市交通流量预测

城市交通流量预测是构建绿色低碳、安全高效的智能交通系统的重要组成部分.时空图神经网络由于具有强大的时空数据表征能力,被广泛应用于城市交通流量预测.当前时空图神经网络在城市交通流量预测中仍存在以下两方面局限性:1)直接构建静态路网拓扑图对城市空间相关性进行表示,忽略了节点的动态交通模式,难以表达节点流量之间的时序相似性,无法捕获路网节点之间在时序上的动态关联.2)只考虑路网节点的局部空间相关性,忽略节点的全局空间相关性,无法建模交通路网中局部区域和全局空间之间的依赖关系.为打破上述局限性,本文提出了一种多视角融合的时空动态图卷积模型用于预测交通流量.首先,从静态空间拓扑和动态流量模式视角出发,构建路网空间结构图和动态流量关联图,并使用动态图卷积学习节点在两种视角下的特征,全面捕获城市路网中多元的空间相关性.其次,从局部视角和全局视角出发,计算路网的全局表示,将全局特征与局部特征融合,增强路网节点特征的表现力,发掘城市交通流量的整体结构特征.接下来,设计了局部卷积多头自注意力机制来获取交通数据的动态时间相关性,实现在多种时间窗口下的准确流量预测.最后,在四种真实交通数据上的实验结果证明了本文模型的有效性和准确性.     

A GRAPH‐BASED APPROACH FOR SEMISUPERVISED CLUSTERING

This paper proposes a graph‐based approach for semisupervised clustering based on pairwise relations among instances. In our approach, the entire data set is represented as an edge‐weighted graph by mapping each data element (instance) as a vertex and connecting the instances by edges with their similarities. In order to reflect pairwise constraints on the clustering process, the graph is modified by contraction as it is known from general graph theory and the graph Laplacian in spectral graph theory. The graph representation enables us to deal with pairwise constraints as well as pairwise similarities over the same unified representation. By exploiting the constraints as well as similarities among instances, the entire data set is projected onto a subspace via the modified graph, and data clustering is conducted over the projected representation. The proposed approach is evaluated over several real‐world data sets. The results are encouraging and show that it is worthwhile to pursue the proposed approach.     

基于LSTM的动态图模型异常检测算法研究

传统异常检测模型往往基于内容特征，随着攻击手段的提高，该方法易于被绕过，因此图挖掘技术逐渐成为了国内外学术研究的热点。为了提高异常检测的准确率，提出了一种基于长短时记忆网络的动态图模型异常检测算法。首先通过对动态图的变化特征进行分析，总结了Egonet图结构距离和编辑距离两类特征，高效地表示动态图结构的变化情况。其次，通过基于LSTM的时间序列分类算法，进行模型的训练。最后对抓取的网络数据流进行入侵检测，对超过6万节点和300万条边的拓扑图进行测试。最终实验结果表明，该算法具有更高的准确率和召回率，可以有效地检测出网络入侵事件。     

面向对象的图可视化系统设计与实现

阐述了一个小型图可视化系统的设计原理及方法。系统采用面向对象的方法设计并按照信息可视化模型分层架构,具有良好的可扩展性。系统支持随机布局、弹力模型、对称[1]等多种图形布局方式;并提供了对GML、DAT、TXT、自定义等多种图形数据封装格式的存取功能。     

超大幅面动态生成图形的WWW发布技术

本文分析了当前WWW动态信息发布技术，针对超大幅面动态生成图形的WWW发布，提出了一种利用Win32 CGI的解决方案。在方案中将超大幅面动态生成图形划分成若干幅易于发布的小幅图形，利用Win32 CGI控制生成这些小幅图形，同时生成显示控制页面，实现在客户端浏览器中形成超大幅面动态生成图形。文中对实现中涉及到的一些主要问题给出相应的解决方案，并对该方案的应用领域进行了初步讨论。     

基于SQL的图相似性查询方法

图作为一种表示复杂信息的数据结构,被广泛应用于社交网络,知识图谱,语义网,生物信息学和化学信息学等领域.随着各领域应用的普及和深入开展,如何管理这些复杂图数据是目前图数据库技术面临的巨大挑战.图的相似性查询是图数据管理中的热点问题之一.对图查询问题的研究主要包括图的相似性查询等.本文重点研究基于编辑距离（Graph Edit Distance）的图相似性查询处理问题.首先,通过对目前代表性的问题求解算法分析发现,其提出的过滤规则都具有自己的优缺点和适用性.其次,针对已有方法在过滤阶段自身存在优缺点和适用性的问题,提出一种全新的面向关系型数据库的过滤框架,新的过滤框架可以支持所有已有的过滤规则,从而通过结合不同的过滤规则来优化图相似查询算法以提高查询效率.该方法可以最大程度保留不同过滤规则的优点并克服其缺点,从而对不同查询具有普遍适用性.最后,基于PubChem数据集,通过比较算法在求解查询结果的时间消耗,验证本文提出算法的高效性及可扩展性,实验结果表明,本文提出的方法优于现有算法.     

Visual Analysis of Large Graphs: State‐of‐the‐Art and Future Research Challenges

The analysis of large graphs plays a prominent role in various fields of research and is relevant in many important application areas. Effective visual analysis of graphs requires appropriate visual presentations in combination with respective user interaction facilities and algorithmic graph analysis methods. How to design appropriate graph analysis systems depends on many factors, including the type of graph describing the data, the analytical task at hand and the applicability of graph analysis methods. The most recent surveys of graph visualization and navigation techniques cover techniques that had been introduced until 2000 or concentrate only on graph layouts published until 2002. Recently, new techniques have been developed covering a broader range of graph types, such as time‐varying graphs. Also, in accordance with ever growing amounts of graph‐structured data becoming available, the inclusion of algorithmic graph analysis and interaction techniques becomes increasingly important. In this State‐of‐the‐Art Report, we survey available techniques for the visual analysis of large graphs. Our review first considers graph visualization techniques according to the type of graphs supported. The visualization techniques form the basis for the presentation of interaction approaches suitable for visual graph exploration. As an important component of visual graph analysis, we discuss various graph algorithmic aspects useful for the different stages of the visual graph analysis process. We also present main open research challenges in this field.     

Automatic layout of statecharts

Graphical notations are widely used for system specification. The usefulness of these notations depends primarily on their readability. Hence, automatic methods are needed to obtain efficient and understandable graphical representations of requirements. In this paper, we present an algorithm that automatically generates layouts of statecharts. We assume that relevant information is stored in a structure that we call a decomposition tree, and we draw the graph that models a statechart in a hierarchical fashion. Our approach excludes diagrams with inter‐level transitions. Copyright © 2001 John Wiley & Sons, Ltd.     

Architecting and implementing distributed Web applications using the graph‐oriented approach

This paper presents a graph‐oriented framework, called WebGOP, for architecture modeling and programming of Web‐based distributed applications. WebGOP is based on the graph‐oriented programming (GOP) model, under which the components of a distributed program are configured as a logical graph and implemented using a set of operations defined over the graph. WebGOP reshapes GOP with a reflective object‐oriented design, which provides powerful architectural support in the World Wide Web environment. In WebGOP, the architecture graph is reified as an explicit object which itself is distributed over the network, providing a graph‐oriented context for the execution of distributed applications. The programmer can specialize the type of graph to represent a particular architecture style tailored for an application. WebGOP also has built‐in support for flexible and dynamic architectures, including both planned and unplanned dynamic reconfiguration of distributed applications. We describe the WebGOP framework, a prototypical implementation of the framework on top of SOAP, and a performance evaluation of the prototype. The prototype demonstrated the feasibility of our approach. Results of the performance evaluation showed that the overhead introduced by WebGOP over SOAP is reasonable and acceptable. Copyright © 2003 John Wiley & Sons, Ltd.     

Using combinatorial testing to build navigation graphs for dynamic web applications

Modelling a software system is often a challenging prerequisite to automatic test case generation. Modelling the navigation structure of a dynamic web application is particularly challenging because of the presence of a large number of pages that are created dynamically and the difficulty of reaching a dynamic page unless a set of appropriate input values are provided for the parameters. To address the first challenge, some form of abstraction is required to enable scalable modelling. For the second challenge, techniques are required to select appropriate input values for parameters and systematically combine them to reach new pages. This paper presents a combinatorial approach in building a navigation graph for dynamic web applications. The navigation graph can then be used to automatically generate test sequences for testing web applications. The novelty of our approach is twofold. First, we use an abstraction scheme to control the page explosion problem, where pages that are likely to have the same navigation behaviour are grouped together and are represented as a single node in the navigation graph. Second, assuming that values of individual parameters are supplied manually or generated from other techniques, we combine parameter values such that well‐defined combinatorial coverage of input parameter values is achieved. Using combinatorial coverage can significantly reduce the number of requests that have to be submitted while still achieving effective coverage of the navigation structure. We implement our combinatorial approach in a tool, Tansuo, and apply the tool on seven open‐source web applications. We evaluate the effectiveness of Tansuo's exploration process guided by t‐way coverage, for t = 1,2,3, with respect to code coverage, and find that the navigation structure exploration by Tansuo, in general, results in high code coverage (more than 80% statement coverage for most of our subject applications when dead code is removed). We compare Tansuo's effectiveness with two other navigation graph tools and find that Tansuo is more effective. Our empirical results indicate that using pairwise coverage in Tansuo results in the efficient generation of navigation graphs and effective exploration of dynamic web applications. Copyright © 2016 John Wiley & Sons, Ltd.     

A survey on dynamic graph processing on GPUs: concepts,terminologies and systems

Graphs that are used to model real-world entities with vertices and relationships among entities with edges, have proven to be a powerful tool for describing real-world problems in applications. In most real-world scenarios, entities and their relationships are subject to constant changes. Graphs that record such changes are called dynamic graphs. In recent years, the widespread application scenarios of dynamic graphs have stimulated extensive research on dynamic graph processing systems that continuously ingest graph updates and produce up-to-date graph analytics results. As the scale of dynamic graphs becomes larger, higher performance requirements are demanded to dynamic graph processing systems. With the massive parallel processing power and high memory bandwidth, GPUs become mainstream vehicles to accelerate dynamic graph processing tasks. GPU-based dynamic graph processing systems mainly address two challenges: maintaining the graph data when updates occur (i.e., graph updating) and producing analytics results in time (i.e., graph computing). In this paper, we survey GPU-based dynamic graph processing systems and review their methods on addressing both graph updating and graph computing. To comprehensively discuss existing dynamic graph processing systems on GPUs, we first introduce the terminologies of dynamic graph processing and then develop a taxonomy to describe the methods employed for graph updating and graph computing. In addition, we discuss the challenges and future research directions of dynamic graph processing on GPUs.     

Knowledge graph embeddings for dealing with concept drift in machine learning

Data stream learning has been largely studied for extracting knowledge structures from continuous and rapid data records. As data is evolving on a temporal basis, its underlying knowledge is subject to many challenges. Concept drift,¹ as one of core challenge from the stream learning community, is described as changes of statistical properties of the data over time, causing most of machine learning models to be less accurate as changes over time are in unforeseen ways. This is particularly problematic as the evolution of data could derive to dramatic change in knowledge. We address this problem by studying the semantic representation of data streams in the Semantic Web, i.e., ontology streams. Such streams are ordered sequences of data annotated with ontological vocabulary. In particular we exploit three levels of knowledge encoded in ontology streams to deal with concept drifts: i) existence of novel knowledge gained from stream dynamics, ii) significance of knowledge change and evolution, and iii) (in)consistency of knowledge evolution. Such knowledge is encoded as knowledge graph embeddings through a combination of novel representations: entailment vectors, entailment weights, and a consistency vector. We illustrate our approach on classification tasks of supervised learning. Key contributions of the study include: (i) an effective knowledge graph embedding approach for stream ontologies, and (ii) a generic consistent prediction framework with integrated knowledge graph embeddings for dealing with concept drifts. The experiments have shown that our approach provides accurate predictions towards air quality in Beijing and bus delay in Dublin with real world ontology streams.     

Flip-Book Visualization of Dynamic Graphs

Dynamic graph visualization techniques can be based on animated or static diagrams showing the evolution over time. In this paper, we apply the concept of small multiples to visually illustrate the dynamics of a graph. Node-link, adjacency matrix, and adjacency list visualizations are used as basic visual metaphors for displaying individual graphs of the sequence. For node-link diagrams, we apply edge splatting to improve readability and reduce visual clutter caused by overlaps and link crossings. Additionally, to obtain a more scalable dynamic graph visualization in the time dimension, we integrate an interactive Rapid Serial Visual Presentation (RSVP) feature to rapidly °ip between the sequences of displayed graphs, similar to the concept of flipping a book''s pages. Our visualization tool supports the focus-and-context design principle by providing an overview of a longer time sequence as small multiples in a grid while also showing a graph in focus as a large single representation in a zoomed in and more detailed view. The usefulness of the technique is illustrated in two case studies investigating a dynamic directed call graph and an evolving social network that consists of more than 1,000 undirected graphs.