Fusion rule algebras from graph theory
NASA Astrophysics Data System (ADS)
Caselle, M.; Ponzano, G.
1989-06-01
We describe a new class of fusion algebras related to graph theory which bear intriguing connections with group algebras. The structure constants and the matrix S, which diagonalizes the fusion rules, are explicitly computed in terms of SU(2) coupling coefficients.
Pattern vectors from algebraic graph theory.
Wilson, Richard C; Hancock, Edwin R; Luo, Bin
2005-07-01
Graph structures have proven computationally cumbersome for pattern analysis. The reason for this is that, before graphs can be converted to pattern vectors, correspondences must be established between the nodes of structures which are potentially of different size. To overcome this problem, in this paper, we turn to the spectral decomposition of the Laplacian matrix. We show how the elements of the spectral matrix for the Laplacian can be used to construct symmetric polynomials that are permutation invariants. The coefficients of these polynomials can be used as graph features which can be encoded in a vectorial manner. We extend this representation to graphs in which there are unary attributes on the nodes and binary attributes on the edges by using the spectral decomposition of a Hermitian property matrix that can be viewed as a complex analogue of the Laplacian. To embed the graphs in a pattern space, we explore whether the vectors of invariants can be embedded in a low-dimensional space using a number of alternative strategies, including principal components analysis (PCA), multidimensional scaling (MDS), and locality preserving projection (LPP). Experimentally, we demonstrate that the embeddings result in well-defined graph clusters. Our experiments with the spectral representation involve both synthetic and real-world data. The experiments with synthetic data demonstrate that the distances between spectral feature vectors can be used to discriminate between graphs on the basis of their structure. The real-world experiments show that the method can be used to locate clusters of graphs. PMID:16013758
K-theory of locally finite graph C∗-algebras
NASA Astrophysics Data System (ADS)
Iyudu, Natalia
2013-09-01
We calculate the K-theory of the Cuntz-Krieger algebra OE associated with an infinite, locally finite graph, via the Bass-Hashimoto operator. The formulae we get express the Grothendieck group and the Whitehead group in purely graph theoretic terms. We consider the category of finite (black-and-white, bi-directed) subgraphs with certain graph homomorphisms and construct a continuous functor to abelian groups. In this category K0 is an inductive limit of K-groups of finite graphs, which were calculated in Cornelissen et al. (2008) [3]. In the case of an infinite graph with the finite Betti number we obtain the formula for the Grothendieck group K0(OE)=Z, where β(E) is the first Betti number and γ(E) is the valency number of the graph E. We note that in the infinite case the torsion part of K0, which is present in the case of a finite graph, vanishes. The Whitehead group depends only on the first Betti number: K1(OE)=Z. These allow us to provide a counterexample to the fact, which holds for finite graphs, that K1(OE) is the torsion free part of K0(OE).
Hard-core lattice bosons: new insights from algebraic graph theory
NASA Astrophysics Data System (ADS)
Squires, Randall W.; Feder, David L.
2014-03-01
Determining the characteristics of hard-core lattice bosons is a problem of long-standing interest in condensed matter physics. While in one-dimensional systems the ground state can be formally obtained via a mapping to free fermions, various properties (such as correlation functions) are often difficult to calculate. In this work we discuss the application of techniques from algebraic graph theory to hard-core lattice bosons in one dimension. Graphs are natural representations of many-body Hamiltonians, with vertices representing Fock basis states and edges representing matrix elements. We prove that the graphs for hard-core bosons and non-interacting bosons have identical connectivity; the only difference is the existence of edge weights. A formal mapping between the two is therefore possible by manipulating the graph incidence matrices. We explore the implications of these insights, in particular the intriguing possibility that ground-state properties of hard-core bosons can be calculated directly from those of non-interacting bosons.
Chen, J.; Safro, I.
2011-01-01
Measuring the connection strength between a pair of vertices in a graph is one of the most important concerns in many graph applications. Simple measures such as edge weights may not be sufficient for capturing the effects associated with short paths of lengths greater than one. In this paper, we consider an iterative process that smooths an associated value for nearby vertices, and we present a measure of the local connection strength (called the algebraic distance; see [D. Ron, I. Safro, and A. Brandt, Multiscale Model. Simul., 9 (2011), pp. 407-423]) based on this process. The proposed measure is attractive in that the process is simple, linear, and easily parallelized. An analysis of the convergence property of the process reveals that the local neighborhoods play an important role in determining the connectivity between vertices. We demonstrate the practical effectiveness of the proposed measure through several combinatorial optimization problems on graphs and hypergraphs.
On Algebraic Singularities, Finite Graphs and D-Brane Gauge Theories: A String Theoretic Perspective
NASA Astrophysics Data System (ADS)
He, Yang-Hui
2002-09-01
In this writing we shall address certain beautiful inter-relations between the construction of 4-dimensional supersymmetric gauge theories and resolution of algebraic singularities, from the perspective of String Theory. We review in some detail the requisite background in both the mathematics, such as orbifolds, symplectic quotients and quiver representations, as well as the physics, such as gauged linear sigma models, geometrical engineering, Hanany-Witten setups and D-brane probes. We investigate aspects of world-volume gauge dynamics using D-brane resolutions of various Calabi-Yau singularities, notably Gorenstein quotients and toric singularities. Attention will be paid to the general methodology of constructing gauge theories for these singular backgrounds, with and without the presence of the NS-NS B-field, as well as the T-duals to brane setups and branes wrapping cycles in the mirror geometry. Applications of such diverse and elegant mathematics as crepant resolution of algebraic singularities, representation of finite groups and finite graphs, modular invariants of affine Lie algebras, etc. will naturally arise. Various viewpoints and generalisations of McKay's Correspondence will also be considered. The present work is a transcription of excerpts from the first three volumes of the author's PhD thesis which was written under the direction of Prof. A. Hanany - to whom he is much indebted - at the Centre for Theoretical Physics of MIT, and which, at the suggestion of friends, he posts to the ArXiv pro hac vice; it is his sincerest wish that the ensuing pages might be of some small use to the beginning student.
Algebraic connectivity and graph robustness.
Feddema, John Todd; Byrne, Raymond Harry; Abdallah, Chaouki T.
2009-07-01
Recent papers have used Fiedler's definition of algebraic connectivity to show that network robustness, as measured by node-connectivity and edge-connectivity, can be increased by increasing the algebraic connectivity of the network. By the definition of algebraic connectivity, the second smallest eigenvalue of the graph Laplacian is a lower bound on the node-connectivity. In this paper we show that for circular random lattice graphs and mesh graphs algebraic connectivity is a conservative lower bound, and that increases in algebraic connectivity actually correspond to a decrease in node-connectivity. This means that the networks are actually less robust with respect to node-connectivity as the algebraic connectivity increases. However, an increase in algebraic connectivity seems to correlate well with a decrease in the characteristic path length of these networks - which would result in quicker communication through the network. Applications of these results are then discussed for perimeter security.
Sanfilippo, Antonio P.
2005-12-27
Graph theory is a branch of discrete combinatorial mathematics that studies the properties of graphs. The theory was pioneered by the Swiss mathematician Leonhard Euler in the 18th century, commenced its formal development during the second half of the 19th century, and has witnessed substantial growth during the last seventy years, with applications in areas as diverse as engineering, computer science, physics, sociology, chemistry and biology. Graph theory has also had a strong impact in computational linguistics by providing the foundations for the theory of features structures that has emerged as one of the most widely used frameworks for the representation of grammar formalisms.
Feynman graph generation and calculations in the Hopf algebra of Feynman graphs
NASA Astrophysics Data System (ADS)
Borinsky, Michael
2014-12-01
Two programs for the computation of perturbative expansions of quantum field theory amplitudes are provided. feyngen can be used to generate Feynman graphs for Yang-Mills, QED and φk theories. Using dedicated graph theoretic tools feyngen can generate graphs of comparatively high loop orders. feyncop implements the Hopf algebra of those Feynman graphs which incorporates the renormalization procedure necessary to calculate finite results in perturbation theory of the underlying quantum field theory. feyngen is validated by comparison to explicit calculations of zero dimensional quantum field theories and feyncop is validated using a combinatorial identity on the Hopf algebra of graphs.
NASA Astrophysics Data System (ADS)
Connes, Alain; Kreimer, Dirk
This paper gives a complete selfcontained proof of our result announced in [6] showing that renormalization in quantum field theory is a special instance of a general mathematical procedure of extraction of finite values based on the Riemann-Hilbert problem. We shall first show that for any quantum field theory, the combinatorics of Feynman graphs gives rise to a Hopf algebra which is commutative as an algebra. It is the dual Hopf algebra of the enveloping algebra of a Lie algebra whose basis is labelled by the one particle irreducible Feynman graphs. The Lie bracket of two such graphs is computed from insertions of one graph in the other and vice versa. The corresponding Lie group G is the group of characters of . We shall then show that, using dimensional regularization, the bare (unrenormalized) theory gives rise to a loop
Graphing Calculator Use in Algebra Teaching
ERIC Educational Resources Information Center
Dewey, Brenda L.; Singletary, Ted J.; Kinzel, Margaret T.
2009-01-01
This study examines graphing calculator technology availability, characteristics of teachers who use it, teacher attitudes, and how use reflects changes to algebra curriculum and instructional practices. Algebra I and Algebra II teachers in 75 high school and junior high/middle schools in a diverse region of a northwestern state were surveyed.…
Complex Kumjian-Pask algebras of 2-graphs
NASA Astrophysics Data System (ADS)
Yusnitha, Isnie; Rosjanuardi, Rizky
2016-02-01
Let Λ be a row-finitek-graph without sources and R be any field. The Kumjian-Pask algebras KPR(Λ) is an algebraic analog of k-graph algebrasC*(Λ). When the field R is the complex field ℂ, there is a special relationship between the complex Kumjian-Pask algebras KP𝕔(Λ) and k-graph algebrasC*(Λ). We examine this relationship particularly to the case 2-graph 𝔽θ+, 2-graph on single vertex generated by m blue edges and n red edges with θ respect to some commutation relations, by analyzing the associated C*-algebras of 𝔽θ+ . As the presence of cycles on 2-graph 𝔽θ+, we can imply that 2-graph algebras C*(𝔽F+ ) is infinite-dimensional. Hence, the complex Kumjian-Pask algebras KP𝕔 (𝔽θ+ ) is also infinite dimensional.
NASA Astrophysics Data System (ADS)
Dankova, T. S.; Rosensteel, G.
1998-10-01
Mean field theory has an unexpected group theoretic mathematical foundation. Instead of representation theory which applies to most group theoretic quantum models, Hartree-Fock and Hartree-Fock-Bogoliubov have been formulated in terms of coadjoint orbits for the groups U(n) and O(2n). The general theory of mean fields is formulated for an arbitrary Lie algebra L of fermion operators. The moment map provides the correspondence between the Hilbert space of microscopic wave functions and the dual space L^* of densities. The coadjoint orbits of the group in the dual space are phase spaces on which time-dependent mean field theory is equivalent to a classical Hamiltonian dynamical system. Indeed it forms a finite-dimensional Lax system. The mean field theories for the Elliott SU(3) and symplectic Sp(3,R) algebras are constructed explicitly in the coadjoint orbit framework.
Ideas in Practice: Graphing Calculators in Beginning Algebra
ERIC Educational Resources Information Center
Martin, Aimee
2008-01-01
This paper reports on a project to improve Beginning Algebra students' understanding of basic algebraic concepts through fully integrated use of the TI-83 graphing calculator. The methodology incorporated an intervention case study including approximately 700 Beginning Algebra students at an open-door community college of 8,500 students in the…
Graph theory and the Virasoro master equation
Obers, N.A.J.
1991-01-01
A brief history of affine Lie algebra, the Virasoro algebra and its culmination in the Virasoro master equation is given. By studying ansaetze of the master equation, the author obtains exact solutions and gains insight in the structure of large slices of affine-Virasoro space. He finds an isomorphism between the constructions in the ansatz SO(n){sub diag}, which is a set of unitary, generically irrational affine-Virasoro constructions on SO(n), and the unlabeled graphs of order n. On the one hand, the conformal constructions, are classified by the graphs, while, conversely, a group-theoretic and conformal field-theoretic identification is obtained for every graph of graph theory. He also defines a class of magic Lie group bases in which the Virasoro master equation admits a simple metric ansatz {l brace}g{sub metric}{r brace}, whose structure is visible in the high-level expansion. When a magic basis is real on compact g, the corresponding g{sub metric} is a large system of unitary, generically irrational conformal field theories. Examples in this class include the graph-theory ansatz SO(n){sub diag} in the Cartesian basis of SO(n), and the ansatz SU(n){sub metric} in the Pauli-like basis of SU(n). Finally, he defines the sine-area graphs' of SU(n), which label the conformal field theories of SU(n){sub metric}, and he notes that, in similar fashion, each magic basis of g defines a generalized graph theory on g which labels the conformal field theories of g{sub metric}.
Slower Algebra Students Meet Faster Tools: Solving Algebra Word Problems with Graphing Software
ERIC Educational Resources Information Center
Yerushalmy, Michal
2006-01-01
The article discusses the ways that less successful mathematics students used graphing software with capabilities similar to a basic graphing calculator to solve algebra problems in context. The study is based on interviewing students who learned algebra for 3 years in an environment where software tools were always present. We found differences…
ERIC Educational Resources Information Center
Hopkins, Brian
2004-01-01
The interconnected world of actors and movies is a familiar, rich example for graph theory. This paper gives the history of the "Kevin Bacon Game" and makes extensive use of a Web site to analyze the underlying graph. The main content is the classroom development of the weighted average to determine the best choice of "center" for the graph. The…
Graph theory and the Virasoro master equation
Obers, N.A.J.
1991-04-01
A brief history of affine Lie algebra, the Virasoro algebra and its culmination in the Virasoro master equations is given. By studying ansaetze of the master equation, we obtain exact solutions and gain insight in the structure of large slices of affine-Virasoro space. We find an isomorphism between the constructions in the ansatz SO(n){sub diag}, which is a set of unitary, generically irrational affine-Virasoro constructions on SO(n), and the unlabelled graphs, while, conversely, a group-theoretic and conformal field-theoretic identification is obtained for every graph of graph theory. We also define a class of magic'' Lie group bases in which the Virasoro master equation admits a simple metric ansatz (gmetric), whose structure is visible in the high-level expansion. When a magic basis is real on compact g, the corresponding g{sub metric} is a large system of unitary, generically irrational conformal field theories. Examples in this class include the graph-theory ansatz SO(n){sub diag} in the Cartesian basis of SO(n), and the ansatz SU(n){sub metric} in the Pauli-like basis of SU(n). Finally, we define the sine-area graphs'' of SU(n), which label the conformal field theories of SU(n){sub metric}, and we note that, in similar fashion, each magic basis of g defines a generalized graph theory on g which labels the conformal field theories of g{sub metric}. 24 figs., 4 tabs.
Applications of optical Boolean matrix operations to graph theory.
Gibson, P M; Caulfield, H J
1991-09-10
The transition from optical numerical matrix algebra to optical Boolean matrix algebra is explored in detail. All important Boolean matrix algebra tasks can be performed optically. Quantitative measurement is replaced by a simple light-or-no-light decision, something optics can do well. The parallelism advantage of optics becomes greater as the matrix size increases. As an illustration of utility, we consider graph theory. PMID:20706446
NASA Technical Reports Server (NTRS)
Iachello, Franco
1995-01-01
An algebraic formulation of quantum mechanics is presented. In this formulation, operators of interest are expanded onto elements of an algebra, G. For bound state problems in nu dimensions the algebra G is taken to be U(nu + 1). Applications to the structure of molecules are presented.
NASA Technical Reports Server (NTRS)
Butler, Ricky W.; Sjogren, Jon A.
1998-01-01
This paper documents the NASA Langley PVS graph theory library. The library provides fundamental definitions for graphs, subgraphs, walks, paths, subgraphs generated by walks, trees, cycles, degree, separating sets, and four notions of connectedness. Theorems provided include Ramsey's and Menger's and the equivalence of all four notions of connectedness.
Using graph theory for automated electric circuit solving
NASA Astrophysics Data System (ADS)
Toscano, L.; Stella, S.; Milotti, E.
2015-05-01
Graph theory plays many important roles in modern physics and in many different contexts, spanning diverse topics such as the description of scale-free networks and the structure of the universe as a complex directed graph in causal set theory. Graph theory is also ideally suited to describe many concepts in computer science. Therefore it is increasingly important for physics students to master the basic concepts of graph theory. Here we describe a student project where we develop a computational approach to electric circuit solving which is based on graph theoretic concepts. This highly multidisciplinary approach combines abstract mathematics, linear algebra, the physics of circuits, and computer programming to reach the ambitious goal of implementing automated circuit solving.
Graphs and matroids weighted in a bounded incline algebra.
Lu, Ling-Xia; Zhang, Bei
2014-01-01
Firstly, for a graph weighted in a bounded incline algebra (or called a dioid), a longest path problem (LPP, for short) is presented, which can be considered the uniform approach to the famous shortest path problem, the widest path problem, and the most reliable path problem. The solutions for LPP and related algorithms are given. Secondly, for a matroid weighted in a linear matroid, the maximum independent set problem is studied. PMID:25126607
Discrete Signal Processing on Graphs: Sampling Theory
NASA Astrophysics Data System (ADS)
Chen, Siheng; Varma, Rohan; Sandryhaila, Aliaksei; Kovacevic, Jelena
2015-12-01
We propose a sampling theory for signals that are supported on either directed or undirected graphs. The theory follows the same paradigm as classical sampling theory. We show that perfect recovery is possible for graph signals bandlimited under the graph Fourier transform. The sampled signal coefficients form a new graph signal, whose corresponding graph structure preserves the first-order difference of the original graph signal. For general graphs, an optimal sampling operator based on experimentally designed sampling is proposed to guarantee perfect recovery and robustness to noise; for graphs whose graph Fourier transforms are frames with maximal robustness to erasures as well as for Erd\\H{o}s-R\\'enyi graphs, random sampling leads to perfect recovery with high probability. We further establish the connection to the sampling theory of finite discrete-time signal processing and previous work on signal recovery on graphs. To handle full-band graph signals, we propose a graph filter bank based on sampling theory on graphs. Finally, we apply the proposed sampling theory to semi-supervised classification on online blogs and digit images, where we achieve similar or better performance with fewer labeled samples compared to previous work.
Chemical Applications of Graph Theory: Part II. Isomer Enumeration.
ERIC Educational Resources Information Center
Hansen, Peter J.; Jurs, Peter C.
1988-01-01
Discusses the use of graph theory to aid in the depiction of organic molecular structures. Gives a historical perspective of graph theory and explains graph theory terminology with organic examples. Lists applications of graph theory to current research projects. (ML)
Some Applications of Graph Theory to Clustering
ERIC Educational Resources Information Center
Hubert, Lawrence J.
1974-01-01
The connection between graph theory and clustering is reviewed and extended. Major emphasis is on restating, in a graph-theoretic context, selected past work in clustering, and conversely, developing alternative strategies from several standard concepts used in graph theory per se. (Author/RC)
The Relationship between Graphing Calculator Use and Teachers' Beliefs about Learning Algebra.
ERIC Educational Resources Information Center
Yoder, Arnita J.
The purpose of this study was to determine teachers' views of learning algebra and to investigate if any relationship exists between their views of learning algebra and the ways that they use graphing calculators in their algebra classes. The 48 algebra teachers who participated in the study were from Allen, Putnam, and Van Wert counties in…
Computational Genomics Using Graph Theory
NASA Astrophysics Data System (ADS)
Schlick, Tamar
2005-03-01
With exciting new discoveries concerning RNA's regulatory cellular roles in gene expression, structural and functional problems associated with DNA's venerable cousin have come to the forefront. RNA folding, for example, is analogous to the well-known protein folding problem, and seeks to link RNA's primary sequence with secondary and tertiary structures. As a single-stranded polynucleotide, RNA's secondary structures are defined by a network of hydrogen bonds, which lead to a variety of stems, loops, junctions, bulges, and other motifs. Supersecondary pseudoknot structures can also occur and, together, lead to RNA's complex tertiary interactions stabilized by salt and solvent ions in the natural cellular milieu. Besides folding, challenges in RNA research include identifying locations and functions of RNA genes, discovering RNA's structural repertoire (folding motifs), designing novel RNAs, and developing new antiviral and antibiotic compounds composed of, or targeting, RNAs. In this talk, I will describe some of these new biological findings concerning RNA and present an approach using graph theory (network theory) to represent RNA secondary structures. Because the RNA motif space using graphs is vastly smaller than RNA's sequence space, many problems related to analyzing and discovering new RNAs can be simplified and studied systematically. Some preliminary applications to designing novel RNAs will also be described.Related ReadingH. H. Gan, S. Pasquali, and T. Schlick, ``A Survey of Existing RNAs using Graph Theory with Implications to RNA Analysis and Design,'' Nuc. Acids Res. 31: 2926--2943 (2003). J. Zorn, H. H. Gan, N. Shiffeldrim, and T. Schlick, ``Structural Motifs in Ribosomal RNAs: Implications for RNA Design and Genomics,'' Biopolymers 73: 340--347 (2004). H. H. Gan, D. Fera, J. Zorn, M. Tang, N. Shiffeldrim, U. Laserson, N. Kim, and T. Schlick,``RAG: RNA-As-Graphs Database -- Concepts, Analysis, and Features,'' Bioinformatics 20: 1285--1291 (2004). U
Flying through Graphs: An Introduction to Graph Theory.
ERIC Educational Resources Information Center
McDuffie, Amy Roth
2001-01-01
Presents an activity incorporating basic terminology, concepts, and solution methods of graph theory in the context of solving problems related to air travel. Discusses prerequisite knowledge and resources and includes a teacher's guide with a student worksheet. (KHR)
Computer algebra and transport theory.
Warsa, J. S.
2004-01-01
Modern symbolic algebra computer software augments and complements more traditional approaches to transport theory applications in several ways. The first area is in the development and enhancement of numerical solution methods for solving the Boltzmann transport equation. Typically, special purpose computer codes are designed and written to solve specific transport problems in particular ways. Different aspects of the code are often written from scratch and the pitfalls of developing complex computer codes are numerous and well known. Software such as MAPLE and MATLAB can be used to prototype, analyze, verify and determine the suitability of numerical solution methods before a full-scale transport application is written. Once it is written, the relevant pieces of the full-scale code can be verified using the same tools I that were developed for prototyping. Another area is in the analysis of numerical solution methods or the calculation of theoretical results that might otherwise be difficult or intractable. Algebraic manipulations are done easily and without error and the software also provides a framework for any additional numerical calculations that might be needed to complete the analysis. We will discuss several applications in which we have extensively used MAPLE and MATLAB in our work. All of them involve numerical solutions of the S{sub N} transport equation. These applications encompass both of the two main areas in which we have found computer algebra software essential.
The graph representation approach to topological field theory in 2 + 1 dimensions
Martin, S.P.
1991-02-01
An alternative definition of topological quantum field theory in 2+1 dimensions is discussed. The fundamental objects in this approach are not gauge fields as in the usual approach, but non-local observables associated with graphs. The classical theory of graphs is defined by postulating a simple diagrammatic rule for computing the Poisson bracket of any two graphs. The theory is quantized by exhibiting a quantum deformation of the classical Poisson bracket algebra, which is realized as a commutator algebra on a Hilbert space of states. The wavefunctions in this graph representation'' approach are functionals on an appropriate set of graphs. This is in contrast to the usual connection representation'' approach in which the theory is defined in terms of a gauge field and the wavefunctions are functionals on the space of flat spatial connections modulo gauge transformations.
Graph Theory and the High School Student.
ERIC Educational Resources Information Center
Chartrand, Gary; Wall, Curtiss E.
1980-01-01
Graph theory is presented as a tool to instruct high school mathematics students. A variety of real world problems can be modeled which help students recognize the importance and difficulty of applying mathematics. (MP)
Application of Computer Graphics to Graphing in Algebra and Trigonometry. Final Report.
ERIC Educational Resources Information Center
Morris, J. Richard
This project was designed to improve the graphing competency of students in elementary algebra, intermediate algebra, and trigonometry courses at Virginia Commonwealth University. Computer graphics programs were designed using an Apple II Plus computer and implemented using Pascal. The software package is interactive and gives students control…
Quantum graphs and random-matrix theory
NASA Astrophysics Data System (ADS)
Pluhař, Z.; Weidenmüller, H. A.
2015-07-01
For simple connected graphs with incommensurate bond lengths and with unitary symmetry we prove the Bohigas-Giannoni-Schmit (BGS) conjecture in its most general form. Using supersymmetry and taking the limit of infinite graph size, we show that the generating function for every (P,Q) correlation function for both closed and open graphs coincides with the corresponding expression of random-matrix theory. We show that the classical Perron-Frobenius operator is bistochastic and possesses a single eigenvalue +1. In the quantum case that implies the existence of a zero (or massless) mode of the effective action. That mode causes universal fluctuation properties. Avoiding the saddle-point approximation we show that for graphs that are classically mixing (i.e. for which the spectrum of the classical Perron-Frobenius operator possesses a finite gap) and that do not carry a special class of bound states, the zero mode dominates in the limit of infinite graph size.
Vertex operator algebras and conformal field theory
Huang, Y.Z. )
1992-04-20
This paper discusses conformal field theory, an important physical theory, describing both two-dimensional critical phenomena in condensed matter physics and classical motions of strings in string theory. The study of conformal field theory will deepen the understanding of these theories and will help to understand string theory conceptually. Besides its importance in physics, the beautiful and rich mathematical structure of conformal field theory has interested many mathematicians. New relations between different branches of mathematics, such as representations of infinite-dimensional Lie algebras and Lie groups, Riemann surfaces and algebraic curves, the Monster sporadic group, modular functions and modular forms, elliptic genera and elliptic cohomology, Calabi-Yau manifolds, tensor categories, and knot theory, are revealed in the study of conformal field theory. It is therefore believed that the study of the mathematics involved in conformal field theory will ultimately lead to new mathematical structures which would be important to both mathematics and physics.
Imperfect Cloning Operations in Algebraic Quantum Theory
NASA Astrophysics Data System (ADS)
Kitajima, Yuichiro
2015-01-01
No-cloning theorem says that there is no unitary operation that makes perfect clones of non-orthogonal quantum states. The objective of the present paper is to examine whether an imperfect cloning operation exists or not in a C*-algebraic framework. We define a universal -imperfect cloning operation which tolerates a finite loss of fidelity in the cloned state, and show that an individual system's algebra of observables is abelian if and only if there is a universal -imperfect cloning operation in the case where the loss of fidelity is less than . Therefore in this case no universal -imperfect cloning operation is possible in algebraic quantum theory.
Algebraic methods in system theory
NASA Technical Reports Server (NTRS)
Brockett, R. W.; Willems, J. C.; Willsky, A. S.
1975-01-01
Investigations on problems of the type which arise in the control of switched electrical networks are reported. The main results concern the algebraic structure and stochastic aspects of these systems. Future reports will contain more detailed applications of these results to engineering studies.
Many-core graph analytics using accelerated sparse linear algebra routines
NASA Astrophysics Data System (ADS)
Kozacik, Stephen; Paolini, Aaron L.; Fox, Paul; Kelmelis, Eric
2016-05-01
Graph analytics is a key component in identifying emerging trends and threats in many real-world applications. Largescale graph analytics frameworks provide a convenient and highly-scalable platform for developing algorithms to analyze large datasets. Although conceptually scalable, these techniques exhibit poor performance on modern computational hardware. Another model of graph computation has emerged that promises improved performance and scalability by using abstract linear algebra operations as the basis for graph analysis as laid out by the GraphBLAS standard. By using sparse linear algebra as the basis, existing highly efficient algorithms can be adapted to perform computations on the graph. This approach, however, is often less intuitive to graph analytics experts, who are accustomed to vertex-centric APIs such as Giraph, GraphX, and Tinkerpop. We are developing an implementation of the high-level operations supported by these APIs in terms of linear algebra operations. This implementation is be backed by many-core implementations of the fundamental GraphBLAS operations required, and offers the advantages of both the intuitive programming model of a vertex-centric API and the performance of a sparse linear algebra implementation. This technology can reduce the number of nodes required, as well as the run-time for a graph analysis problem, enabling customers to perform more complex analysis with less hardware at lower cost. All of this can be accomplished without the requirement for the customer to make any changes to their analytics code, thanks to the compatibility with existing graph APIs.
Excision in algebraic K-theory and Karoubi's conjecture.
Suslin, A A; Wodzicki, M
1990-12-15
We prove that the property of excision in algebraic K-theory is for a Q-algebra A equivalent to the H-unitality of the latter. Our excision theorem, in particular, implies Karoubi's conjecture on the equality of algebraic and topological K-theory groups of stable C*-algebras. It also allows us to identify the algebraic K-theory of the symbol map in the theory of pseudodifferential operators. PMID:11607130
Excision in algebraic K-theory and Karoubi's conjecture.
Suslin, A A; Wodzicki, M
1990-01-01
We prove that the property of excision in algebraic K-theory is for a Q-algebra A equivalent to the H-unitality of the latter. Our excision theorem, in particular, implies Karoubi's conjecture on the equality of algebraic and topological K-theory groups of stable C*-algebras. It also allows us to identify the algebraic K-theory of the symbol map in the theory of pseudodifferential operators. PMID:11607130
The conceptual basis of mathematics in cardiology: (I) algebra, functions and graphs.
Bates, Jason H T; Sobel, Burton E
2003-02-01
This is the first in a series of four articles developed for the readers of. Without language ideas cannot be articulated. What may not be so immediately obvious is that they cannot be formulated either. One of the essential languages of cardiology is mathematics. Unfortunately, medical education does not emphasize, and in fact, often neglects empowering physicians to think mathematically. Reference to statistics, conditional probability, multicompartmental modeling, algebra, calculus and transforms is common but often without provision of genuine conceptual understanding. At the University of Vermont College of Medicine, Professor Bates developed a course designed to address these deficiencies. The course covered mathematical principles pertinent to clinical cardiovascular and pulmonary medicine and research. It focused on fundamental concepts to facilitate formulation and grasp of ideas. This series of four articles was developed to make the material available for a wider audience. The articles will be published sequentially in Coronary Artery Disease. Beginning with fundamental axioms and basic algebraic manipulations they address algebra, function and graph theory, real and complex numbers, calculus and differential equations, mathematical modeling, linear system theory and integral transforms and statistical theory. The principles and concepts they address provide the foundation needed for in-depth study of any of these topics. Perhaps of even more importance, they should empower cardiologists and cardiovascular researchers to utilize the language of mathematics in assessing the phenomena of immediate pertinence to diagnosis, pathophysiology and therapeutics. The presentations are interposed with queries (by Coronary Artery Disease, abbreviated as CAD) simulating the nature of interactions that occurred during the course itself. Each article concludes with one or more examples illustrating application of the concepts covered to cardiovascular medicine and
NASA Astrophysics Data System (ADS)
Uribe Peláez, Simon
2010-04-01
Identifying coverage holes makes an important topic for optimization of quality service for wireless sensor network hosts. This paper introduces a new way to identify and describe how is the network's structure, its number of holes and its components, assuming there's a sensor covering an area where a network communication exists. The simplicial complex method and algebraic graph theory will be applied. Betti numbers and Euler characteristics will be used for a sensor network represented by a simplicial complex, and the Tutte polynomial will be used for describing visual graphs algebraically, for a complete identification.
Reducing Abstraction When Learning Graph Theory
ERIC Educational Resources Information Center
Hazzan, Orit; Hadar, Irit
2005-01-01
This article presents research on students' understanding of basic concepts in Graph Theory. Students' understanding is analyzed through the lens of the theoretical framework of reducing abstraction (Hazzan, 1999). As it turns out, in spite of the relative simplicity of the concepts that are introduced in the introductory part of a traditional…
Algebraic theory of recombination spaces.
Stadler, P F; Wagner, G P
1997-01-01
A new mathematical representation is proposed for the configuration space structure induced by recombination, which we call "P-structure." It consists of a mapping of pairs of objects to the power set of all objects in the search space. The mapping assigns to each pair of parental "genotypes" the set of all recombinant genotypes obtainable from the parental ones. It is shown that this construction allows a Fourier decomposition of fitness landscapes into a superposition of "elementary landscapes." This decomposition is analogous to the Fourier decomposition of fitness landscapes on mutation spaces. The elementary landscapes are obtained as eigenfunctions of a Laplacian operator defined for P-structures. For binary string recombination, the elementary landscapes are exactly the p-spin functions (Walsh functions), that is, the same as the elementary landscapes of the string point mutation spaces (i.e., the hypercube). This supports the notion of a strong homomorphism between string mutation and recombination spaces. However, the effective nearest neighbor correlations on these elementary landscapes differ between mutation and recombination and among different recombination operators. On average, the nearest neighbor correlation is higher for one-point recombination than for uniform recombination. For one-point recombination, the correlations are higher for elementary landscapes with fewer interacting sites as well as for sites that have closer linkage, confirming the qualitative predictions of the Schema Theorem. We conclude that the algebraic approach to fitness landscape analysis can be extended to recombination spaces and provides an effective way to analyze the relative hardness of a landscape for a given recombination operator. PMID:10021760
ERIC Educational Resources Information Center
Reznichenko, Nataliya
2006-01-01
A major goal of this paper is to document changes that occurred in developmental mathematics classrooms in the community college setting when the graphing calculator (GC) Texas Instruments (TI)-83 was introduced to students. The six-week intervention was conducted during the section of Intermediate Algebra in the Community College Baltimore County…
Algebraic Theories and (Infinity,1)-Categories
NASA Astrophysics Data System (ADS)
Cranch, James
2010-11-01
We adapt the classical framework of algebraic theories to work in the setting of (infinity,1)-categories developed by Joyal and Lurie. This gives a suitable approach for describing highly structured objects from homotopy theory. A central example, treated at length, is the theory of E_infinity spaces: this has a tidy combinatorial description in terms of span diagrams of finite sets. We introduce a theory of distributive laws, allowing us to describe objects with two distributing E_infinity stuctures. From this we produce a theory of E_infinity ring spaces. We also study grouplike objects, and produce theories modelling infinite loop spaces (or connective spectra), and infinite loop spaces with coherent multiplicative structure (or connective ring spectra). We use this to construct the units of a grouplike E_infinity ring space in a natural manner. Lastly we provide a speculative pleasant description of the K-theory of monoidal quasicategories and quasicategories with ring-like structures.
Role of division algebra in seven-dimensional gauge theory
NASA Astrophysics Data System (ADS)
Kalauni, Pushpa; Barata, J. C. A.
2015-03-01
The algebra of octonions 𝕆 forms the largest normed division algebra over the real numbers ℝ, complex numbers ℂ and quaternions ℍ. The usual three-dimensional vector product is given by quaternions, while octonions produce seven-dimensional vector product. Thus, octonionic algebra is closely related to the seven-dimensional algebra, therefore one can extend generalization of rotations in three dimensions to seven dimensions using octonions. An explicit algebraic description of octonions has been given to describe rotational transformation in seven-dimensional space. We have also constructed a gauge theory based on non-associative algebra to discuss Yang-Mills theory and field equation in seven-dimensional space.
Algebraic K-theory, K-regularity, and -duality of -stable C ∗-algebras
NASA Astrophysics Data System (ADS)
Mahanta, Snigdhayan
2015-12-01
We develop an algebraic formalism for topological -duality. More precisely, we show that topological -duality actually induces an isomorphism between noncommutative motives that in turn implements the well-known isomorphism between twisted K-theories (up to a shift). In order to establish this result we model topological K-theory by algebraic K-theory. We also construct an E ∞ -operad starting from any strongly self-absorbing C ∗-algebra . Then we show that there is a functorial topological K-theory symmetric spectrum construction on the category of separable C ∗-algebras, such that is an algebra over this operad; moreover, is a module over this algebra. Along the way we obtain a new symmetric spectra valued functorial model for the (connective) topological K-theory of C ∗-algebras. We also show that -stable C ∗-algebras are K-regular providing evidence for a conjecture of Rosenberg. We conclude with an explicit description of the algebraic K-theory of a x+ b-semigroup C ∗-algebras coming from number theory and that of -stabilized noncommutative tori.
Quantum field theories on algebraic curves. I. Additive bosons
NASA Astrophysics Data System (ADS)
Takhtajan, Leon A.
2013-04-01
Using Serre's adelic interpretation of cohomology, we develop a `differential and integral calculus' on an algebraic curve X over an algebraically closed field k of constants of characteristic zero, define algebraic analogues of additive multi-valued functions on X and prove the corresponding generalized residue theorem. Using the representation theory of the global Heisenberg algebra and lattice Lie algebra, we formulate quantum field theories of additive and charged bosons on an algebraic curve X. These theories are naturally connected with the algebraic de Rham theorem. We prove that an extension of global symmetries (Witten's additive Ward identities) from the k-vector space of rational functions on X to the vector space of additive multi-valued functions uniquely determines these quantum theories of additive and charged bosons.
ERIC Educational Resources Information Center
Reznichenko, Nataliya
2012-01-01
Since technology has taken its place in almost all classrooms in schools and colleges across the country, there is a need to know how technology influences the mathematics that is taught and how students learn. In this study, the graphing calculator (GC) (namely the Texas Instruments TI-83) was implemented as a tool to enhance learning of function…
Chemical Graph Theory--The Mathematical Connection
NASA Astrophysics Data System (ADS)
Gutman, Ivan
The impact that research done in chemical graph theory (CGT) had and has on "serious" or "pure" mathematics is examined. Although this impact is minor, it is not fully negligible. By means of two case studies we intend to demonstrate the following general features of the CGT --> Mathematics connection: (a) Scholars familiar with chemistry design a mathematical model of the examined chemical phenomena; (b) such a model may require the usage of non-trivial mathematical objects and methods, and may lead to difficult and interesting mathematical problems; (c) in order to grasp the significance of a particular mathematical object/method/problem of CGT, mathematicians need a very long time, sometimes as much as 20-30 years; (d) once this significance is recognized, a vigorous mathematical research begins; (e) mathematicians usually generalize and extend the original object/method/problem of CGT, and the results they obtain may be lacking value for CGT. The two case studies pertain to the graph energy and the connectivity (or Randic) index.
Metric Lie 3-algebras in Bagger-Lambert theory
NASA Astrophysics Data System (ADS)
de Medeiros, Paul; Figueroa-O'Farrill, José; Méndez-Escobar, Elena
2008-08-01
We recast physical properties of the Bagger-Lambert theory, such as shift-symmetry and decoupling of ghosts, the absence of scale and parity invariance, in Lie 3-algebraic terms, thus motivating the study of metric Lie 3-algebras and their Lie algebras of derivations. We prove a structure theorem for metric Lie 3-algebras in arbitrary signature showing that they can be constructed out of the simple and one-dimensional Lie 3-algebras iterating two constructions: orthogonal direct sum and a new construction called a double extension, by analogy with the similar construction for Lie algebras. We classify metric Lie 3-algebras of signature (2, p) and study their Lie algebras of derivations, including those which preserve the conformal class of the inner product. We revisit the 3-algebraic criteria spelt out at the start of the paper and select those algebras with signature (2, p) which satisfy them, as well as indicate the construction of more general metric Lie 3-algebras satisfying the ghost-decoupling criterion.
Zapata, Francisco; Kreinovich, Vladik; Joslyn, Cliff A.; Hogan, Emilie A.
2013-08-01
To make a decision, we need to compare the values of quantities. In many practical situations, we know the values with interval uncertainty. In such situations, we need to compare intervals. Allen’s algebra describes all possible relations between intervals on the real line, and ordering relations between such intervals are well studied. In this paper, we extend this description to intervals in an arbitrary partially ordered set (poset). In particular, we explicitly describe ordering relations between intervals that generalize relation between points. As auxiliary results, we provide a logical interpretation of the relation between intervals, and extend the results about interval graphs to intervals over posets.
Generative Graph Prototypes from Information Theory.
Han, Lin; Wilson, Richard C; Hancock, Edwin R
2015-10-01
In this paper we present a method for constructing a generative prototype for a set of graphs by adopting a minimum description length approach. The method is posed in terms of learning a generative supergraph model from which the new samples can be obtained by an appropriate sampling mechanism. We commence by constructing a probability distribution for the occurrence of nodes and edges over the supergraph. We encode the complexity of the supergraph using an approximate Von Neumann entropy. A variant of the EM algorithm is developed to minimize the description length criterion in which the structure of the supergraph and the node correspondences between the sample graphs and the supergraph are treated as missing data. To generate new graphs, we assume that the nodes and edges of graphs arise under independent Bernoulli distributions and sample new graphs according to their node and edge occurrence probabilities. Empirical evaluations on real-world databases demonstrate the practical utility of the proposed algorithm and show the effectiveness of the generative model for the tasks of graph classification, graph clustering and generating new sample graphs. PMID:26340255
Graph-based linear scaling electronic structure theory
NASA Astrophysics Data System (ADS)
Niklasson, Anders M. N.; Mniszewski, Susan M.; Negre, Christian F. A.; Cawkwell, Marc J.; Swart, Pieter J.; Mohd-Yusof, Jamal; Germann, Timothy C.; Wall, Michael E.; Bock, Nicolas; Rubensson, Emanuel H.; Djidjev, Hristo
2016-06-01
We show how graph theory can be combined with quantum theory to calculate the electronic structure of large complex systems. The graph formalism is general and applicable to a broad range of electronic structure methods and materials, including challenging systems such as biomolecules. The methodology combines well-controlled accuracy, low computational cost, and natural low-communication parallelism. This combination addresses substantial shortcomings of linear scaling electronic structure theory, in particular with respect to quantum-based molecular dynamics simulations.
Graph-based linear scaling electronic structure theory.
Niklasson, Anders M N; Mniszewski, Susan M; Negre, Christian F A; Cawkwell, Marc J; Swart, Pieter J; Mohd-Yusof, Jamal; Germann, Timothy C; Wall, Michael E; Bock, Nicolas; Rubensson, Emanuel H; Djidjev, Hristo
2016-06-21
We show how graph theory can be combined with quantum theory to calculate the electronic structure of large complex systems. The graph formalism is general and applicable to a broad range of electronic structure methods and materials, including challenging systems such as biomolecules. The methodology combines well-controlled accuracy, low computational cost, and natural low-communication parallelism. This combination addresses substantial shortcomings of linear scaling electronic structure theory, in particular with respect to quantum-based molecular dynamics simulations. PMID:27334148
Applications of graph theory to landscape genetics
Garroway, Colin J; Bowman, Jeff; Carr, Denis; Wilson, Paul J
2008-01-01
We investigated the relationships among landscape quality, gene flow, and population genetic structure of fishers (Martes pennanti) in ON, Canada. We used graph theory as an analytical framework considering each landscape as a network node. The 34 nodes were connected by 93 edges. Network structure was characterized by a higher level of clustering than expected by chance, a short mean path length connecting all pairs of nodes, and a resiliency to the loss of highly connected nodes. This suggests that alleles can be efficiently spread through the system and that extirpations and conservative harvest are not likely to affect their spread. Two measures of node centrality were negatively related to both the proportion of immigrants in a node and node snow depth. This suggests that central nodes are producers of emigrants, contain high-quality habitat (i.e., deep snow can make locomotion energetically costly) and that fishers were migrating from high to low quality habitat. A method of community detection on networks delineated five genetic clusters of nodes suggesting cryptic population structure. Our analyses showed that network models can provide system-level insight into the process of gene flow with implications for understanding how landscape alterations might affect population fitness and evolutionary potential. PMID:25567802
Guidelines for the CSMP K-6 Curriculum in Graph Theory.
ERIC Educational Resources Information Center
Deskins, W. E.; And Others
This volume is designed for teachers preparing to teach upper elementary students using the Comprehensive School Mathematics Program (CSMP) curriculum. It begins with a discussion of the importance of graph theory in mathematics and science. A mathematical development of graph-theoretic concepts and theorems is presented, followed by a set of…
Fourier theory and C∗-algebras
NASA Astrophysics Data System (ADS)
Bédos, Erik; Conti, Roberto
2016-07-01
We discuss a number of results concerning the Fourier series of elements in reduced twisted group C∗-algebras of discrete groups, and, more generally, in reduced crossed products associated to twisted actions of discrete groups on unital C∗-algebras. A major part of the article gives a review of our previous work on this topic, but some new results are also included.
Bailor, P.D.
1989-01-01
This investigation develops a generalized formal language theory model and associated theorems for the specification, analysis, and mapping of graphs and graph-based languages. The developed model is defined as a graph generative system, and the model is analyzed from a set theoretic, formal language, algebraic, and abstract automata perspective. As a result of the analysis, numerous theorems pertaining to the properties of the model, graphs, and graph-based languages are derived. Additionally, the graph generative system model serves as the basis for applying graph-based languages to areas such as the specification and design of software and visual programming. The specific application area emphasized is the use of graph-based languages as user friendly interfaces for wide-spectrum languages that include structures for representing parallelism. The goal of this approach is to provide an effective, efficient, and formal method for the specification, design, and rapid prototyping of parallel software. To demonstrate the utility of the theory and the feasibility of the application, two models of parallel computation are chosen. The widely used Petri net model of parallel computation is formalized as a graph-based language. The Petri net syntax is formally mapped into the corresponding syntax of a Communicating Sequential Processes (CSP) model of parallel computation where CSP is used as the formalism for extended wide-spectrum languages. Finally, the Petri net to CSP mapping is analyzed from a behavioral perspective to demonstrate that the CSP specification formally behaves in a manner equivalent to the Petri net model.
Bailor, P.D.
1989-09-01
Ageneralized formal language theory model and associated theorems were developed for the specification, analysis, and mapping of graphs and graph-based languages. The developed model, defined as a graph-generative system, is analyzed from a set theoretic, formal language, algebraic, and abstract automata perspective. As a result of the analysis, numerous theorems pertaining to the properties of the model, graphs, and graph-based languages are derived. The graph generative system model also serves as the basis for applying graph based languages to areas such as the specification and design of software and visual programming. The specific application area emphasized is the use of graph-based languages as user-friendly interfaces for wide-spectrum languages that include structures for representing parallelism. The goal of this approach is to provide an effective, efficient, and formal method for the specification, design, and rapid prototyping of parallel software. To demonstrate the theory's utility and the feasibility of the application, two models of parallel computation are chosen. The widely used Petri net model of parallel computation is formalized as a graph-based language. The Petri net syntax is formally mapped into the corresponding syntax of a Communicating Sequential Processes(CSP) model of parallel computation where CSP is used as the formalism for extended wide-spectrum languages. Finally, the Petri net to CSP mapping is analyzed to demonstrate that the CSP specification formally behaves in a manner equivalent to the Petri net model.
Graph Theory In Protein Sequence Clustering And Tertiary Structural Matching
NASA Astrophysics Data System (ADS)
Abdullah, Rosni; Rashid, Nur'Aini Abdul; Othman, Fazilah
2008-01-01
The principle of graph theory which has been widely used in computer networks is now being adopted for work in protein clustering, protein structural matching, and protein folding and modeling. In this work, we present two case studies on the use of graph theory for protein clustering and tertiary structural matching. In protein clustering, we extended a clustering algorithm based on a maximal clique while in the protein tertiary structural matching we explored the bipartite graph matching algorithm. The results obtained in both the case studies will be presented.
Symmetric linear systems - An application of algebraic systems theory
NASA Technical Reports Server (NTRS)
Hazewinkel, M.; Martin, C.
1983-01-01
Dynamical systems which contain several identical subsystems occur in a variety of applications ranging from command and control systems and discretization of partial differential equations, to the stability augmentation of pairs of helicopters lifting a large mass. Linear models for such systems display certain obvious symmetries. In this paper, we discuss how these symmetries can be incorporated into a mathematical model that utilizes the modern theory of algebraic systems. Such systems are inherently related to the representation theory of algebras over fields. We will show that any control scheme which respects the dynamical structure either implicitly or explicitly uses the underlying algebra.
Rasch Measurement Theory, the Method of Paired Comparisons, and Graph Theory.
ERIC Educational Resources Information Center
Garner, Mary; Engelhard, George, Jr.
This paper considers the following questions: (1) what is the relationship between the method of paired comparisons and Rasch measurement theory? (2) what is the relationship between the method of paired comparisons and graph theory? and (3) what can graph theory contribute to the understanding of Rasch measurement theory? It is specifically shown…
The arithmetic theory of algebraic groups
NASA Astrophysics Data System (ADS)
Platonov, V. P.
1982-06-01
CONTENTS Introduction § 1. Arithmetic groups § 2. Adèle groups § 3. Tamagawa numbers § 4. Approximations in algebraic groups § 5. Class numbers and class groups of algebraic groups § 6. The genus problem in arithmetic groups § 7. Classification of maximal arithmetic subgroups § 8. The congruence problem § 9. Groups of rational points over global fields § 10. Galois cohomology and the Hasse principle § 11. Cohomology of arithmetic groups References
Entanglement witnesses for graph states: General theory and examples
Jungnitsch, Bastian; Moroder, Tobias; Guehne, Otfried
2011-09-15
We present a general theory for the construction of witnesses that detect genuine multipartite entanglement in graph states. First, we present explicit witnesses for all graph states of up to six qubits which are better than all criteria so far. Therefore, lower fidelities are required in experiments that aim at the preparation of graph states. Building on these results, we develop analytical methods to construct two different types of entanglement witnesses for general graph states. For many classes of states, these operators exhibit white noise tolerances that converge to 1 when increasing the number of particles. We illustrate our approach for states such as the linear and the 2D cluster state. Finally, we study an entanglement monotone motivated by our approach for graph states.
Applications of graph theory in protein structure identification.
Yan, Yan; Zhang, Shenggui; Wu, Fang-Xiang
2011-01-01
There is a growing interest in the identification of proteins on the proteome wide scale. Among different kinds of protein structure identification methods, graph-theoretic methods are very sharp ones. Due to their lower costs, higher effectiveness and many other advantages, they have drawn more and more researchers' attention nowadays. Specifically, graph-theoretic methods have been widely used in homology identification, side-chain cluster identification, peptide sequencing and so on. This paper reviews several methods in solving protein structure identification problems using graph theory. We mainly introduce classical methods and mathematical models including homology modeling based on clique finding, identification of side-chain clusters in protein structures upon graph spectrum, and de novo peptide sequencing via tandem mass spectrometry using the spectrum graph model. In addition, concluding remarks and future priorities of each method are given. PMID:22165974
Graph theory in structure-property correlations
NASA Astrophysics Data System (ADS)
Vinogradova, M. G.; Fedina, Yu. A.; Papulov, Yu. G.
2016-02-01
The possibilities of the theoretical graph approach to the construction and interpretation of additive schemes for calculation and prediction are discussed. Working formulas are derived for calculating the thermodynamic properties of alkanes and their substitutes. The obtained algorithms are used to calculate thermodynamic properties of chloroalkanes that correspond to experimental values.
ERIC Educational Resources Information Center
Hatem, Neil
2010-01-01
This study investigates the relationship between the use of graphing calculators employed as Type II technology and student achievement, as determined by assessing students' problem solving skills associated with the concept of function, at the college algebra and pre-calculus level. In addition, this study explores the integration of graphing…
ERIC Educational Resources Information Center
Ruthven, Kenneth; Deaney, Rosemary; Hennessy, Sara
2009-01-01
From preliminary analysis of teacher-nominated examples of successful technology-supported practice in secondary-school mathematics, the use of graphing software to teach about algebraic forms was identified as being an important archetype. Employing evidence from lesson observation and teacher interview, such practice was investigated in greater…
Quantifying Riverscape Connectivity with Graph Theory
NASA Astrophysics Data System (ADS)
Carbonneau, P.; Milledge, D.; Sinha, R.; Tandon, S. K.
2013-12-01
Fluvial catchments convey fluxes of water, sediment, nutrients and aquatic biota. At continental scales, crustal topography defines the overall path of channels whilst at local scales depositional and/or erosional features generally determine the exact path of a channel. Furthermore, constructions such as dams, for either water abstraction or hydropower, often have a significant impact on channel networks.The concept of ';connectivity' is commonly invoked when conceptualising the structure of a river network.This concept is easy to grasp but there have been uneven efforts across the environmental sciences to actually quantify connectivity. Currently there have only been a few studies reporting quantitative indices of connectivity in river sciences, notably, in the study of avulsion processes. However, the majority of current work describing some form of environmental connectivity in a quantitative manner is in the field of landscape ecology. Driven by the need to quantify habitat fragmentation, landscape ecologists have returned to graph theory. Within this formal setting, landscape ecologists have successfully developed a range of indices which can model connectivity loss. Such formal connectivity metrics are currently needed for a range of applications in fluvial sciences. One of the most urgent needs relates to dam construction. In the developed world, hydropower development has generally slowed and in many countries, dams are actually being removed. However, this is not the case in the developing world where hydropower is seen as a key element to low-emissions power-security. For example, several dam projects are envisaged in Himalayan catchments in the next 2 decades. This region is already under severe pressure from climate change and urbanisation, and a better understanding of the network fragmentation which can be expected in this system is urgently needed. In this paper, we apply and adapt connectivity metrics from landscape ecology. We then examine the
Three-Dimensional Algebraic Models of the tRNA Code and 12 Graphs for Representing the Amino Acids.
José, Marco V; Morgado, Eberto R; Guimarães, Romeu Cardoso; Zamudio, Gabriel S; de Farías, Sávio Torres; Bobadilla, Juan R; Sosa, Daniela
2014-01-01
Three-dimensional algebraic models, also called Genetic Hotels, are developed to represent the Standard Genetic Code, the Standard tRNA Code (S-tRNA-C), and the Human tRNA code (H-tRNA-C). New algebraic concepts are introduced to be able to describe these models, to wit, the generalization of the 2n-Klein Group and the concept of a subgroup coset with a tail. We found that the H-tRNA-C displayed broken symmetries in regard to the S-tRNA-C, which is highly symmetric. We also show that there are only 12 ways to represent each of the corresponding phenotypic graphs of amino acids. The averages of statistical centrality measures of the 12 graphs for each of the three codes are carried out and they are statistically compared. The phenotypic graphs of the S-tRNA-C display a common triangular prism of amino acids in 10 out of the 12 graphs, whilst the corresponding graphs for the H-tRNA-C display only two triangular prisms. The graphs exhibit disjoint clusters of amino acids when their polar requirement values are used. We contend that the S-tRNA-C is in a frozen-like state, whereas the H-tRNA-C may be in an evolving state. PMID:25370377
Three-Dimensional Algebraic Models of the tRNA Code and 12 Graphs for Representing the Amino Acids
José, Marco V.; Morgado, Eberto R.; Guimarães, Romeu Cardoso; Zamudio, Gabriel S.; de Farías, Sávio Torres; Bobadilla, Juan R.; Sosa, Daniela
2014-01-01
Three-dimensional algebraic models, also called Genetic Hotels, are developed to represent the Standard Genetic Code, the Standard tRNA Code (S-tRNA-C), and the Human tRNA code (H-tRNA-C). New algebraic concepts are introduced to be able to describe these models, to wit, the generalization of the 2n-Klein Group and the concept of a subgroup coset with a tail. We found that the H-tRNA-C displayed broken symmetries in regard to the S-tRNA-C, which is highly symmetric. We also show that there are only 12 ways to represent each of the corresponding phenotypic graphs of amino acids. The averages of statistical centrality measures of the 12 graphs for each of the three codes are carried out and they are statistically compared. The phenotypic graphs of the S-tRNA-C display a common triangular prism of amino acids in 10 out of the 12 graphs, whilst the corresponding graphs for the H-tRNA-C display only two triangular prisms. The graphs exhibit disjoint clusters of amino acids when their polar requirement values are used. We contend that the S-tRNA-C is in a frozen-like state, whereas the H-tRNA-C may be in an evolving state. PMID:25370377
From string theory to algebraic geometry and back
Brinzanescu, Vasile
2011-02-10
We describe some facts in physics which go up to the modern string theory and the related concepts in algebraic geometry. Then we present some recent results on moduli-spaces of vector bundles on non-Kaehler Calabi-Yau 3-folds and their consequences for heterotic string theory.
Equity trees and graphs via information theory
NASA Astrophysics Data System (ADS)
Harré, M.; Bossomaier, T.
2010-01-01
We investigate the similarities and differences between two measures of the relationship between equities traded in financial markets. Our measures are the correlation coefficients and the mutual information. In the context of financial markets correlation coefficients are well established whereas mutual information has not previously been as well studied despite its theoretically appealing properties. We show that asset trees which are derived from either the correlation coefficients or the mutual information have a mixture of both similarities and differences at the individual equity level and at the macroscopic level. We then extend our consideration from trees to graphs using the "genus 0" condition recently introduced in order to study the networks of equities.
A Cohomology Theory of Grading-Restricted Vertex Algebras
NASA Astrophysics Data System (ADS)
Huang, Yi-Zhi
2014-04-01
We introduce a cohomology theory of grading-restricted vertex algebras. To construct the correct cohomologies, we consider linear maps from tensor powers of a grading-restricted vertex algebra to "rational functions valued in the algebraic completion of a module for the algebra," instead of linear maps from tensor powers of the algebra to a module for the algebra. One subtle complication arising from such functions is that we have to carefully address the issue of convergence when we compose these linear maps with vertex operators. In particular, for each , we have an inverse system of nth cohomologies and an additional nth cohomology of a grading-restricted vertex algebra V with coefficients in a V-module W such that is isomorphic to the inverse limit of the inverse system . In the case of n = 2, there is an additional second cohomology denoted by which will be shown in a sequel to the present paper to correspond to what we call square-zero extensions of V and to first order deformations of V when W = V.
Algebraic isomorphism in two-dimensional anomalous gauge theories
Carvalhaes, C.G.; Natividade, C.P.
1997-08-01
The operator solution of the anomalous chiral Schwinger model is discussed on the basis of the general principles of Wightman field theory. Some basic structural properties of the model are analyzed taking a careful control on the Hilbert space associated with the Wightman functions. The isomorphism between gauge noninvariant and gauge invariant descriptions of the anomalous theory is established in terms of the corresponding field algebras. We show that (i) the {Theta}-vacuum representation and (ii) the suggested equivalence of vector Schwinger model and chiral Schwinger model cannot be established in terms of the intrinsic field algebra. {copyright} 1997 Academic Press, Inc.
Graph theory findings in the pathophysiology of temporal lobe epilepsy
Chiang, Sharon; Haneef, Zulfi
2014-01-01
Temporal lobe epilepsy (TLE) is the most common form of adult epilepsy. Accumulating evidence has shown that TLE is a disorder of abnormal epileptogenic networks, rather than focal sources. Graph theory allows for a network-based representation of TLE brain networks, and has potential to illuminate characteristics of brain topology conducive to TLE pathophysiology, including seizure initiation and spread. We review basic concepts which we believe will prove helpful in interpreting results rapidly emerging from graph theory research in TLE. In addition, we summarize the current state of graph theory findings in TLE as they pertain its pathophysiology. Several common findings have emerged from the many modalities which have been used to study TLE using graph theory, including structural MRI, diffusion tensor imaging, surface EEG, intracranial EEG, magnetoencephalography, functional MRI, cell cultures, simulated models, and mouse models, involving increased regularity of the interictal network configuration, altered local segregation and global integration of the TLE network, and network reorganization of temporal lobe and limbic structures. As different modalities provide different views of the same phenomenon, future studies integrating data from multiple modalities are needed to clarify findings and contribute to the formation of a coherent theory on the pathophysiology of TLE. PMID:24831083
Graph theory findings in the pathophysiology of temporal lobe epilepsy.
Chiang, Sharon; Haneef, Zulfi
2014-07-01
Temporal lobe epilepsy (TLE) is the most common form of adult epilepsy. Accumulating evidence has shown that TLE is a disorder of abnormal epileptogenic networks, rather than focal sources. Graph theory allows for a network-based representation of TLE brain networks, and has potential to illuminate characteristics of brain topology conducive to TLE pathophysiology, including seizure initiation and spread. We review basic concepts which we believe will prove helpful in interpreting results rapidly emerging from graph theory research in TLE. In addition, we summarize the current state of graph theory findings in TLE as they pertain its pathophysiology. Several common findings have emerged from the many modalities which have been used to study TLE using graph theory, including structural MRI, diffusion tensor imaging, surface EEG, intracranial EEG, magnetoencephalography, functional MRI, cell cultures, simulated models, and mouse models, involving increased regularity of the interictal network configuration, altered local segregation and global integration of the TLE network, and network reorganization of temporal lobe and limbic structures. As different modalities provide different views of the same phenomenon, future studies integrating data from multiple modalities are needed to clarify findings and contribute to the formation of a coherent theory on the pathophysiology of TLE. PMID:24831083
Applying Directed Graph Theory to Faculty Contact Structure.
ERIC Educational Resources Information Center
House, Ernest R.; Long, John M.
Although recent writings indicate the importance of personal contact structures in diffusing innovations and in determining perceptions, the internal contact structure of the school faculty remains unexamined. This study applies directed graph theory, a new branch of mathematics, to analyzing school contact structure. Sociometric data and…
Category of trees in representation theory of quantum algebras
Moskaliuk, N. M.; Moskaliuk, S. S.
2013-10-15
New applications of categorical methods are connected with new additional structures on categories. One of such structures in representation theory of quantum algebras, the category of Kuznetsov-Smorodinsky-Vilenkin-Smirnov (KSVS) trees, is constructed, whose objects are finite rooted KSVS trees and morphisms generated by the transition from a KSVS tree to another one.
Algebraic K-theory of discrete subgroups of Lie groups.
Farrell, F T; Jones, L E
1987-05-01
Let G be a Lie group (with finitely many connected components) and Gamma be a discrete, cocompact, torsion-free subgroup of G. We rationally calculate the algebraic K-theory of the integral group ring ZGamma in terms of the homology of Gamma with trivial rational coefficients. PMID:16593834
Algebraic K-theory of discrete subgroups of Lie groups
Farrell, F. T.; Jones, L. E.
1987-01-01
Let G be a Lie group (with finitely many connected components) and Γ be a discrete, cocompact, torsion-free subgroup of G. We rationally calculate the algebraic K-theory of the integral group ring ZΓ in terms of the homology of Γ with trivial rational coefficients. PMID:16593834
Partial Fractions in Calculus, Number Theory, and Algebra
ERIC Educational Resources Information Center
Yackel, C. A.; Denny, J. K.
2007-01-01
This paper explores the development of the method of partial fraction decomposition from elementary number theory through calculus to its abstraction in modern algebra. This unusual perspective makes the topic accessible and relevant to readers from high school through seasoned calculus instructors.
Dynamic modeling of electrochemical systems using linear graph theory
NASA Astrophysics Data System (ADS)
Dao, Thanh-Son; McPhee, John
An electrochemical cell is a multidisciplinary system which involves complex chemical, electrical, and thermodynamical processes. The primary objective of this paper is to develop a linear graph-theoretical modeling for the dynamic description of electrochemical systems through the representation of the system topologies. After a brief introduction to the topic and a review of linear graphs, an approach to develop linear graphs for electrochemical systems using a circuitry representation is discussed, followed in turn by the use of the branch and chord transformation techniques to generate final dynamic equations governing the system. As an example, the application of linear graph theory to modeling a nickel metal hydride (NiMH) battery will be presented. Results show that not only the number of equations are reduced significantly, but also the linear graph model simulates faster compared to the original lumped parameter model. The approach presented in this paper can be extended to modeling complex systems such as an electric or hybrid electric vehicle where a battery pack is interconnected with other components in many different domains.
Forms and algebras in (half-)maximal supergravity theories
NASA Astrophysics Data System (ADS)
Howe, Paul; Palmkvist, Jakob
2015-05-01
The forms in D-dimensional (half-)maximal supergravity theories are discussed for 3 ≤ D ≤ 11. Superspace methods are used to derive consistent sets of Bianchi identities for all the forms for all degrees, and to show that they are soluble and fully compatible with supersymmetry. The Bianchi identities determine Lie superalgebras that can be extended to Borcherds superalgebras of a special type. It is shown that any Borcherds superalgebra of this type gives the same form spectrum, up to an arbitrary degree, as an associated Kac-Moody algebra. For maximal supergravity up to D-form potentials, this is the very extended Kac-Moody algebra E 11. It is also shown how gauging can be carried out in a simple fashion by deforming the Bianchi identities by means of a new algebraic element related to the embedding tensor. In this case the appropriate extension of the form algebra is a truncated version of the so-called tensor hierarchy algebra.
Edge covers and independence: Algebraic approach
NASA Astrophysics Data System (ADS)
Kalinina, E. A.; Khitrov, G. M.; Pogozhev, S. V.
2016-06-01
In this paper, linear algebra methods are applied to solve some problems of graph theory. For ordinary connected graphs, edge coverings and independent sets are considered. Some results concerning minimum edge covers and maximum matchings are proved with the help of linear algebraic approach. The problem of finding a maximum matching of a graph is fundamental both practically and theoretically, and has numerous applications, e.g., in computational chemistry and mathematical chemistry.
NASA Astrophysics Data System (ADS)
Binterová, Helena; Fuchs, Eduard
2014-07-01
In this paper, alternative descriptions of functions are demonstrated with the use of a computer. If we understand functions as mono-unary algebraic functions or functional graphs, it is possible, even at the school level, to suitably present many of their characteristics. First, we describe cyclic graphs of constant and linear functions, which are a part of the upper-secondary level educational curriculum. Students are usually surprised by the unexpected characteristics of such simple functions which cannot be revealed using the traditional Cartesian graphing. The next part of the paper deals with the characteristics of functional graphs of quadratic functions, which play an important role in school mathematics and in applications, for instance, in the description of non-linear processes. We show that their description is much more complicated. In contrast to functional graphs of linear functions, it is necessary to use computers. Students can find space for their own individual exploration to reveal lines of interesting characteristics of quadratic functions, which give students a new view on this part of school mathematics.
Stationary waves on nonlinear quantum graphs: General framework and canonical perturbation theory
NASA Astrophysics Data System (ADS)
Gnutzmann, Sven; Waltner, Daniel
2016-03-01
In this paper we present a general framework for solving the stationary nonlinear Schrödinger equation (NLSE) on a network of one-dimensional wires modeled by a metric graph with suitable matching conditions at the vertices. A formal solution is given that expresses the wave function and its derivative at one end of an edge (wire) nonlinearly in terms of the values at the other end. For the cubic NLSE this nonlinear transfer operation can be expressed explicitly in terms of Jacobi elliptic functions. Its application reduces the problem of solving the corresponding set of coupled ordinary nonlinear differential equations to a finite set of nonlinear algebraic equations. For sufficiently small amplitudes we use canonical perturbation theory, which makes it possible to extract the leading nonlinear corrections over large distances.
Stationary waves on nonlinear quantum graphs: General framework and canonical perturbation theory.
Gnutzmann, Sven; Waltner, Daniel
2016-03-01
In this paper we present a general framework for solving the stationary nonlinear Schrödinger equation (NLSE) on a network of one-dimensional wires modeled by a metric graph with suitable matching conditions at the vertices. A formal solution is given that expresses the wave function and its derivative at one end of an edge (wire) nonlinearly in terms of the values at the other end. For the cubic NLSE this nonlinear transfer operation can be expressed explicitly in terms of Jacobi elliptic functions. Its application reduces the problem of solving the corresponding set of coupled ordinary nonlinear differential equations to a finite set of nonlinear algebraic equations. For sufficiently small amplitudes we use canonical perturbation theory, which makes it possible to extract the leading nonlinear corrections over large distances. PMID:27078341
NASA Astrophysics Data System (ADS)
Hoppe, Jens
Over the past years, associative algebras have come to play a major role in several areas of theoretical physics. Firstly, it has been realized that Yang Baxter algebras [1] constitute the relevant structure underlying 1+1 dimensional integrable models; in addition, their relation to braid groups, the theory of knots and links, and the exchange algebras of 1+1 dimensional conformal field theories [2] has been quite well understood by now. Secondly, deformations of Poisson structures that appeared in 2+1 dimensional field theories as infinite dimensional symmetry algebras possess underlying associative structures, which have also been studied in some detail (concerning higher spin theories see, e.g., [3, 4] and references therein, concerning the enveloping algebra of sl(2, C) see, e.g., [5], concerning deformations of diffAT2 — the Lie algebra of infinitesimal area preserving diffeomorphisms of the Torus — see [6, 7, 8, 9]). Ideas on how both investigations could eventually converge (i.e., a relation between 2+1 and 1+1 dimensions) have, e.g., been expressed in [10]. As indicated by the two subtitles there will be two parts to my paper: the first one presents a view on something I met long ago [11], and recently got interested in again [5, 7, 9, 12], while the second part introduces some algebraic structures that seem to be interesting, and possibly new.
Non-simply laced Lie algebras via F theory strings
NASA Astrophysics Data System (ADS)
Bonora, L.; Savelli, R.
2010-11-01
In order to describe the appearance in F theory of the non-simply-laced Lie algebras, we use the representation of symmetry enhancements by means of string junctions. After an introduction to the techniques used to describe symmetry enhancement, that is algebraic geometry, BPS states analysis and string junctions, we concentrate on the latter. We give an explicit description of the folding of D 2n to B n , of the folding of E 6 to F 4 and that of D 4 to G 2 in terms of junctions and Jordan strings. We also discuss the case of C n , but we are unable in this case to provide a string interpretation.
Do malaria parasites follow the algebra of sex ratio theory?
Schall, Jos J
2009-03-01
The ratio of male to female gametocytes seen in infections of Plasmodium and related haemosporidian parasites varies substantially, both within and among parasite species. Sex ratio theory, a mainstay of evolutionary biology, accounts for this variation. The theory provides an algebraic solution for the optimal sex ratio that will maximize parasite fitness. A crucial term in this solution is the probability of selfing by clone-mates within the vector (based on the clone number and their relative abundance). Definitive tests of the theory have proven elusive because of technical challenges in measuring clonal diversity within infections. Newly developed molecular methods now provide opportunities to test the theory with an exquisite precision. PMID:19201653
Functional connectivity and graph theory in preclinical Alzheimer's disease.
Brier, Matthew R; Thomas, Jewell B; Fagan, Anne M; Hassenstab, Jason; Holtzman, David M; Benzinger, Tammie L; Morris, John C; Ances, Beau M
2014-04-01
Alzheimer's disease (AD) has a long preclinical phase in which amyloid and tau cerebral pathology accumulate without producing cognitive symptoms. Resting state functional connectivity magnetic resonance imaging has demonstrated that brain networks degrade during symptomatic AD. It is unclear to what extent these degradations exist before symptomatic onset. In this study, we investigated graph theory metrics of functional integration (path length), functional segregation (clustering coefficient), and functional distinctness (modularity) as a function of disease severity. Further, we assessed whether these graph metrics were affected in cognitively normal participants with cerebrospinal fluid evidence of preclinical AD. Clustering coefficient and modularity, but not path length, were reduced in AD. Cognitively normal participants who harbored AD biomarker pathology also showed reduced values in these graph measures, demonstrating brain changes similar to, but smaller than, symptomatic AD. Only modularity was significantly affected by age. We also demonstrate that AD has a particular effect on hub-like regions in the brain. We conclude that AD causes large-scale disconnection that is present before onset of symptoms. PMID:24216223
ERIC Educational Resources Information Center
Merriweather, Michelle; Tharp, Marcia L.
1999-01-01
Focuses on changes in attitude toward mathematics and calculator use and changes in how general mathematics students naturalistically solve algebraic problems. Uses a survey to determine whether a student is rule-based. Concludes that the rule-based students used an equation to solve the algebraic word problem whereas the non-rule-based students…
Graph Theory Roots of Spatial Operators for Kinematics and Dynamics
NASA Technical Reports Server (NTRS)
Jain, Abhinandan
2011-01-01
Spatial operators have been used to analyze the dynamics of robotic multibody systems and to develop novel computational dynamics algorithms. Mass matrix factorization, inversion, diagonalization, and linearization are among several new insights obtained using such operators. While initially developed for serial rigid body manipulators, the spatial operators and the related mathematical analysis have been shown to extend very broadly including to tree and closed topology systems, to systems with flexible joints, links, etc. This work uses concepts from graph theory to explore the mathematical foundations of spatial operators. The goal is to study and characterize the properties of the spatial operators at an abstract level so that they can be applied to a broader range of dynamics problems. The rich mathematical properties of the kinematics and dynamics of robotic multibody systems has been an area of strong research interest for several decades. These properties are important to understand the inherent physical behavior of systems, for stability and control analysis, for the development of computational algorithms, and for model development of faithful models. Recurring patterns in spatial operators leads one to ask the more abstract question about the properties and characteristics of spatial operators that make them so broadly applicable. The idea is to step back from the specific application systems, and understand more deeply the generic requirements and properties of spatial operators, so that the insights and techniques are readily available across different kinematics and dynamics problems. In this work, techniques from graph theory were used to explore the abstract basis for the spatial operators. The close relationship between the mathematical properties of adjacency matrices for graphs and those of spatial operators and their kernels were established. The connections hold across very basic requirements on the system topology, the nature of the component
Using Combinatorica/Mathematica for Student Projects in Random Graph Theory
ERIC Educational Resources Information Center
Pfaff, Thomas J.; Zaret, Michele
2006-01-01
We give an example of a student project that experimentally explores a topic in random graph theory. We use the "Combinatorica" package in "Mathematica" to estimate the minimum number of edges needed in a random graph to have a 50 percent chance that the graph is connected. We provide the "Mathematica" code and compare it to the known theoretical…
n-Nucleotide circular codes in graph theory.
Fimmel, Elena; Michel, Christian J; Strüngmann, Lutz
2016-03-13
The circular code theory proposes that genes are constituted of two trinucleotide codes: the classical genetic code with 61 trinucleotides for coding the 20 amino acids (except the three stop codons {TAA,TAG,TGA}) and a circular code based on 20 trinucleotides for retrieving, maintaining and synchronizing the reading frame. It relies on two main results: the identification of a maximal C(3) self-complementary trinucleotide circular code X in genes of bacteria, eukaryotes, plasmids and viruses (Michel 2015 J. Theor. Biol. 380, 156-177. (doi:10.1016/j.jtbi.2015.04.009); Arquès & Michel 1996 J. Theor. Biol. 182, 45-58. (doi:10.1006/jtbi.1996.0142)) and the finding of X circular code motifs in tRNAs and rRNAs, in particular in the ribosome decoding centre (Michel 2012 Comput. Biol. Chem. 37, 24-37. (doi:10.1016/j.compbiolchem.2011.10.002); El Soufi & Michel 2014 Comput. Biol. Chem. 52, 9-17. (doi:10.1016/j.compbiolchem.2014.08.001)). The univerally conserved nucleotides A1492 and A1493 and the conserved nucleotide G530 are included in X circular code motifs. Recently, dinucleotide circular codes were also investigated (Michel & Pirillo 2013 ISRN Biomath. 2013, 538631. (doi:10.1155/2013/538631); Fimmel et al. 2015 J. Theor. Biol. 386, 159-165. (doi:10.1016/j.jtbi.2015.08.034)). As the genetic motifs of different lengths are ubiquitous in genes and genomes, we introduce a new approach based on graph theory to study in full generality n-nucleotide circular codes X, i.e. of length 2 (dinucleotide), 3 (trinucleotide), 4 (tetranucleotide), etc. Indeed, we prove that an n-nucleotide code X is circular if and only if the corresponding graph [Formula: see text] is acyclic. Moreover, the maximal length of a path in [Formula: see text] corresponds to the window of nucleotides in a sequence for detecting the correct reading frame. Finally, the graph theory of tournaments is applied to the study of dinucleotide circular codes. It has full equivalence between the combinatorics
On the algebraic K-theory of the complex K-theory spectrum
NASA Astrophysics Data System (ADS)
Ausoni, Christian
2010-03-01
Let p>3 be a prime, let ku be the connective complex K-theory spectrum, and let K(ku) be the algebraic K-theory spectrum of ku. We study the p-primary homotopy type of the spectrum K(ku) by computing its mod (p,v_1) homotopy groups. We show that up to a finite summand, these groups form a finitely generated free module over a polynomial algebra F_p[b], where b is a class of degree 2p+2 defined as a higher Bott element.
Topological insulators and C*-algebras: Theory and numerical practice
Hastings, Matthew B.; Loring, Terry A.
2011-07-15
Research Highlights: > We classify topological insulators using C* algebras. > We present new K-theory invariants. > We develop efficient numerical algorithms based on this technique. > We observe unexpected quantum phase transitions using our algorithm. - Abstract: We apply ideas from C*-algebra to the study of disordered topological insulators. We extract certain almost commuting matrices from the free Fermi Hamiltonian, describing band projected coordinate matrices. By considering topological obstructions to approximating these matrices by exactly commuting matrices, we are able to compute invariants quantifying different topological phases. We generalize previous two dimensional results to higher dimensions; we give a general expression for the topological invariants for arbitrary dimension and several symmetry classes, including chiral symmetry classes, and we present a detailed K-theory treatment of this expression for time reversal invariant three dimensional systems. We can use these results to show non-existence of localized Wannier functions for these systems. We use this approach to calculate the index for time-reversal invariant systems with spin-orbit scattering in three dimensions, on sizes up to 12{sup 3}, averaging over a large number of samples. The results show an interesting separation between the localization transition and the point at which the average index (which can be viewed as an 'order parameter' for the topological insulator) begins to fluctuate from sample to sample, implying the existence of an unsuspected quantum phase transition separating two different delocalized phases in this system. One of the particular advantages of the C*-algebraic technique that we present is that it is significantly faster in practice than other methods of computing the index, allowing the study of larger systems. In this paper, we present a detailed discussion of numerical implementation of our method.
Calculation of exchange energies using algebraic perturbation theory
Burrows, B. L.; Dalgarno, A.; Cohen, M.
2010-04-15
An algebraic perturbation theory is presented for efficient calculations of localized states and hence of exchange energies, which are the differences between low-lying states of the valence electron of a molecule, formed by the collision of an ion Y{sup +} with an atom X. For the case of a homonuclear molecule these are the gerade and ungerade states and the exchange energy is an exponentially decreasing function of the internuclear distance. For such homonuclear systems the theory is used in conjunction with the Herring-Holstein technique to give accurate exchange energies for a range of intermolecular separations R. Since the perturbation parameter is essentially 1/R, this method is suitable for large R. In particular, exchange energies are calculated for X{sub 2}{sup +} systems, where X is H, Li, Na, K, Rb, or Cs.
COMMENT: Comment on `Dirac theory in spacetime algebra'
NASA Astrophysics Data System (ADS)
Baylis, William E.
2002-06-01
In contrast to formulations of the Dirac theory by Hestenes and by the present author, the formulation recently presented by Joyce (Joyce W P 2001 J. Phys. A: Math. Gen. 34 1991-2005) is equivalent to the usual Dirac equation only in the case of vanishing mass. For nonzero mass, solutions to Joyce's equation can be solutions either of the Dirac equation in the Hestenes form or of the same equation with the sign of the mass reversed, and in general they are mixtures of the two possibilities. Because of this relationship, Joyce obtains twice as many linearly independent plane-wave solutions for a given momentum eigenvalue as exist in the conventional theory. A misconception about the symmetry of the Hestenes equation and the geometric significance of the algebraic spinors is also briefly discussed.
Graph theory approach for match reduction in image mosaicing.
Elibol, Armagan; Gracias, Nuno; Garcia, Rafael; Kim, Jinwhan
2014-04-01
One of the crucial steps in image mosaicing is global alignment, which requires finding the best image registration parameters by employing nonlinear minimization methods over correspondences between overlapping image pairs for a dataset. Based on graph theory, we propose a simple but efficient method to reduce the number of overlapping image pairs without any noticeable effect on the final mosaic quality. This reduction significantly lowers the computational cost of the image mosaicing process. The proposed method can be applied in a topology estimation process to reduce the number of image matching attempts. The method has been validated through experiments on challenging underwater image sequences obtained during sea trials with different unmanned underwater vehicles. PMID:24695139
Automatic cone photoreceptor segmentation using graph theory and dynamic programming
Chiu, Stephanie J.; Lokhnygina, Yuliya; Dubis, Adam M.; Dubra, Alfredo; Carroll, Joseph; Izatt, Joseph A.; Farsiu, Sina
2013-01-01
Geometrical analysis of the photoreceptor mosaic can reveal subclinical ocular pathologies. In this paper, we describe a fully automatic algorithm to identify and segment photoreceptors in adaptive optics ophthalmoscope images of the photoreceptor mosaic. This method is an extension of our previously described closed contour segmentation framework based on graph theory and dynamic programming (GTDP). We validated the performance of the proposed algorithm by comparing it to the state-of-the-art technique on a large data set consisting of over 200,000 cones and posted the results online. We found that the GTDP method achieved a higher detection rate, decreasing the cone miss rate by over a factor of five. PMID:23761854
Topological insulators and C∗-algebras: Theory and numerical practice
NASA Astrophysics Data System (ADS)
Hastings, Matthew B.; Loring, Terry A.
2011-07-01
We apply ideas from C∗-algebra to the study of disordered topological insulators. We extract certain almost commuting matrices from the free Fermi Hamiltonian, describing band projected coordinate matrices. By considering topological obstructions to approximating these matrices by exactly commuting matrices, we are able to compute invariants quantifying different topological phases. We generalize previous two dimensional results to higher dimensions; we give a general expression for the topological invariants for arbitrary dimension and several symmetry classes, including chiral symmetry classes, and we present a detailed K-theory treatment of this expression for time reversal invariant three dimensional systems. We can use these results to show non-existence of localized Wannier functions for these systems. We use this approach to calculate the index for time-reversal invariant systems with spin-orbit scattering in three dimensions, on sizes up to 12 3, averaging over a large number of samples. The results show an interesting separation between the localization transition and the point at which the average index (which can be viewed as an "order parameter" for the topological insulator) begins to fluctuate from sample to sample, implying the existence of an unsuspected quantum phase transition separating two different delocalized phases in this system. One of the particular advantages of the C∗-algebraic technique that we present is that it is significantly faster in practice than other methods of computing the index, allowing the study of larger systems. In this paper, we present a detailed discussion of numerical implementation of our method.
K-theory of the chair tiling via AF-algebras
NASA Astrophysics Data System (ADS)
Julien, Antoine; Savinien, Jean
2016-08-01
We compute the K-theory groups of the groupoid C∗-algebra of the chair tiling, using a new method. We use exact sequences of Putnam to compute these groups from the K-theory groups of the AF-algebras of the substitution and the induced lower dimensional substitutions on edges and vertices.
Graph Theory and Its Application in Educational Research: A Review and Integration.
ERIC Educational Resources Information Center
Tatsuoka, Maurice M.
1986-01-01
A nontechnical exposition of graph theory is presented, followed by survey of the literature on applications of graph theory in research in education and related disciplines. Applications include order-theoretic studies of the dimensionality of data sets, the investigation of hierarchical structures in various domains, and cluster analysis.…
Alternative Representations for Algebraic Problem Solving: When Are Graphs Better than Equations?
ERIC Educational Resources Information Center
Mielicki, Marta K.; Wiley, Jennifer
2016-01-01
Successful algebraic problem solving entails adaptability of solution methods using different representations. Prior research has suggested that students are more likely to prefer symbolic solution methods (equations) over graphical ones, even when graphical methods should be more efficient. However, this research has not tested how representation…
On a programming language for graph algorithms
NASA Technical Reports Server (NTRS)
Rheinboldt, W. C.; Basili, V. R.; Mesztenyi, C. K.
1971-01-01
An algorithmic language, GRAAL, is presented for describing and implementing graph algorithms of the type primarily arising in applications. The language is based on a set algebraic model of graph theory which defines the graph structure in terms of morphisms between certain set algebraic structures over the node set and arc set. GRAAL is modular in the sense that the user specifies which of these mappings are available with any graph. This allows flexibility in the selection of the storage representation for different graph structures. In line with its set theoretic foundation, the language introduces sets as a basic data type and provides for the efficient execution of all set and graph operators. At present, GRAAL is defined as an extension of ALGOL 60 (revised) and its formal description is given as a supplement to the syntactic and semantic definition of ALGOL. Several typical graph algorithms are written in GRAAL to illustrate various features of the language and to show its applicability.
Solutions in bosonic string field theory and higher spin algebras in AdS
NASA Astrophysics Data System (ADS)
Polyakov, Dimitri
2015-11-01
We find a class of analytic solutions in open bosonic string field theory, parametrized by the chiral copy of higher spin algebra in AdS3. The solutions are expressed in terms of the generating function for the products of Bell polynomials in derivatives of bosonic space-time coordinates Xm(z ) of the open string, the form of which is determined in this work. The products of these polynomials form a natural operator algebra realizations of w∞ (area-preserving diffeomorphisms), enveloping algebra of SU(2) and higher spin algebra in AdS3. The class of string field theory solutions found can, in turn, be interpreted as the "enveloping of enveloping," or the enveloping of AdS3 higher spin algebra. We also discuss the extensions of this class of solutions to superstring theory and their relations to higher spin algebras in higher space-time dimensions.
The Clifford algebra of physical space and Dirac theory
NASA Astrophysics Data System (ADS)
Vaz, Jayme, Jr.
2016-09-01
The claim found in many textbooks that the Dirac equation cannot be written solely in terms of Pauli matrices is shown to not be completely true. It is only true as long as the term β \\psi in the usual Dirac factorization of the Klein–Gordon equation is assumed to be the product of a square matrix β and a column matrix ψ. In this paper we show that there is another possibility besides this matrix product, in fact a possibility involving a matrix operation, and show that it leads to another possible expression for the Dirac equation. We show that, behind this other possible factorization is the formalism of the Clifford algebra of physical space. We exploit this fact, and discuss several different aspects of Dirac theory using this formalism. In particular, we show that there are four different possible sets of definitions for the parity, time reversal, and charge conjugation operations for the Dirac equation.
Quantization of gauge fields, graph polynomials and graph homology
Kreimer, Dirk; Sars, Matthias; Suijlekom, Walter D. van
2013-09-15
We review quantization of gauge fields using algebraic properties of 3-regular graphs. We derive the Feynman integrand at n loops for a non-abelian gauge theory quantized in a covariant gauge from scalar integrands for connected 3-regular graphs, obtained from the two Symanzik polynomials. The transition to the full gauge theory amplitude is obtained by the use of a third, new, graph polynomial, the corolla polynomial. This implies effectively a covariant quantization without ghosts, where all the relevant signs of the ghost sector are incorporated in a double complex furnished by the corolla polynomial–we call it cycle homology–and by graph homology. -- Highlights: •We derive gauge theory Feynman from scalar field theory with 3-valent vertices. •We clarify the role of graph homology and cycle homology. •We use parametric renormalization and the new corolla polynomial.
Graph theory as a proxy for spatially explicit population models in conservation planning.
Minor, Emily S; Urban, Dean L
2007-09-01
Spatially explicit population models (SEPMs) are often considered the best way to predict and manage species distributions in spatially heterogeneous landscapes. However, they are computationally intensive and require extensive knowledge of species' biology and behavior, limiting their application in many cases. An alternative to SEPMs is graph theory, which has minimal data requirements and efficient algorithms. Although only recently introduced to landscape ecology, graph theory is well suited to ecological applications concerned with connectivity or movement. This paper compares the performance of graph theory to a SEPM in selecting important habitat patches for Wood Thrush (Hylocichla mustelina) conservation. We use both models to identify habitat patches that act as population sources and persistent patches and also use graph theory to identify patches that act as stepping stones for dispersal. Correlations of patch rankings were very high between the two models. In addition, graph theory offers the ability to identify patches that are very important to habitat connectivity and thus long-term population persistence across the landscape. We show that graph theory makes very similar predictions in most cases and in other cases offers insight not available from the SEPM, and we conclude that graph theory is a suitable and possibly preferable alternative to SEPMs for species conservation in heterogeneous landscapes. PMID:17913139
NASA Astrophysics Data System (ADS)
Samatova, N. F.; Schmidt, M. C.; Hendrix, W.; Breimyer, P.; Thomas, K.; Park, B.-H.
2008-07-01
Data-driven construction of predictive models for biological systems faces challenges from data intensity, uncertainty, and computational complexity. Data-driven model inference is often considered a combinatorial graph problem where an enumeration of all feasible models is sought. The data-intensive and the NP-hard nature of such problems, however, challenges existing methods to meet the required scale of data size and uncertainty, even on modern supercomputers. Maximal clique enumeration (MCE) in a graph derived from such biological data is often a rate-limiting step in detecting protein complexes in protein interaction data, finding clusters of co-expressed genes in microarray data, or identifying clusters of orthologous genes in protein sequence data. We report two key advances that address this challenge. We designed and implemented the first (to the best of our knowledge) parallel MCE algorithm that scales linearly on thousands of processors running MCE on real-world biological networks with thousands and hundreds of thousands of vertices. In addition, we proposed and developed the Graph Perturbation Theory (GPT) that establishes a foundation for efficiently solving the MCE problem in perturbed graphs, which model the uncertainty in the data. GPT formulates necessary and sufficient conditions for detecting the differences between the sets of maximal cliques in the original and perturbed graphs and reduces the enumeration time by more than 80% compared to complete recomputation.
A Theory of Graphs for Reading Comprehension and Writing Communication.
ERIC Educational Resources Information Center
Fry, Edward
Graphs are increasingly being used in written communication and writers expect readers to understand them. One definition of graphs--information transmitted by position of point, line or area on a two dimensional surface--excludes displays composed chiefly of numbers or words such as tables or outlines. However, it does include time lines, flow…
Hopf algebras and topological recursion
NASA Astrophysics Data System (ADS)
Esteves, João N.
2015-11-01
We consider a model for topological recursion based on the Hopf algebra of planar binary trees defined by Loday and Ronco (1998 Adv. Math. 139 293-309 We show that extending this Hopf algebra by identifying pairs of nearest neighbor leaves, and thus producing graphs with loops, we obtain the full recursion formula discovered by Eynard and Orantin (2007 Commun. Number Theory Phys. 1 347-452).
Scheduling for indoor visible light communication based on graph theory.
Tao, Yuyang; Liang, Xiao; Wang, Jiaheng; Zhao, Chunming
2015-02-01
Visible light communication (VLC) has drawn much attention in the field of high-rate indoor wireless communication. While most existing works focused on point-to-point VLC technologies, few studies have concerned multiuser VLC, where multiple optical access points (APs) transmit data to multiple user receivers. In such scenarios, inter-user interference constitutes the major factor limiting the system performance. Therefore, a proper scheduling scheme has to be proposed to coordinate the interference and optimize the whole system performance. In this work, we aim to maximize the sum rate of the system while taking into account user fairness by appropriately assigning LED lamps to multiple users. The formulated scheduling problem turns out to be a maximum weighted independent set problem. We then propose a novel and efficient resource allocation method based on graph theory to achieve high sum rates. Moreover, we also introduce proportional fairness into our scheduling scheme to ensure the user fairness. Our proposed scheduling scheme can, with low complexity, achieve more multiplexing gains, higher sum rate, and better fairness than the existing works. PMID:25836136
Fragmentation network of doubly charged methionine: Interpretation using graph theory.
Ha, D T; Yamazaki, K; Wang, Y; Alcamí, M; Maeda, S; Kono, H; Martín, F; Kukk, E
2016-09-01
The fragmentation of doubly charged gas-phase methionine (HO2CCH(NH2)CH2CH2SCH3) is systematically studied using the self-consistent charge density functional tight-binding molecular dynamics (MD) simulation method. We applied graph theory to analyze the large number of the calculated MD trajectories, which appears to be a highly effective and convenient means of extracting versatile information from the large data. The present theoretical results strongly concur with the earlier studied experimental ones. Essentially, the dication dissociates into acidic group CO2H and basic group C4NSH10. The former may carry a single or no charge and stays intact in most cases, whereas the latter may hold either a single or a double charge and tends to dissociate into smaller fragments. The decay of the basic group is observed to follow the Arrhenius law. The dissociation pathways to CO2H and C4NSH10 and subsequent fragmentations are also supported by ab initio calculations. PMID:27608997
ERIC Educational Resources Information Center
Debnath, Lokenath
2010-01-01
This article is essentially devoted to a brief historical introduction to Euler's formula for polyhedra, topology, theory of graphs and networks with many examples from the real-world. Celebrated Konigsberg seven-bridge problem and some of the basic properties of graphs and networks for some understanding of the macroscopic behaviour of real…
Clifford Algebra Cℓ 3(ℂ) for Applications to Field Theories
NASA Astrophysics Data System (ADS)
Panicaud, B.
2011-10-01
The multivectorial algebras present yet both an academic and a technological interest. Difficulties can occur for their use. Indeed, in all applications care is taken to distinguish between polar and axial vectors and between scalars and pseudo scalars. Then a total of eight elements are often considered even if they are not given the correct name of multivectors. Eventually because of their simplicity, only the vectorial algebra or the quaternions algebra are explicitly used for physical applications. Nevertheless, it should be more convenient to use directly more complex algebras in order to have a wider range of application. The aim of this paper is to inquire into one particular Clifford algebra which could solve this problem. The present study is both didactic concerning its construction and pragmatic because of the introduced applications. The construction method is not an original one. But this latter allows to build up the associated real algebra as well as a peculiar formalism that enables a formal analogy with the classical vectorial algebra. Finally several fields of the theoretical physics will be described thanks to this algebra, as well as a more applied case in general relativity emphasizing simultaneously its relative validity in this particular domain and the easiness of modeling some physical problems.
Fibonacci Identities, Matrices, and Graphs
ERIC Educational Resources Information Center
Huang, Danrun
2005-01-01
General strategies used to help discover, prove, and generalize identities for Fibonacci numbers are described along with some properties about the determinants of square matrices. A matrix proof for identity (2) that has received immense attention from many branches of mathematics, like linear algebra, dynamical systems, graph theory and others…
Chemical Applications of Graph Theory: Part I. Fundamentals and Topological Indices.
ERIC Educational Resources Information Center
Hansen, Peter J.; Jurs, Peter C.
1988-01-01
Explores graph theory and use of topological indices to predict boiling points. Lists three indices: Wiener Number, Randic Branching Index and Molecular Connectivity, and Molecular Identification numbers. Warns of inadequacies with stereochemistry. (ML)
Perturbative quantization of Yang-Mills theory with classical double as gauge algebra
NASA Astrophysics Data System (ADS)
Ruiz Ruiz, F.
2016-02-01
Perturbative quantization of Yang-Mills theory with a gauge algebra given by the classical double of a semisimple Lie algebra is considered. The classical double of a real Lie algebra is a nonsemisimple real Lie algebra that admits a nonpositive definite invariant metric, the indefiniteness of the metric suggesting an apparent lack of unitarity. It is shown that the theory is UV divergent at one loop and that there are no radiative corrections at higher loops. One-loop UV divergences are removed through renormalization of the coupling constant, thus introducing a renormalization scale. The terms in the classical action that would spoil unitarity are proved to be cohomologically trivial with respect to the Slavnov-Taylor operator that controls gauge invariance for the quantum theory. Hence they do not contribute gauge invariant radiative corrections to the quantum effective action and the theory is unitary.
Algebraic methods for diagonalization of a quaternion matrix in quaternionic quantum theory
Jiang Tongsong
2005-05-01
By means of complex representation and real representation of a quaternion matrix, this paper studies the problem of diagonalization of a quaternion matrix, gives two algebraic methods for diagonalization of quaternion matrices in quaternionic quantum theory.
NASA Technical Reports Server (NTRS)
Byrnes, C. I.
1980-01-01
It is noted that recent work by Kamen (1979) on the stability of half-plane digital filters shows that the problem of the existence of a feedback law also arises for other Banach algebras in applications. This situation calls for a realization theory and stabilizability criteria for systems defined over Banach for Frechet algebra A. Such a theory is developed here, with special emphasis placed on the construction of finitely generated realizations, the existence of coprime factorizations for T(s) defined over A, and the solvability of the quadratic optimal control problem and the associated algebraic Riccati equation over A.
NASA Astrophysics Data System (ADS)
Debnath, Lokenath
2010-09-01
This article is essentially devoted to a brief historical introduction to Euler's formula for polyhedra, topology, theory of graphs and networks with many examples from the real-world. Celebrated Königsberg seven-bridge problem and some of the basic properties of graphs and networks for some understanding of the macroscopic behaviour of real physical systems are included. We also mention some important and modern applications of graph theory or network problems from transportation to telecommunications. Graphs or networks are effectively used as powerful tools in industrial, electrical and civil engineering, communication networks in the planning of business and industry. Graph theory and combinatorics can be used to understand the changes that occur in many large and complex scientific, technical and medical systems. With the advent of fast large computers and the ubiquitous Internet consisting of a very large network of computers, large-scale complex optimization problems can be modelled in terms of graphs or networks and then solved by algorithms available in graph theory. Many large and more complex combinatorial problems dealing with the possible arrangements of situations of various kinds, and computing the number and properties of such arrangements can be formulated in terms of networks. The Knight's tour problem, Hamilton's tour problem, problem of magic squares, the Euler Graeco-Latin squares problem and their modern developments in the twentieth century are also included.
Detecting labor using graph theory on connectivity matrices of uterine EMG.
Al-Omar, S; Diab, A; Nader, N; Khalil, M; Karlsson, B; Marque, C
2015-08-01
Premature labor is one of the most serious health problems in the developed world. One of the main reasons for this is that no good way exists to distinguish true labor from normal pregnancy contractions. The aim of this paper is to investigate if the application of graph theory techniques to multi-electrode uterine EMG signals can improve the discrimination between pregnancy contractions and labor. To test our methods we first applied them to synthetic graphs where we detected some differences in the parameters results and changes in the graph model from pregnancy-like graphs to labor-like graphs. Then, we applied the same methods to real signals. We obtained the best differentiation between pregnancy and labor through the same parameters. Major improvements in differentiating between pregnancy and labor were obtained using a low pass windowing preprocessing step. Results show that real graphs generally became more organized when moving from pregnancy, where the graph showed random characteristics, to labor where the graph became a more small-world like graph. PMID:26736726
Time-dependence of graph theory metrics in functional connectivity analysis.
Chiang, Sharon; Cassese, Alberto; Guindani, Michele; Vannucci, Marina; Yeh, Hsiang J; Haneef, Zulfi; Stern, John M
2016-01-15
Brain graphs provide a useful way to computationally model the network structure of the connectome, and this has led to increasing interest in the use of graph theory to quantitate and investigate the topological characteristics of the healthy brain and brain disorders on the network level. The majority of graph theory investigations of functional connectivity have relied on the assumption of temporal stationarity. However, recent evidence increasingly suggests that functional connectivity fluctuates over the length of the scan. In this study, we investigate the stationarity of brain network topology using a Bayesian hidden Markov model (HMM) approach that estimates the dynamic structure of graph theoretical measures of whole-brain functional connectivity. In addition to extracting the stationary distribution and transition probabilities of commonly employed graph theory measures, we propose two estimators of temporal stationarity: the S-index and N-index. These indexes can be used to quantify different aspects of the temporal stationarity of graph theory measures. We apply the method and proposed estimators to resting-state functional MRI data from healthy controls and patients with temporal lobe epilepsy. Our analysis shows that several graph theory measures, including small-world index, global integration measures, and betweenness centrality, may exhibit greater stationarity over time and therefore be more robust. Additionally, we demonstrate that accounting for subject-level differences in the level of temporal stationarity of network topology may increase discriminatory power in discriminating between disease states. Our results confirm and extend findings from other studies regarding the dynamic nature of functional connectivity, and suggest that using statistical models which explicitly account for the dynamic nature of functional connectivity in graph theory analyses may improve the sensitivity of investigations and consistency across investigations. PMID
NASA Astrophysics Data System (ADS)
Taormina, Anne
1993-05-01
The representation theory of the doubly extended N=4 superconformal algebra is reviewed. The modular properties of the corresponding characters can be derived, using characters sumrules for coset realizations of these N=4 algebras. Some particular combinations of massless characters are shown to transform as affine SU(2) characters under S and T, a fact used to completely classify the massless sector of the partition function.
Poor Textural Image Matching Based on Graph Theory
NASA Astrophysics Data System (ADS)
Chen, Shiyu; Yuan, Xiuxiao; Yuan, Wei; Cai, Yang
2016-06-01
Image matching lies at the heart of photogrammetry and computer vision. For poor textural images, the matching result is affected by low contrast, repetitive patterns, discontinuity or occlusion, few or homogeneous textures. Recently, graph matching became popular for its integration of geometric and radiometric information. Focused on poor textural image matching problem, it is proposed an edge-weight strategy to improve graph matching algorithm. A series of experiments have been conducted including 4 typical landscapes: Forest, desert, farmland, and urban areas. And it is experimentally found that our new algorithm achieves better performance. Compared to SIFT, doubled corresponding points were acquired, and the overall recall rate reached up to 68%, which verifies the feasibility and effectiveness of the algorithm.
Higher gauge theories from Lie n-algebras and off-shell covariantization
NASA Astrophysics Data System (ADS)
Carow-Watamura, Ursula; Heller, Marc Andre; Ikeda, Noriaki; Kaneko, Yukio; Watamura, Satoshi
2016-07-01
We analyze higher gauge theories in various dimensions using a supergeometric method based on a differential graded symplectic manifold, called a QP-manifold, which is closely related to the BRST-BV formalism in gauge theories. Extensions of the Lie 2-algebra gauge structure are formulated within the Lie n-algebra induced by the QP-structure. We find that in 5 and 6 dimensions there are special extensions of the gauge algebra. In these cases, a restriction of the gauge symmetry by imposing constraints on the auxiliary gauge fields leads to a covariantized theory. As an example we show that we can obtain an off-shell covariantized higher gauge theory in 5 dimensions, which is similar to the one proposed in [1].
Cluster Algebras from Dualities of 2d = (2, 2) Quiver Gauge Theories
NASA Astrophysics Data System (ADS)
Benini, Francesco; Park, Daniel S.; Zhao, Peng
2015-11-01
We interpret certain Seiberg-like dualities of two-dimensional = (2,2) quiver gauge theories with unitary groups as cluster mutations in cluster algebras, originally formulated by Fomin and Zelevinsky. In particular, we show how the complexified Fayet-Iliopoulos parameters of the gauge group factors transform under those dualities and observe that they are in fact related to the dual cluster variables of cluster algebras. This implies that there is an underlying cluster algebra structure in the quantum Kähler moduli space of manifolds constructed from the corresponding Kähler quotients. We study the S 2 partition function of the gauge theories, showing that it is invariant under dualities/mutations, up to an overall normalization factor, whose physical origin and consequences we spell out in detail. We also present similar dualities in = (2,2)* quiver gauge theories, which are related to dualities of quantum integrable spin chains.
Matched signal detection on graphs: Theory and application to brain imaging data classification.
Hu, Chenhui; Sepulcre, Jorge; Johnson, Keith A; Fakhri, Georges E; Lu, Yue M; Li, Quanzheng
2016-01-15
Motivated by recent progress in signal processing on graphs, we have developed a matched signal detection (MSD) theory for signals with intrinsic structures described by weighted graphs. First, we regard graph Laplacian eigenvalues as frequencies of graph-signals and assume that the signal is in a subspace spanned by the first few graph Laplacian eigenvectors associated with lower eigenvalues. The conventional matched subspace detector can be applied to this case. Furthermore, we study signals that may not merely live in a subspace. Concretely, we consider signals with bounded variation on graphs and more general signals that are randomly drawn from a prior distribution. For bounded variation signals, the test is a weighted energy detector. For the random signals, the test statistic is the difference of signal variations on associated graphs, if a degenerate Gaussian distribution specified by the graph Laplacian is adopted. We evaluate the effectiveness of the MSD on graphs both with simulated and real data sets. Specifically, we apply MSD to the brain imaging data classification problem of Alzheimer's disease (AD) based on two independent data sets: 1) positron emission tomography data with Pittsburgh compound-B tracer of 30 AD and 40 normal control (NC) subjects, and 2) resting-state functional magnetic resonance imaging (R-fMRI) data of 30 early mild cognitive impairment and 20 NC subjects. Our results demonstrate that the MSD approach is able to outperform the traditional methods and help detect AD at an early stage, probably due to the success of exploiting the manifold structure of the data. PMID:26481679
Revealing Long-Range Interconnected Hubs in Human Chromatin Interaction Data Using Graph Theory
NASA Astrophysics Data System (ADS)
Boulos, R. E.; Arneodo, A.; Jensen, P.; Audit, B.
2013-09-01
We use graph theory to analyze chromatin interaction (Hi-C) data in the human genome. We show that a key functional feature of the genome—“master” replication origins—corresponds to DNA loci of maximal network centrality. These loci form a set of interconnected hubs both within chromosomes and between different chromosomes. Our results open the way to a fruitful use of graph theory concepts to decipher DNA structural organization in relation to genome functions such as replication and transcription. This quantitative information should prove useful to discriminate between possible polymer models of nuclear organization.
Wigner-Racah Algebra Approach to Caselle-Ponzano Fusion Rules
NASA Astrophysics Data System (ADS)
Nomura, Masao
1991-07-01
Caselle-Ponzano fusion rules, based on graph theory, are investigated in the framework of Wigner-Racah algebras. While in the graph theory parameters of fusion rules are taken over specific values, the restriction of parameters is removed in the present formalism. Formal extension to q-analogs is also given.
Classification of operator algebraic conformal field theories in dimensions one and two
NASA Astrophysics Data System (ADS)
Kawahigashi, Yasuyuki
2006-03-01
We formulate conformal field theory in the setting of algebraic quantum field theory as Haag-Kastler nets of local observable algebras with diffeomorphism covariance on the two-dimensional Minkowski space. We then obtain a decomposition of a two-dimensional theory into two chiral theories. We give the first classification result of such chiral theories with representation theoretic invariants. That is, we use the central charge as the first invariant, and if it is less than 1, we obtain a complete classification. Our classification list contains a new net which does not seem to arise from the known constructions such as the coset or orbifold constructions. We also present a classification of full two-dimensional conformal theories. These are joint works with Roberto Longo.
Insights into the organization of biochemical regulatory networks using graph theory analyses.
Ma'ayan, Avi
2009-02-27
Graph theory has been a valuable mathematical modeling tool to gain insights into the topological organization of biochemical networks. There are two types of insights that may be obtained by graph theory analyses. The first provides an overview of the global organization of biochemical networks; the second uses prior knowledge to place results from multivariate experiments, such as microarray data sets, in the context of known pathways and networks to infer regulation. Using graph analyses, biochemical networks are found to be scale-free and small-world, indicating that these networks contain hubs, which are proteins that interact with many other molecules. These hubs may interact with many different types of proteins at the same time and location or at different times and locations, resulting in diverse biological responses. Groups of components in networks are organized in recurring patterns termed network motifs such as feedback and feed-forward loops. Graph analysis revealed that negative feedback loops are less common and are present mostly in proximity to the membrane, whereas positive feedback loops are highly nested in an architecture that promotes dynamical stability. Cell signaling networks have multiple pathways from some input receptors and few from others. Such topology is reminiscent of a classification system. Signaling networks display a bow-tie structure indicative of funneling information from extracellular signals and then dispatching information from a few specific central intracellular signaling nexuses. These insights show that graph theory is a valuable tool for gaining an understanding of global regulatory features of biochemical networks. PMID:18940806
Equivariant algebraic vector bundles over representations of reductive groups: theory.
Masuda, M; Petrie, T
1991-01-01
Let G be a reductive algebraic group and let B be an affine variety with an algebraic action of G. Everything is defined over the field C of complex numbers. Consider the trivial G-vector bundle B x S = S over B where S is a G-module. From the endomorphism ring R of the G-vector bundle S a construction of G-vector bundles over B is given. The bundles constructed this way have the property that when added to S they are isomorphic to F + S for a fixed G-module F. For such a bundle E an invariant rho(E) is defined that lies in a quotient of R. This invariant allows us to distinguish nonisomorphic G-vector bundles. This is applied to the case where B is a G-module and, in that case, an invariant of the underlying equivariant variety is given too. These constructions and invariants are used to produce families of inequivalent G-vector bundles over G-modules and families of inequivalent G actions on affine spaces for some finite and some connected semisimple groups. PMID:11607220
Topics in Computational Learning Theory and Graph Algorithms.
ERIC Educational Resources Information Center
Board, Raymond Acton
This thesis addresses problems from two areas of theoretical computer science. The first area is that of computational learning theory, which is the study of the phenomenon of concept learning using formal mathematical models. The goal of computational learning theory is to investigate learning in a rigorous manner through the use of techniques…
Comparing Brain Networks of Different Size and Connectivity Density Using Graph Theory
van Wijk, Bernadette C. M.; Stam, Cornelis J.; Daffertshofer, Andreas
2010-01-01
Graph theory is a valuable framework to study the organization of functional and anatomical connections in the brain. Its use for comparing network topologies, however, is not without difficulties. Graph measures may be influenced by the number of nodes (N) and the average degree (k) of the network. The explicit form of that influence depends on the type of network topology, which is usually unknown for experimental data. Direct comparisons of graph measures between empirical networks with different N and/or k can therefore yield spurious results. We list benefits and pitfalls of various approaches that intend to overcome these difficulties. We discuss the initial graph definition of unweighted graphs via fixed thresholds, average degrees or edge densities, and the use of weighted graphs. For instance, choosing a threshold to fix N and k does eliminate size and density effects but may lead to modifications of the network by enforcing (ignoring) non-significant (significant) connections. Opposed to fixing N and k, graph measures are often normalized via random surrogates but, in fact, this may even increase the sensitivity to differences in N and k for the commonly used clustering coefficient and small-world index. To avoid such a bias we tried to estimate the N,k-dependence for empirical networks, which can serve to correct for size effects, if successful. We also add a number of methods used in social sciences that build on statistics of local network structures including exponential random graph models and motif counting. We show that none of the here-investigated methods allows for a reliable and fully unbiased comparison, but some perform better than others. PMID:21060892
What Can Graph Theory Tell Us about Word Learning and Lexical Retrieval?
ERIC Educational Resources Information Center
Vitevitch, Michael S.
2008-01-01
Purpose: Graph theory and the new science of networks provide a mathematically rigorous approach to examine the development and organization of complex systems. These tools were applied to the mental lexicon to examine the organization of words in the lexicon and to explore how that structure might influence the acquisition and retrieval of…
ERIC Educational Resources Information Center
Wilks, Clarissa; Meara, Paul
2002-01-01
Examines the implications of the metaphor of the vocabulary network. Takes a formal approach to the exploration of this metaphor by applying the principles of graph theory to word association data to compare the relative densities of the first language and second language lexical networks. (Author/VWL)
A Qualitative Analysis Framework Using Natural Language Processing and Graph Theory
ERIC Educational Resources Information Center
Tierney, Patrick J.
2012-01-01
This paper introduces a method of extending natural language-based processing of qualitative data analysis with the use of a very quantitative tool--graph theory. It is not an attempt to convert qualitative research to a positivist approach with a mathematical black box, nor is it a "graphical solution". Rather, it is a method to help qualitative…
Chen Famin; Wu Yongshi
2010-11-15
We present a superspace formulation of the D=3, N=4, 5 superconformal Chern-Simons Matter theories, with matter supermultiplets valued in a symplectic 3-algebra. We first construct an N=1 superconformal action and then generalize a method used by Gaitto and Witten to enhance the supersymmetry from N=1 to N=5. By decomposing the N=5 supermultiplets and the symplectic 3-algebra properly and proposing a new superpotential term, we construct the N=4 superconformal Chern-Simons matter theories in terms of two sets of generators of a (quaternion) symplectic 3-algebra. The N=4 theories can also be derived by requiring that the supersymmetry transformations are closed on-shell. The relationship between the 3-algebras, Lie superalgebras, Lie algebras, and embedding tensors (proposed in [E. A. Bergshoeff, O. Hohm, D. Roest, H. Samtleben, and E. Sezgin, J. High Energy Phys. 09 (2008) 101.]) is also clarified. The general N=4, 5 superconformal Chern-Simons matter theories in terms of ordinary Lie algebras can be re-derived in our 3-algebra approach. All known N=4, 5 superconformal Chern-Simons matter theories can be recovered in the present superspace formulation for super-Lie algebra realization of symplectic 3-algebras.
Regular perturbation theory of relativistic corrections: II. Algebraic approximation
NASA Astrophysics Data System (ADS)
Rutkowski, A.; Kozłowski, R.; Rutkowska, D.
2001-01-01
A four-component equivalent of the Schrödinger equation, describing both the nonrelativistic electron and the nonrelativistic positron, is introduced. The difference between this equation and the Dirac equation is treated as a perturbation. The relevant perturbation equations and formulas for corrections to the energy are derived. Owing to the semibounded character of the Schrödinger Hamiltonian of the unperturbed equation the variational perturbation method is formulated. The Hylleraas functionals become then either upper or lower bounds to the respective exact corrections to the energy. In order to demonstrate the usefulness of this approach to the problem of the variational optimization of nonlinear parameters, the perturbation corrections to wave functions for the of hydrogenlike atoms have been approximated in terms of exponential basis functions. The Dirac equation in this algebraic approximation is solved iteratively starting with the solution of the Schrödinger equation.
Graph theory and stability analysis of protein complex interaction networks.
Huang, Chien-Hung; Chen, Teng-Hung; Ng, Ka-Lok
2016-04-01
Protein complexes play an essential role in many biological processes. Complexes can interact with other complexes to form protein complex interaction network (PCIN) that involves in important cellular processes. There are relatively few studies on examining the interaction topology among protein complexes; and little is known about the stability of PCIN under perturbations. We employed graph theoretical approach to reveal hidden properties and features of four species PCINs. Two main issues are addressed, (i) the global and local network topological properties, and (ii) the stability of the networks under 12 types of perturbations. According to the topological parameter classification, we identified some critical protein complexes and validated that the topological analysis approach could provide meaningful biological interpretations of the protein complex systems. Through the Kolmogorov-Smimov test, we showed that local topological parameters are good indicators to characterise the structure of PCINs. We further demonstrated the effectiveness of the current approach by performing the scalability and data normalization tests. To measure the robustness of PCINs, we proposed to consider eight topological-based perturbations, which are specifically applicable in scenarios of targeted, sustained attacks. We found that the degree-based, betweenness-based and brokering-coefficient-based perturbations have the largest effect on network stability. PMID:26997661
Graph theory-based measures as predictors of gene morbidity.
Massanet-Vila, Raimon; Caminal, Pere; Perera, Alexandre
2010-01-01
Previous studies have suggested that some graph properties of protein interaction networks might be related with gene morbidity. In particular, it has been suggested that when a polymorphism affects a gene, it is more likely to produce a disease if the node degree in the interaction network is higher than for other genes. However, these results do not take into account the possible bias introduced by the variance in the amount of information available for different genes. This work models the relationship between the morbidity associated with a gene and the degrees of the nodes in the protein interaction network controlling the amount of information available in the literature. A set of 7461 genes and 3665 disease identifiers reported in the Online Mendelian Inheritance in Man (OMIM) was mined jointly with 9630 nodes and 38756 interactions of the Human Proteome Resource Database (HPRD). The information available from a gene was measured through PubMed mining. Results suggest that the correlation between the degree of a node in the protein interaction network and its morbidity is largely contributed by the information available from the gene. Even though the results suggest a positive correlation between the degree of a node and its morbidity while controlling the information factor, we believe this correlation has to be taken with caution for it can be affected by other factors not taken into account in this study. PMID:21096114
Impaired functional integration in multiple sclerosis: a graph theory study.
Rocca, Maria A; Valsasina, Paola; Meani, Alessandro; Falini, Andrea; Comi, Giancarlo; Filippi, Massimo
2016-01-01
Aim of this study was to explore the topological organization of functional brain network connectivity in a large cohort of multiple sclerosis (MS) patients and to assess whether its disruption contributes to disease clinical manifestations. Graph theoretical analysis was applied to resting state fMRI data from 246 MS patients and 55 matched healthy controls (HC). Functional connectivity between 116 cortical and subcortical brain regions was estimated using a bivariate correlation analysis. Global network properties (network degree, global efficiency, hierarchy, path length and assortativity) were abnormal in MS patients vs HC, and contributed to distinguish cognitively impaired MS patients (34%) from HC, but not the main MS clinical phenotypes. Compared to HC, MS patients also showed: (1) a loss of hubs in the superior frontal gyrus, precuneus and anterior cingulum in the left hemisphere; (2) a different lateralization of basal ganglia hubs (mostly located in the left hemisphere in HC, and in the right hemisphere in MS patients); and (3) a formation of hubs, not seen in HC, in the left temporal pole and cerebellum. MS patients also experienced a decreased nodal degree in the bilateral caudate nucleus and right cerebellum. Such a modification of regional network properties contributed to cognitive impairment and phenotypic variability of MS. An impairment of global integration (likely to reflect a reduced competence in information exchange between distant brain areas) occurs in MS and is associated with cognitive deficits. A regional redistribution of network properties contributes to cognitive status and phenotypic variability of these patients. PMID:25257603
Towards a loop representation of connection theories defined over a super Lie algebra
Urrutia, L.F. |
1996-02-01
The purpose of this contribution is to review some aspects of the loop space formulation of pure gauge theories having the connection defined over a Lie algebra. The emphasis is focused on the discussion of the Mandelstam identities, which provide the basic constraints upon both the classical and the quantum degrees of freedom of the theory. In the case where the connection is extended to be valued on a super Lie algebra, some new results are presented which can be considered as first steps towards the construction of the Mandelstam identities in this situation, which encompasses such interesting cases as supergravity in 3+1 dimensions together with 2+1 super Chern-Simons theories, for example. Also, these ideas could be useful in the loop space formulation of fully supersymmetric theories. {copyright} {ital 1996 American Institute of Physics.}
Towards a loop representation of connection theories defined over a super Lie algebra
Urrutia, Luis F.
1996-02-20
The purpose of this contribution is to review some aspects of the loop space formulation of pure gauge theories having the connection defined over a Lie algebra. The emphasis is focused on the discussion of the Mandelstam identities, which provide the basic constraints upon both the classical and the quantum degrees of freedom of the theory. In the case where the connection is extended to be valued on a super Lie algebra, some new results are presented which can be considered as first steps towards the construction of the Mandelstam identities in this situation, which encompasses such interesting cases as supergravity in 3+1 dimensions together with 2+1 super Chern-Simons theories, for example. Also, these ideas could be useful in the loop space formulation of fully supersymmetric theories.
An algebraic PT-symmetric quantum theory with a maximal mass
NASA Astrophysics Data System (ADS)
Rodionov, V. N.; Kravtsova, G. A.
2016-03-01
In this paper, we draw attention to the fact that the studies by V.G. Kadyshevsky devoted to the creation of the geometric quantum field theory with a fundamental mass have had great development recently, as regards a non-Hermitian algebraic approach to construction of the quantum theory. The central idea of such theories is to construct a new scalar product in which the average values of non-Hermitian Hamiltonians are real. Many studies in this field include both purely mathematical ones and those containing the discussion of experimental results. We consider the development of an algebraic relativistic pseudo-Hermitian quantum theory with a maximal mass and discuss its experimentally important corollaries.
Experimental demonstration of the connection between quantum contextuality and graph theory
NASA Astrophysics Data System (ADS)
Cañas, Gustavo; Acuña, Evelyn; Cariñe, Jaime; Barra, Johanna F.; Gómez, Esteban S.; Xavier, Guilherme B.; Lima, Gustavo; Cabello, Adán
2016-07-01
We report a method that exploits a connection between quantum contextuality and graph theory to reveal any form of quantum contextuality in high-precision experiments. We use this technique to identify a graph which corresponds to an extreme form of quantum contextuality unnoticed before and test it using high-dimensional quantum states encoded in the linear transverse momentum of single photons. Our results open the door to the experimental exploration of quantum contextuality in all its forms, including those needed for quantum computation.
Magic bases, metric ansaetze and generalized graph theories in the Virasoro master equation
Halpern, M.B.; Obers, N.A. )
1991-11-15
The authors define a class of magic Lie group bases in which the Virasoro master equation admits a class of simple metric ansaetze (g{sub metric}), whose structure is visible in the high-level expansion. When a magic basis is real on compact g, the corresponding g{sub metric} is a large system of unitary, generically irrational conformal field theories. Examples in this class include the graph-theory ansatz SO(n){sub diag} in the Cartesian basis of So(n) and the ansatz SU(n){sub metric} in the Pauli-like basis of SU(n). A new phenomenon is observed in the high-level comparison of SU(n){sub metric}: Due to the trigonometric structure constants of the Pauli-like basis, irrational central charge is clearly visible at finite order of the expansion. They also define the sine-area graphs of SU(n), which label the conformal field theories of SU(n){sub metric} and note that, in a similar fashion, each magic basis of g defines a generalize graph theory on g which labels the conformal field theories of g{sub metric}.
NASA Astrophysics Data System (ADS)
Orantin, N.
2007-09-01
The 2-matrix model has been introduced to study Ising model on random surfaces. Since then, the link between matrix models and combinatorics of discrete surfaces has strongly tightened. This manuscript aims to investigate these deep links and extend them beyond the matrix models, following my work's evolution. First, I take care to define properly the hermitian 2 matrix model which gives rise to generating functions of discrete surfaces equipped with a spin structure. Then, I show how to compute all the terms in the topological expansion of any observable by using algebraic geometry tools. They are obtained as differential forms on an algebraic curve associated to the model: the spectral curve. In a second part, I show how to define such differentials on any algebraic curve even if it does not come from a matrix model. I then study their numerous symmetry properties under deformations of the algebraic curve. In particular, I show that these objects coincide with the topological expansion of the observable of a matrix model if the algebraic curve is the spectral curve of this model. Finally, I show that fine tuning the parameters ensure that these objects can be promoted to modular invariants and satisfy the holomorphic anomaly equation of the Kodaira-Spencer theory. This gives a new hint that the Dijkgraaf-Vafa conjecture is correct.
K-Theory of Crossed Products of Tiling C*-Algebras by Rotation Groups
NASA Astrophysics Data System (ADS)
Starling, Charles
2015-02-01
Let Ω be a tiling space and let G be the maximal group of rotations which fixes Ω. Then the cohomology of Ω and Ω/ G are both invariants which give useful geometric information about the tilings in Ω. The noncommutative analog of the cohomology of Ω is the K-theory of a C*-algebra associated to Ω, and for translationally finite tilings of dimension 2 or less, the K-theory is isomorphic to the direct sum of cohomology groups. In this paper we give a prescription for calculating the noncommutative analog of the cohomology of Ω/ G, that is, the K-theory of the crossed product of the tiling C*-algebra by G. We also provide a table with some calculated K-groups for many common examples, including the Penrose and pinwheel tilings.
Algebraic Characterization of the Vacuum in Light-Front Field Theory
NASA Astrophysics Data System (ADS)
Herrmann, Marc; Polyzou, Wayne
2016-03-01
In the light-front formulation of quantum field theory, the vacuum vector of an interacting field theory has a relatively simple relationship to the vacuum of a free field theory. This is a benefit over the usual equal-time formulation where the interacting vacuum vector has infinite norm with respect to the Hilbert space of the free field theory. By describing the vacuum as a positive linear functional on an operator algebra constructed from free fields with two distinct masses, it can be demonstrated that the complications associated with adding dynamics to the vacuum of a free theory are not present in the construction of the light-front vacuum. Instead, the complications are moved into defining a subalgebra of the light-front algebra which corresponds to the physically relevant algebra of local fields. These results can then be applied to interacting fields by first describing them in terms of asymptotic in or out fields. However, in order to treat local operators products, the vacuum functional may need to be modified to include states with zero eigenvalue of the generator of translations in the direction along the light front, x- =1/√(2) >x0-x3. This work supported by DOE contract No. DE-FG02-86ER40286.
Lamplighter groups, de Brujin graphs, spider-web graphs and their spectra
NASA Astrophysics Data System (ADS)
Grigorchuk, R.; Leemann, P.-H.; Nagnibeda, T.
2016-05-01
We study the infinite family of spider-web graphs \\{{{ S }}k,N,M\\}, k≥slant 2, N≥slant 0 and M≥slant 1, initiated in the 50s in the context of network theory. It was later shown in physical literature that these graphs have remarkable percolation and spectral properties. We provide a mathematical explanation of these properties by putting the spider-web graphs in the context of group theory and algebraic graph theory. Namely, we realize them as tensor products of the well-known de Bruijn graphs \\{{{ B }}k,N\\} with cyclic graphs \\{{C}M\\} and show that these graphs are described by the action of the lamplighter group {{ L }}k={Z}/k{Z}\\wr {Z} on the infinite binary tree. Our main result is the identification of the infinite limit of \\{{{ S }}k,N,M\\}, as N,M\\to ∞ , with the Cayley graph of the lamplighter group {{ L }}k which, in turn, is one of the famous Diestel–Leader graphs {{DL}}k,k. As an application we compute the spectra of all spider-web graphs and show their convergence to the discrete spectral distribution associated with the Laplacian on the lamplighter group.
LieART-A Mathematica application for Lie algebras and representation theory
NASA Astrophysics Data System (ADS)
Feger, Robert; Kephart, Thomas W.
2015-07-01
We present the Mathematica application "LieART" (Lie Algebras and Representation Theory) for computations frequently encountered in Lie algebras and representation theory, such as tensor product decomposition and subalgebra branching of irreducible representations. LieART can handle all classical and exceptional Lie algebras. It computes root systems of Lie algebras, weight systems and several other properties of irreducible representations. LieART's user interface has been created with a strong focus on usability and thus allows the input of irreducible representations via their dimensional name, while the output is in the textbook style used in most particle-physics publications. The unique Dynkin labels of irreducible representations are used internally and can also be used for input and output. LieART exploits the Weyl reflection group for most of the calculations, resulting in fast computations and a low memory consumption. Extensive tables of properties, tensor products and branching rules of irreducible representations are included as online supplementary material (see Appendix A).
Visibility graph analysis on quarterly macroeconomic series of China based on complex network theory
NASA Astrophysics Data System (ADS)
Wang, Na; Li, Dong; Wang, Qiwen
2012-12-01
The visibility graph approach and complex network theory provide a new insight into time series analysis. The inheritance of the visibility graph from the original time series was further explored in the paper. We found that degree distributions of visibility graphs extracted from Pseudo Brownian Motion series obtained by the Frequency Domain algorithm exhibit exponential behaviors, in which the exponential exponent is a binomial function of the Hurst index inherited in the time series. Our simulations presented that the quantitative relations between the Hurst indexes and the exponents of degree distribution function are different for different series and the visibility graph inherits some important features of the original time series. Further, we convert some quarterly macroeconomic series including the growth rates of value-added of three industry series and the growth rates of Gross Domestic Product series of China to graphs by the visibility algorithm and explore the topological properties of graphs associated from the four macroeconomic series, namely, the degree distribution and correlations, the clustering coefficient, the average path length, and community structure. Based on complex network analysis we find degree distributions of associated networks from the growth rates of value-added of three industry series are almost exponential and the degree distributions of associated networks from the growth rates of GDP series are scale free. We also discussed the assortativity and disassortativity of the four associated networks as they are related to the evolutionary process of the original macroeconomic series. All the constructed networks have “small-world” features. The community structures of associated networks suggest dynamic changes of the original macroeconomic series. We also detected the relationship among government policy changes, community structures of associated networks and macroeconomic dynamics. We find great influences of government
Scale-adaptive tensor algebra for local many-body methods of electronic structure theory
Liakh, Dmitry I
2014-01-01
While the formalism of multiresolution analysis (MRA), based on wavelets and adaptive integral representations of operators, is actively progressing in electronic structure theory (mostly on the independent-particle level and, recently, second-order perturbation theory), the concepts of multiresolution and adaptivity can also be utilized within the traditional formulation of correlated (many-particle) theory which is based on second quantization and the corresponding (generally nonorthogonal) tensor algebra. In this paper, we present a formalism called scale-adaptive tensor algebra (SATA) which exploits an adaptive representation of tensors of many-body operators via the local adjustment of the basis set quality. Given a series of locally supported fragment bases of a progressively lower quality, we formulate the explicit rules for tensor algebra operations dealing with adaptively resolved tensor operands. The formalism suggested is expected to enhance the applicability and reliability of local correlated many-body methods of electronic structure theory, especially those directly based on atomic orbitals (or any other localized basis functions).
The Casimir Effect from the Point of View of Algebraic Quantum Field Theory
NASA Astrophysics Data System (ADS)
Dappiaggi, Claudio; Nosari, Gabriele; Pinamonti, Nicola
2016-06-01
We consider a region of Minkowski spacetime bounded either by one or by two parallel, infinitely extended plates orthogonal to a spatial direction and a real Klein-Gordon field satisfying Dirichlet boundary conditions. We quantize these two systems within the algebraic approach to quantum field theory using the so-called functional formalism. As a first step we construct a suitable unital ∗-algebra of observables whose generating functionals are characterized by a labelling space which is at the same time optimal and separating and fulfils the F-locality property. Subsequently we give a definition for these systems of Hadamard states and we investigate explicit examples. In the case of a single plate, it turns out that one can build algebraic states via a pull-back of those on the whole Minkowski spacetime, moreover inheriting from them the Hadamard property. When we consider instead two plates, algebraic states can be put in correspondence with those on flat spacetime via the so-called method of images, which we translate to the algebraic setting. For a massless scalar field we show that this procedure works perfectly for a large class of quasi-free states including the Poincaré vacuum and KMS states. Eventually Wick polynomials are introduced. Contrary to the Minkowski case, the extended algebras, built in globally hyperbolic subregions can be collected in a global counterpart only after a suitable deformation which is expressed locally in terms of a *-isomorphism. As a last step, we construct explicitly the two-point function and the regularized energy density, showing, moreover, that the outcome is consistent with the standard results of the Casimir effect.
On the Algebraic K Theory of the Massive D8 and M9-Branes
NASA Astrophysics Data System (ADS)
Vancea, Ion V.
In this paper we review some basic relations of algebraic K theory and we formulate them in the language of D-branes. Then we study the relation between the D8-branes wrapped on an orientable compact manifold W in a massive Type IIA supergravity background and the M9-branes wrapped on a compact manifold Z in a massive d=11 supergravity background from the K-theoretic point of view. By interpreting the D8-brane charges as elements of K0(C(W)) and the (inequivalent classes of) spaces of gauge fields on the M9-branes as the elements of K0(C(Z)x{¯ {k}*}G) where G is a one-dimensional compact group, a connection between charges and gauge fields is argued to exists. This connection could be realized as a composition map between the corresponding algebraic K theory groups.
The theory of Enceladus and Dione: An application of computerized algebra in dynamical astronomy
NASA Technical Reports Server (NTRS)
Jefferys, W. H.; Ries, L. M.
1974-01-01
A theory of Saturn's satellites Enceladus and Dione is discussed which is literal (all constants of integration appear explicitly), canonically invariant (the Hori-Lie method is used), and which correctly handles the eccentricity-type resonance between the two satellites. Algebraic manipulations are designed to be performed using the TRIGMAN formula manipulation language, and computer programs were developed so that, with minor modifications, they can be used on the Mimas-Tethys and Titan-Hyperion systems.
ERIC Educational Resources Information Center
Malkevitch, Joseph
One of the great strengths of mathematics is viewed as the fact that apparently diverse real-world questions translate into that same mathematical question. It is felt that studying a mathematical problem can often bring about a tool of surprisingly diverse usability. The module is geared to help users know how to use graph theory to model simple…
Sparsified-dynamics modeling of discrete point vortices with graph theory
NASA Astrophysics Data System (ADS)
Taira, Kunihiko; Nair, Aditya
2014-11-01
We utilize graph theory to derive a sparsified interaction-based model that captures unsteady point vortex dynamics. The present model builds upon the Biot-Savart law and keeps the number of vortices (graph nodes) intact and reduces the number of inter-vortex interactions (graph edges). We achieve this reduction in vortex interactions by spectral sparsification of graphs. This approach drastically reduces the computational cost to predict the dynamical behavior, sharing characteristics of reduced-order models. Sparse vortex dynamics are illustrated through an example of point vortex clusters interacting amongst themselves. We track the centroids of the individual vortex clusters to evaluate the error in bulk motion of the point vortices in the sparsified setup. To further improve the accuracy in predicting the nonlinear behavior of the vortices, resparsification strategies are employed for the sparsified interaction-based models. The model retains the nonlinearity of the interaction and also conserves the invariants of discrete vortex dynamics; namely the Hamiltonian, linear impulse, and angular impulse as well as circulation. Work supported by US Army Research Office (W911NF-14-1-0386) and US Air Force Office of Scientific Research (YIP: FA9550-13-1-0183).
Quantification of Spatial Parameters in 3D Cellular Constructs Using Graph Theory
Lund, A. W.; Bilgin, C. C.; Hasan, M. A.; McKeen, L. M.; Stegemann, J. P.; Yener, B.; Zaki, M. J.; Plopper, G. E.
2009-01-01
Multispectral three-dimensional (3D) imaging provides spatial information for biological structures that cannot be measured by traditional methods. This work presents a method of tracking 3D biological structures to quantify changes over time using graph theory. Cell-graphs were generated based on the pairwise distances, in 3D-Euclidean space, between nuclei during collagen I gel compaction. From these graphs quantitative features are extracted that measure both the global topography and the frequently occurring local structures of the “tissue constructs.” The feature trends can be controlled by manipulating compaction through cell density and are significant when compared to random graphs. This work presents a novel methodology to track a simple 3D biological event and quantitatively analyze the underlying structural change. Further application of this method will allow for the study of complex biological problems that require the quantification of temporal-spatial information in 3D and establish a new paradigm in understanding structure-function relationships. PMID:19920859
Energy Minimization of Discrete Protein Titration State Models Using Graph Theory.
Purvine, Emilie; Monson, Kyle; Jurrus, Elizabeth; Star, Keith; Baker, Nathan A
2016-08-25
There are several applications in computational biophysics that require the optimization of discrete interacting states, for example, amino acid titration states, ligand oxidation states, or discrete rotamer angles. Such optimization can be very time-consuming as it scales exponentially in the number of sites to be optimized. In this paper, we describe a new polynomial time algorithm for optimization of discrete states in macromolecular systems. This algorithm was adapted from image processing and uses techniques from discrete mathematics and graph theory to restate the optimization problem in terms of "maximum flow-minimum cut" graph analysis. The interaction energy graph, a graph in which vertices (amino acids) and edges (interactions) are weighted with their respective energies, is transformed into a flow network in which the value of the minimum cut in the network equals the minimum free energy of the protein and the cut itself encodes the state that achieves the minimum free energy. Because of its deterministic nature and polynomial time performance, this algorithm has the potential to allow for the ionization state of larger proteins to be discovered. PMID:27089174
NASA Astrophysics Data System (ADS)
Zemenkova, M. Yu; Shipovalov, A. N.; Zemenkov, Yu D.
2016-04-01
The main technological equipment of pipeline transport of hydrocarbons are hydraulic machines. During transportation of oil mainly used of centrifugal pumps, designed to work in the “pumping station-pipeline” system. Composition of a standard pumping station consists of several pumps, complex hydraulic piping. The authors have developed a set of models and algorithms for calculating system reliability of pumps. It is based on the theory of reliability. As an example, considered one of the estimation methods with the application of graph theory.
Functional Organization of the Action Observation Network in Autism: A Graph Theory Approach
Alaerts, Kaat; Geerlings, Franca; Herremans, Lynn; Swinnen, Stephan P.; Verhoeven, Judith; Sunaert, Stefan; Wenderoth, Nicole
2015-01-01
Background The ability to recognize, understand and interpret other’s actions and emotions has been linked to the mirror system or action-observation-network (AON). Although variations in these abilities are prevalent in the neuro-typical population, persons diagnosed with autism spectrum disorders (ASD) have deficits in the social domain and exhibit alterations in this neural network. Method Here, we examined functional network properties of the AON using graph theory measures and region-to-region functional connectivity analyses of resting-state fMRI-data from adolescents and young adults with ASD and typical controls (TC). Results Overall, our graph theory analyses provided convergent evidence that the network integrity of the AON is altered in ASD, and that reductions in network efficiency relate to reductions in overall network density (i.e., decreased overall connection strength). Compared to TC, individuals with ASD showed significant reductions in network efficiency and increased shortest path lengths and centrality. Importantly, when adjusting for overall differences in network density between ASD and TC groups, participants with ASD continued to display reductions in network integrity, suggesting that also network-level organizational properties of the AON are altered in ASD. Conclusion While differences in empirical connectivity contributed to reductions in network integrity, graph theoretical analyses provided indications that also changes in the high-level network organization reduced integrity of the AON. PMID:26317222
A graph-theory framework for evaluating landscape connectivity and conservation planning.
Minor, Emily S; Urban, Dean L
2008-04-01
Connectivity of habitat patches is thought to be important for movement of genes, individuals, populations, and species over multiple temporal and spatial scales. We used graph theory to characterize multiple aspects of landscape connectivity in a habitat network in the North Carolina Piedmont (U.S.A). We compared this landscape with simulated networks with known topology, resistance to disturbance, and rate of movement. We introduced graph measures such as compartmentalization and clustering, which can be used to identify locations on the landscape that may be especially resilient to human development or areas that may be most suitable for conservation. Our analyses indicated that for songbirds the Piedmont habitat network was well connected. Furthermore, the habitat network had commonalities with planar networks, which exhibit slow movement, and scale-free networks, which are resistant to random disturbances. These results suggest that connectivity in the habitat network was high enough to prevent the negative consequences of isolation but not so high as to allow rapid spread of disease. Our graph-theory framework provided insight into regional and emergent global network properties in an intuitive and visual way and allowed us to make inferences about rates and paths of species movements and vulnerability to disturbance. This approach can be applied easily to assessing habitat connectivity in any fragmented or patchy landscape. PMID:18241238
NASA Astrophysics Data System (ADS)
Grifoni, E.; Legnaioli, S.; Lorenzetti, G.; Pagnotta, S.; Palleschi, V.
2016-04-01
In this paper we present a new approach for unsupervised classification of materials from the spectra obtained using the Laser-Induced Breakdown Spectroscopy technique. The method is based on the calculation of the correlation matrix between the LIBS spectra, which is interpreted as an Adjacency matrix in the framework of Graph theory. A threshold is applied on the edge values, which is determined through maximization of the Modularity of the Graph. The classification of the spectra is done automatically after the calculation of the Modularity parameter. An example of the application of the proposed method is given, based on the study of six bronze standards of known composition. The advantages of the proposed approach with respect to Principal Component Analysis are also discussed.
Representations of Conformal Nets, Universal C*-Algebras and K-Theory
NASA Astrophysics Data System (ADS)
Carpi, Sebastiano; Conti, Roberto; Hillier, Robin; Weiner, Mihály
2013-05-01
We study the representation theory of a conformal net {{A}} on S 1 from a K-theoretical point of view using its universal C*-algebra {C^*({A})}. We prove that if {{A}} satisfies the split property then, for every representation π of {{A}} with finite statistical dimension, {π(C^*({A}))} is weakly closed and hence a finite direct sum of type I∞ factors. We define the more manageable locally normal universal C*-algebra {C_ln^*({A})} as the quotient of {C^*({A})} by its largest ideal vanishing in all locally normal representations and we investigate its structure. In particular, if {{A}} is completely rational with n sectors, then {C_ln^*({A})} is a direct sum of n type I∞ factors. Its ideal {{K}_{A}} of compact operators has nontrivial K-theory, and we prove that the DHR endomorphisms of {C^*({A})} with finite statistical dimension act on {{K}_{A}}, giving rise to an action of the fusion semiring of DHR sectors on {K_0({K}_{A})}. Moreover, we show that this action corresponds to the regular representation of the associated fusion algebra.
NASA Astrophysics Data System (ADS)
Méliot, Pierre-Loïc
2010-12-01
In this thesis, we investigate the asymptotics of random partitions chosen according to probability measures coming from the representation theory of the symmetric groups S_n and of the finite Chevalley groups GL(n,F_q) and Sp(2n,F_q). More precisely, we prove laws of large numbers and central limit theorems for the q-Plancherel measures of type A and B, the Schur-Weyl measures and the Gelfand measures. Using the RSK algorithm, it also gives results on longest increasing subsequences in random words. We develop a technique of moments (and cumulants) for random partitions, thereby using the polynomial functions on Young diagrams in the sense of Kerov and Olshanski. The algebra of polynomial functions, or observables of Young diagrams is isomorphic to the algebra of partial permutations; in the last part of the thesis, we try to generalize this beautiful construction.
Sharing Teaching Ideas: Graphing Families of Curves Using Transformations of Reference Graphs
ERIC Educational Resources Information Center
Kukla, David
2007-01-01
This article provides for a fast extremely accurate approach to graphing functions that is based on learning function reference graphs and then applying algebraic transformations to these reference graphs.
NASA Astrophysics Data System (ADS)
Yang, Y.; Li, H. T.; Han, Y. S.; Gu, H. Y.
2015-06-01
Image segmentation is the foundation of further object-oriented image analysis, understanding and recognition. It is one of the key technologies in high resolution remote sensing applications. In this paper, a new fast image segmentation algorithm for high resolution remote sensing imagery is proposed, which is based on graph theory and fractal net evolution approach (FNEA). Firstly, an image is modelled as a weighted undirected graph, where nodes correspond to pixels, and edges connect adjacent pixels. An initial object layer can be obtained efficiently from graph-based segmentation, which runs in time nearly linear in the number of image pixels. Then FNEA starts with the initial object layer and a pairwise merge of its neighbour object with the aim to minimize the resulting summed heterogeneity. Furthermore, according to the character of different features in high resolution remote sensing image, three different merging criterions for image objects based on spectral and spatial information are adopted. Finally, compared with the commercial remote sensing software eCognition, the experimental results demonstrate that the efficiency of the algorithm has significantly improved, and the result can maintain good feature boundaries.
A graph theory practice on transformed image: a random image steganography.
Thanikaiselvan, V; Arulmozhivarman, P; Subashanthini, S; Amirtharajan, Rengarajan
2013-01-01
Modern day information age is enriched with the advanced network communication expertise but unfortunately at the same time encounters infinite security issues when dealing with secret and/or private information. The storage and transmission of the secret information become highly essential and have led to a deluge of research in this field. In this paper, an optimistic effort has been taken to combine graceful graph along with integer wavelet transform (IWT) to implement random image steganography for secure communication. The implementation part begins with the conversion of cover image into wavelet coefficients through IWT and is followed by embedding secret image in the randomly selected coefficients through graph theory. Finally stegoimage is obtained by applying inverse IWT. This method provides a maximum of 44 dB peak signal to noise ratio (PSNR) for 266646 bits. Thus, the proposed method gives high imperceptibility through high PSNR value and high embedding capacity in the cover image due to adaptive embedding scheme and high robustness against blind attack through graph theoretic random selection of coefficients. PMID:24453857
A Graph Theory Practice on Transformed Image: A Random Image Steganography
Thanikaiselvan, V.; Arulmozhivarman, P.; Subashanthini, S.; Amirtharajan, Rengarajan
2013-01-01
Modern day information age is enriched with the advanced network communication expertise but unfortunately at the same time encounters infinite security issues when dealing with secret and/or private information. The storage and transmission of the secret information become highly essential and have led to a deluge of research in this field. In this paper, an optimistic effort has been taken to combine graceful graph along with integer wavelet transform (IWT) to implement random image steganography for secure communication. The implementation part begins with the conversion of cover image into wavelet coefficients through IWT and is followed by embedding secret image in the randomly selected coefficients through graph theory. Finally stegoimage is obtained by applying inverse IWT. This method provides a maximum of 44 dB peak signal to noise ratio (PSNR) for 266646 bits. Thus, the proposed method gives high imperceptibility through high PSNR value and high embedding capacity in the cover image due to adaptive embedding scheme and high robustness against blind attack through graph theoretic random selection of coefficients. PMID:24453857
NASA Astrophysics Data System (ADS)
Nakata, Yosuke; Urade, Yoshiro; Nakanishi, Toshihiro; Miyamaru, Fumiaki; Takeda, Mitsuo Wada; Kitano, Masao
2016-04-01
We investigate the supersymmetry (SUSY) structures for inductor-capacitor circuit networks on a simple regular graph and its line graph. We show that their eigenspectra must coincide (except, possibly, for the highest eigenfrequency) due to SUSY, which is derived from the topological nature of the circuits. To observe this spectra correspondence in the high-frequency range, we study spoof plasmons on metallic hexagonal and kagomé lattices. The band correspondence between them is predicted by a simulation. Using terahertz time-domain spectroscopy, we demonstrate the band correspondence of fabricated metallic hexagonal and kagomé lattices.
Dilt, Thomas E; Weisberg, Peter J; Leitner, Philip; Matocq, Marjorie D; Inman, Richard D; Nussear, Kenneth E; Esque, Todd C
2016-06-01
Conservation planning and biodiversity management require information on landscape connectivity across a range of spatial scales from individual home ranges to large regions. Reduction in landscape connectivity due changes in land use or development is expected to act synergistically with alterations to habitat mosaic configuration arising from climate change. We illustrate a multiscale connectivity framework to aid habitat conservation prioritization in the context of changing land use and climate. Our approach, which builds upon the strengths of multiple landscape connectivity methods, including graph theory, circuit theory, and least-cost path analysis, is here applied to the conservation planning requirements of the Mohave ground squirrel. The distribution of this threatened Californian species, as for numerous other desert species, overlaps with the proposed placement of several utility-scale renewable energy developments in the American southwest. Our approach uses information derived at three spatial scales to forecast potential changes in habitat connectivity under various scenarios of energy development and climate change. By disentangling the potential effects of habitat loss and fragmentation across multiple scales, we identify priority conservation areas for both core habitat and critical corridor or stepping stone habitats. This approach is a first step toward applying graph theory to analyze habitat connectivity for species with continuously distributed habitat and should be applicable across a broad range of taxa. PMID:27509760
Dilts, Thomas E.; Weisberg, Peter J.; Leitner, Phillip; Matocq, Marjorie D.; Inman, Richard D.; Nussear, Ken E.; Esque, Todd
2016-01-01
Conservation planning and biodiversity management require information on landscape connectivity across a range of spatial scales from individual home ranges to large regions. Reduction in landscape connectivity due changes in land-use or development is expected to act synergistically with alterations to habitat mosaic configuration arising from climate change. We illustrate a multi-scale connectivity framework to aid habitat conservation prioritization in the context of changing land use and climate. Our approach, which builds upon the strengths of multiple landscape connectivity methods including graph theory, circuit theory and least-cost path analysis, is here applied to the conservation planning requirements of the Mohave ground squirrel. The distribution of this California threatened species, as for numerous other desert species, overlaps with the proposed placement of several utility-scale renewable energy developments in the American Southwest. Our approach uses information derived at three spatial scales to forecast potential changes in habitat connectivity under various scenarios of energy development and climate change. By disentangling the potential effects of habitat loss and fragmentation across multiple scales, we identify priority conservation areas for both core habitat and critical corridor or stepping stone habitats. This approach is a first step toward applying graph theory to analyze habitat connectivity for species with continuously-distributed habitat, and should be applicable across a broad range of taxa.
Walker, Robert; Arima, Eugenio; Messina, Joe; Soares-Filho, Britaldo; Perz, Stephen; Vergara, Dante; Sales, Marcio; Pereira, Ritaumaria; Castro, Williams
2013-01-01
This article addresses the spatial decision-making of loggers and implications for forest fragmentation in the Amazon basin. It provides a behavioral explanation for fragmentation by modeling how loggers build road networks, typically abandoned upon removal of hardwoods. Logging road networks provide access to land, and the settlers who take advantage of them clear fields and pastures that accentuate their spatial signatures. In shaping agricultural activities, these networks organize emergent patterns of forest fragmentation, even though the loggers move elsewhere. The goal of the article is to explicate how loggers shape their road networks, in order to theoretically explain an important type of forest fragmentation found in the Amazon basin, particularly in Brazil. This is accomplished by adapting graph theory to represent the spatial decision-making of loggers, and by implementing computational algorithms that build graphs interpretable as logging road networks. The economic behavior of loggers is conceptualized as a profit maximization problem, and translated into spatial decision-making by establishing a formal correspondence between mathematical graphs and road networks. New computational approaches, adapted from operations research, are used to construct graphs and simulate spatial decision-making as a function of discount rates, land tenure, and topographic constraints. The algorithms employed bracket a range of behavioral settings appropriate for areas of terras de volutas, public lands that have not been set aside for environmental protection, indigenous peoples, or colonization. The simulation target sites are located in or near so-called Terra do Meio, once a major logging frontier in the lower Amazon Basin. Simulation networks are compared to empirical ones identified by remote sensing and then used to draw inferences about factors influencing the spatial behavior of loggers. Results overall suggest that Amazonia's logging road networks induce more
An Automated Method to Identify Mesoscale Convective Complexes (MCCs) Implementing Graph Theory
NASA Astrophysics Data System (ADS)
Whitehall, K. D.; Mattmann, C. A.; Jenkins, G. S.; Waliser, D. E.; Rwebangira, R.; Demoz, B.; Kim, J.; Goodale, C. E.; Hart, A. F.; Ramirez, P.; Joyce, M. J.; Loikith, P.; Lee, H.; Khudikyan, S.; Boustani, M.; Goodman, A.; Zimdars, P. A.; Whittell, J.
2013-12-01
Mesoscale convective complexes (MCCs) are convectively-driven weather systems with a duration of ~10 - 12 hours and contributions of large amounts to the rainfall daily and monthly totals. More than 400 MCCs occur annually over various locations on the globe. In West Africa, ~170 MCCs occur annually during the 180 days representing the summer months (June - November), and contribute ~75% of the annual wet season rainfall. The main objective of this study is to improve automatic identification of MCC over West Africa. The spatial expanse of MCCs and the spatio-temporal variability in their convective characteristics make them difficult to characterize even in dense networks of radars and/or surface gauges. As such there exist criteria for identifying MCCs with satellite images - mostly using infrared (IR) data. Automated MCC identification methods are based on forward and/or backward in time spatial-temporal analysis of the IR satellite data and characteristically incorporate a manual component as these algorithms routinely falter with merging and splitting cloud systems between satellite images. However, these algorithms are not readily transferable to voluminous data or other satellite-derived datasets (e.g. TRMM), thus hindering comprehensive studies of these features both at weather and climate timescales. Recognizing the existing limitations of automated methods, this study explores the applicability of graph theory to creating a fully automated method for deriving a West African MCC dataset from hourly infrared satellite images between 2001- 2012. Graph theory, though not heavily implemented in the atmospheric sciences, has been used for the predicting (nowcasting) of thunderstorms from radar and satellite data by considering the relationship between atmospheric variables at a given time, or for the spatial-temporal analysis of cloud volumes. From these few studies, graph theory appears to be innately applicable to the complexity, non-linearity and inherent
Li, Qu; Yang, Jianhua; Xu, Ning
2014-01-01
Online friend recommendation is a fast developing topic in web mining. In this paper, we used SVD matrix factorization to model user and item feature vector and used stochastic gradient descent to amend parameter and improve accuracy. To tackle cold start problem and data sparsity, we used KNN model to influence user feature vector. At the same time, we used graph theory to partition communities with fairly low time and space complexity. What is more, matrix factorization can combine online and offline recommendation. Experiments showed that the hybrid recommendation algorithm is able to recommend online friends with good accuracy. PMID:24757410
NASA Astrophysics Data System (ADS)
Vieira, Sidney R.; Vidal Vázquez, Eva; Miranda, José G. V.; Paz Ferreiro, Jorge; Topp, George C.
2010-05-01
Spatial and temporal variability of soil moisture content has been frequently evaluated using statistical and geostatistical methods for several issues. For example, the statistical study of the temporal persistence or temporal stability in spatial patterns of soil moisture content has found interest to improve soil water monitoring strategies and to correct the average soil water content for missing data. Fractal analysis and graph theory are additional tools that can provide information and further insight to assess and to model indirect or hidden interactions in soil moisture content. In fractal analysis the fractal dimension (D) is an indicator of the pattern and extent of spatial and/or temporal variability. Large D values indicate the importance of short-range variation, while small D values reflect the importance of long-range variation when spatial and temporal data sets are analyzed. Moreover, for spatial and temporal variability, D can range from 1 to 2 for a profile and from 2 to 3 for a two dimensional network. Moreover, as the fractal dimension value increases the degree of roughness also increases. Graph theory tools take into account network structure by modelling pair wise relations between objects, which allow considering explicitly spatial-temporal connectivity of a given data set. The objective of this study was to use fractal analysis and graph theory to characterize the pattern of spatial and temporal variability of soil moisture content. The experimental field was located at Ottawa, Canada. Volumetric water content was monitored using Time Domain Reflectometry (TDR) during 34 dates at 164 locations per date. The depth of the TDR probes was 20 cm. The first and last measurements were 21 month apart and no data were taken in winter when the soil was covered by snow. The fractal dimension, D, was estimated from the slope of the regression line of log semivariogram versus distance for each of studied data sets. Using graph theory various
The theory of Enceladus and Dione - An application of computerized algebra in dynamical astronomy
NASA Technical Reports Server (NTRS)
Jefferys, W. H.; Ries, L. M.
1975-01-01
The orbits of the satellites of the outer planets are poorly known, due to lack of attention over the past half century. We have been developing a new theory of Saturn's satellites Enceladus and Dione which is literal (all constants of integration appear explicitly), canonically invariant (the Hori-Lie method is used), and which correctly handles the eccentricity-type resonance between the two satellites. The algebraic manipulations are being performed using the TRIGMAN formula manipulation language, and the programs have been developed so that with minor modifications they can be used on the Mimas-Tethys and Titan-Hyperion systems.
Discovering Authorities and Hubs in Different Topological Web Graph Structures.
ERIC Educational Resources Information Center
Meghabghab, George
2002-01-01
Discussion of citation analysis on the Web considers Web hyperlinks as a source to analyze citations. Topics include basic graph theory applied to Web pages, including matrices, linear algebra, and Web topology; and hubs and authorities, including a search technique called HITS (Hyperlink Induced Topic Search). (Author/LRW)
ERIC Educational Resources Information Center
Axtell, M.; Stickles, J.
2010-01-01
The last ten years have seen an explosion of research in the zero-divisor graphs of commutative rings--by professional mathematicians "and" undergraduates. The objective is to find algebraic information within the geometry of these graphs. This topic is approachable by anyone with one or two semesters of abstract algebra. This article gives the…
Caveats: numerical requirements in graph theory based quantitation of tissue architecture.
Sudbø, J; Marcelpoil, R; Reith, A
2000-01-01
Graph theory based methods represent one approach to an objective and reproducible structural analysis of tissue architecture. By these methods, neighborhood relations between a number of objects (e.g., cells) are explored and inherent to these methods are therefore certain requirements as to the number of objects to be included in the analysis. However, the question of how many objects are required to achieve reproducible values in repeated computations of proposed structural features, has previously not been adressed specifically. After digitising HE stained slides and storing them as grey level images, cell nuclei were segmented and their geometrical centre of gravity were computed, serving as the basis for construction of the Voronoi diagram (VD) and its subgraphs. Variations in repeated computations of structural features derived from these graphs were related to the number of cell nuclei included in the analysis. We demonstrate a large variation in the values of the structural features from one computation to another in one and the same section when only a limited number of cells (100-500) are included in the analysis. This variation decreased with increasing number of cells analyzed. The exact number of cells required to achieve reproducible values differ significantly between tissues, but not between separate cases of similar lesions. There are no significant differences between normal and malignantly changed tissues in oral mucosa with respect to how many cells must be included. For graph theory based analysis of tissue architecture, care must be taken to include an adequate number of objects; for some of the structural features we have tested, more than 3000 cells. PMID:11310642
Differences in graph theory functional connectivity in left and right temporal lobe epilepsy
Chiang, Sharon; Stern, John M.; Engel, Jerome; Levin, Harvey S.; Haneef, Zulfi
2016-01-01
Summary Purpose To investigate lateralized differences in limbic system functional connectivity between left and right temporal lobe epilepsy (TLE) using graph theory. Methods Interictal resting state fMRI was performed in 14 left TLE patients, 11 right TLE patients, and 12 controls. Graph theory analysis of 10 bilateral limbic regions of interest was conducted. Changes in edgewise functional connectivity, network topology, and regional topology were quantified, and then left and right TLE were compared. Results Limbic edgewise functional connectivity was predominantly reduced in both left and right TLE. More regional connections were reduced in right TLE, most prominently involving reduced interhemispheric connectivity between the bilateral insula and bilateral hippocampi. A smaller number of limbic connections were increased in TLE, more so in left than in right TLE. Topologically, the most pronounced change was a reduction in average network betweenness centrality and concurrent increase in left hippocampal betweenness centrality in right TLE. In contrast, left TLE exhibited a weak trend toward increased right hippocampal betweenness centrality, with no change in average network betweenness centrality. Conclusion Limbic functional connectivity is predominantly reduced in both left and right TLE, with more pronounced reductions in right TLE. In contrast, left TLE exhibits both edgewise and topological changes that suggest a tendency toward reorganization. Network changes in TLE and lateralized differences thereof may have important diagnostic and prognostic implications. PMID:25445238
ERIC Educational Resources Information Center
Store, Jessie Chitsanzo
2012-01-01
There is ample literature documenting that, for many decades, high school students view algebra as difficult and do not demonstrate understanding of algebraic concepts. Algebraic reasoning in elementary school aims at meaningfully introducing algebra to elementary school students in preparation for higher-level mathematics. While there is research…
Rule-based graph theory to enable exploration of the space system architecture design space
NASA Astrophysics Data System (ADS)
Arney, Dale Curtis
The primary goal of this research is to improve upon system architecture modeling in order to enable the exploration of design space options. A system architecture is the description of the functional and physical allocation of elements and the relationships, interactions, and interfaces between those elements necessary to satisfy a set of constraints and requirements. The functional allocation defines the functions that each system (element) performs, and the physical allocation defines the systems required to meet those functions. Trading the functionality between systems leads to the architecture-level design space that is available to the system architect. The research presents a methodology that enables the modeling of complex space system architectures using a mathematical framework. To accomplish the goal of improved architecture modeling, the framework meets five goals: technical credibility, adaptability, flexibility, intuitiveness, and exhaustiveness. The framework is technically credible, in that it produces an accurate and complete representation of the system architecture under consideration. The framework is adaptable, in that it provides the ability to create user-specified locations, steady states, and functions. The framework is flexible, in that it allows the user to model system architectures to multiple destinations without changing the underlying framework. The framework is intuitive for user input while still creating a comprehensive mathematical representation that maintains the necessary information to completely model complex system architectures. Finally, the framework is exhaustive, in that it provides the ability to explore the entire system architecture design space. After an extensive search of the literature, graph theory presents a valuable mechanism for representing the flow of information or vehicles within a simple mathematical framework. Graph theory has been used in developing mathematical models of many transportation and
Review of uses of network and graph theory concepts within proteomics.
Grindrod, Peter; Kibble, Milla
2004-08-01
The size and nature of data collected on gene and protein interactions has led to a rapid growth of interest in graph theory and modern techniques for describing, characterizing and comparing networks. Simultaneously, this is a field of growth within mathematics and theoretical physics, where the global properties, and emergent behavior of networks, as a function of the local properties has long been studied. In this review, a number of approaches for exploiting modern network theory to help describe and analyze different data sets and problems associated with proteomic data are considered. This review aims to help biologists find their way towards useful ideas and references, yet may also help scientists from a mathematics and physics background to understand where they may apply their expertise. PMID:15966817
Figueroa-O'Farrill, Jose Miguel
2009-11-15
We phrase deformations of n-Leibniz algebras in terms of the cohomology theory of the associated Leibniz algebra. We do the same for n-Lie algebras and for the metric versions of n-Leibniz and n-Lie algebras. We place particular emphasis on the case of n=3 and explore the deformations of 3-algebras of relevance to three-dimensional superconformal Chern-Simons theories with matter.
PDB2Graph: A toolbox for identifying critical amino acids map in proteins based on graph theory.
Niknam, Niloofar; Khakzad, Hamed; Arab, Seyed Shahriar; Naderi-Manesh, Hossein
2016-05-01
The integrative and cooperative nature of protein structure involves the assessment of topological and global features of constituent parts. Network concept takes complete advantage of both of these properties in the analysis concomitantly. High compatibility to structural concepts or physicochemical properties in addition to exploiting a remarkable simplification in the system has made network an ideal tool to explore biological systems. There are numerous examples in which different protein structural and functional characteristics have been clarified by the network approach. Here, we present an interactive and user-friendly Matlab-based toolbox, PDB2Graph, devoted to protein structure network construction, visualization, and analysis. Moreover, PDB2Graph is an appropriate tool for identifying critical nodes involved in protein structural robustness and function based on centrality indices. It maps critical amino acids in protein networks and can greatly aid structural biologists in selecting proper amino acid candidates for manipulating protein structures in a more reasonable and rational manner. To introduce the capability and efficiency of PDB2Graph in detail, the structural modification of Calmodulin through allosteric binding of Ca(2+) is considered. In addition, a mutational analysis for three well-identified model proteins including Phage T4 lysozyme, Barnase and Ribonuclease HI, was performed to inspect the influence of mutating important central residues on protein activity. PMID:27043857
Algebraic vs physical N = 6 3-algebras
Cantarini, Nicoletta; Kac, Victor G.
2014-01-15
In our previous paper, we classified linearly compact algebraic simple N = 6 3-algebras. In the present paper, we classify their “physical” counterparts, which actually appear in the N = 6 supersymmetric 3-dimensional Chern-Simons theories.
ERIC Educational Resources Information Center
De Jong, Marvin L.
1993-01-01
Describes the powerful graphing ability of computer algebra systems (CAS) to create three-dimensional graphs or surface graphics of electric potentials. Provides equations along with examples of the printouts. Lists the programs Mathematica, Maple, Derive, Theorist, MathCad, and MATLAB as promising CAS systems. (MVL)
Daianu, Madelaine; Mezher, Adam; Jahanshad, Neda; Hibar, Derrek P.; Nir, Talia M.; Jack, Clifford R.; Weiner, Michael W.; Bernstein, Matt A.; Thompson, Paul M.
2015-01-01
Our understanding of network breakdown in Alzheimer’s disease (AD) is likely to be enhanced through advanced mathematical descriptors. Here, we applied spectral graph theory to provide novel metrics of structural connectivity based on 3-Tesla diffusion weighted images in 42 AD patients and 50 healthy controls. We reconstructed connectivity networks using whole-brain tractography and examined, for the first time here, cortical disconnection based on the graph energy and spectrum. We further assessed supporting metrics - link density and nodal strength - to better interpret our results. Metrics were analyzed in relation to the well-known APOE-4 genetic risk factor for late-onset AD. The number of disconnected cortical regions increased with the number of copies of the APOE-4 risk gene in people with AD. Each additional copy of the APOE-4 risk gene may lead to more dysfunctional networks with weakened or abnormal connections, providing evidence for the previously hypothesized “disconnection syndrome”. PMID:26413205
Stavrakas, Vassilis; Alexopoulos, Leonidas G.
2015-01-01
Modeling of signal transduction pathways is instrumental for understanding cells’ function. People have been tackling modeling of signaling pathways in order to accurately represent the signaling events inside cells’ biochemical microenvironment in a way meaningful for scientists in a biological field. In this article, we propose a method to interrogate such pathways in order to produce cell-specific signaling models. We integrate available prior knowledge of protein connectivity, in a form of a Prior Knowledge Network (PKN) with phosphoproteomic data to construct predictive models of the protein connectivity of the interrogated cell type. Several computational methodologies focusing on pathways’ logic modeling using optimization formulations or machine learning algorithms have been published on this front over the past few years. Here, we introduce a light and fast approach that uses a breadth-first traversal of the graph to identify the shortest pathways and score proteins in the PKN, fitting the dependencies extracted from the experimental design. The pathways are then combined through a heuristic formulation to produce a final topology handling inconsistencies between the PKN and the experimental scenarios. Our results show that the algorithm we developed is efficient and accurate for the construction of medium and large scale signaling networks. We demonstrate the applicability of the proposed approach by interrogating a manually curated interaction graph model of EGF/TNFA stimulation against made up experimental data. To avoid the possibility of erroneous predictions, we performed a cross-validation analysis. Finally, we validate that the introduced approach generates predictive topologies, comparable to the ILP formulation. Overall, an efficient approach based on graph theory is presented herein to interrogate protein–protein interaction networks and to provide meaningful biological insights. PMID:26020784
Stavrakas, Vassilis; Melas, Ioannis N; Sakellaropoulos, Theodore; Alexopoulos, Leonidas G
2015-01-01
Modeling of signal transduction pathways is instrumental for understanding cells' function. People have been tackling modeling of signaling pathways in order to accurately represent the signaling events inside cells' biochemical microenvironment in a way meaningful for scientists in a biological field. In this article, we propose a method to interrogate such pathways in order to produce cell-specific signaling models. We integrate available prior knowledge of protein connectivity, in a form of a Prior Knowledge Network (PKN) with phosphoproteomic data to construct predictive models of the protein connectivity of the interrogated cell type. Several computational methodologies focusing on pathways' logic modeling using optimization formulations or machine learning algorithms have been published on this front over the past few years. Here, we introduce a light and fast approach that uses a breadth-first traversal of the graph to identify the shortest pathways and score proteins in the PKN, fitting the dependencies extracted from the experimental design. The pathways are then combined through a heuristic formulation to produce a final topology handling inconsistencies between the PKN and the experimental scenarios. Our results show that the algorithm we developed is efficient and accurate for the construction of medium and large scale signaling networks. We demonstrate the applicability of the proposed approach by interrogating a manually curated interaction graph model of EGF/TNFA stimulation against made up experimental data. To avoid the possibility of erroneous predictions, we performed a cross-validation analysis. Finally, we validate that the introduced approach generates predictive topologies, comparable to the ILP formulation. Overall, an efficient approach based on graph theory is presented herein to interrogate protein-protein interaction networks and to provide meaningful biological insights. PMID:26020784
Quantification of Three-Dimensional Cell-Mediated Collagen Remodeling Using Graph Theory
Bilgin, Cemal Cagatay; Lund, Amanda W.; Can, Ali; Plopper, George E.; Yener, Bülent
2010-01-01
Background Cell cooperation is a critical event during tissue development. We present the first precise metrics to quantify the interaction between mesenchymal stem cells (MSCs) and extra cellular matrix (ECM). In particular, we describe cooperative collagen alignment process with respect to the spatio-temporal organization and function of mesenchymal stem cells in three dimensions. Methodology/Principal Findings We defined two precise metrics: Collagen Alignment Index and Cell Dissatisfaction Level, for quantitatively tracking type I collagen and fibrillogenesis remodeling by mesenchymal stem cells over time. Computation of these metrics was based on graph theory and vector calculus. The cells and their three dimensional type I collagen microenvironment were modeled by three dimensional cell-graphs and collagen fiber organization was calculated from gradient vectors. With the enhancement of mesenchymal stem cell differentiation, acceleration through different phases was quantitatively demonstrated. The phases were clustered in a statistically significant manner based on collagen organization, with late phases of remodeling by untreated cells clustering strongly with early phases of remodeling by differentiating cells. The experiments were repeated three times to conclude that the metrics could successfully identify critical phases of collagen remodeling that were dependent upon cooperativity within the cell population. Conclusions/Significance Definition of early metrics that are able to predict long-term functionality by linking engineered tissue structure to function is an important step toward optimizing biomaterials for the purposes of regenerative medicine. PMID:20927339
Dual algebraic formulation of differential GPS
NASA Astrophysics Data System (ADS)
Lannes, A.; Dur, S.
2003-05-01
A new approach to differential GPS is presented. The corresponding theoretical framework calls on elementary concepts of algebraic graph theory. The notion of double difference, which is related to that of closure in the sense of Kirchhoff, is revisited in this context. The Moore-Penrose pseudo-inverse of the closure operator plays a key role in the corresponding dual formulation. This approach, which is very attractive from a conceptual point of view, sheds a new light on the Teunissen formulation.
Hart, Michael G; Ypma, Rolf J F; Romero-Garcia, Rafael; Price, Stephen J; Suckling, John
2016-06-01
Neuroanatomy has entered a new era, culminating in the search for the connectome, otherwise known as the brain's wiring diagram. While this approach has led to landmark discoveries in neuroscience, potential neurosurgical applications and collaborations have been lagging. In this article, the authors describe the ideas and concepts behind the connectome and its analysis with graph theory. Following this they then describe how to form a connectome using resting state functional MRI data as an example. Next they highlight selected insights into healthy brain function that have been derived from connectome analysis and illustrate how studies into normal development, cognitive function, and the effects of synthetic lesioning can be relevant to neurosurgery. Finally, they provide a précis of early applications of the connectome and related techniques to traumatic brain injury, functional neurosurgery, and neurooncology. PMID:26544769
Graph theory approach to the eigenvalue problem of large space structures
NASA Technical Reports Server (NTRS)
Reddy, A. S. S. R.; Bainum, P. M.
1981-01-01
Graph theory is used to obtain numerical solutions to eigenvalue problems of large space structures (LSS) characterized by a state vector of large dimensions. The LSS are considered as large, flexible systems requiring both orientation and surface shape control. Graphic interpretation of the determinant of a matrix is employed to reduce a higher dimensional matrix into combinations of smaller dimensional sub-matrices. The reduction is implemented by means of a Boolean equivalent of the original matrices formulated to obtain smaller dimensional equivalents of the original numerical matrix. Computation time becomes less and more accurate solutions are possible. An example is provided in the form of a free-free square plate. Linearized system equations and numerical values of a stiffness matrix are presented, featuring a state vector with 16 components.
HBNG: Graph theory based visualization of hydrogen bond networks in protein structures
Tiwari, Abhishek; Tiwari, Vivek
2007-01-01
HBNG is a graph theory based tool for visualization of hydrogen bond network in 2D. Digraphs generated by HBNG facilitate visualization of cooperativity and anticooperativity chains and rings in protein structures. HBNG takes hydrogen bonds list files (output from HBAT, HBEXPLORE, HBPLUS and STRIDE) as input and generates a DOT language script and constructs digraphs using freeware AT and T Graphviz tool. HBNG is useful in the enumeration of favorable topologies of hydrogen bond networks in protein structures and determining the effect of cooperativity and anticooperativity on protein stability and folding. HBNG can be applied to protein structure comparison and in the identification of secondary structural regions in protein structures. Availability Program is available from the authors for non-commercial purposes. PMID:18084648
Morphological brain network assessed using graph theory and network filtration in deaf adults.
Kim, Eunkyung; Kang, Hyejin; Lee, Hyekyoung; Lee, Hyo-Jeong; Suh, Myung-Whan; Song, Jae-Jin; Oh, Seung-Ha; Lee, Dong Soo
2014-09-01
Prolonged deprivation of auditory input can change brain networks in pre- and postlingual deaf adults by brain-wide reorganization. To investigate morphological changes in these brains voxel-based morphometry, voxel-wise correlation with the primary auditory cortex, and whole brain network analyses using morphological covariance were performed in eight prelingual deaf, eleven postlingual deaf, and eleven hearing adults. Network characteristics based on graph theory and network filtration based on persistent homology were examined. Gray matter density in the primary auditor cortex was preserved in prelingual deafness, while it tended to decrease in postlingual deafness. Unlike postlingual, prelingual deafness showed increased bilateral temporal connectivity of the primary auditory cortex compared to the hearing adults. Of the graph theory-based characteristics, clustering coefficient, betweenness centrality, and nodal efficiency all increased in prelingual deafness, while all the parameters of postlingual deafness were similar to the hearing adults. Patterns of connected components changing during network filtration were different between prelingual deafness and hearing adults according to the barcode, dendrogram, and single linkage matrix representations, while these were the same in postlingual deafness. Nodes in fronto-limbic and left temporal components were closely coupled, and nodes in the temporo-parietal component were loosely coupled, in prelingual deafness. Patterns of connected components changing in postlingual deafness were the same as hearing adults. We propose that the preserved density of auditory cortex associated with increased connectivity in prelingual deafness, and closer coupling between certain brain areas, represent distinctive reorganization of auditory and related cortices compared with hearing or postlingual deaf adults. The differential network reorganization in the prelingual deaf adults could be related to the absence of auditory speech
What graph theory actually tells us about resting state interictal MEG epileptic activity
Niso, Guiomar; Carrasco, Sira; Gudín, María; Maestú, Fernando; del-Pozo, Francisco; Pereda, Ernesto
2015-01-01
Graph theory provides a useful framework to study functional brain networks from neuroimaging data. In epilepsy research, recent findings suggest that it offers unique insight into the fingerprints of this pathology on brain dynamics. Most studies hitherto have focused on seizure activity during focal epilepsy, but less is known about functional epileptic brain networks during interictal activity in frontal focal and generalized epilepsy. Besides, it is not clear yet which measures are most suitable to characterize these networks. To address these issues, we recorded magnetoencephalographic (MEG) data using two orthogonal planar gradiometers from 45 subjects from three groups (15 healthy controls (7 males, 24 ± 6 years), 15 frontal focal (8 male, 32 ± 16 years) and 15 generalized epileptic (6 male, 27 ± 7 years) patients) during interictal resting state with closed eyes. Then, we estimated the total and relative spectral power of the largest principal component of the gradiometers, and the degree of phase synchronization between each sensor site in the frequency range [0.5–40 Hz]. We further calculated a comprehensive battery of 15 graph-theoretic measures and used the affinity propagation clustering algorithm to elucidate the minimum set of them that fully describe these functional brain networks. The results show that differences in spectral power between the control and the other two groups have a distinctive pattern: generalized epilepsy presents higher total power for all frequencies except the alpha band over a widespread set of sensors; frontal focal epilepsy shows higher relative power in the beta band bilaterally in the fronto-central sensors. Moreover, all network indices can be clustered into three groups, whose exemplars are the global network efficiency, the eccentricity and the synchronizability. Again, the patterns of differences were clear: the brain network of the generalized epilepsy patients presented greater efficiency and lower
What graph theory actually tells us about resting state interictal MEG epileptic activity.
Niso, Guiomar; Carrasco, Sira; Gudín, María; Maestú, Fernando; Del-Pozo, Francisco; Pereda, Ernesto
2015-01-01
Graph theory provides a useful framework to study functional brain networks from neuroimaging data. In epilepsy research, recent findings suggest that it offers unique insight into the fingerprints of this pathology on brain dynamics. Most studies hitherto have focused on seizure activity during focal epilepsy, but less is known about functional epileptic brain networks during interictal activity in frontal focal and generalized epilepsy. Besides, it is not clear yet which measures are most suitable to characterize these networks. To address these issues, we recorded magnetoencephalographic (MEG) data using two orthogonal planar gradiometers from 45 subjects from three groups (15 healthy controls (7 males, 24 ± 6 years), 15 frontal focal (8 male, 32 ± 16 years) and 15 generalized epileptic (6 male, 27 ± 7 years) patients) during interictal resting state with closed eyes. Then, we estimated the total and relative spectral power of the largest principal component of the gradiometers, and the degree of phase synchronization between each sensor site in the frequency range [0.5-40 Hz]. We further calculated a comprehensive battery of 15 graph-theoretic measures and used the affinity propagation clustering algorithm to elucidate the minimum set of them that fully describe these functional brain networks. The results show that differences in spectral power between the control and the other two groups have a distinctive pattern: generalized epilepsy presents higher total power for all frequencies except the alpha band over a widespread set of sensors; frontal focal epilepsy shows higher relative power in the beta band bilaterally in the fronto-central sensors. Moreover, all network indices can be clustered into three groups, whose exemplars are the global network efficiency, the eccentricity and the synchronizability. Again, the patterns of differences were clear: the brain network of the generalized epilepsy patients presented greater efficiency and lower
NASA Astrophysics Data System (ADS)
Brazhnik, Olga D.; Freed, Karl F.
1996-07-01
The lattice cluster theory (LCT) is extended to enable inclusion of longer range correlation contributions to the partition function of lattice model polymers in the athermal limit. A diagrammatic technique represents the expansion of the partition function in powers of the inverse lattice coordination number. Graph theory is applied to sort, classify, and evaluate the numerous diagrams appearing in higher orders. New general theorems are proven that provide a significant reduction in the computational labor required to evaluate the contributions from higher order correlations. The new algorithm efficiently generates the correction to the Flory mean field approximation from as many as eight sterically interacting bonds. While the new results contain the essential ingredients for treating a system of flexible chains with arbitrary lengths and concentrations, the complexity of our new algorithm motivates us to test the theory here for the simplest case of a system of lattice dimers by comparison to the dimer packing entropies from the work of Gaunt. This comparison demonstrates that the eight bond LCT is exact through order φ5 for dimers in one through three dimensions, where φ is the volume fraction of dimers. A subsequent work will use the contracted diagrams, derived and tested here, to treat the packing entropy for a system of flexible N-mers at a volume fraction of φ on hypercubic lattices.
The kinematic algebras from the scattering equations
NASA Astrophysics Data System (ADS)
Monteiro, Ricardo; O'Connell, Donal
2014-03-01
We study kinematic algebras associated to the recently proposed scattering equations, which arise in the description of the scattering of massless particles. In particular, we describe the role that these algebras play in the BCJ duality between colour and kinematics in gauge theory, and its relation to gravity. We find that the scattering equations are a consistency condition for a self-dual-type vertex which is associated to each solution of those equations. We also identify an extension of the anti-self-dual vertex, such that the two vertices are not conjugate in general. Both vertices correspond to the structure constants of Lie algebras. We give a prescription for the use of the generators of these Lie algebras in trivalent graphs that leads to a natural set of BCJ numerators. In particular, we write BCJ numerators for each contribution to the amplitude associated to a solution of the scattering equations. This leads to a decomposition of the determinant of a certain kinematic matrix, which appears naturally in the amplitudes, in terms of trivalent graphs. We also present the kinematic analogues of colour traces, according to these algebras, and the associated decomposition of that determinant.
Prognostic value of graph theory-based tissue architecture analysis in carcinomas of the tongue.
Sudbø, J; Bankfalvi, A; Bryne, M; Marcelpoil, R; Boysen, M; Piffko, J; Hemmer, J; Kraft, K; Reith, A
2000-12-01
Several studies on oral squamous cell carcinomas (OSCC) suggest that the clinical value of traditional histologic grading is limited both by poor reproducibility and by low prognostic impact. However, the prognostic potential of a strictly quantitative and highly reproducible assessment of the tissue architecture in OSCC has not been evaluated. Using image analysis, in 193 cases of T1-2 (Stage I-II) OSCC we retrospectively investigated the prognostic impact of two graph theory-derived structural features: the average Delaunay Edge Length (DEL_av) and the average homogeneity of the Ulam Tree (ELH_av). Both structural features were derived from subgraphs of the Voronoi Diagram. The geometric centers of the cell nuclei were computed, generating a two-dimensional swarm of point-like seeds from which graphs could be constructed. The impact on survival of the computed values of ELH_av and DEL_av was estimated by the method of Kaplan and Meier, with relapse-free survival and overall survival as end-points. The prognostic values of DEL_av and ELH_av as computed for the invasive front, the superficial part of the carcinoma, the total carcinoma, and the normal-appearing oral mucosa were compared. For DEL_av, significant prognostic information was found in the invasive front (p < 0.001). No significant prognostic information was found in superficial part of the carcinoma (p = 0.34), in the carcinoma as a whole (p = 0.35), or in the normal-appearing mucosa (p = 0.27). For ELH_av, significant prognostic information was found in the invasive front (p = 0.01) and, surprisingly, in putatively normal mucosa (p = 0.03). No significant prognostic information was found in superficial parts of the carcinoma (p = 0.34) or in the total carcinoma (p = 0.11). In conclusion, strictly quantitative assessment of tissue architecture in the invasive front of OSCC yields highly prognostic information. PMID:11140700
Müller, Patrick; Hillebrandt, Sabina; Krufczik, Matthias; Bach, Margund; Kaufmann, Rainer; Hausmann, Michael; Heermann, Dieter W.
2015-01-01
It has been well established that the architecture of chromatin in cell nuclei is not random but functionally correlated. Chromatin damage caused by ionizing radiation raises complex repair machineries. This is accompanied by local chromatin rearrangements and structural changes which may for instance improve the accessibility of damaged sites for repair protein complexes. Using stably transfected HeLa cells expressing either green fluorescent protein (GFP) labelled histone H2B or yellow fluorescent protein (YFP) labelled histone H2A, we investigated the positioning of individual histone proteins in cell nuclei by means of high resolution localization microscopy (Spectral Position Determination Microscopy = SPDM). The cells were exposed to ionizing radiation of different doses and aliquots were fixed after different repair times for SPDM imaging. In addition to the repair dependent histone protein pattern, the positioning of antibodies specific for heterochromatin and euchromatin was separately recorded by SPDM. The present paper aims to provide a quantitative description of structural changes of chromatin after irradiation and during repair. It introduces a novel approach to analyse SPDM images by means of statistical physics and graph theory. The method is based on the calculation of the radial distribution functions as well as edge length distributions for graphs defined by a triangulation of the marker positions. The obtained results show that through the cell nucleus the different chromatin re-arrangements as detected by the fluorescent nucleosomal pattern average themselves. In contrast heterochromatic regions alone indicate a relaxation after radiation exposure and re-condensation during repair whereas euchromatin seemed to be unaffected or behave contrarily. SPDM in combination with the analysis techniques applied allows the systematic elucidation of chromatin re-arrangements after irradiation and during repair, if selected sub-regions of nuclei are
Computer Algebra Systems in Undergraduate Instruction.
ERIC Educational Resources Information Center
Small, Don; And Others
1986-01-01
Computer algebra systems (such as MACSYMA and muMath) can carry out many of the operations of calculus, linear algebra, and differential equations. Use of them with sketching graphs of rational functions and with other topics is discussed. (MNS)
Marrero-Ponce, Yovani; Santiago, Oscar Martínez; López, Yoan Martínez; Barigye, Stephen J; Torrens, Francisco
2012-11-01
In this report, we present a new mathematical approach for describing chemical structures of organic molecules at atomic-molecular level, proposing for the first time the use of the concept of the derivative ([Formula: see text]) of a molecular graph (MG) with respect to a given event (E), to obtain a new family of molecular descriptors (MDs). With this purpose, a new matrix representation of the MG, which generalizes graph's theory's traditional incidence matrix, is introduced. This matrix, denominated the generalized incidence matrix, Q, arises from the Boolean representation of molecular sub-graphs that participate in the formation of the graph molecular skeleton MG and could be complete (representing all possible connected sub-graphs) or constitute sub-graphs of determined orders or types as well as a combination of these. The Q matrix is a non-quadratic and unsymmetrical in nature, its columns (n) and rows (m) are conditions (letters) and collection of conditions (words) with which the event occurs. This non-quadratic and unsymmetrical matrix is transformed, by algebraic manipulation, to a quadratic and symmetric matrix known as relations frequency matrix, F, which characterizes the participation intensity of the conditions (letters) in the events (words). With F, we calculate the derivative over a pair of atomic nuclei. The local index for the atomic nuclei i, Δ(i), can therefore be obtained as a linear combination of all the pair derivatives of the atomic nuclei i with all the rest of the j's atomic nuclei. Here, we also define new strategies that generalize the present form of obtaining global or local (group or atom-type) invariants from atomic contributions (local vertex invariants, LOVIs). In respect to this, metric (norms), means and statistical invariants are introduced. These invariants are applied to a vector whose components are the values Δ(i) for the atomic nuclei of the molecule or its fragments. Moreover, with the purpose of differentiating
NASA Astrophysics Data System (ADS)
Putnam, Ian F.
2010-03-01
We investigate the C*-algebras associated to aperiodic structures called model sets obtained by the cut-and-project method. These C*-algebras are Morita equivalent to crossed product C*-algebras obtained from dynamics on a disconnected version of the internal space. This construction may be made from more general data, which we call a hyperplane system. From a hyperplane system, others may be constructed by a process of reduction and we show how the C*-algebras involved are related to each other. In particular, there are natural elements in the Kasparov KK-groups for the C*-algebra of a hyperplane system and that of its reduction. The induced map on K-theory fits in a six-term exact sequence. This provides a new method of the computation of the K-theory of such C*-algebras which is done completely in the setting of non-commutative geometry.
The three-dimensional origin of the classifying algebra
NASA Astrophysics Data System (ADS)
Fuchs, Jürgen; Schweigert, Christoph; Stigner, Carl
2010-01-01
It is known that reflection coefficients for bulk fields of a rational conformal field theory in the presence of an elementary boundary condition can be obtained as representation matrices of irreducible representations of the classifying algebra, a semisimple commutative associative complex algebra. We show how this algebra arises naturally from the three-dimensional geometry of factorization of correlators of bulk fields on the disk. This allows us to derive explicit expressions for the structure constants of the classifying algebra as invariants of ribbon graphs in the three-manifold S×S. Our result unravels a precise relation between intertwiners of the action of the mapping class group on spaces of conformal blocks and boundary conditions in rational conformal field theories.
Anticipation-related brain connectivity in bipolar and unipolar depression: a graph theory approach.
Manelis, Anna; Almeida, Jorge R C; Stiffler, Richelle; Lockovich, Jeanette C; Aslam, Haris A; Phillips, Mary L
2016-09-01
Bipolar disorder is often misdiagnosed as major depressive disorder, which leads to inadequate treatment. Depressed individuals versus healthy control subjects, show increased expectation of negative outcomes. Due to increased impulsivity and risk for mania, however, depressed individuals with bipolar disorder may differ from those with major depressive disorder in neural mechanisms underlying anticipation processes. Graph theory methods for neuroimaging data analysis allow the identification of connectivity between multiple brain regions without prior model specification, and may help to identify neurobiological markers differentiating these disorders, thereby facilitating development of better therapeutic interventions. This study aimed to compare brain connectivity among regions involved in win/loss anticipation in depressed individuals with bipolar disorder (BDD) versus depressed individuals with major depressive disorder (MDD) versus healthy control subjects using graph theory methods. The study was conducted at the University of Pittsburgh Medical Center and included 31 BDD, 39 MDD, and 36 healthy control subjects. Participants were scanned while performing a number guessing reward task that included the periods of win and loss anticipation. We first identified the anticipatory network across all 106 participants by contrasting brain activation during all anticipation periods (win anticipation + loss anticipation) versus baseline, and win anticipation versus loss anticipation. Brain connectivity within the identified network was determined using the Independent Multiple sample Greedy Equivalence Search (IMaGES) and Linear non-Gaussian Orientation, Fixed Structure (LOFS) algorithms. Density of connections (the number of connections in the network), path length, and the global connectivity direction ('top-down' versus 'bottom-up') were compared across groups (BDD/MDD/healthy control subjects) and conditions (win/loss anticipation). These analyses showed that
A Graph Theory Method For Determination Of Cryo-EM Image Focuses
Jiang, Wen; Guo, Fei; Liu, Zheng
2012-01-01
Accurate determination of micrograph focuses is essential for averaging multiple images to reach high-resolution 3-D reconstructions in electron cryo-microscopy (cryo-EM). Current methods use iterative fitting of focus-dependent simulated power spectra to the power spectra of experimental images, with the fitting performed independently for different images. Here we have developed a novel graph theory based method in which the rotational average focus and individual angular sector focuses of all images are determined simultaneously in closed form using the least square solution of overdetermined linear equations. The new method was shown to be fast, accurate, and robust in tests with large datasets of experimental low dose cryo-EM images. Its integration with three classic power spectra fitting methods also allows cross validation of the results by these vastly different methods. The new integrated focus determination method will improve reliability of automated focus determination for large-scale data processing that is increasingly common in the cryo-EM field. PMID:22842112
Morphology and Performance of Polymer Solar Cell Characterized by DPD Simulation and Graph Theory
NASA Astrophysics Data System (ADS)
Du, Chunmiao; Ji, Yujin; Xue, Junwei; Hou, Tingjun; Tang, Jianxin; Lee, Shuit-Tong; Li, Youyong
2015-11-01
The morphology of active layers in the bulk heterojunction (BHJ) solar cells is critical to the performance of organic photovoltaics (OPV). Currently, there is limited information for the morphology from transmission electron microscopy (TEM) techniques. Meanwhile, there are limited approaches to predict the morphology /efficiency of OPV. Here we use Dissipative Particle Dynamics (DPD) to determine 3D morphology of BHJ solar cells and show DPD to be an efficient approach to predict the 3D morphology. Based on the 3D morphology, we estimate the performance indicator of BHJ solar cells by using graph theory. Specifically, we study poly (3-hexylthiophene)/[6, 6]-phenyl-C61butyric acid methyl ester (P3HT/PCBM) BHJ solar cells. We find that, when the volume fraction of PCBM is in the region 0.4 ∼ 0.5, P3HT/PCBM will show bi-continuous morphology and optimum performance, consistent with experimental results. Further, the optimum temperature (413 K) for the morphology and performance of P3HT/PCBM is in accord with annealing results. We find that solvent additive plays a critical role in the desolvation process of P3HT/PCBM BHJ solar cell. Our approach provides a direct method to predict dynamic 3D morphology and performance indicator for BHJ solar cells.
Morphology and Performance of Polymer Solar Cell Characterized by DPD Simulation and Graph Theory
Du, Chunmiao; Ji, Yujin; Xue, Junwei; Hou, Tingjun; Tang, Jianxin; Lee, Shuit-Tong; Li, Youyong
2015-01-01
The morphology of active layers in the bulk heterojunction (BHJ) solar cells is critical to the performance of organic photovoltaics (OPV). Currently, there is limited information for the morphology from transmission electron microscopy (TEM) techniques. Meanwhile, there are limited approaches to predict the morphology /efficiency of OPV. Here we use Dissipative Particle Dynamics (DPD) to determine 3D morphology of BHJ solar cells and show DPD to be an efficient approach to predict the 3D morphology. Based on the 3D morphology, we estimate the performance indicator of BHJ solar cells by using graph theory. Specifically, we study poly (3-hexylthiophene)/[6, 6]-phenyl-C61butyric acid methyl ester (P3HT/PCBM) BHJ solar cells. We find that, when the volume fraction of PCBM is in the region 0.4 ∼ 0.5, P3HT/PCBM will show bi-continuous morphology and optimum performance, consistent with experimental results. Further, the optimum temperature (413 K) for the morphology and performance of P3HT/PCBM is in accord with annealing results. We find that solvent additive plays a critical role in the desolvation process of P3HT/PCBM BHJ solar cell. Our approach provides a direct method to predict dynamic 3D morphology and performance indicator for BHJ solar cells. PMID:26581407
Morphology and Performance of Polymer Solar Cell Characterized by DPD Simulation and Graph Theory.
Du, Chunmiao; Ji, Yujin; Xue, Junwei; Hou, Tingjun; Tang, Jianxin; Lee, Shuit-Tong; Li, Youyong
2015-01-01
The morphology of active layers in the bulk heterojunction (BHJ) solar cells is critical to the performance of organic photovoltaics (OPV). Currently, there is limited information for the morphology from transmission electron microscopy (TEM) techniques. Meanwhile, there are limited approaches to predict the morphology /efficiency of OPV. Here we use Dissipative Particle Dynamics (DPD) to determine 3D morphology of BHJ solar cells and show DPD to be an efficient approach to predict the 3D morphology. Based on the 3D morphology, we estimate the performance indicator of BHJ solar cells by using graph theory. Specifically, we study poly (3-hexylthiophene)/[6, 6]-phenyl-C61butyric acid methyl ester (P3HT/PCBM) BHJ solar cells. We find that, when the volume fraction of PCBM is in the region 0.4 ∼ 0.5, P3HT/PCBM will show bi-continuous morphology and optimum performance, consistent with experimental results. Further, the optimum temperature (413 K) for the morphology and performance of P3HT/PCBM is in accord with annealing results. We find that solvent additive plays a critical role in the desolvation process of P3HT/PCBM BHJ solar cell. Our approach provides a direct method to predict dynamic 3D morphology and performance indicator for BHJ solar cells. PMID:26581407
Utilizing graph theory to select the largest set of unrelated individuals for genetic analysis.
Staples, Jeffrey; Nickerson, Deborah A; Below, Jennifer E
2013-02-01
Many statistical analyses of genetic data rely on the assumption of independence among samples. Consequently, relatedness is either modeled in the analysis or samples are removed to "clean" the data of any pairwise relatedness above a tolerated threshold. Current methods do not maximize the number of unrelated individuals retained for further analysis, and this is a needless loss of resources. We report a novel application of graph theory that identifies the maximum set of unrelated samples in any dataset given a user-defined threshold of relatedness as well as all networks of related samples. We have implemented this method into an open source program called Pedigree Reconstruction and Identification of a Maximum Unrelated Set, PRIMUS. We show that PRIMUS outperforms the three existing methods, allowing researchers to retain up to 50% more unrelated samples. A unique strength of PRIMUS is its ability to weight the maximum clique selection using additional criteria (e.g. affected status and data missingness). PRIMUS is a permanent solution to identifying the maximum number of unrelated samples for a genetic analysis. PMID:22996348
ERIC Educational Resources Information Center
Senarat, Somprasong; Tayraukham, Sombat; Piyapimonsit, Chatsiri; Tongkhambanjong, Sakesan
2013-01-01
The purpose of this research is to develop a multidimensional computerized adaptive test for diagnosing the cognitive process of grade 7 students in learning algebra by applying multidimensional item response theory. The research is divided into 4 steps: 1) the development of item bank of algebra, 2) the development of the multidimensional…
Algebraic K-theory of spaces stratified fibered over hyperbolic orbifolds.
Farrell, F T; Jones, L E
1986-08-01
Among other results, we rationally calculate the algebraic K-theory of any discrete cocompact subgroup of a Lie group G, where G is either O(n, 1), U(n, 1), Sp(n, 1), or F(4), in terms of the homology of the double coset space Gamma\\G/K, where K is a maximal cocompact subgroup of G. We obtain the formula K(n)(ZGamma) [unk] [unk] congruent with [unk](i=0) (infinity)H(i)(Gamma\\G/K; [unk](n-i)), where [unk](j) is a stratified system of Q vector spaces over Gamma\\G/K and the vector space [unk](j)(GammagK) corresponding to the double coset GammagK is isomorphic to K(J)(Z(Gamma [unk] gKg(-1))) [unk] Q. Note Gamma [unk] gKg(-1) is a finite subgroup of Gamma. Earlier, a similar formula for discrete cocompact subgroups Gamma of the group of rigid motions of Euclidean space was conjectured by F. T. Farrell and W. C. Hsiang and proven by F. Quinn. PMID:16593733
Algebraic K-theory of spaces stratified fibered over hyperbolic orbifolds
Farrell, F. T.; Jones, L. E.
1986-01-01
Among other results, we rationally calculate the algebraic K-theory of any discrete cocompact subgroup of a Lie group G, where G is either O(n, 1), U(n, 1), Sp(n, 1), or F4, in terms of the homology of the double coset space Γ\\G/K, where K is a maximal cocompact subgroup of G. We obtain the formula Kn(ZΓ) [unk] [unk] ≅ [unk]i=0∞Hi(Γ\\G/K; [unk]n-i), where [unk]j is a stratified system of Q vector spaces over Γ\\G/K and the vector space [unk]j(ΓgK) corresponding to the double coset ΓgK is isomorphic to KJ(Z(Γ [unk] gKg-1)) [unk] Q. Note Γ [unk] gKg-1 is a finite subgroup of Γ. Earlier, a similar formula for discrete cocompact subgroups Γ of the group of rigid motions of Euclidean space was conjectured by F. T. Farrell and W. C. Hsiang and proven by F. Quinn. PMID:16593733
Cytoscape.js: a graph theory library for visualisation and analysis
Franz, Max; Lopes, Christian T.; Huck, Gerardo; Dong, Yue; Sumer, Onur; Bader, Gary D.
2016-01-01
Summary: Cytoscape.js is an open-source JavaScript-based graph library. Its most common use case is as a visualization software component, so it can be used to render interactive graphs in a web browser. It also can be used in a headless manner, useful for graph operations on a server, such as Node.js. Availability and implementation: Cytoscape.js is implemented in JavaScript. Documentation, downloads and source code are available at http://js.cytoscape.org. Contact: gary.bader@utoronto.ca PMID:26415722
Applications of automata and graphs: Labeling operators in Hilbert space. II
Cho, Ilwoo; Jorgensen, Palle E. T.
2009-06-15
We introduced a family of infinite graphs directly associated with a class of von Neumann automaton model A{sub G}. These are finite state models used in symbolic dynamics: stimuli models and in control theory. In the context of groupoid von Neumann algebras, and an associated fractal group, we prove a classification theorem for representations of automata.
S-duality and the prepotential of N={2}^{star } theories (II): the non-simply laced algebras
NASA Astrophysics Data System (ADS)
Billó, M.; Frau, M.; Fucito, F.; Lerda, A.; Morales, J. F.
2015-11-01
We derive a modular anomaly equation satisfied by the prepotential of the N={2}^{star } supersymmetric theories with non-simply laced gauge algebras, including the classical B r and C r infinite series and the exceptional F 4 and G 2 cases. This equation determines the exact prepotential recursively in an expansion for small mass in terms of quasi-modular forms of the S-duality group. We also discuss the behaviour of these theories under S-duality and show that the prepotential of the SO(2 r + 1) theory is mapped to that of the Sp(2 r) theory and viceversa, while the exceptional F 4 and G 2 theories are mapped into themselves (up to a rotation of the roots) in analogy with what happens for the N=4 supersymmetric theories. These results extend the analysis for the simply laced groups presented in a companion paper.
Orientation in operator algebras
Alfsen, Erik M.; Shultz, Frederic W.
1998-01-01
A concept of orientation is relevant for the passage from Jordan structure to associative structure in operator algebras. The research reported in this paper bridges the approach of Connes for von Neumann algebras and ourselves for C*-algebras in a general theory of orientation that is of geometric nature and is related to dynamics. PMID:9618457
Gramatica, Ruggero; Di Matteo, T.; Giorgetti, Stefano; Barbiani, Massimo; Bevec, Dorian; Aste, Tomaso
2014-01-01
We introduce a methodology to efficiently exploit natural-language expressed biomedical knowledge for repurposing existing drugs towards diseases for which they were not initially intended. Leveraging on developments in Computational Linguistics and Graph Theory, a methodology is defined to build a graph representation of knowledge, which is automatically analysed to discover hidden relations between any drug and any disease: these relations are specific paths among the biomedical entities of the graph, representing possible Modes of Action for any given pharmacological compound. We propose a measure for the likeliness of these paths based on a stochastic process on the graph. This measure depends on the abundance of indirect paths between a peptide and a disease, rather than solely on the strength of the shortest path connecting them. We provide real-world examples, showing how the method successfully retrieves known pathophysiological Mode of Action and finds new ones by meaningfully selecting and aggregating contributions from known bio-molecular interactions. Applications of this methodology are presented, and prove the efficacy of the method for selecting drugs as treatment options for rare diseases. PMID:24416311
NASA Astrophysics Data System (ADS)
Khudaverdian, H. M.
2014-03-01
We consider differential operators acting on densities of arbitrary weights on manifold M identifying pencils of such operators with operators on algebra of densities of all weights. This algebra can be identified with the special subalgebra of functions on extended manifold . On one hand there is a canonical lift of projective structures on M to affine structures on extended manifold . On the other hand the restriction of algebra of all functions on extended manifold to this special subalgebra of functions implies the canonical scalar product. This leads in particular to classification of second order operators with use of Kaluza-Klein-like mechanisms.
Enhancing multiple-point geostatistical modeling: 1. Graph theory and pattern adjustment
NASA Astrophysics Data System (ADS)
Tahmasebi, Pejman; Sahimi, Muhammad
2016-03-01
In recent years, higher-order geostatistical methods have been used for modeling of a wide variety of large-scale porous media, such as groundwater aquifers and oil reservoirs. Their popularity stems from their ability to account for qualitative data and the great flexibility that they offer for conditioning the models to hard (quantitative) data, which endow them with the capability for generating realistic realizations of porous formations with very complex channels, as well as features that are mainly a barrier to fluid flow. One group of such models consists of pattern-based methods that use a set of data points for generating stochastic realizations by which the large-scale structure and highly-connected features are reproduced accurately. The cross correlation-based simulation (CCSIM) algorithm, proposed previously by the authors, is a member of this group that has been shown to be capable of simulating multimillion cell models in a matter of a few CPU seconds. The method is, however, sensitive to pattern's specifications, such as boundaries and the number of replicates. In this paper the original CCSIM algorithm is reconsidered and two significant improvements are proposed for accurately reproducing large-scale patterns of heterogeneities in porous media. First, an effective boundary-correction method based on the graph theory is presented by which one identifies the optimal cutting path/surface for removing the patchiness and discontinuities in the realization of a porous medium. Next, a new pattern adjustment method is proposed that automatically transfers the features in a pattern to one that seamlessly matches the surrounding patterns. The original CCSIM algorithm is then combined with the two methods and is tested using various complex two- and three-dimensional examples. It should, however, be emphasized that the methods that we propose in this paper are applicable to other pattern-based geostatistical simulation methods.
Open-Closed Homotopy Algebras and Strong Homotopy Leibniz Pairs Through Koszul Operad Theory
NASA Astrophysics Data System (ADS)
Hoefel, Eduardo; Livernet, Muriel
2012-08-01
Open-closed homotopy algebras (OCHA) and strong homotopy Leibniz pairs (SHLP) were introduced by Kajiura and Stasheff in 2004. In an appendix to their paper, Markl observed that an SHLP is equivalent to an algebra over the minimal model of a certain operad, without showing that the operad is Koszul. In the present paper, we show that both OCHA and SHLP are algebras over the minimal model of the zeroth homology of two versions of the Swiss-cheese operad and prove that these two operads are Koszul. As an application, we show that the OCHA operad is non-formal as a 2-colored operad but is formal as an algebra in the category of 2-collections.
Lie algebra extensions of current algebras on S3
NASA Astrophysics Data System (ADS)
Kori, Tosiaki; Imai, Yuto
2015-06-01
An affine Kac-Moody algebra is a central extension of the Lie algebra of smooth mappings from S1 to the complexification of a Lie algebra. In this paper, we shall introduce a central extension of the Lie algebra of smooth mappings from S3 to the quaternization of a Lie algebra and investigate its root space decomposition. We think this extension of current algebra might give a mathematical tool for four-dimensional conformal field theory as Kac-Moody algebras give it for two-dimensional conformal field theory.
Quantum cluster algebras and quantum nilpotent algebras
Goodearl, Kenneth R.; Yakimov, Milen T.
2014-01-01
A major direction in the theory of cluster algebras is to construct (quantum) cluster algebra structures on the (quantized) coordinate rings of various families of varieties arising in Lie theory. We prove that all algebras in a very large axiomatically defined class of noncommutative algebras possess canonical quantum cluster algebra structures. Furthermore, they coincide with the corresponding upper quantum cluster algebras. We also establish analogs of these results for a large class of Poisson nilpotent algebras. Many important families of coordinate rings are subsumed in the class we are covering, which leads to a broad range of applications of the general results to the above-mentioned types of problems. As a consequence, we prove the Berenstein–Zelevinsky conjecture [Berenstein A, Zelevinsky A (2005) Adv Math 195:405–455] for the quantized coordinate rings of double Bruhat cells and construct quantum cluster algebra structures on all quantum unipotent groups, extending the theorem of Geiß et al. [Geiß C, et al. (2013) Selecta Math 19:337–397] for the case of symmetric Kac–Moody groups. Moreover, we prove that the upper cluster algebras of Berenstein et al. [Berenstein A, et al. (2005) Duke Math J 126:1–52] associated with double Bruhat cells coincide with the corresponding cluster algebras. PMID:24982197
ERIC Educational Resources Information Center
Buerman, Margaret
2007-01-01
Finding real-world examples for middle school algebra classes can be difficult but not impossible. As we strive to accomplish teaching our students how to solve and graph equations, we neglect to teach the big ideas of algebra. One of those big ideas is functions. This article gives three examples of functions that are found in Arches National…
dos Santos Siqueira, Anderson; Biazoli Junior, Claudinei Eduardo; Comfort, William Edgar; Rohde, Luis Augusto; Sato, João Ricardo
2014-01-01
The framework of graph theory provides useful tools for investigating the neural substrates of neuropsychiatric disorders. Graph description measures may be useful as predictor variables in classification procedures. Here, we consider several centrality measures as predictor features in a classification algorithm to identify nodes of resting-state networks containing predictive information that can discriminate between typical developing children and patients with attention-deficit/hyperactivity disorder (ADHD). The prediction was based on a support vector machines classifier. The analyses were performed in a multisite and publicly available resting-state fMRI dataset of healthy children and ADHD patients: the ADHD-200 database. Network centrality measures contained little predictive information for the discrimination between ADHD patients and healthy subjects. However, the classification between inattentive and combined ADHD subtypes was more promising, achieving accuracies higher than 65% (balance between sensitivity and specificity) in some sites. Finally, brain regions were ranked according to the amount of discriminant information and the most relevant were mapped. As hypothesized, we found that brain regions in motor, frontoparietal, and default mode networks contained the most predictive information. We concluded that the functional connectivity estimations are strongly dependent on the sample characteristics. Thus different acquisition protocols and clinical heterogeneity decrease the predictive values of the graph descriptors. PMID:25309910
Permutation centralizer algebras and multimatrix invariants
NASA Astrophysics Data System (ADS)
Mattioli, Paolo; Ramgoolam, Sanjaye
2016-03-01
We introduce a class of permutation centralizer algebras which underly the combinatorics of multimatrix gauge-invariant observables. One family of such noncommutative algebras is parametrized by two integers. Its Wedderburn-Artin decomposition explains the counting of restricted Schur operators, which were introduced in the physics literature to describe open strings attached to giant gravitons and were subsequently used to diagonalize the Gaussian inner product for gauge invariants of two-matrix models. The structure of the algebra, notably its dimension, its center and its maximally commuting subalgebra, is related to Littlewood-Richardson numbers for composing Young diagrams. It gives a precise characterization of the minimal set of charges needed to distinguish arbitrary matrix gauge invariants, which are related to enhanced symmetries in gauge theory. The algebra also gives a star product for matrix invariants. The center of the algebra allows efficient computation of a sector of multimatrix correlators. These generate the counting of a certain class of bicoloured ribbon graphs with arbitrary genus.
NASA Astrophysics Data System (ADS)
Chen, Luwan; Han, Ling; Ning, Xiaohong
2015-12-01
An auto new segmentation approach based on graph theory which named self-adaptive mean-shift for high-resolution remote sensing images was proposed in this paper. This approach could overcome some defects that classic Mean-Shift must determine the fixed bandwidth through trial many times, and could effectively distinguish the difference between different features in the texture rich region. Segmentation experiments were processed with WorldView satellite image. The results show that the presented method is adaptive, and its speed and precision can satisfy application, so it is a robust automatic segmentation algorithm.
Kreimer, Dirk . E-mail: kreimer@ihes.fr
2006-12-15
We exhibit the role of Hochschild cohomology in quantum field theory with particular emphasis on gauge theory and Dyson-Schwinger equations, the quantum equations of motion. These equations emerge from Hopf- and Lie algebra theory and free quantum field theory only. In the course of our analysis, we exhibit an intimate relation between the Slavnov-Taylor identities for the couplings and the existence of Hopf sub-algebras defined on the sum of all graphs at a given loop order, surpassing the need to work on single diagrams.
ERIC Educational Resources Information Center
Bair, Sherry L.; Rich, Beverly S.
2011-01-01
This article characterizes the development of a deep and connected body of mathematical knowledge categorized by Ball and Bass' (2003b) model of Mathematical Knowledge for Teaching (MKT), as Specialized Content Knowledge for Teaching (SCK) in algebraic reasoning and number sense. The research employed multiple cases across three years from two…
An Application of Cartesian Graphing to Seismic Exploration.
ERIC Educational Resources Information Center
Robertson, Douglas Frederick
1992-01-01
Describes how college students enrolled in a course in elementary algebra apply graphing and algebra to data collected from a seismic profile to uncover the structure of a subterranean rock formation. Includes steps guiding the activity. (MDH)
Replica theory for learning curves for Gaussian processes on random graphs
NASA Astrophysics Data System (ADS)
Urry, M. J.; Sollich, P.
2012-10-01
We use a statistical physics approach to derive accurate predictions for the challenging problem of predicting the performance of Gaussian process regression. Performance is quantified by the learning curve, defined as the average error versus number of training examples. We assume the Gaussian process prior is defined by a random walk kernel, inputs are vertices on a random graph and the outputs are noisy function values. We show that replica techniques can be used to obtain exact performance predictions in the limit of large graphs, after first rewriting the average error in terms of a graphical model. Conventionally, the Gaussian process kernel is only globally normalized, so that the prior variance can differ between vertices. As a more principled alternative we also consider local normalization, where the prior variance is uniform. The normalization constants for the prior then have to be defined as thermal averages in an unnormalized model and this requires the introduction of a second, auxiliary set of replicas. Our results for both types of kernel normalization apply generically to all random graph ensembles constrained by a fixed but arbitrary degree distribution. We compare with numerically simulated learning curves and find excellent agreement, a significant improvement over existing approximations.
Box graphs and resolutions II: From Coulomb phases to fiber faces
NASA Astrophysics Data System (ADS)
Braun, Andreas P.; Schäfer-Nameki, Sakura
2016-04-01
Box graphs, or equivalently Coulomb phases of three-dimensional N = 2 supersymmetric gauge theories with matter, give a succinct, comprehensive and elegant characterization of crepant resolutions of singular elliptically fibered varieties. Furthermore, the box graphs predict that the phases are organized in terms of a network of flop transitions. The geometric construction of the resolutions associated to the phases is, however, a difficult problem. Here, we identify a correspondence between box graphs for the gauge algebras su (2 k + 1) with resolutions obtained using toric tops and generalizations thereof. Moreover, flop transitions between different such resolutions agree with those predicted by the box graphs. Our results thereby provide explicit realizations of the box graph resolutions.
Tracing retinal blood vessels by matrix-forest theorem of directed graphs.
Cheng, Li; De, Jaydeep; Zhang, Xiaowei; Lin, Feng; Li, Huiqi
2014-01-01
This paper aims to trace retinal blood vessel trees in fundus images. This task is far from being trivial as the crossover of vessels are commonly encountered in image-based vessel networks. Meanwhile it is often crucial to separate the vessel tree structures in applications such as diabetic retinopathy analysis. In this work, a novel directed graph based approach is proposed to cast the task as label propagation over directed graphs, such that the graph is to be partitioned into disjoint sub-graphs, or equivalently, each of the vessel trees is traced and separated from the rest of the vessel network. Then the tracing problem is addressed by making novel usage of the matrix-forest theorem in algebraic graph theory. Empirical experiments on synthetic as well as publicly available fundus image datasets demonstrate the applicability of our approach. PMID:25333171
Perfect quantum state transfer of hard-core bosons on weighted path graphs
NASA Astrophysics Data System (ADS)
Large, Steven J.; Underwood, Michael S.; Feder, David L.
2015-03-01
The ability to accurately transfer quantum information through networks is an important primitive in distributed quantum systems. While perfect quantum state transfer (PST) can be effected by a single particle undergoing continuous-time quantum walks on a variety of graphs, it is not known if PST persists for many particles in the presence of interactions. We show that if single-particle PST occurs on one-dimensional weighted path graphs, then systems of hard-core bosons undergoing quantum walks on these paths also undergo PST. The analysis extends the Tonks-Girardeau ansatz to weighted graphs using techniques in algebraic graph theory. The results suggest that hard-core bosons do not generically undergo PST, even on graphs which exhibit single-particle PST.
Toppi, J; Ciaramidaro, A; Vogel, P; Mattia, D; Babiloni, F; Siniatchkin, M; Astolfi, L
2015-08-01
Hyperscanning consists in the simultaneous recording of hemodynamic or neuroelectrical signals from two or more subjects acting in a social context. Well-established methodologies for connectivity estimation have already been adapted to hyperscanning purposes. The extension of graph theory approach to multi-subjects case is still a challenging issue. In the present work we aim to test the ability of the currently used graph theory global indices in describing the properties of a network given by two interacting subjects. The testing was conducted first on surrogate brain-to-brain networks reproducing typical social scenarios and then on real EEG hyperscanning data recorded during a Joint Action task. The results of the simulation study highlighted the ability of all the investigated indexes in modulating their values according to the level of interaction between subjects. However, only global efficiency and path length indexes demonstrated to be sensitive to an asymmetry in the communication between the two subjects. Such results were, then, confirmed by the application on real EEG data. Global efficiency modulated, in fact, their values according to the inter-brain density, assuming higher values in the social condition with respect to the non-social condition. PMID:26736730
Cluster Consensus of Nonlinearly Coupled Multi-Agent Systems in Directed Graphs
NASA Astrophysics Data System (ADS)
Lu, Xiao-Qing; Francis, Austin; Chen, Shi-Hua
2010-05-01
We investigate the cluster consensus problem in directed networks of nonlinearly coupled multi-agent systems by using pinning control. Depending on the community structure generated by the group partition of the underlying digraph, various clusters can be made coherently independent by applying feedback injections to a fraction of the agents. Sufficient conditions for cluster consensus are obtained using algebraic graph theory and matrix theory and some simulations results are included to illustrate the method.
Pseudorational Impulse Responses — Algebraic System Theory for Distributed Parameter Systems
NASA Astrophysics Data System (ADS)
Yamamoto, Yutaka
This paper gives a comprehensive account on a class of distributed parameter systems, whose impulse response is called pseudorational. This notion was introduced by the author in 1980's, and is particularly amenable for the study of systems with bounded-time memory. We emphasize algebraic structures induced by this class of systems. Some recent results on coprimeness issues and H∞ control are discussed and illustrated.
Teaching Algebra without Algebra
ERIC Educational Resources Information Center
Kalman, Richard S.
2008-01-01
Algebra is, among other things, a shorthand way to express quantitative reasoning. This article illustrates ways for the classroom teacher to convert algebraic solutions to verbal problems into conversational solutions that can be understood by students in the lower grades. Three reasonably typical verbal problems that either appeared as or…
Handling context-sensitivity in protein structures using graph theory: bona fide prediction.
Samudrala, R; Moult, J
1997-01-01
We constructed five comparative models in a blind manner for the second meeting on the Critical Assessment of protein Structure Prediction methods (CASP2). The method used is based on a novel graph-theoretic clique-finding approach, and attempts to address the problem of interconnected structural changes in the comparative modeling of protein structures. We discuss briefly how the method is used for protein structure prediction, and detail how it performs in the blind tests. We find that compared to CASP1, significant improvements in building insertions and deletions and sidechain conformations have been achieved. PMID:9485494