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.

A topological algorithm for identification of structural domains of proteins

Background: Identification of the structural domains of proteins is important for our understanding of the organizational principles and mechanisms of protein folding, and for insights into protein function and evolution. Algorithmic methods of dissecting protein of known structure into domains developed so far are based on an examination of multiple geometrical, physical and topological features. Successful as many of these approaches are, they employ a lot of heuristics, and it is not clear whether they illuminate any deep underlying principles of protein domain organization. Other well-performing domain dissection methods rely on comparative sequence analysis. These methods are applicable to sequences with known and unknown structure alike, and their success highlights a fundamental principle of protein modularity, but this does not directly improve our understanding of protein spatial structure.

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.

Topological analysis of the Escherichia coli WcaJ protein reveals a new conserved configuration for the polyisoprenyl-phosphate hexose-1-phosphate transferase family

WcaJ is an Escherichia coli membrane enzyme catalysing the biosynthesis of undecaprenyl-diphosphate-glucose, the first step in the assembly of colanic acid exopolysaccharide. WcaJ belongs to a large family of polyisoprenyl-phosphate hexose-1-phosphate transferases (PHPTs) sharing a similar predicted topology consisting of an N-terminal domain containing four transmembrane helices (TMHs), a large central periplasmic loop, and a C-terminal domain containing the fifth TMH (TMH-V) and a cytosolic tail. However, the topology of PHPTs has not been experimentally validated. Here, we investigated the topology of WcaJ using a combination of LacZ/PhoA reporter fusions and sulfhydryl
labelling by PEGylation of novel cysteine residues introduced into a cysteine-less WcaJ. The results showed that the large central loop and the C-terminal tail both reside in the cytoplasm and are separated by TMH-V, which does not fully span the membrane, likely forming a "hairpin" structure. Modelling of TMH-V revealed that a highly conserved proline might contribute to a helix-break-helix structure in all PHPT members. Bioinformatic analyses show that all of these features are conserved in PHPT homologues from
Gram-negative and Gram-positive bacteria. Our data demonstrate a novel topological configuration for PHPTs, which is proposed as a signature for all members of this enzyme family

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.