Gossip: The Architecture of SpreadPlots

A spreadplot is a visualization that simultaneously shows several different views of a dataset or model. The individual views can be dynamic, can support high-interaction direct manipulation, and can be algebraically linked with each other, possibly via an underlying statistical model. Thus, when a data analyst changes the information shown in one view of a statistical model, the changes can be processed by the model and instantly represented in the other views. Spreadplots simplify the analyst's task when many different plots are relevant to the analysis at hand, as is the case in regression analysis, where there are many plots that can be used for model building and diagnosis. On the other hand, the development of a visualization involving many dynamic, highly interactive, directly manipulable graphics is not a trivial task. This article discusses a software architecture which simplifies the spreadplot developer's task. The architecture addresses the two main problems in constructing a spreadplot, simplifying the layout of the plots and structuring the communication between them.     

Differentially Private Significance Tests for Regression Coefficients

Many data producers seek to provide users access to confidential data without unduly compromising data subjects’ privacy and confidentiality. One general strategy is to require users to do analyses without seeing the confidential data; for example, analysts only get access to synthetic data or query systems that provide disclosure-protected outputs of statistical models. With synthetic data or redacted outputs, the analyst never really knows how much to trust the resulting findings. In particular, if the user did the same analysis on the confidential data, would regression coefficients of interest be statistically significant or not? We present algorithms for assessing this question that satisfy differential privacy. We describe conditions under which the algorithms should give accurate answers about statistical significance. We illustrate the properties of the proposed methods using artificial and genuine data. Supplementary materials for this article are available online.     

Activity graphs: A language for flexible consultation systems

An intelligent decision system (IDS) uses artificial intelligence principles to deliver automated, interactive decision analysis (DA) consultations. Network methods adapted from operations research underlie two key IDS components: influence diagrams and activity graphs. Influence diagrams, which are familiar to DA researchers and practitioners, represent decision problems inevent space. Activity graphs, which are introduced in this paper, represent processes inaction space. While activity graphs can represent any process, we use them as a knowledge-engineering and programming language to represent the process knowledge of skilled decision analysts in the context of a specific class of decisions. This paper defines activity graphs as an extension of directed AND-OR graphs. Anactivity tree is a directed AND-OR tree consisting of nodes, which may contain activities (small computer programs) and connectors that establish logical relationships among nodes and define logical resolution agendas. Anactivity graph is a directed, multiply connected network of activity trees. Activity graphs may involve recursion. Development of the activity graph language is motivated by our desire to enable professional decision analysts — or other experts — with limited advanced programming experience to design and build consultation systems that combine the guidance offered by protocol systems with the flexibility and generality of transaction systems. This paper defines the activity graph language in detail. A simple example illustrates key concepts. The paper also discusses our experience using a computer system that implements activity graphs for developing commercial IDSs.     

金融证券分析师投资评级数据的分析和挖掘

证券分析师为股票市场提供上市公司的信息,是股票市场上的重要角色.随着中国股市的发展,各类证券投资咨询机构发布的投资研究报告也越来越多,它们对投资者特别是机构投资者发挥着越来越大的影响.通过建立该问题的数学和统计模型,评估了证券分析师投资建议的实际效果,并通过数据挖掘方法进一步筛选出了各个行业的明星分析师.对金融证券分析师投资评级数据的深入分析和挖掘,有助于投资者更加合理有效的使用这些信息.     

Path delays in communication networks

A communication network is modelled by a weighted graph. The vertices of the graph represent stations with storage capabilities, while the edges of the graph represent communication channels (or other information processing media). Channel capacity weights are assigned to the edges of the network. The network is assumed to operate in a store-and-forward manner, so that when a channel is busy the messages directed into it are stored at the station, joining there a queue which is governed by a first-come first-served service discipline. Assuming messages, with fixed length, to arrive at random at the network, following the statistics of a Poisson point process, we calculate the statistical characteristics of the message time-delays along a path in a communication network. We solve for the steadystate distributions of the message waiting-times along the path, for the distribution of the overall message delay-time, for the average memory size requirements at the stations, as well as for other statistical characteristics of the message flow and the queueing processes along a communication path.     

Maximum matching and the game of Slither

Slither is a game played on a finite graph in which the players alternately choose edges so as to form a path. In this paper we present a strategy for Slither. The strategy depends upon an application of Edmond's maximum matching algorithm to the graph and a sequence of induced subgraphs. The strategy is practical in the sense that the amount of computation necessary has a polynomial bound.     

Graphical Sensitivity Analysis for Multidimensional Scaling

