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.

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.

Goal Recognition through Goal Graph Analysis

We present a novel approach to goal recognition based on a two-stage paradigm of graph construction and analysis. First, a graph structure called a Goal Graph is constructed to represent the observed actions, the state of the world, and the achieved goals as well as various connections between these nodes at consecutive time steps. Then, the Goal Graph is analysed at each time step to recognise those partially or fully achieved goals that are consistent with the actions observed so far. The Goal Graph analysis also reveals valid plans for the recognised goals or part of these goals. Our approach to goal recognition does not need a plan library. It does not suffer from the problems in the acquisition and hand-coding of large plan libraries, neither does it have the problems in searching the plan space of exponential size. We describe two algorithms for Goal Graph construction and analysis in this paradigm. These algorithms are both provably sound, polynomial-time, and polynomial-space. The number of goals recognised by our algorithms is usually very small after a sequence of observed actions has been processed. Thus the sequence of observed actions is well explained by the recognised goals with little ambiguity. We have evaluated these algorithms in the UNIX domain, in which excellent performance has been achieved in terms of accuracy, efficiency, and scalability.

Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems

In this paper, we present a random iterative graph based hyper-heuristic to produce a collection of heuristic sequences to construct solutions of different quality. These heuristic sequences can be seen as dynamic hybridisations of different graph colouring heuristics that construct solutions step by step. Based on these sequences, we statistically analyse the way in which graph colouring heuristics are automatically hybridised. This, to our knowledge, represents a new direction in hyper-heuristic research. It is observed that spending the search effort on hybridising Largest Weighted Degree with Saturation Degree at the early stage of solution construction tends to generate high quality solutions. Based on these observations, an iterative hybrid approach is developed to adaptively hybridise these two graph colouring heuristics at different stages of solution construction. The overall aim here is to automate the heuristic design process, which draws upon an emerging research theme on developing computer methods to design and adapt heuristics automatically. Experimental results on benchmark exam timetabling and graph colouring problems demonstrate the effectiveness and generality of this adaptive hybrid approach compared with previous methods on automatically generating and adapting heuristics. Indeed, we also show that the approach is competitive with the state of the art human produced methods.

Compact Toffoli gate using weighted graph states

We introduce three compact graph states that can be used to perform a measurement-based Toffoli gate. Given a weighted graph of six, seven, or eight qubits, we show that success probabilities of 1/4, 1/2, and 1, respectively, can be achieved. Our study puts a measurement-based version of this important quantum logic gate within the reach of current experiments. As the graphs are setup independent, they could be realized in a variety of systems, including linear optics and ion traps.

Tetrahedra and vertex-sharing double tetrahedra in the ammonium iodomercurates(II) (NH4)(7)[HgI4](2)[Hg2I7](H2O) and (NH4)(3)[Hg2I7]

The new ammonium iodomercurates(II), (NH4)(7)[HgI4](2)[Hg2I7](H2O) (1) and (NH4)(3)[Hg2I7] (2) contain isolated tetrahedra and vertex-sharing double tetrahedra as the anions. The crystal structures were determined from single-crystal X-ray diffraction data: 1: orthorhombic, Pnma (no. 62), a = 2175.9(2), b = 1781.8(2), c = 1256.2(2) pm, Z = 4. R-1 [I-0 > 2 sigma(I-0)] = 0.0520; 2: monoclinic, P2(1)/c (no. 14), a = 1259.0(2), b = 773.2(1), c = 2172.4(3) pm, beta = 101.18(2)degrees, Z = 4, R, [I-0 > 2 sigma(I-0)] = 0.0308.

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.

New Financial Elites, or Financial Dualism in Historical perspective? An Extended Reply to Folkman, Froud, Johal and Williams

This paper challenges the recent suggestion that a new financial elite has evolved which is able to capture substantial profit shares for itself. Specifically, it questions the assumption that new groups of financial intermediaries have increased in significance primarily because there is evidence that various types of financial speculators have played a similarly extensive role at several junctures of economic development. The paper then develops the alternative hypothesis that, rather than being a recent development, the rise of these financial intermediaries is a cyclical phenomenon which is linked to specific regimes of capital accumulation. The hypothesis is underpinned by historical data from the US National Income and Product Accounts for the period from 1930 to 2000, which suggest that the activities of `mainstream' financial intermediaries have been accompanied by the frequently countercyclical activities of a `speculative' sector of security and commodity brokers. Based on the combination of this qualitative and quantitative evidence, the paper concludes that the rise of a speculative financial sector is a potentially recurrent phenomenon which is linked to periods of economic restructuring and turmoil.