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.

Using Graph Components Derived from an Associative Concept Dictionary to Predict fMRI Neural Activation Patterns that Represent the Meaning of Nouns

In this study, we introduce an original distance definition for graphs, called the Markov-inverse-F measure (MiF). This measure enables the integration of classical graph theory indices with new knowledge pertaining to structural feature extraction from semantic networks. MiF improves the conventional Jaccard and/or Simpson indices, and reconciles both the geodesic information (random walk) and co-occurrence adjustment (degree balance and distribution). We measure the effectiveness of graph-based coefficients through the application of linguistic graph information for a neural activity recorded during conceptual processing in the human brain. Specifically, the MiF distance is computed between each of the nouns used in a previous neural experiment and each of the in-between words in a subgraph derived from the Edinburgh Word Association Thesaurus of English. From the MiF-based information matrix, a machine learning model can accurately obtain a scalar parameter that specifies the degree to which each voxel in (the MRI image of) the brain is activated by each word or each principal component of the intermediate semantic features. Furthermore, correlating the voxel information with the MiF-based principal components, a new computational neurolinguistics model with a network connectivity paradigm is created. This allows two dimensions of context space to be incorporated with both semantic and neural distributional representations.

Memory-centric VDF Graph Transformations for Practical FPGA Implementation

Realising memory intensive applications such as image and video processing on FPGA requires creation of complex, multi-level memory hierarchies to achieve real-time performance; however commerical High Level Synthesis tools are unable to automatically derive such structures and hence are unable to meet the demanding bandwidth and capacity constraints of these applications. Current approaches to solving this problem can only derive either single-level memory structures or very deep, highly inefficient hierarchies, leading in either case to one or more of high implementation cost and low performance. This paper presents an enhancement to an existing MC-HLS synthesis approach which solves this problem; it exploits and eliminates data duplication at multiple levels levels of the generated hierarchy, leading to a reduction in the number of levels and ultimately higher performance, lower cost implementations. When applied to synthesis of C-based Motion Estimation, Matrix Multiplication and Sobel Edge Detection applications, this enables reductions in Block RAM and Look Up Table (LUT) cost of up to 25%, whilst simultaneously increasing throughput.

A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph

A family of quadratic programming problems whose optimal values are upper bounds on the independence number of a graph is introduced. Among this family, the quadratic programming problem which gives the best upper bound is identified. Also the proof that the upper bound introduced by Hoffman and Lovász for regular graphs is a particular case of this family is given. In addition, some new results characterizing the class of graphs for which the independence number attains the optimal value of the above best upper bound are given. Finally a polynomial-time algorithm for approximating the size of the maximum independent set of an arbitrary graph is described and the computational experiments carried out on 36 DIMACS clique benchmark instances are reported.

Necessary and sufficient conditions for a Hamiltonian graph

A graph is singular if the zero eigenvalue is in the spectrum of its 0-1 adjacency matrix A. If an eigenvector belonging to the zero eigenspace of A has no zero entries, then the singular graph is said to be a core graph. A ( k,t)-regular set is a subset of the vertices inducing a k -regular subgraph such that every vertex not in the subset has t neighbours in it. We consider the case when k=t which relates to the eigenvalue zero under certain conditions. We show that if a regular graph has a ( k,k )-regular set, then it is a core graph. By considering the walk matrix we develop an algorithm to extract ( k,k )-regular sets and formulate a necessary and sufficient condition for a graph to be Hamiltonian.

Spectra of graphs obtained by a generalization of the join graph operation

Taking a Fiedler’s result on the spectrum of a matrix formed from two symmetric matrices as a motivation, a more general result is deduced and applied to the determination of adjacency and Laplacian spectra of graphs obtained by a generalized join graph operation on families of graphs (regular in the case of adjacency spectra and arbitrary in the case of Laplacian spectra). Some additional consequences are explored, namely regarding the largest eigenvalue and algebraic connectivity.

Gene Network Inference using Machine Learning and Graph Algorithms on Big Biomedical Data

Thesis (Master's)--University of Washington, 2016-03

A Fractional Perspective to the Bond Graph Modelling of World Economies

Inspired in dynamic systems theory and Brewer’s contributions to apply it to economics, this paper establishes a bond graph model. Two main variables, a set of inter-connectivities based on nodes and links (bonds) and a fractional order dynamical perspective, prove to be a good macro-economic representation of countries’ potential performance in nowadays globalization. The estimations based on time series for 50 countries throughout the last 50 decades confirm the accuracy of the model and the importance of scale for economic performance.

Graph usage in financial reports: Evidence from Portuguese listed companies

When assessing investment options, investors focus on the graphs of annual reports, despite lack of auditing. If poorly constructed, graphs distort perceptions and lead to inaccurate decisions. This study examines graph usage in all the companies listed on Euronext Lisbon in 2013. The findings suggest that graphs are common in the annual reports of Portuguese companies and that, while there is no evidence of Selectivity Distortion, both Measurement and Orientation Distortions are pervasive. The study recommends the auditing of financial graphs, and urges preparers and users of annual reports to be wary of the possibility of graph distortion.

Graph usage in annual reports, evidence from Norwegian listed companies

As investors and other users of annual reports often focus their attention on graphs, it is important that they portray accurate and reliable information. However, previous studies show that graphs often distort information and mislead users. This study analyses graph usage in annual reports from the 52 most traded Norwegian companies. The findings suggest that Norwegian companies commonly use graphs, and that the graph distortions, presentational enhancement and measurement distortion, are present. No evidence of selectivity was found. This study recommends development of guidelines for graphical disclosure, and advises preparers and users of annual reports to be aware of misleading graphs.

Properties and algorithms of the hyper-star graph and its related graphs

The hyper-star interconnection network was proposed in 2002 to overcome the drawbacks of the hypercube and its variations concerning the network cost, which is defined by the product of the degree and the diameter. Some properties of the graph such as connectivity, symmetry properties, embedding properties have been studied by other researchers, routing and broadcasting algorithms have also been designed. This thesis studies the hyper-star graph from both the topological and algorithmic point of view. For the topological properties, we try to establish relationships between hyper-star graphs with other known graphs. We also give a formal equation for the surface area of the graph. Another topological property we are interested in is the Hamiltonicity problem of this graph. For the algorithms, we design an all-port broadcasting algorithm and a single-port neighbourhood broadcasting algorithm for the regular form of the hyper-star graphs. These algorithms are both optimal time-wise. Furthermore, we prove that the folded hyper-star, a variation of the hyper-star, to be maixmally fault-tolerant.