1,720,999 research outputs found
st-Orientations with Few Transitive Edges
No full textThe problem of orienting the edges of an undirected graph such that the resulting digraph is acyclic and has a single source s and a single sink t has a long tradition in graph theory and is central to many graph drawing algorithms. Such an orientation is called an st-orientation. We address the problem of computing storientations of undirected graphs with the minimum number of transitive edges. We prove that the problem is NP-hard in the general case. For planar graphs we describe an ILP (Integer Linear Programming) model that is fast in practice, namely it takes on average less than 1 second for graphs with up to 100 vertices, and about 10 seconds for larger instances with up to 1000 vertices. We experimentally show that optimum solutions significantly reduce (35% on average) the number of transitive edges with respect to unconstrained st-orientations computed via classical st-numbering algorithms. Moreover, focusing on popular graph drawing algorithms that apply an st-orientation as a preliminary step, we show that reducing the number of transitive edges leads to drawings that are much more compact (with an improvement between 30% and 50% for most of the instances)
Placing Arrows in Directed Graph Layouts: Algorithms and Experiments
No full textWe study how to place arrow heads in directed graph drawings aiming at minimizing their overlaps and avoiding intersections between arrow heads and edges. The objective is to support users to correctly and quickly recognize edge orientations, i.e. to deduce unambiguously the edge orientations. Our contribution is two-fold: (i) We present exact and heuristic algorithms for this arrow placement problem, along with an extensive experimental analysis of these techniques; and (ii) we report on a user study aimed to understand the impact of different arrow placement strategies on performing global and local analysis tasks on directed graph layouts
ChordLink: A New Hybrid Visualization Model
No full textMany real-world networks are globally sparse but locally dense. Typical examples are social networks, biological networks, and information networks. This double structural nature makes it difficult to adopt a homogeneous visualization model that clearly conveys an overview of the network and the internal structure of its communities at the same time. As a consequence, the use of hybrid visualizations has been proposed. For instance, NodeTrix combines node-link and matrix-based representations (Henry et al., 2007). In this paper we describe ChordLink, a hybrid visualization model that embeds chord diagrams, used to represent dense subgraphs, into a node-link diagram, which shows the global network structure. The visualization is intuitive and makes it possible to interactively highlight the structure of a community while keeping the rest of the layout stable. We discuss the intriguing algorithmic challenges behind the ChordLink model, present a prototype system, and illustrate case studies on real-world networks
Efficient and trustworthy decision making through human-in-the-loop visual analytics: A case study on tax risk assessment | Processi decisionali efficienti e affidabili tramite analisi visuale con metodologia human-in-the-loop: un caso di studio sulla valutazione del rischio fiscale
No full textIl data mining e l'intelligenza artificiale sono sempre più utilizzati nell'analisi dei dati. L'ideale sarebbe ottenere un'automazione completa, ma in molte applicazioni ciò comporta rischi significativi. In questi casi è necessario il coinvolgimento diretto di analisti umani per raffinare l'analisi o per prendere le decisioni finali. Un problema rilevante è quindi come garantire un processo decisionale efficiente e affidabile nel quale gli esseri umani sono parte integrante del processo di analisi. Proponiamo una metodologia human-in-the-loop che sfrutta il data mining, il machine learning, e la visualizzazione per migliorare il processo di analisi. Un elemento chiave è l'uso di una dashboard visuale intuitiva, di supporto all'individuazione di relazioni e pattern di dati nascosti. Come caso di studio, descriviamo un'applicazione di questa metodologia per l'analisi del rischio fiscale nell'ambito delle attività dell’Agenzia delle Entrate.Data mining and AI techniques are increasingly being used to automate data analysis. Ideally, one may wish to completely automate the data analysis process, but in many real-world applications a full automation may pose significant risks. In these cases, human analysts must be directly involved to refine the analysis or to make the final decisions. A challenging problem, therefore, is how to perform efficient and trustworthy decision-making when humans are an integral part of the analysis pipeline. We propose a "human-in-the-loop" methodology that leverages data mining, machine learning, and visual analytics to improve and speed up the analysis. A key feature is the use of a dashboard that integrates intuitive visual tools, which aid analysts to efficiently discover hidden data patterns or to get helpful insights. We describe in particular how this methodology has been successfully applied to support Revenue Agency officers in tax risk assessment
Computing Bend-Minimum Orthogonal Drawings of Plane Series–Parallel Graphs in Linear Time
No full textA planar orthogonal drawing of a planar 4-graph G (i.e., a planar graph with vertex-degree at most four) is a crossing-free drawing that maps each vertex of G to a distinct point of the plane and each edge of G to a polygonal chain consisting of horizontal and vertical segments. A longstanding open question in Graph Drawing, dating back over 30 years, is whether there exists a linear-time algorithm to compute an orthogonal drawing of a plane 4-graph with the minimum number of bends. The term “plane” indicates that the input graph comes together with a planar embedding, which must be preserved by the drawing (i.e., the drawing must have the same set of faces as the input graph). In this paper we positively answer the question above for the widely-studied class of series–parallel graphs. Our linear-time algorithm is based on a characterization of the planar series–parallel graphs that admit an orthogonal drawing without bends. This characterization is given in terms of the orthogonal spirality that each type of triconnected component of the graph can take; the orthogonal spirality of a component measures how much that component is “rolled-up” in an orthogonal drawing of the graph
A User Study on Hybrid Graph Visualizations
No full textHybrid visualizations mix different metaphors in a single layout of a network. In particular, the popular NodeTrix model, introduced by Henry, Fekete, and McGuffin in 2007, combines node-link diagrams and matrix-based representations to support the analysis of real-world networks that are globally sparse but locally dense. That idea inspired a series of works, proposing variants or alternatives to NodeTrix. We present a user study that compares the classical node-link model and three hybrid visualization models designed to work on the same types of networks. The results of our study provide interesting indications about advantages/drawbacks of the considered models on performing classical tasks of analysis. At the same time, our experiment has some limitations and opens up to further research on the subject
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
