Comparing large graphs efficiently by margins of feature vectors

Measuring the structural similarity of graphs is a challenging and outstanding problem. Most of the classical approaches of the so-called exact graph matching methods are based on graph or subgraph isomorphic relations of the underlying graphs. In contrast to these methods in this paper we introduce a novel approach to measure the structural similarity of directed and undirected graphs that is mainly based on margins of feature vectors representing graphs. We introduce novel graph similarity and dissimilarity measures, provide some properties and analyze their algorithmic complexity. We find that the computational complexity of our measures is polynomial in the graph size and, hence, significantly better than classical methods from, e.g. exact graph matching which are NP-complete. Numerically, we provide some examples of our measure and compare the results with the well-known graph edit distance. (c) 2006 Elsevier Inc. All rights reserved.

The Computational Complexity of Dominance and Consistency in CP-Nets

We investigate the computational complexity of testing dominance and consistency in CP-nets. Previously, the complexity of dominance has been determined for restricted classes in which the dependency graph of the CP-net is acyclic. However, there are preferences of interest that define cyclic dependency graphs; these are modeled with general CP-nets. In our main results, we show here that both dominance and consistency for general CP-nets are PSPACE-complete. We then consider the concept of strong dominance, dominance equivalence and dominance incomparability, and several notions of optimality, and identify the complexity of the corresponding decision problems. The reductions used in the proofs are from STRIPS planning, and thus reinforce the earlier established connections between both areas.

Use of data dependence graphs in the design of bit-level systolic arrays

The use of bit-level systolic array circuits as building blocks in the construction of larger word-level systolic systems is investigated. It is shown that the overall structure and detailed timing of such systems may be derived quite simply using the dependence graph and cut-set procedure developed by S. Y. Kung (1988). This provides an attractive and intuitive approach to the bit-level design of many VLSI signal processing components. The technique can be applied to ripple-through and partly pipelined circuits as well as fully systolic designs. It therefore provides a means of examining the relative tradeoff between levels of pipelining, chip area, power consumption, and throughput rate within a given VLSI design.

Organizational assessment in paediatric primary care:Development and initial validation of the primary care organizational questionnaire

Primary care in the United States is undergoing many changes. Reliable and valid instruments are needed to assess the effects of these changes. The Primary Care Organizational Questionnaire (PCOQ), a 56-item 5-point Likert scale survey that evaluates interactions among members of the clinic/practice and job-related attributes, was administered to clinicians and staff in 36 primary care practices serving paediatric populations in Connecticut. A priori scales were reliable (Cronbach alpha =0.7). Analysis of variance (ANOVA) showed greater heterogeneity across clinics than within clinics for 13 of 15 a priori scales, which were then included in a principal component factor analysis with varimax rotation. Eigenvalue analysis showed nine significant factors, largely similar to the a priori scales, indicating concurrent construct validity. Further research will ascertain the utility of the PCOQ in predicting the effectiveness of primary care practices in implementing disease management programmes. © 2006 Royal Society of Medicine Press.

The structure of compact disjointness preserving operators on continuous functions

Let T be a compact disjointness preserving linear operator from C0(X) into C0(Y), where X and Y are locally compact Hausdorff spaces. We show that T can be represented as a norm convergent countable sum of disjoint rank one operators. More precisely, T = Snd ?hn for a (possibly finite) sequence {xn }n of distinct points in X and a norm null sequence {hn }n of mutually disjoint functions in C0(Y). Moreover, we develop a graph theoretic method to describe the spectrum of such an operator

On the Condition Number Distribution of Complex Wishart Matrices

This paper investigates the distribution of the condition number of complex Wishart matrices. Two closely related measures are considered: the standard condition number (SCN) and the Demmel condition number (DCN), both of which have important applications in the context of multiple-input multipleoutput (MIMO) communication systems, as well as in various branches of mathematics. We first present a novel generic framework for the SCN distribution which accounts for both central and non-central Wishart matrices of arbitrary dimension. This result is a simple unified expression which involves only a single scalar integral, and therefore allows for fast and efficient computation. For the case of dual Wishart matrices, we derive new exact polynomial expressions for both the SCN and DCN distributions. We also formulate a new closed-form expression for the tail SCN distribution which applies for correlated central Wishart matrices of arbitrary dimension and demonstrates an interesting connection to the maximum eigenvalue moments of Wishart matrices of smaller dimension. Based on our analytical results, we gain valuable insights into the statistical behavior of the channel conditioning for various MIMO fading scenarios, such as uncorrelated/semi-correlated Rayleigh fading and Ricean fading. © 2010 IEEE.

The Forgiving Graph: a distributed data structure for low stretch under adversarial attack

We consider the problem of self-healing in peer-to-peer networks that are under repeated attack by an omniscient adversary. We assume that, over a sequence of rounds, an adversary either inserts a node with arbitrary connections or deletes an arbitrary node from the network. The network responds to each such change by quick “repairs,” which consist of adding or deleting a small number of edges. These repairs essentially preserve closeness of nodes after adversarial deletions, without increasing node degrees by too much, in the following sense. At any point in the algorithm, nodes v and w whose distance would have been l in the graph formed by considering only the adversarial insertions (not the adversarial deletions), will be at distance at most l log n in the actual graph, where n is the total number of vertices seen so far. Similarly, at any point, a node v whose degree would have been d in the graph with adversarial insertions only, will have degree at most 3d in the actual graph. Our distributed data structure, which we call the Forgiving Graph, has low latency and bandwidth requirements. The Forgiving Graph improves on the Forgiving Tree distributed data structure from Hayes et al. (2008) in the following ways: 1) it ensures low stretch over all pairs of nodes, while the Forgiving Tree only ensures low diameter increase; 2) it handles both node insertions and deletions, while the Forgiving Tree only handles deletions; 3) it requires only a very simple and minimal initialization phase, while the Forgiving Tree initially requires construction of a spanning tree of the network.

