Connections between Classical and Parametric Network Entropies

This paper explores relationships between classical and parametric measures of graph (or network) complexity. Classical measures are based on vertex decompositions induced by equivalence relations. Parametric measures, on the other hand, are constructed by using information functions to assign probabilities to the vertices. The inequalities established in this paper relating classical and parametric measures lay a foundation for systematic classification of entropy-based measures of graph complexity.

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.

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.

Using entropy based mean shift filter and modified watershed transform for grain segmentation

Life science research aims to continuously improve the quality and standard of human life. One of the major challenges in this area is to maintain food safety and security. A number of image processing techniques have been used to investigate the quality of food products. In this paper,we propose a new algorithm to effectively segment connected grains so that each of them can be inspected in a later processing stage. One family of the existing segmentation methods is based on the idea of watersheding, and it has shown promising results in practice.However,due to the over-segmentation issue,this technique has experienced poor performance in various applications,such as inhomogeneous background and connected targets. To solve this problem,we present a combination of two classical techniques to handle this issue.In the first step,a mean shift filter is used to eliminate the inhomogeneous background, where entropy is used to be a converging criterion. Secondly,a color gradient algorithm is used in order to detect the most significant edges, and a marked watershed transform is applied to segment cluttered objects out of the previous processing stages. The proposed framework is capable of compromising among execution time, usability, efficiency and segmentation outcome in analyzing ring die pellets. The experimental results demonstrate that the proposed approach is effectiveness and robust.

Macroscopic bound entanglement in thermal graph states

We address the presence of bound entanglement in strongly interacting spin systems at thermal equilibrium. In particular, we consider thermal graph states composed of an arbitrary number of particles. We show that for a certain range of temperatures no entanglement can be extracted by means of local operations and classical communication, even though the system is still entangled. This is found by harnessing the independence of the entanglement in some bipartitions of such states with the system's size. Specific examples for one- and two-dimensional systems are given. Our results thus prove the existence of thermal bound entanglement in an arbitrary large spin system with finite-range local interactions.

Vertex Clustering of Augmented Graph Streams

In this paper we propose a graph stream clustering algorithm with a unied similarity measure on both structural and attribute properties of vertices, with each attribute being treated as a vertex. Unlike others, our approach does not require an input parameter for the number of clusters, instead, it dynamically creates new sketch-based clusters and periodically merges existing similar clusters. Experiments on two publicly available datasets reveal the advantages of our approach in detecting vertex clusters in the graph stream. We provide a detailed investigation into how parameters affect the algorithm performance. We also provide a quantitative evaluation and comparison with a well-known offline community detection algorithm which shows that our streaming algorithm can achieve comparable or better average cluster purity.

Ultrasound entropy may be a new non-invasive measure of pre-clinical vascular damage in young hypertensive patients

Background: The identification of pre-clinical microvascular damage in hypertension by non-invasive techniques has proved frustrating for clinicians. This proof of concept study investigated whether entropy, a novel summary measure for characterizing blood velocity waveforms, is altered in participants with hypertension and may therefore be useful in risk stratification.

Methods: Doppler ultrasound waveforms were obtained from the carotid and retrobulbar circulation in 42 participants with uncomplicated grade 1 hypertension (mean systolic/diastolic blood pressure (BP) 142/92 mmHg), and 26 healthy controls (mean systolic/diastolic BP 116/69 mmHg). Mean wavelet entropy was derived from flow-velocity data and compared with traditional haemodynamic measures of microvascular function, namely the resistive and pulsatility indices.

Results: Entropy, was significantly higher in control participants in the central retinal artery (CRA) (differential mean 0.11 (standard error 0.05 cms(-1)), CI 0.009 to 0.219, p 0.017) and ophthalmic artery (0.12 (0.05), CI 0.004 to 0.215, p 0.04). In comparison, the resistive index (0.12 (0.05), CI 0.005 to 0.226, p 0.029) and pulsatility index (0.96 (0.38), CI 0.19 to 1.72, p 0.015) showed significant differences between groups in the CRA alone. Regression analysis indicated that entropy was significantly influenced by age and systolic blood pressure (r values 0.4-0.6). None of the measures were significantly altered in the larger conduit vessel.

Conclusion: This is the first application of entropy to human blood velocity waveform analysis and shows that this new technique has the ability to discriminate health from early hypertensive disease, thereby promoting the early identification of cardiovascular disease in a young hypertensive population.

Performance assessment of cascade control loopswith non-Gaussian disturbances using entropy information

Cascade control is one of the routinely used control strategies in industrial processes because it can dramatically improve the performance of single-loop control, reducing both the maximum deviation and the integral error of the disturbance response. Currently, many control performance assessment methods of cascade control loops are developed based on the assumption that all the disturbances are subject to Gaussian distribution. However, in the practical condition, several disturbance sources occur in the manipulated variable or the upstream exhibits nonlinear behaviors. In this paper, a general and effective index of the performance assessment of the cascade control system subjected to the unknown disturbance distribution is proposed. Like the minimum variance control (MVC) design, the output variances of the primary and the secondary loops are decomposed into a cascade-invariant and a cascade-dependent term, but the estimated ARMA model for the cascade control loop based on the minimum entropy, instead of the minimum mean squares error, is developed for non-Gaussian disturbances. Unlike the MVC index, an innovative control performance index is given based on the information theory and the minimum entropy criterion. The index is informative and in agreement with the expected control knowledge. To elucidate wide applicability and effectiveness of the minimum entropy cascade control index, a simulation problem and a cascade control case of an oil refinery are applied. The comparison with MVC based cascade control is also included.