This article introduces graphical sensitivity analysis for multidimensional scaling. This new technique is designed to combat two problems associated with multidimensional scaling analyses: The possibility of local minima and the uncertainty regarding sensitivity of the solution to changes in the parameters. Graphical sensitivity analysis is currently available in ViSta-MDS, a test bed for graphical model examination. By graphically manipulating points in the solution space, analysts may examine the sensitivity of the solution to changes in the model parameters. Furthermore, the analyst may search for alternative solutions that represent local minima. An example of graphical sensitivity analysis using ViSta-MDS is described.     

Minimal comparability completions of arbitrary graphs

A transitive orientation of an undirected graph is an assignment of directions to its edges so that these directed edges represent a transitive relation between the vertices of the graph. Not every graph has a transitive orientation, but every graph can be turned into a graph that has a transitive orientation, by adding edges. We study the problem of adding an inclusion minimal set of edges to an arbitrary graph so that the resulting graph is transitively orientable. We show that this problem can be solved in polynomial time, and we give a surprisingly simple algorithm for it. We use a vertex incremental approach in this algorithm, and we also give a more general result that describes graph classes Π for which Π completion of arbitrary graphs can be achieved through such a vertex incremental approach.     

The Plot-Data Interface in Statistical Graphics

Abstract

Statistical software systems include modules for manipulating data sets, model fitting, and graphics. Because plots display data, and models are fit to data, both the model-fitting and graphics modules depend on the data. Today's statistical environments allow the analyst to choose or even build a suitable data structure for storing the data and to implement new kinds of plots. The multiplicity problem caused by many plot varieties and many data representations is avoided by constructing a plot-data interface. The interface is a convention by which plots communicate with data sets, allowing plots to be independent of the actual data representation. This article describes the components of such a plot-data interface. The same strategy may be used to deal with the dependence of model-fitting procedures on data.     

Some geometrical aspects of a maximal three-coloured triangle-free graph

A three-coloured triangle-free complete graph with 16 vertices is constructed in an ad hoc manner. The edges of one colour in the complete graph, with the 16 vertices, form a Greenwood-Gleason graph, which can be regarded as the edges and diagonals of a hypercube in four dimensions, and which also has a representation as a graph in five dimensions all of whose automorphisms are isometries. In the complete graph, the blue edges form 40 quadrilaterals; 20 of these have red diagonals, and these 20 “red quadrilaterals,” meeting along 40 edges and at 16 vertices, represent a topological surface of characteristic ?4, a Klein bottle with two handles. This surface can be represented using a tessellation of regular quadrilaterals in the hyperbolic plane. To obtain the only other three-coloured triangle-free complete graph with 16 vertices some of the blue and red edges are interchanged in a way that can be described very simply using either the surface of characteristic ?4 or the hyperbolic tessellation.     

Implementation of parallel branch-and-bound algorithms – experiences with the graph partitioning problem

Parallel processing is one of the essential concepts in the attempts to increase the computational power available for solving continuous and discrete optimization problems. In the case where an optimization algorithm is search-based, crucial issues of parallel distributed implementations are work-load distribution and granularity, i.e. how to distribute the search space among processors and how to control the amount of processing between interprocessor communication. The present paper compares distributed implementations of two branch-and-bound algorithms for the graph partitioning problem: Given an undirected graph with an even number of edges and weights assigned to each edge, partition the vertices into two subsets of equal size such that the sum of the costs of edges connecting vertices in different subsets is as small as possible. The problem is known to be NP-complete. The two branch-and-bound methods compared differ in design strategy: One is based on time-consuming bound calculations leading to tight bounds and thus a narrow search tree with few nodes, whereas the other employs an easy bound calculation scheme leading to a larger search tree. Both have been implemented on an iPSC-hypercube with 32 processors. We investigate the influence of the design strategy on the performance of the algorithms.     

On Erdős's Eulerian Trail Game

 Paul Erdős proposed the following graph game. Starting with the empty graph on n vertices, two players, Trailmaker and Breaker, draw edges alternatingly. Each edge drawn has to start at the endpoint of the previously drawn edge, so the sequence of edges defines a trail. The game ends when it is impossible to continue the trail, and Trailmaker wins if the trail is eulerian. For all values of n, we determine which player has a winning strategy. Received: November 6, 1996 / Revised: May 2, 1997     

Nuclei for totally point determining graphs

The nucleus (edge nucleus) of a point determining graph is defined by Geoffroy and Sumner to be the set of all points (edges) whose removal leaves the graph point determining. It is the purpose of this paper to develop the analogous concepts for totally point determining graphs, that is, graphs in which distinct points have distinct neighborhoods and closed neighborhoods.     