Analysis of Load Impact on Small-signal Stability based on Load Active Power Sensitivity

While load flow conditions vary with different loads, the small-signal stability of the entire system is closely related with to the locations, capacities and models of loads. In this paper, load impacts with different capacities and models on the small-signal stability are analysed. In the real large-scale power system case, the load sensitivity which denotes the sensitivity of the eigenvalue with respect to the load active power is introduced and applied to rank the loads. The loads with high sensitivity are also considered.

Adaptive linear combination of heuristic orderings in constructing examination timetables

In this paper, we investigate adaptive linear combinations of graph coloring heuristics with a heuristic modifier to address the examination timetabling problem. We invoke a normalisation strategy for each parameter in order to generalise the specific problem data. Two graph coloring heuristics were used in this study (largest degree and saturation degree). A score for the difficulty of assigning each examination was obtained from an adaptive linear combination of these two heuristics and examinations in the list were ordered based on this value. The examinations with the score value representing the higher difficulty were chosen for scheduling based on two strategies. We tested for single and multiple heuristics with and without a heuristic modifier with different combinations of weight values for each parameter on the Toronto and ITC2007 benchmark data sets. We observed that the combination of multiple heuristics with a heuristic modifier offers an effective way to obtain good solution quality. Experimental results demonstrate that our approach delivers promising results. We conclude that this adaptive linear combination of heuristics is a highly effective method and simple to implement.

Analysis of Dependence Tracking Algorithms for Task Dataflow Execution

Processor architectures has taken a turn towards many-core processors, which integrate multiple processing cores on a single chip to increase overall performance, and there are no signs that this trend will stop in the near future. Many-core processors are harder to program than multi-core and single-core processors due to the need of writing parallel or concurrent programs with high degrees of parallelism. Moreover, many-cores have to operate in a mode of strong scaling because of memory bandwidth constraints. In strong scaling increasingly finer-grain parallelism must be extracted in order to keep all processing cores busy.

Task dataflow programming models have a high potential to simplify parallel program- ming because they alleviate the programmer from identifying precisely all inter-task de- pendences when writing programs. Instead, the task dataflow runtime system detects and enforces inter-task dependences during execution based on the description of memory each task accesses. The runtime constructs a task dataflow graph that captures all tasks and their dependences. Tasks are scheduled to execute in parallel taking into account dependences specified in the task graph.

Several papers report important overheads for task dataflow systems, which severely limits the scalability and usability of such systems. In this paper we study efficient schemes to manage task graphs and analyze their scalability. We assume a programming model that supports input, output and in/out annotations on task arguments, as well as commutative in/out and reductions. We analyze the structure of task graphs and identify versions and generations as key concepts for efficient management of task graphs. Then, we present three schemes to manage task graphs building on graph representations, hypergraphs and lists. We also consider a fourth edge-less scheme that synchronizes tasks using integers. Analysis using micro-benchmarks shows that the graph representation is not always scalable and that the edge-less scheme introduces least overhead in nearly all situations.

The Forgiving Graph:A distributed data structure for low stretch under adversarial attack

We consider the problem of self-healing in peer-to-peer networks that are under repeated attack by an omniscient adversary. We assume that, over a sequence of rounds, an adversary either inserts a node with arbitrary connections or deletes an arbitrary node from the network. The network responds to each such change by quick "repairs," which consist of adding or deleting a small number of edges. These repairs essentially preserve closeness of nodes after adversarial deletions,without increasing node degrees by too much, in the following sense. At any point in the algorithm, nodes v and w whose distance would have been - in the graph formed by considering only the adversarial insertions (not the adversarial deletions), will be at distance at most - log n in the actual graph, where n is the total number of vertices seen so far. Similarly, at any point, a node v whose degreewould have been d in the graph with adversarial insertions only, will have degree at most 3d in the actual graph. Our distributed data structure, which we call the Forgiving Graph, has low latency and bandwidth requirements. The Forgiving Graph improves on the Forgiving Tree distributed data structure from Hayes et al. (2008) in the following ways: 1) it ensures low stretch over all pairs of nodes, while the Forgiving Tree only ensures low diameter increase; 2) it handles both node insertions and deletions, while the Forgiving Tree only handles deletions; 3) it requires only a very simple and minimal initialization phase, while the Forgiving Tree initially requires construction of a spanning tree of the network. © Springer-Verlag 2012.

Overcoming the Scalability Challenges of Epidemic Simulations on Blue Waters

Modeling dynamical systems represents an important application class covering a wide range of disciplines including but not limited to biology, chemistry, finance, national security, and health care. Such applications typically involve large-scale, irregular graph processing, which makes them difficult to scale due to the evolutionary nature of their workload, irregular communication and load imbalance. EpiSimdemics is such an application simulating epidemic diffusion in extremely large and realistic social contact networks. It implements a graph-based system that captures dynamics among co-evolving entities. This paper presents an implementation of EpiSimdemics in Charm++ that enables future research by social, biological and computational scientists at unprecedented data and system scales. We present new methods for application-specific processing of graph data and demonstrate the effectiveness of these methods on a Cray XE6, specifically NCSA's Blue Waters system.