Structural information content of networks: Graph entropy based on local vertex functionals

In this paper we define the structural information content of graphs as their corresponding graph entropy. This definition is based on local vertex functionals obtained by calculating-spheres via the algorithm of Dijkstra. We prove that the graph entropy and, hence, the local vertex functionals can be computed with polynomial time complexity enabling the application of our measure for large graphs. In this paper we present numerical results for the graph entropy of chemical graphs and discuss resulting properties. (C) 2007 Elsevier Ltd. All rights reserved.

Low frequency rTMS effects on sensorimotor synchronization

Previous studies using low frequency (1 Hz) rTMS over the motor and premotor cortex have examined repetitive movements, but focused either on motor aspects of performance such as movement speed, or on variability of the produced intervals. A novel question is whether TMS affects the synchronization of repetitive movements with an external cue (sensorimotor synchronization). In the present study participants synchronized finger taps with the tones of an auditory metronome. The aim of the study was to examine whether motor and premotor cortical inhibition induced by rTMS affects timing aspects of synchronization performance such as the coupling between the tap and the tone and error correction after a metronome perturbation. Metronome sequences included perturbations corresponding to a change in the duration of a single interval (phase shifts) that were either small and below the threshold for conscious perception (10 ms) or large and perceivable (50 ms). Both premotor and motor cortex stimulation induced inhibition, as reflected in a lengthening of the silent period. Neither motor nor premotor cortex rTMS altered error correction after a phase shift. However, motor cortex stimulation made participants tap closer to the tone, yielding a decrease in tap-tone asynchrony. This provides the first neurophysiological demonstration of a dissociation between error correction and tap-tone asynchrony in sensorimotor synchronization. We discuss the results in terms of current theories of timing and error correction.

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.

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.

Moving with Beats and Loops: The Structure of Auditory Events and Sensorimotor Timing

Traditionally, audio-motor timing processes have been understood as motor output from an internal clock, the speed of which is set by heard sound pulses. In contrast, this paper proposes a more ecologically-grounded approach, arguing that audio-motor processes are better characterized as performed actions on the perceived structure of auditory events. This position is explored in the context of auditory sensorimotor synchronization and continuation timing. Empirical research shows that the structure of sounds as auditory events can lead to marked differences in movement timing performance. The nature of these effects is discussed in the context of perceived action-relevance of auditory event structure. It is proposed that different forms of sound invite or support different patterns of sensorimotor timing. Hence, the temporal information in looped auditory signals is more than just the interval durations between onsets: all metronomes are not created equal. The potential implications for auditory guides in motor performance enhancement are also described.