Valuating residential real estate using parametric programming

When the estimation of the single equation multiple linear regression model is looked upon as an optimization problem, we show how the principles and methods of optimization can assist the analyst in finding an attractive prediction model. We illustrate this with the estimation of a linear prediction model for valuating residential property using regression quantiles. We make use of the linear parametric programming formulation to obtain the family of regression quantile models associated with a data set. We use the principle of dominance to reduce the number of models for consideration in the search for the most preferred property valuation model (s). We also provide useful displays that assist the analyst and the decision maker in selecting the final model (s). The approach is an interface between data analysis and operations research.     

GLOUDS: Representing tree-like graphs

The Graph Level Order Unary Degree Sequence (GLOUDS) is a new succinct data structure for directed graphs that are “tree-like,” in the sense that the number of “additional” edges (w.r.t. a spanning tree) is not too high. The algorithmic idea is to represent a BFS-spanning tree of the graph (consisting of n nodes) with a well known succinct data structure for trees, named LOUDS, and enhance it with additional information that accounts for the non-tree edges. In practical tests, our data structure performs well for graphs containing up to $m=5n$ edges, while still having competitive running times for listing adjacent nodes.     

An interactive graphical method for community detection in network data

The detection of community structures within network data is a type of graph analysis with increasing interest across a broad range of disciplines. In a network, communities represent clusters of nodes that exhibit strong intra-connections or relationships among nodes in the cluster. Current methodology for community detection often involves an algorithmic approach, and commonly partitions a graph into node clusters in an iterative manner before some stopping criterion is met. Other statistical approaches for community detection often require model choices and prior selection in Bayesian analyses, which are difficult without some amount of data inspection and pre-processing. Because communities are often fuzzily-defined human concepts, an alternative approach is to leverage human vision to identify communities. The work presents a tool for community detection in form of a web application, called gravicom, which facilitates the detection of community structures through visualization and direct user interaction. In the process of detecting communities, the gravicom application can serve as a standalone tool or as a step to potentially initialize (and/or post-process) another community detection algorithm. In this paper we discuss the design of gravicom and demonstrate its use for community detection with several network data sets. An “Appendix” describes details in the technical formulation of this web application built on the R package Shiny and the JavaScript library D3.     

Odd Crossing Number and Crossing Number Are Not the Same

The crossing number of a graph is the minimum number of edge intersections in a plane drawing of a graph, where each intersection is counted separately. If instead we count the number of pairs of edges that intersect an odd number of times, we obtain the odd crossing number. We show that there is a graph for which these two concepts differ, answering a well-known open question on crossing numbers. To derive the result we study drawings of maps (graphs with rotation systems).     

Victorian statistical graphics and the iconography of Florence Nightingale's polar area graph

The popular iconic image of Florence Nightingale as the ‘Lady with the Lamp’, who administered acute nursing care to the casualties during the Crimean War, belies a more integrated approach to Nightingale's nursing, which was shaped by her use of evidence-based medicine, promulgated in her statistical reports, books and papers. This image thus undermines Nightingale's prodigious statistical work and her innovative statistical graphs that led to major health reforms in military and civilian hospitals, usually with the full support of the government. It was this empirically based strategy that enabled her to establish the necessary and essential nursing and hospital reforms, which modernized nursing in the mid- to late-Victorian period. This paper will examine the mathematical and statistical graphs that arose in the nineteenth century, which influenced Nightingale's use of statistical graphs. The iconography of her polar area graph, which was based on the mortality rates of British soldiers during the Crimean War, will also be assessed. It will be shown that Nightingale's role in promoting this graph helped to establish its iconic status, as did her introduction of new elements into the ordinary polar area graph.     

Paths, trees and matchings under disjunctive constraints

We study the minimum spanning tree problem, the maximum matching problem and the shortest path problem subject to binary disjunctive constraints: A negative disjunctive constraint states that a certain pair of edges cannot be contained simultaneously in a feasible solution. It is convenient to represent these negative disjunctive constraints in terms of a so-called conflict graph whose vertices correspond to the edges of the underlying graph, and whose edges encode the constraints.We prove that the minimum spanning tree problem is strongly NP-hard, even if every connected component of the conflict graph is a path of length two. On the positive side, this problem is polynomially solvable if every connected component is a single edge (that is, a path of length one). The maximum matching problem is NP-hard for conflict graphs where every connected component is a single edge.Furthermore we will also investigate these graph problems under positive disjunctive constraints: In this setting for certain pairs of edges, a feasible solution must contain at least one edge from every pair. We establish a number of complexity results for these variants including APX-hardness for the shortest path problem.