Science.gov

Sample records for local graph invariants

  1. Scale-invariant geometric random graphs

    NASA Astrophysics Data System (ADS)

    Xie, Zheng; Rogers, Tim

    2016-03-01

    We introduce and analyze a class of growing geometric random graphs that are invariant under rescaling of space and time. Directed connections between nodes are drawn according to influence zones that depend on node position in space and time, mimicking the heterogeneity and increased specialization found in growing networks. Through calculations and numerical simulations we explore the consequences of scale invariance for geometric random graphs generated this way. Our analysis reveals a dichotomy between scale-free and Poisson distributions of in- and out-degree, the existence of a random number of hub nodes, high clustering, and unusual percolation behavior. These properties are similar to those of empirically observed web graphs.

  2. The uniqueness of DMAX-matrix graph invariants.

    PubMed

    Dehmer, Matthias; Shi, Yongtang

    2014-01-01

    In this paper, we examine the uniqueness (discrimination power) of a newly proposed graph invariant based on the matrix DMAX defined by Randić et al. In order to do so, we use exhaustively generated graphs instead of special graph classes such as trees only. Using these graph classes allow us to generalize the findings towards complex networks as they usually do not possess any structural constraints. We obtain that the uniqueness of this newly proposed graph invariant is approximately as low as the uniqueness of the Balaban J index on exhaustively generated (general) graphs. PMID:24392099

  3. Invariant feature extraction for color image mosaic by graph card processing

    NASA Astrophysics Data System (ADS)

    Liu, Jin; Chen, Lin; Li, Deren

    2009-10-01

    Image mosaic can be widely used in remote measuring, scout in battlefield and Panasonic image demonstration. In this project, we find a general method for video (or sequence images) mosaic by techniques, such as extracting invariant features, gpu processing, multi-color feature selection, ransac algorithm for homograph matching. In order to match the image sequence automatically without influence of rotation, scale and contrast transform, local invariant feature descriptor have been extracted by graph card unit. The gpu mosaic algorithm performs very well that can be compare to slow CPU version of mosaic program with little cost time.

  4. Invariants of the local Clifford group

    SciTech Connect

    Nest, Maarten van den; Dehaene, Jeroen; Moor, Bart de

    2005-02-01

    We study the algebra of complex polynomials which remain invariant under the action of the local Clifford group under conjugation. Within this algebra, we consider the linear spaces of homogeneous polynomials degree by degree and construct bases for these vector spaces for each degree, thereby obtaining a generating set of polynomial invariants. Our approach is based on the description of Clifford operators in terms of linear operations over GF(2). Such a study of polynomial invariants of the local Clifford group is mainly of importance in quantum coding theory, in particular in the classification of binary quantum codes. Some applications in entanglement theory and quantum computing are briefly discussed as well.

  5. Local and gauge invariant observables in gravity

    NASA Astrophysics Data System (ADS)

    Khavkine, Igor

    2015-09-01

    It is well known that general relativity (GR) does not possess any non-trivial local (in a precise standard sense) and diffeomorphism invariant observable. We propose a generalized notion of local observables, which retain the most important properties that follow from the standard definition of locality, yet is flexible enough to admit a large class of diffeomorphism invariant observables in GR. The generalization comes at a small price—that the domain of definition of a generalized local observable may not cover the entire phase space of GR and two such observables may have distinct domains. However, the subset of metrics on which generalized local observables can be defined is in a sense generic (its open interior is non-empty in the Whitney strong topology). Moreover, generalized local gauge invariant observables are sufficient to separate diffeomorphism orbits on this admissible subset of the phase space. Connecting the construction with the notion of differential invariants gives a general scheme for defining generalized local gauge invariant observables in arbitrary gauge theories, which happens to agree with well-known results for Maxwell and Yang-Mills theories.

  6. Testing local Lorentz invariance with gravitational waves

    NASA Astrophysics Data System (ADS)

    Kostelecký, V. Alan; Mewes, Matthew

    2016-06-01

    The effects of local Lorentz violation on dispersion and birefringence of gravitational waves are investigated. The covariant dispersion relation for gravitational waves involving gauge-invariant Lorentz-violating operators of arbitrary mass dimension is constructed. The chirp signal from the gravitational-wave event GW150914 is used to place numerous first constraints on gravitational Lorentz violation.

  7. New invariants of weighted graphs for calculating the critical properties of freons

    NASA Astrophysics Data System (ADS)

    Kruglyak, Yu. A.; Peredunova, I. V.

    2015-12-01

    A new approach to structure-property problems using new invariants of fully weighted graphs to provide a quantitative description of the critical properties of freons is proposed. A general principle for constructing topological invariants of fully weighted graphs for structure-property correlations is formulated. Two new invariants are proposed and used to calculate critical properties of freons of the methane, ethane, and propane series. It is shown that unlike all other known incremental methods, the proposed approach does not require the use of experimental data or calibrations to calculate critical properties. It ensures a statistically reliable linear dependence of all critical properties of freons on the value of the matching index for our corresponding molecular graph. Over 2.5 thousand previously unknown values of the critical properties of lower freons are calculated.

  8. Local Unitary Invariant Spin-Squeezing in Multiqubit States

    NASA Astrophysics Data System (ADS)

    Divyamani, B. G.; Sudha; Usha Devi, A. R.

    2016-05-01

    We investiage Local Unitary Invariant Spin Squeezing (LUISS) in symmetric and non-symmetric multiqubit states. On developing an operational procedure to evaluate Local Unitary Invariant Spin Squeezing parameters, we explicitly evaluate these parameters for pure as well as mixed non-symmetric multiqubit states. We show that the existence of local unitary invariant version of Kitegawa-Ueda spin squeezing may not witness pairwise entanglement whereas the local unitary invariant analogue of Wineland spin squeezing necessarily implies pairwise entanglement.

  9. Geometric local invariants and pure three-qubit states

    NASA Astrophysics Data System (ADS)

    Williamson, Mark S.; Ericsson, Marie; Johansson, Markus; Sjöqvist, Erik; Sudbery, Anthony; Vedral, Vlatko; Wootters, William K.

    2011-06-01

    We explore a geometric approach to generating local SU(2) and SL(2,C) invariants for a collection of qubits inspired by lattice gauge theory. Each local invariant or “gauge” invariant is associated with a distinct closed path (or plaquette) joining some or all of the qubits. In lattice gauge theory, the lattice points are the discrete space-time points, the transformations between the points of the lattice are defined by parallel transporters, and the gauge invariant observable associated with a particular closed path is given by the Wilson loop. In our approach the points of the lattice are qubits, the link transformations between the qubits are defined by the correlations between them, and the gauge invariant observable, the local invariants associated with a particular closed path, are also given by a Wilson looplike construction. The link transformations share many of the properties of parallel transporters, although they are not undone when one retraces one’s steps through the lattice. This feature is used to generate many of the invariants. We consider a pure three-qubit state as a test case and find we can generate a complete set of algebraically independent local invariants in this way; however, the framework given here is applicable to generating local unitary invariants for mixed states composed of any number of d-level quantum systems. We give an operational interpretation of these invariants in terms of observables.

  10. Geometric local invariants and pure three-qubit states

    SciTech Connect

    Williamson, Mark S.; Ericsson, Marie; Johansson, Markus; Sjoeqvist, Erik; Sudbery, Anthony; Vedral, Vlatko; Wootters, William K.

    2011-06-15

    We explore a geometric approach to generating local SU(2) and SL(2,C) invariants for a collection of qubits inspired by lattice gauge theory. Each local invariant or ''gauge'' invariant is associated with a distinct closed path (or plaquette) joining some or all of the qubits. In lattice gauge theory, the lattice points are the discrete space-time points, the transformations between the points of the lattice are defined by parallel transporters, and the gauge invariant observable associated with a particular closed path is given by the Wilson loop. In our approach the points of the lattice are qubits, the link transformations between the qubits are defined by the correlations between them, and the gauge invariant observable, the local invariants associated with a particular closed path, are also given by a Wilson looplike construction. The link transformations share many of the properties of parallel transporters, although they are not undone when one retraces one's steps through the lattice. This feature is used to generate many of the invariants. We consider a pure three-qubit state as a test case and find we can generate a complete set of algebraically independent local invariants in this way; however, the framework given here is applicable to generating local unitary invariants for mixed states composed of any number of d-level quantum systems. We give an operational interpretation of these invariants in terms of observables.

  11. Percolation in invariant Poisson graphs with i.i.d. degrees

    NASA Astrophysics Data System (ADS)

    Deijfen, Maria; Häggström, Olle; Holroyd, Alexander E.

    2012-04-01

    Let each point of a homogeneous Poisson process in ℝ d independently be equipped with a random number of stubs (half-edges) according to a given probability distribution μ on the positive integers. We consider translation-invariant schemes for perfectly matching the stubs to obtain a simple graph with degree distribution μ. Leaving aside degenerate cases, we prove that for any μ there exist schemes that give only finite components as well as schemes that give infinite components. For a particular matching scheme which is a natural extension of Gale-Shapley stable marriage, we give sufficient conditions on μ for the absence and presence of infinite components.

  12. Coloring random graphs and maximizing local diversity.

    PubMed

    Bounkong, S; van Mourik, J; Saad, D

    2006-11-01

    We study a variation of the graph coloring problem on random graphs of finite average connectivity. Given the number of colors, we aim to maximize the number of different colors at neighboring vertices (i.e., one edge distance) of any vertex. Two efficient algorithms, belief propagation and Walksat, are adapted to carry out this task. We present experimental results based on two types of random graphs for different system sizes and identify the critical value of the connectivity for the algorithms to find a perfect solution. The problem and the suggested algorithms have practical relevance since various applications, such as distributed storage, can be mapped onto this problem. PMID:17280022

  13. Translationally invariant conservation laws of local Lindblad equations

    SciTech Connect

    Žnidarič, Marko; Benenti, Giuliano; Casati, Giulio

    2014-02-15

    We study the conditions under which one can conserve local translationally invariant operators by local translationally invariant Lindblad equations in one-dimensional rings of spin-1/2 particles. We prove that for any 1-local operator (e.g., particle density) there exist Lindblad dissipators that conserve that operator, while on the other hand we prove that among 2-local operators (e.g., energy density) only trivial ones of the Ising type can be conserved, while all the other cannot be conserved, neither locally nor globally, by any 2- or 3-local translationally invariant Lindblad equation. Our statements hold for rings of any finite length larger than some minimal length determined by the locality of Lindblad equation. These results show in particular that conservation of energy density in interacting systems is fundamentally more difficult than conservation of 1-local quantities.

  14. 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).

  15. A global/local affinity graph for image segmentation.

    PubMed

    Xiaofang Wang; Yuxing Tang; Masnou, Simon; Liming Chen

    2015-04-01

    Construction of a reliable graph capturing perceptual grouping cues of an image is fundamental for graph-cut based image segmentation methods. In this paper, we propose a novel sparse global/local affinity graph over superpixels of an input image to capture both short- and long-range grouping cues, and thereby enabling perceptual grouping laws, including proximity, similarity, continuity, and to enter in action through a suitable graph-cut algorithm. Moreover, we also evaluate three major visual features, namely, color, texture, and shape, for their effectiveness in perceptual segmentation and propose a simple graph fusion scheme to implement some recent findings from psychophysics, which suggest combining these visual features with different emphases for perceptual grouping. In particular, an input image is first oversegmented into superpixels at different scales. We postulate a gravitation law based on empirical observations and divide superpixels adaptively into small-, medium-, and large-sized sets. Global grouping is achieved using medium-sized superpixels through a sparse representation of superpixels' features by solving a ℓ0-minimization problem, and thereby enabling continuity or propagation of local smoothness over long-range connections. Small- and large-sized superpixels are then used to achieve local smoothness through an adjacent graph in a given feature space, and thus implementing perceptual laws, for example, similarity and proximity. Finally, a bipartite graph is also introduced to enable propagation of grouping cues between superpixels of different scales. Extensive experiments are carried out on the Berkeley segmentation database in comparison with several state-of-the-art graph constructions. The results show the effectiveness of the proposed approach, which outperforms state-of-the-art graphs using four different objective criteria, namely, the probabilistic rand index, the variation of information, the global consistency error, and the

  16. A novel eye localization method with rotation invariance.

    PubMed

    Ren, Yan; Wang, Shuang; Hou, Biao; Ma, Jingjing

    2014-01-01

    This paper presents a novel learning method for precise eye localization, a challenge to be solved in order to improve the performance of face processing algorithms. Few existing approaches can directly detect and localize eyes with arbitrary angels in predicted eye regions, face images, and original portraits at the same time. To preserve rotation invariant property throughout the entire eye localization framework, a codebook of invariant local features is proposed for the representation of eye patterns. A heat map is then generated by integrating a 2-class sparse representation classifier with a pyramid-like detecting and locating strategy to fulfill the task of discriminative classification and precise localization. Furthermore, a series of prior information is adopted to improve the localization precision and accuracy. Experimental results on three different databases show that our method is capable of effectively locating eyes in arbitrary rotation situations (360° in plane). PMID:24184729

  17. Completed Local Ternary Pattern for Rotation Invariant Texture Classification

    PubMed Central

    Rassem, Taha H.

    2014-01-01

    Despite the fact that the two texture descriptors, the completed modeling of Local Binary Pattern (CLBP) and the Completed Local Binary Count (CLBC), have achieved a remarkable accuracy for invariant rotation texture classification, they inherit some Local Binary Pattern (LBP) drawbacks. The LBP is sensitive to noise, and different patterns of LBP may be classified into the same class that reduces its discriminating property. Although, the Local Ternary Pattern (LTP) is proposed to be more robust to noise than LBP, however, the latter's weakness may appear with the LTP as well as with LBP. In this paper, a novel completed modeling of the Local Ternary Pattern (LTP) operator is proposed to overcome both LBP drawbacks, and an associated completed Local Ternary Pattern (CLTP) scheme is developed for rotation invariant texture classification. The experimental results using four different texture databases show that the proposed CLTP achieved an impressive classification accuracy as compared to the CLBP and CLBC descriptors. PMID:24977193

  18. Analysis of Graph Invariants in Functional Neocortical Circuitry Reveals Generalized Features Common to Three Areas of Sensory Cortex

    PubMed Central

    Gururangan, Suchin S.; Sadovsky, Alexander J.; MacLean, Jason N.

    2014-01-01

    Correlations in local neocortical spiking activity can provide insight into the underlying organization of cortical microcircuitry. However, identifying structure in patterned multi-neuronal spiking remains a daunting task due to the high dimensionality of the activity. Using two-photon imaging, we monitored spontaneous circuit dynamics in large, densely sampled neuronal populations within slices of mouse primary auditory, somatosensory, and visual cortex. Using the lagged correlation of spiking activity between neurons, we generated functional wiring diagrams to gain insight into the underlying neocortical circuitry. By establishing the presence of graph invariants, which are label-independent characteristics common to all circuit topologies, our study revealed organizational features that generalized across functionally distinct cortical regions. Regardless of sensory area, random and -nearest neighbors null graphs failed to capture the structure of experimentally derived functional circuitry. These null models indicated that despite a bias in the data towards spatially proximal functional connections, functional circuit structure is best described by non-random and occasionally distal connections. Eigenvector centrality, which quantifies the importance of a neuron in the temporal flow of circuit activity, was highly related to feedforwardness in all functional circuits. The number of nodes participating in a functional circuit did not scale with the number of neurons imaged regardless of sensory area, indicating that circuit size is not tied to the sampling of neocortex. Local circuit flow comprehensively covered angular space regardless of the spatial scale that we tested, demonstrating that circuitry itself does not bias activity flow toward pia. Finally, analysis revealed that a minimal numerical sample size of neurons was necessary to capture at least 90 percent of functional circuit topology. These data and analyses indicated that functional circuitry

  19. Efficient and Accurate Indoor Localization Using Landmark Graphs

    NASA Astrophysics Data System (ADS)

    Gu, F.; Kealy, A.; Khoshelham, K.; Shang, J.

    2016-06-01

    Indoor localization is important for a variety of applications such as location-based services, mobile social networks, and emergency response. Fusing spatial information is an effective way to achieve accurate indoor localization with little or with no need for extra hardware. However, existing indoor localization methods that make use of spatial information are either too computationally expensive or too sensitive to the completeness of landmark detection. In this paper, we solve this problem by using the proposed landmark graph. The landmark graph is a directed graph where nodes are landmarks (e.g., doors, staircases, and turns) and edges are accessible paths with heading information. We compared the proposed method with two common Dead Reckoning (DR)-based methods (namely, Compass + Accelerometer + Landmarks and Gyroscope + Accelerometer + Landmarks) by a series of experiments. Experimental results show that the proposed method can achieve 73% accuracy with a positioning error less than 2.5 meters, which outperforms the other two DR-based methods.

  20. The Critical Z-Invariant Ising Model via Dimers: Locality Property

    NASA Astrophysics Data System (ADS)

    Boutillier, Cédric; de Tilière, Béatrice

    2011-01-01

    We study a large class of critical two-dimensional Ising models, namely critical Z-invariant Ising models. Fisher (J Math Phys 7:1776-1781, 1966) introduced a correspondence between the Ising model and the dimer model on a decorated graph, thus setting dimer techniques as a powerful tool for understanding the Ising model. In this paper, we give a full description of the dimer model corresponding to the critical Z-invariant Ising model, consisting of explicit expressions which only depend on the local geometry of the underlying isoradial graph. Our main result is an explicit local formula for the inverse Kasteleyn matrix, in the spirit of Kenyon (Invent Math 150(2):409-439, 2002), as a contour integral of the discrete exponential function of Mercat (Discrete period matrices and related topics, 2002) and Kenyon (Invent Math 150(2):409-439, 2002) multiplied by a local function. Using results of Boutillier and de Tilière (Prob Theor Rel Fields 147(3-4):379-413, 2010) and techniques of de Tilière (Prob Th Rel Fields 137(3-4):487-518, 2007) and Kenyon (Invent Math 150(2):409-439, 2002), this yields an explicit local formula for a natural Gibbs measure, and a local formula for the free energy. As a corollary, we recover Baxter's formula for the free energy of the critical Z-invariant Ising model (Baxter, in Exactly solved models in statistical mechanics, Academic Press, London, 1982), and thus a new proof of it. The latter is equal, up to a constant, to the logarithm of the normalized determinant of the Laplacian obtained in Kenyon (Invent Math 150(2):409-439, 2002).

  1. Structural information content of networks: graph entropy based on local vertex functionals.

    PubMed

    Dehmer, Matthias; Emmert-Streib, Frank

    2008-04-01

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

  2. Invariant currents and scattering off locally symmetric potential landscapes

    NASA Astrophysics Data System (ADS)

    Kalozoumis, P. A.; Morfonios, C. V.; Diakonos, F. K.; Schmelcher, P.

    2015-11-01

    We study the effect of discrete symmetry breaking in inhomogeneous scattering media within the framework of generic wave propagation. Our focus is on one-dimensional scattering potentials exhibiting local symmetries. We find a class of spatially invariant nonlocal currents, emerging when the corresponding generalized potential exhibits symmetries in arbitrary spatial domains. These invariants characterize the wave propagation and provide a spatial mapping of the wave function between any symmetry related domains. This generalizes the Bloch and parity theorems for broken reflection and translational symmetries, respectively. Their nonvanishing values indicate the symmetry breaking, whereas a zero value denotes the restoration of the global symmetry where the well-known forms of the two theorems are recovered. These invariants allow for a systematic treatment of systems with any local symmetry combination, providing a tool for the investigation of the scattering properties of aperiodic but locally symmetric systems. To this aim we express the transfer matrix of a locally symmetric potential unit via the corresponding invariants and derive quantities characterizing the complete scattering device which serve as key elements for the investigation of transmission spectra and particularly of perfect transmission resonances.

  3. Invariant current approach to wave propagation in locally symmetric structures

    NASA Astrophysics Data System (ADS)

    Zampetakis, V. E.; Diakonou, M. K.; Morfonios, C. V.; Kalozoumis, P. A.; Diakonos, F. K.; Schmelcher, P.

    2016-05-01

    A theory for wave mechanical systems with local inversion and translation symmetries is developed employing the two-dimensional solution space of the stationary Schrödinger equation. The local symmetries of the potential are encoded into corresponding local basis vectors in terms of symmetry-induced two-point invariant currents which map the basis amplitudes between symmetry-related points. A universal wavefunction structure in locally symmetric potentials is revealed, independently of the physical boundary conditions, by using special local bases which are adapted to the existing local symmetries. The local symmetry bases enable efficient computation of spatially resolved wave amplitudes in systems with arbitrary combinations of local inversion and translation symmetries. The approach opens the perspective of a flexible analysis and control of wave localization in structurally complex systems.

  4. Approximate locality for quantum systems on graphs.

    PubMed

    Osborne, Tobias J

    2008-10-01

    In this Letter we make progress on a long-standing open problem of Aaronson and Ambainis [Theory Comput. 1, 47 (2005)]: we show that if U is a sparse unitary operator with a gap Delta in its spectrum, then there exists an approximate logarithm H of U which is also sparse. The sparsity pattern of H gets more dense as 1/Delta increases. This result can be interpreted as a way to convert between local continuous-time and local discrete-time quantum processes. As an example we show that the discrete-time coined quantum walk can be realized stroboscopically from an approximately local continuous-time quantum walk. PMID:18851512

  5. Invariant currents in lossy acoustic waveguides with complete local symmetry

    NASA Astrophysics Data System (ADS)

    Kalozoumis, P. A.; Richoux, O.; Diakonos, F. K.; Theocharis, G.; Schmelcher, P.

    2015-07-01

    We implement the concept of complete local symmetry in lossy acoustic waveguides. Despite the presence of losses, the existence of a spatially invariant current is shown theoretically and observed experimentally. We demonstrate how this invariant current leads to the generalization of the Bloch and parity theorems for lossy systems defining a mapping of the pressure field between symmetry-related spatial domains. Using experimental data, we verify this mapping with remarkable accuracy. For the performed experiment, we employ a construction technique based on local symmetries that allows the design of setups with prescribed perfect transmission resonances in the lossless case. Our results reveal the fundamental role of symmetries in restricted spatial domains, and they clearly indicate that completely locally symmetric devices constitute a promising class of setups with regard to the manipulation of wave propagation.

  6. An Invariant of Topologically Ordered States Under Local Unitary Transformations

    NASA Astrophysics Data System (ADS)

    Haah, Jeongwan

    2016-03-01

    For an anyon model in two spatial dimensions described by a modular tensor category, the topological S-matrix encodes the mutual braiding statistics, the quantum dimensions, and the fusion rules of anyons. It is nontrivial whether one can compute the S-matrix from a single ground state wave function. Here, we define a class of Hamiltonians consisting of local commuting projectors and an associated matrix that is invariant under local unitary transformations. We argue that the invariant is equivalent to the topological S-matrix. The definition does not require degeneracy of the ground state. We prove that the invariant depends on the state only, in the sense that it can be computed by any Hamiltonian in the class of which the state is a ground state. As a corollary, we prove that any local quantum circuit that connects two ground states of quantum double models (discrete gauge theories) with non-isomorphic abelian groups must have depth that is at least linear in the system's diameter. As a tool for the proof, a manifestly Hamiltonian-independent notion of locally invisible operators is introduced. This gives a sufficient condition for a many-body state not to be generated from a product state by any small depth quantum circuit; this is a many-body entanglement witness.

  7. Interaction graph mining for protein complexes using local clique merging.

    PubMed

    Li, Xiao-Li; Tan, Soon-Heng; Foo, Chuan-Sheng; Ng, See-Kiong

    2005-01-01

    While recent technological advances have made available large datasets of experimentally-detected pairwise protein-protein interactions, there is still a lack of experimentally-determined protein complex data. To make up for this lack of protein complex data, we explore the mining of existing protein interaction graphs for protein complexes. This paper proposes a novel graph mining algorithm to detect the dense neighborhoods (highly connected regions) in an interaction graph which may correspond to protein complexes. Our algorithm first locates local cliques for each graph vertex (protein) and then merge the detected local cliques according to their affinity to form maximal dense regions. We present experimental results with yeast protein interaction data to demonstrate the effectiveness of our proposed method. Compared with other existing techniques, our predicted complexes can match or overlap significantly better with the known protein complexes in the MIPS benchmark database. Novel protein complexes were also predicted to help biologists in their search for new protein complexes. PMID:16901108

  8. Derivatives in discrete mathematics: a novel graph-theoretical invariant for generating new 2/3D molecular descriptors. I. Theory and QSPR application.

    PubMed

    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

  9. Graph rigidity and localization of multi-robot formations.

    PubMed

    Zhang, Fan

    2004-05-01

    This paper provides theoretical foundation for the problem of localization in multi-robot formations. Sufficient and necessary conditions for completely localizing a formation of mobile robots/vehicles in SE(2) based on distributed sensor networks and graph rigidity are proposed. A method for estimating the quality of localizations via a linearized weighted least-squares algorithm is presented, which considers incomplete and noisy sensory information. The approach in this paper had been implemented in a multi-robot system of five car-like robots equipped with omni-directional cameras and IEEE 802.11b wireless network. PMID:15083542

  10. Visual odometry based on structural matching of local invariant features using stereo camera sensor.

    PubMed

    Núñez, Pedro; Vázquez-Martín, Ricardo; Bandera, Antonio

    2011-01-01

    This paper describes a novel sensor system to estimate the motion of a stereo camera. Local invariant image features are matched between pairs of frames and linked into image trajectories at video rate, providing the so-called visual odometry, i.e., motion estimates from visual input alone. Our proposal conducts two matching sessions: the first one between sets of features associated to the images of the stereo pairs and the second one between sets of features associated to consecutive frames. With respect to previously proposed approaches, the main novelty of this proposal is that both matching algorithms are conducted by means of a fast matching algorithm which combines absolute and relative feature constraints. Finding the largest-valued set of mutually consistent matches is equivalent to finding the maximum-weighted clique on a graph. The stereo matching allows to represent the scene view as a graph which emerge from the features of the accepted clique. On the other hand, the frame-to-frame matching defines a graph whose vertices are features in 3D space. The efficiency of the approach is increased by minimizing the geometric and algebraic errors to estimate the final displacement of the stereo camera between consecutive acquired frames. The proposed approach has been tested for mobile robotics navigation purposes in real environments and using different features. Experimental results demonstrate the performance of the proposal, which could be applied in both industrial and service robot fields. PMID:22164016

  11. Visual Odometry Based on Structural Matching of Local Invariant Features Using Stereo Camera Sensor

    PubMed Central

    Núñez, Pedro; Vázquez-Martín, Ricardo; Bandera, Antonio

    2011-01-01

    This paper describes a novel sensor system to estimate the motion of a stereo camera. Local invariant image features are matched between pairs of frames and linked into image trajectories at video rate, providing the so-called visual odometry, i.e., motion estimates from visual input alone. Our proposal conducts two matching sessions: the first one between sets of features associated to the images of the stereo pairs and the second one between sets of features associated to consecutive frames. With respect to previously proposed approaches, the main novelty of this proposal is that both matching algorithms are conducted by means of a fast matching algorithm which combines absolute and relative feature constraints. Finding the largest-valued set of mutually consistent matches is equivalent to finding the maximum-weighted clique on a graph. The stereo matching allows to represent the scene view as a graph which emerge from the features of the accepted clique. On the other hand, the frame-to-frame matching defines a graph whose vertices are features in 3D space. The efficiency of the approach is increased by minimizing the geometric and algebraic errors to estimate the final displacement of the stereo camera between consecutive acquired frames. The proposed approach has been tested for mobile robotics navigation purposes in real environments and using different features. Experimental results demonstrate the performance of the proposal, which could be applied in both industrial and service robot fields. PMID:22164016

  12. Image retrieval based on local grey-level invariants

    NASA Astrophysics Data System (ADS)

    Bordeaux, Eva; Shrikhande, Neelima

    2005-10-01

    During past decades, the enormous growth of image archives has significantly increased the demand for research efforts aimed at efficiently finding specific images within large databases. This paper investigates matching of images of buildings, architectural designs, blueprints and sketches. Their geometrical constrains lead to the proposed approach: the use of local grey-level invariants based on internal contours of the object. The problem involves three key phases: object recognition in image data, matching two images and searching the database of images. The emphasis of this paper is on object recognition based on internal contours of image data. In her master's thesis, M.M. Kulkarni described a technique for image retrieval by contour analysis implemented on external contours of an object in an image data. This is used to define the category of a building (tower, dome, flat, etc). Integration of these results with local grey-level invariant analysis creates a more robust image retrieval system. Thus, the best match result is the intersection of the results of contour analysis and grey-level invariants analysis. Experiments conducted for the database of architectural buildings have shown robustness w.r.t. to image rotation, translation, small view-point variations, partial visibility and extraneous features. The recognition rate is above 99% for a variety of tested images taken under different conditions.

  13. MEG source localization using invariance of noise space.

    PubMed

    Zhang, Junpeng; Raij, Tommi; Hämäläinen, Matti; Yao, Dezhong

    2013-01-01

    We propose INvariance of Noise (INN) space as a novel method for source localization of magnetoencephalography (MEG) data. The method is based on the fact that modulations of source strengths across time change the energy in signal subspace but leave the noise subspace invariant. We compare INN with classical MUSIC, RAP-MUSIC, and beamformer approaches using simulated data while varying signal-to-noise ratios as well as distance and temporal correlation between two sources. We also demonstrate the utility of INN with actual auditory evoked MEG responses in eight subjects. In all cases, INN performed well, especially when the sources were closely spaced, highly correlated, or one source was considerably stronger than the other. PMID:23505502

  14. Local unitary invariants for N-qubit pure states

    SciTech Connect

    Sharma, S. Shelly; Sharma, N. K.

    2010-11-15

    The concept of negativity font, a basic unit of multipartite entanglement, is introduced. Transformation properties of determinants of negativity fonts under local unitary (LU) transformations are exploited to obtain relevant N-qubit polynomial invariants and construct entanglement monotones from first principles. It is shown that entanglement monotones that detect the entanglement of specific parts of the composite system may be constructed to distinguish between states with distinct types of entanglement. The structural difference between entanglement monotones for an odd and even number of qubits is brought out.

  15. f(T) gravity and local Lorentz invariance

    SciTech Connect

    Li Baojiu; Sotiriou, Thomas P.; Barrow, John D.

    2011-03-15

    We show that in theories of generalized teleparallel gravity, whose Lagrangians are algebraic functions of the usual teleparallel Lagrangian, the action and the field equations are not invariant under local Lorentz transformations. We also argue that these theories appear to have extra degrees of freedom with respect to general relativity. The usual teleparallel Lagrangian, which has been extensively studied and leads to a theory dynamically equivalent to general relativity, is an exception. Both of these facts appear to have been overlooked in the recent literature on f(T) gravity, but are crucial for assessing the viability of these theories as alternative explanations for the acceleration of the Universe.

  16. Efficient algorithm to recognize the local Clifford equivalence of graph states

    SciTech Connect

    Nest, Maarten van den; Dehaene, Jeroen; Moor, Bart de

    2004-09-01

    In Van den Nest et al. [Phys. Rev. A 69, 022316 (2004)] we presented a description of the action of local Clifford operations on graph states in terms of a graph transformation rule, known in graph theory as local complementation. It was shown that two graph states are equivalent under the local Clifford group if and only if there exists a sequence of local complementations which relates their associated graphs. In this Brief Report we report the existence of a polynomial time algorithm, published in A. Bouchet [Combinatorica 11, 315 (1991)], which decides whether two given graphs are related by a sequence of local complementations. Hence an efficient algorithm to detect local Clifford equivalence of graph states is obtained.

  17. Reflection symmetry detection using locally affine invariant edge correspondence.

    PubMed

    Wang, Zhaozhong; Tang, Zesheng; Zhang, Xiao

    2015-04-01

    Reflection symmetry detection receives increasing attentions in recent years. The state-of-the-art algorithms mainly use the matching of intensity-based features (such as the SIFT) within a single image to find symmetry axes. This paper proposes a novel approach by establishing the correspondence of locally affine invariant edge-based features, which are superior to the intensity based in the aspects that it is insensitive to illumination variations, and applicable to textureless objects. The locally affine invariance is achieved by simple linear algebra for efficient and robust computations, making the algorithm suitable for detections under object distortions like perspective projection. Commonly used edge detectors and a voting process are, respectively, used before and after the edge description and matching steps to form a complete reflection detection pipeline. Experiments are performed using synthetic and real-world images with both multiple and single reflection symmetry axis. The test results are compared with existing algorithms to validate the proposed method. PMID:25608306

  18. Fermions in gravity with local spin-base invariance

    NASA Astrophysics Data System (ADS)

    Gies, Holger; Lippoldt, Stefan

    2014-03-01

    We study a formulation of Dirac fermions in curved spacetime that respects general coordinate invariance as well as invariance under local spin-base transformations. The natural variables for this formulation are spacetime-dependent Dirac matrices subject to the Clifford-algebra constraint. In particular, a coframe, i.e. vierbein field is not required. The corresponding affine spin connection consists of a canonical part that is completely fixed in terms of the Dirac matrices and a free part that can be interpreted as spin torsion. A general variation of the Dirac matrices naturally induces a spinorial Lie derivative which coincides with the known Kosmann-Lie derivative in the absence of torsion. Using this formulation for building a field theory of quantized gravity and matter fields, we show that it suffices to quantize the metric and the matter fields. This observation is of particular relevance for field theory approaches to quantum gravity, as it can serve for a purely metric-based quantization scheme for gravity even in the presence of fermions.

  19. Local graph regularized coding for salient object detection

    NASA Astrophysics Data System (ADS)

    Huo, Lina; Yang, Shuyuan; Jiao, Licheng; Wang, Shuang; Shi, Jiao

    2016-07-01

    Subspace segmentation based salient object detection has received increasing interests in recent years. To preserve the locality and similarity of regions, a grouping effect of representation is introduced to segment the salient object and background in subspace. Then a new saliency map is calculated by incorporating this local graph regularizer into coding, which explicitly explores the data self-representation model and thus locate more accurate salient regions. Moreover, a heuristic object-based dictionary from background superpixels is obtained in border set removing the image regions within the potential object regions. Experimental results on four large benchmark databases demonstrate that the proposed method performs favorably against eight recent state-of-the-art methods in terms of three evaluation criterions, with a reduction of MAE by 19.8% than GR and 29.3% than CB in the two SED datasets, respectively. Meanwhile, our method also runs faster than the comparative detection approaches.

  20. Parameterized locally invariant manifolds: A tool for multiscale modeling

    NASA Astrophysics Data System (ADS)

    Sawant, Aarti

    In this thesis two methods for coarse graining in nonlinear ODE systems are demonstrated through analysis of model problems. The basic ideas of a method for model reduction and a method for non-asymptotic time-averaging are presented, using the idea of the Parameterized locally invariant manifolds. New approximation techniques for carrying out this methodology are developed. The work is divided in four categories based on the type of coarse-graining used: reduction of degrees of freedom, spatial averaging, time averaging and a combination of space and time averaging. Model problems showing complex dynamics are selected and various features of the PLIM method are elaborated. The quality and efficiency of the different coarse-graining approaches are evaluated. From the computational standpoint, it is shown that the method has the potential of serving as a subgrid modeling tool for problems in engineering. The developed ideas are evaluated on the following model problems: Lorenz System, a 4D Hamiltonian System due to Hald, 1D Elastodynamics in a strongly heterogeneous medium, kinetics of a phase transforming material with wiggly energy due to Abeyaratne, Chu and James, 2D gradient system with wiggly energy due to Menon, and macroscopic stress-strain behavior of an atomic chain based on the Frenkel-Kontorova model.

  1. Local invariants vanishing on stationary horizons: a diagnostic for locating black holes.

    PubMed

    Page, Don N; Shoom, Andrey A

    2015-04-10

    Inspired by the example of Abdelqader and Lake for the Kerr metric, we construct local scalar polynomial curvature invariants that vanish on the horizon of any stationary black hole: the squared norms of the wedge products of n linearly independent gradients of scalar polynomial curvature invariants, where n is the local cohomogeneity of the spacetime. PMID:25910105

  2. Sampling of Graph Signals With Successive Local Aggregations

    NASA Astrophysics Data System (ADS)

    Marques, Antonio G.; Segarra, Santiago; Leus, Geert; Ribeiro, Alejandro

    2016-04-01

    A new scheme to sample signals defined in the nodes of a graph is proposed. The underlying assumption is that such signals admit a sparse representation in a frequency domain related to the structure of the graph, which is captured by the so-called graph-shift operator. Most of the works that have looked at this problem have focused on using the value of the signal observed at a subset of nodes to recover the signal in the entire graph. Differently, the sampling scheme proposed here uses as input observations taken at a single node. The observations correspond to sequential applications of the graph-shift operator, which are linear combinations of the information gathered by the neighbors of the node. When the graph corresponds to a directed cycle (which is the support of time-varying signals), our method is equivalent to the classical sampling in the time domain. When the graph is more general, we show that the Vandermonde structure of the sampling matrix, which is critical to guarantee recovery when sampling time-varying signals, is preserved. Sampling and interpolation are analyzed first in the absence of noise and then noise is considered. We then study the recovery of the sampled signal when the specific set of frequencies that is active is not known. Moreover, we present a more general sampling scheme, under which, either our aggregation approach or the alternative approach of sampling a graph signal by observing the value of the signal at a subset of nodes can be both viewed as particular cases. The last part of the paper presents numerical experiments that illustrate the results developed through both synthetic graph signals and a real-world graph of the economy of the United States.

  3. Graphical rule of transforming continuous-variable graph states by local homodyne detection

    SciTech Connect

    Zhang Jing

    2010-09-15

    Graphical rule, describing that any single-mode homodyne detection turns a given continuous-variable (CV) graph state into a new one, is presented. Employing two simple graphical rules--local complement operation and vertex deletion (single quadrature-amplitude x measurement)--the graphical rule for any single-mode quadrature component measurement can be obtained. The shape of CV weighted graph state may be designed and constructed easily from a given larger graph state by applying this graphical rule.

  4. Generalized Local-to-Global Shape Feature Detection Based on Graph Wavelets.

    PubMed

    Li, Nannan; Wang, Shengfa; Zhong, Ming; Su, Zhixun; Qin, Hong

    2016-09-01

    Informative and discriminative feature descriptors are vital in qualitative and quantitative shape analysis for a large variety of graphics applications. Conventional feature descriptors primarily concentrate on discontinuity of certain differential attributes at different orders that naturally give rise to their discriminative power in depicting point, line, small patch features, etc. This paper seeks novel strategies to define generalized, user-specified features anywhere on shapes. Our new region-based feature descriptors are constructed primarily with the powerful spectral graph wavelets (SGWs) that are both multi-scale and multi-level in nature, incorporating both local (differential) and global (integral) information. To our best knowledge, this is the first attempt to organize SGWs in a hierarchical way and unite them with the bi-harmonic diffusion field towards quantitative region-based shape analysis. Furthermore, we develop a local-to-global shape feature detection framework to facilitate a host of graphics applications, including partial matching without point-wise correspondence, coarse-to-fine recognition, model recognition, etc. Through the extensive experiments and comprehensive comparisons with the state-of-the-art, our framework has exhibited many attractive advantages such as being geometry-aware, robust, discriminative, isometry-invariant, etc. PMID:26561459

  5. Seven Experiments to Test the Local Lorentz Invariance of c

    NASA Technical Reports Server (NTRS)

    Gezari, Daniel Y.

    2005-01-01

    The speed of light has never been measured directly with a moving detector to test the fundamental assertion of special relativity that c is invariant to motion of the observer. Seven simple experiments are proposed, four of which could test the invariance of c to motion of the detector. Three other observations of moving sources could test Einstein s second postulate and the relativity of stellar aberration. There are lingering concerns that the speed of light may depend on the motion of the observer, after all. This issue can now be resolved by experiment.

  6. Local dependence in random graph models: characterization, properties and statistical inference

    PubMed Central

    Schweinberger, Michael; Handcock, Mark S.

    2015-01-01

    Summary Dependent phenomena, such as relational, spatial and temporal phenomena, tend to be characterized by local dependence in the sense that units which are close in a well-defined sense are dependent. In contrast with spatial and temporal phenomena, though, relational phenomena tend to lack a natural neighbourhood structure in the sense that it is unknown which units are close and thus dependent. Owing to the challenge of characterizing local dependence and constructing random graph models with local dependence, many conventional exponential family random graph models induce strong dependence and are not amenable to statistical inference. We take first steps to characterize local dependence in random graph models, inspired by the notion of finite neighbourhoods in spatial statistics and M-dependence in time series, and we show that local dependence endows random graph models with desirable properties which make them amenable to statistical inference. We show that random graph models with local dependence satisfy a natural domain consistency condition which every model should satisfy, but conventional exponential family random graph models do not satisfy. In addition, we establish a central limit theorem for random graph models with local dependence, which suggests that random graph models with local dependence are amenable to statistical inference. We discuss how random graph models with local dependence can be constructed by exploiting either observed or unobserved neighbourhood structure. In the absence of observed neighbourhood structure, we take a Bayesian view and express the uncertainty about the neighbourhood structure by specifying a prior on a set of suitable neighbourhood structures. We present simulation results and applications to two real world networks with ‘ground truth’. PMID:26560142

  7. Discrete spectrum for quantum graph with local disturbance of the periodicity

    NASA Astrophysics Data System (ADS)

    Popov, Igor Yu; Blinova, Irina V.; Popov, Anton I.

    2015-12-01

    The problem of discrete spectrum for quantum graph with local disturbance of the periodicity is described. The Hamiltonian is determined as 1D Schrödinger operator on each edge and some boundary conditions at each vertex. The spectral analysis of the quantum graph having the form of branching strips with hexagonal (honeycomb) structure is considered in more details.

  8. Localization Computation of One-Point Disk Invariants of Projective Calabi-Yau Complete Intersections

    NASA Astrophysics Data System (ADS)

    Popa, Alexandra

    2014-12-01

    We define one-point disk invariants of a smooth projective Calabi-Yau complete intersection in the presence of an anti-holomorphic involution via localization. We show that these invariants are rational numbers and obtain a formula for them which confirms, in particular, a conjecture by Jinzenji-Shimizu [(Int J Geom Method M 11(1):1456005, 2014), Conjecture 1].

  9. Local quality functions for graph clustering with non-negative matrix factorization

    NASA Astrophysics Data System (ADS)

    van Laarhoven, Twan; Marchiori, Elena

    2014-12-01

    Many graph clustering quality functions suffer from a resolution limit, namely the inability to find small clusters in large graphs. So-called resolution-limit-free quality functions do not have this limit. This property was previously introduced for hard clustering, that is, graph partitioning. We investigate the resolution-limit-free property in the context of non-negative matrix factorization (NMF) for hard and soft graph clustering. To use NMF in the hard clustering setting, a common approach is to assign each node to its highest membership cluster. We show that in this case symmetric NMF is not resolution-limit free, but that it becomes so when hardness constraints are used as part of the optimization. The resulting function is strongly linked to the constant Potts model. In soft clustering, nodes can belong to more than one cluster, with varying degrees of membership. In this setting resolution-limit free turns out to be too strong a property. Therefore we introduce locality, which roughly states that changing one part of the graph does not affect the clustering of other parts of the graph. We argue that this is a desirable property, provide conditions under which NMF quality functions are local, and propose a novel class of local probabilistic NMF quality functions for soft graph clustering.

  10. Feature-based affine-Invariant localization of faces.

    PubMed

    Hamouz, M; Kittler, J; Kamarainen, J K; Paalanen, P; Kälviäinen, H; Matas, J

    2005-09-01

    We present a novel method for localizing faces in person identification scenarios. Such scenarios involve high resolution images of frontal faces. The proposed algorithm does not require color, copes well in cluttered backgrounds, and accurately localizes faces including eye centers. An extensive analysis and a performance evaluation on the XM2VTS database and on the realistic BioID and BANCA face databases is presented. We show that the algorithm has precision superior to reference methods. PMID:16173191

  11. Localization and the invariant probability measure for a structural dynamic system

    NASA Astrophysics Data System (ADS)

    Kissel, Glen J.

    2009-03-01

    In the one-dimensional classical analogs to Anderson localization, whether optical, acoustical or structural dynamic, the periodic system has its periodicity disrupted by having one or more of its parameters randomly disordered. Such randomized systems can be modeled via an infinite product of random transfer matrices. In the case where the transfer matrices are 2x2, the upper (and positive) Lyapunov exponent of the random matrix product is identified as the localization factor (inverse localization length) for the disordered one-dimensional model. It is this localization factor which governs the confinement of energy transmission along the disordered system, and for which the localization phenomenon has been of interest. The theorem of Furstenberg for infinite products of random matrices allows us to calculate this upper Lyapunov exponent. In Furstenberg's master formula we integrate with respect to the probability measure of the random matrices, but also with respect to the invariant probability measure of the direction of the vector propagated by the long chain of random matrices. This invariant measure is difficult to find analytically, and, as a result, either an approximating assumption is frequently made, or, less frequently, the invariant measure is determined numerically. Here we calculate the invariant measure numerically using a Monte Carlo bin counting technique and then numerically integrate Furstenberg's formula to arrive at the localization factor for both continuous and discrete disorder of the mass. This result is cross checked with the (modified) Wolf algorithm.

  12. Test of local position invariance using a double-cavity laser system

    SciTech Connect

    Agachev, A. R.; Belov, I. Yu.; Bochkarev, V. V.; Daishev, R. A.; Mavrin, S. V.; Murzakhanov, Z. G.; Skochilov, A. F. Chugunov, Yu. P.; Shindyaev, O. P.

    2010-01-15

    The results of testing local position invariance, which is a constituent of the Einstein equivalence principle, in a 'null' gravitational redshift experiment are reported. The processing of the experimental data collected during the five-month operation of a double-c avity laser system, where one cavity operates in the free generation mode and the frequency of the second cavity is stabilized with the nonlinear ultranarrow absorption resonance of the methane molecule, has confirmed the universality of the gravitational redshift law at a level of 0.9%. This result almost doubly improves the best existing accuracy (1.7%) of testing local position invariance for clocks of different physical natures.

  13. A three-colour graph as a complete topological invariant for gradient-like diffeomorphisms of surfaces

    SciTech Connect

    Grines, V Z; Pochinka, O V; Kapkaeva, S Kh

    2014-10-31

    In a paper of Oshemkov and Sharko, three-colour graphs were used to make the topological equivalence of Morse-Smale flows on surfaces obtained by Peixoto more precise. In the present paper, in the language of three-colour graphs equipped with automorphisms, we obtain a complete (including realization) topological classification of gradient-like cascades on surfaces. Bibliography: 25 titles.

  14. Trivalent Graphs, Volume Conjectures and Character Varieties

    NASA Astrophysics Data System (ADS)

    Nawata, Satoshi; Pichai, Ramadevi; Zodinmawia

    2014-10-01

    The generalized volume conjecture and the AJ conjecture (a.k.a. the quantum volume conjecture) are extended to colored quantum invariants of the theta and tetrahedron graph. The character variety of the fundamental group of the complement of a trivalent graph with E edges in S 3 is a Lagrangian subvariety of the Hitchin moduli space over the Riemann surface of genus g = E/3 + 1. For the theta and tetrahedron graph, we conjecture that the configuration of the character variety is locally determined by large color asymptotics of the quantum invariants of the trivalent graph in terms of complex Fenchel-Nielsen coordinates. Moreover, the q-holonomic difference equation of the quantum invariants provides the quantization of the character variety.

  15. Local energy-momentum conservation in scalar-tensor-like gravity with generic curvature invariants

    NASA Astrophysics Data System (ADS)

    Tian, David Wenjie

    2016-08-01

    For a large class of scalar-tensor-like gravity whose action contains nonminimal couplings between a scalar field φ (x^α ) and generic curvature invariants R beyond the Ricci scalar R=R^α _{α }, we prove the covariant invariance of its field equation and confirm/prove the local energy-momentum conservation. These φ (x^α )- R coupling terms break the symmetry of diffeomorphism invariance under an active transformation, which implies that the solutions to the field equation should satisfy the consistency condition R ≡ 0 when φ (x^α ) is nondynamical and massless. Following this fact and based on the accelerated expansion of the observable Universe, we propose a primary test to check the viability of the modified gravity to be an effective dark energy, and a simplest example passing the test is the "Weyl/conformal dark energy".

  16. Scale-invariant hidden local symmetry, topology change, and dense baryonic matter

    NASA Astrophysics Data System (ADS)

    Paeng, Won-Gi; Kuo, Thomas T. S.; Lee, Hyun Kyu; Rho, Mannque

    2016-05-01

    When scale symmetry is implemented into hidden local symmetry in low-energy strong interactions to arrive at a scale-invariant hidden local symmetric (HLS) theory, the scalar f0(500 ) may be interpreted as pseudo-Nambu-Goldstone (pNG) boson, i.e., dilaton, of spontaneously broken scale invariance, joining the pseudoscalar pNG bosons π and the matter fields V =(ρ ,ω ) as relevant degrees of freedom. Implementing the skyrmion-half-skyrmion transition predicted at large Nc in QCD at a density roughly twice the nuclear matter density found in the crystal simulation of dense skyrmion matter, we determine the intrinsically density-dependent "bare parameters" of the scale-invariant HLS Lagrangian matched to QCD at a matching scale ΛM. The resulting effective Lagrangian, with the parameters scaling with the density of the system, is applied to nuclear matter and dense baryonic matter relevant to massive compact stars by means of the double-decimation renormalization-group Vlow k formalism. We satisfactorily postdict the properties of normal nuclear matter and more significantly predict the equation of state of dense compact-star matter that quantitatively accounts for the presently available data coming from both the terrestrial and space laboratories. We interpret the resulting structure of compact-star matter as revealing how the combination of hidden-scale symmetry and hidden local symmetry manifests itself in compressed baryonic matter.

  17. Autonomous mobile robot exploration based on the generalized Voronoi graph in the presence of localization error

    NASA Astrophysics Data System (ADS)

    Nagatani, Keiji; Choset, Howie M.

    1999-01-01

    Sensor based exploration is a task which enables a robot to explore and map an unknown environment, using sensor information. The map used in this paper is the generalized Voronoi graph (GVG). The robot explores an unknown environment using an already developed incremental construction procedure to generate the GVG using sensor information. This paper presents some initial results which uses the GVG for robot localization, while mitigating the need to update encoder values. Experimental result verify the described work.

  18. Classification of EEG Single Trial Microstates Using Local Global Graphs and Discrete Hidden Markov Models.

    PubMed

    Michalopoulos, Kostas; Zervakis, Michalis; Deiber, Marie-Pierre; Bourbakis, Nikolaos

    2016-09-01

    We present a novel synergistic methodology for the spatio-temporal analysis of single Electroencephalogram (EEG) trials. This new methodology is based on the novel synergy of Local Global Graph (LG graph) to characterize define the structural features of the EEG topography as a global descriptor for robust comparison of dominant topographies (microstates) and Hidden Markov Models (HMM) to model the topographic sequence in a unique way. In particular, the LG graph descriptor defines similarity and distance measures that can be successfully used for the difficult comparison of the extracted LG graphs in the presence of noise. In addition, hidden states represent periods of stationary distribution of topographies that constitute the equivalent of the microstates in the model. The transitions between the different microstates and the formed syntactic patterns can reveal differences in the processing of the input stimulus between different pathologies. We train the HMM model to learn the transitions between the different microstates and express the syntactic patterns that appear in the single trials in a compact and efficient way. We applied this methodology in single trials consisting of normal subjects and patients with Progressive Mild Cognitive Impairment (PMCI) to discriminate these two groups. The classification results show that this approach is capable to efficiently discriminate between control and Progressive MCI single trials. Results indicate that HMMs provide physiologically meaningful results that can be used in the syntactic analysis of Event Related Potentials. PMID:27255799

  19. Local conformal-invariance of the wave equation for finite-component fields. I. The conditions for invariance, and fully-reducible fields

    NASA Astrophysics Data System (ADS)

    Bracken, A. J.; Jessup, Barry

    1982-10-01

    The conditions for local conformal-invariance of the wave equation are obtained for finite-component fields, of Types Ia and Ib [in the terminology of Mack and Salam, Ann. Phys. 53, 174 (1969).] These conditions generate a set of locally invariant free massless field equations and restrict the relevant representation of the Lie algebra [(k4⊕d)⊕sl(2,C)] in the index space of the field to belong to a certain class. Those fully-reducible representations which are in this class are described in full. The corresponding Type Ia field equations include only the massless scalar field equation, neutrino equations, Maxwell's equations, and the Bargmann-Wigner equations for massless fields of arbitrary helicity, and no others. In particular, it is confirmed [Bracken, Lett. Nuovo Cimento 2, 574 (1971)] that not all Poincaré-invariant sets of massless Type Ia field equations are conformal-invariant, contrary to some often-quoted results of McLennan [Nuovo Cimento 3, 1360 (1956)], which are shown to be invalid. It is also shown that in the case of a potential, the wave equation is never conformal-invariant in the strong sense (excluding gauge transformations).

  20. How many invariant polynomials are needed to decide local unitary equivalence of qubit states?

    SciTech Connect

    Maciążek, Tomasz; Oszmaniec, Michał

    2013-09-15

    Given L-qubit states with the fixed spectra of reduced one-qubit density matrices, we find a formula for the minimal number of invariant polynomials needed for solving local unitary (LU) equivalence problem, that is, problem of deciding if two states can be connected by local unitary operations. Interestingly, this number is not the same for every collection of the spectra. Some spectra require less polynomials to solve LU equivalence problem than others. The result is obtained using geometric methods, i.e., by calculating the dimensions of reduced spaces, stemming from the symplectic reduction procedure.

  1. Path collapse in Feynman formula. Stable path integral formula from local time reparametrization invariant amplitude

    NASA Astrophysics Data System (ADS)

    Kleinert, H.

    1989-06-01

    The Feynman formula, which expresses the time displacement amplitude > x b | exp (-t Ȟ) | x a< in terms of a path integral Π 1N (∫ dn) Π 1N+1 ( {∫ dp n}/{2π}) exp{Σ 1N [ ip n(x n-x n-1) - ɛH (p n, x n)]} with large N, does not exist for systems with Coulomb {-1}/{r} potential and gives incorrect threshold behaviours near centrifugal {1}/{r 2} or angular {1}/{sin2θ } barriers. We discuss the physical origin of this failure and propose an alternative well-defined path integral formula based on a family of amplitudes that is invariant under arbitrary local time reparametrizations. The time slicing with finite N breaks this invariance. For appropriate choices of the reparametrization function the fluctuations are stabilized and the new formula is applicable to all the above systems.

  2. Invariant conserved currents in gravity theories with local Lorentz and diffeomorphism symmetry

    SciTech Connect

    Obukhov, Yuri N.; Rubilar, Guillermo F.

    2006-09-15

    We discuss conservation laws for gravity theories invariant under general coordinate and local Lorentz transformations. We demonstrate the possibility to formulate these conservation laws in many covariant and noncovariant(ly looking) ways. An interesting mathematical fact underlies such a diversity: there is a certain ambiguity in a definition of the (Lorentz-) covariant generalization of the usual Lie derivative. Using this freedom, we develop a general approach to the construction of invariant conserved currents generated by an arbitrary vector field on the spacetime. This is done in any dimension, for any Lagrangian of the gravitational field and of a (minimally or nonminimally) coupled matter field. A development of the ''regularization via relocalization'' scheme is used to obtain finite conserved quantities for asymptotically nonflat solutions. We illustrate how our formalism works by some explicit examples.

  3. A graph-based approach for local and global panorama imaging in cystoscopy

    NASA Astrophysics Data System (ADS)

    Bergen, Tobias; Wittenberg, Thomas; Münzenmayer, Christian; Chen, Chi Chiung Grace; Hager, Gregory D.

    2013-03-01

    Inspection of the urinary bladder with an endoscope (cystoscope) is the usual procedure for early detection of bladder cancer. The very limited field of view provided by the endoscope makes it challenging to ensure, that the interior bladder wall has been examined completely. Panorama imaging techniques can be used to assist the surgeon and provide a larger view field. Different approaches have been proposed, but generating a panorama image of the entire bladder from real patient data is still a challenging research topic. We propose a graph-based and hierarchical approach to assess this problem to first generate several local panorama images, followed by a global textured three-dimensional reconstruction of the organ. In this contribution, we address details of the first level of the approach including a graph-based algorithm to deal with the challenging condition of in-vivo data. This graph strategy gives rise to a robust relocalization strategy in case of tracking failure, an effective keyframe selection process as well as the concept of building locally optimized sub-maps, which lay the ground for a global optimization process. Our results show the successful application of the method to four in-vivo data sets.

  4. Space-Time Hierarchical-Graph Based Cooperative Localization in Wireless Sensor Networks

    NASA Astrophysics Data System (ADS)

    Lv, Tiejun; Gao, Hui; Li, Xiaopeng; Yang, Shaoshi; Hanzo, Lajos

    2016-01-01

    It has been shown that cooperative localization is capable of improving both the positioning accuracy and coverage in scenarios where the global positioning system (GPS) has a poor performance. However, due to its potentially excessive computational complexity, at the time of writing the application of cooperative localization remains limited in practice. In this paper, we address the efficient cooperative positioning problem in wireless sensor networks. A space-time hierarchical-graph based scheme exhibiting fast convergence is proposed for localizing the agent nodes. In contrast to conventional methods, agent nodes are divided into different layers with the aid of the space-time hierarchical-model and their positions are estimated gradually. In particular, an information propagation rule is conceived upon considering the quality of positional information. According to the rule, the information always propagates from the upper layers to a certain lower layer and the message passing process is further optimized at each layer. Hence, the potential error propagation can be mitigated. Additionally, both position estimation and position broadcasting are carried out by the sensor nodes. Furthermore, a sensor activation mechanism is conceived, which is capable of significantly reducing both the energy consumption and the network traffic overhead incurred by the localization process. The analytical and numerical results provided demonstrate the superiority of our space-time hierarchical-graph based cooperative localization scheme over the benchmarking schemes considered.

  5. Compounding Local Invariant Features and Global Deformable Geometry for Medical Image Registration

    PubMed Central

    Zhang, Jianhua; Chen, Lei; Wang, Xiaoyan; Teng, Zhongzhao; Brown, Adam J.; Gillard, Jonathan H.; Guan, Qiu; Chen, Shengyong

    2014-01-01

    Using deformable models to register medical images can result in problems of initialization of deformable models and robustness and accuracy of matching of inter-subject anatomical variability. To tackle these problems, a novel model is proposed in this paper by compounding local invariant features and global deformable geometry. This model has four steps. First, a set of highly-repeatable and highly-robust local invariant features, called Key Features Model (KFM), are extracted by an effective matching strategy. Second, local features can be matched more accurately through the KFM for the purpose of initializing a global deformable model. Third, the positional relationship between the KFM and the global deformable model can be used to precisely pinpoint all landmarks after initialization. And fourth, the final pose of the global deformable model is determined by an iterative process with a lower time cost. Through the practical experiments, the paper finds three important conclusions. First, it proves that the KFM can detect the matching feature points well. Second, the precision of landmark locations adjusted by the modeled relationship between KFM and global deformable model is greatly improved. Third, regarding the fitting accuracy and efficiency, by observation from the practical experiments, it is found that the proposed method can improve % of the fitting accuracy and reduce around 50% of the computational time compared with state-of-the-art methods. PMID:25165985

  6. Pattern vectors from algebraic graph theory.

    PubMed

    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

  7. Retinal Vessel Segmentation: An Efficient Graph Cut Approach with Retinex and Local Phase

    PubMed Central

    Zhao, Yitian; Liu, Yonghuai; Wu, Xiangqian; Harding, Simon P.; Zheng, Yalin

    2015-01-01

    Our application concerns the automated detection of vessels in retinal images to improve understanding of the disease mechanism, diagnosis and treatment of retinal and a number of systemic diseases. We propose a new framework for segmenting retinal vasculatures with much improved accuracy and efficiency. The proposed framework consists of three technical components: Retinex-based image inhomogeneity correction, local phase-based vessel enhancement and graph cut-based active contour segmentation. These procedures are applied in the following order. Underpinned by the Retinex theory, the inhomogeneity correction step aims to address challenges presented by the image intensity inhomogeneities, and the relatively low contrast of thin vessels compared to the background. The local phase enhancement technique is employed to enhance vessels for its superiority in preserving the vessel edges. The graph cut-based active contour method is used for its efficiency and effectiveness in segmenting the vessels from the enhanced images using the local phase filter. We have demonstrated its performance by applying it to four public retinal image datasets (3 datasets of color fundus photography and 1 of fluorescein angiography). Statistical analysis demonstrates that each component of the framework can provide the level of performance expected. The proposed framework is compared with widely used unsupervised and supervised methods, showing that the overall framework outperforms its competitors. For example, the achieved sensitivity (0:744), specificity (0:978) and accuracy (0:953) for the DRIVE dataset are very close to those of the manual annotations obtained by the second observer. PMID:25830353

  8. Strong restriction on inflationary vacua from the local gauge invariance III: Infrared regularity of graviton loops

    NASA Astrophysics Data System (ADS)

    Tanaka, Takahiro; Urakawa, Yuko

    2014-07-01

    It has been claimed that the super-Hubble modes of the graviton generated during inflation can make loop corrections diverge. Even if we introduce an infrared (IR) cutoff at a comoving scale as an ad hoc but practical method of regularization, we encounter secular growth, which may lead to the breakdown of perturbative expansion for a sufficiently long-lasting inflation. In this paper, we show that the IR pathology concerning the graviton can be attributed to the presence of residual gauge degrees of freedom in the local observable universe, as in the case of the adiabatic curvature perturbation. We will show that choosing the Euclidean vacuum as the initial state ensures invariance under the above-mentioned residual gauge transformations. We will also show that, as long as we consider a gauge invariant quantity in the local universe, we encounter neither IR divergence nor secular growth. The argument in this paper applies to general single-field models of inflation up to a sufficiently high order in perturbation.

  9. Dynamics of many-body localization in a translation-invariant quantum glass model

    NASA Astrophysics Data System (ADS)

    van Horssen, Merlijn; Levi, Emanuele; Garrahan, Juan P.

    2015-09-01

    We study the real-time dynamics of a translationally invariant quantum spin chain, based on the East kinetically constrained glass model, in search for evidence of many-body localization in the absence of disorder. Numerical simulations indicate a change, controlled by a coupling parameter, from a regime of fast relaxation-corresponding to thermalization-to a regime of very slow relaxation. This slowly relaxing regime is characterized by dynamical features usually associated with nonergodicity and many-body localization (MBL): memory of initial conditions, logarithmic growth of entanglement entropy, and nonexponential decay of time correlators. We show that slow relaxation is a consequence of sensitivity to spatial fluctuations in the initial state. While numerical results and physical considerations indicate that relaxation time scales grow markedly with size, our finite size results are consistent both with an MBL transition, expected to only occur in disordered systems, and with a pronounced quasi-MBL crossover.

  10. Automated Image Retrieval of Chest CT Images Based on Local Grey Scale Invariant Features.

    PubMed

    Arrais Porto, Marcelo; Cordeiro d'Ornellas, Marcos

    2015-01-01

    Textual-based tools are regularly employed to retrieve medical images for reading and interpretation using current retrieval Picture Archiving and Communication Systems (PACS) but pose some drawbacks. All-purpose content-based image retrieval (CBIR) systems are limited when dealing with medical images and do not fit well into PACS workflow and clinical practice. This paper presents an automated image retrieval approach for chest CT images based local grey scale invariant features from a local database. Performance was measured in terms of precision and recall, average retrieval precision (ARP), and average retrieval rate (ARR). Preliminary results have shown the effectiveness of the proposed approach. The prototype is also a useful tool for radiology research and education, providing valuable information to the medical and broader healthcare community. PMID:26262345

  11. Atom interferometry tests of local Lorentz invariance in gravity and electrodynamics

    SciTech Connect

    Chung, Keng-Yeow; Chiow, Sheng-wey; Herrmann, Sven; Chu, Steven; Mueller, Holger

    2009-07-01

    We present atom-interferometer tests of the local Lorentz invariance of post-Newtonian gravity. An experiment probing for anomalous vertical gravity on Earth, which has already been performed, uses the highest-resolution atomic gravimeter so far. The influence of Lorentz violation in electrodynamics is also taken into account, resulting in combined bounds on Lorentz violation in gravity and electrodynamics. Expressed within the standard model extension or Nordtvedt's anisotropic universe model, we limit 12 linear combinations of seven coefficients for Lorentz violation at the part per billion level, from which we derive limits on six coefficients (and seven when taking into account additional data from lunar laser ranging). We also discuss the use of horizontal interferometers, including atom-chip or guided-atom devices, which potentially allow the use of longer coherence times in order to achieve higher sensitivity.

  12. Tests of local Lorentz invariance violation of gravity in the standard model extension with pulsars.

    PubMed

    Shao, Lijing

    2014-03-21

    The standard model extension is an effective field theory introducing all possible Lorentz-violating (LV) operators to the standard model and general relativity (GR). In the pure-gravity sector of minimal standard model extension, nine coefficients describe dominant observable deviations from GR. We systematically implemented 27 tests from 13 pulsar systems to tightly constrain eight linear combinations of these coefficients with extensive Monte Carlo simulations. It constitutes the first detailed and systematic test of the pure-gravity sector of minimal standard model extension with the state-of-the-art pulsar observations. No deviation from GR was detected. The limits of LV coefficients are expressed in the canonical Sun-centered celestial-equatorial frame for the convenience of further studies. They are all improved by significant factors of tens to hundreds with existing ones. As a consequence, Einstein's equivalence principle is verified substantially further by pulsar experiments in terms of local Lorentz invariance in gravity. PMID:24702346

  13. Optimal preparation of graph states

    SciTech Connect

    Cabello, Adan; Lopez-Tarrida, Antonio J.; Danielsen, Lars Eirik; Portillo, Jose R.

    2011-04-15

    We show how to prepare any graph state of up to 12 qubits with (a) the minimum number of controlled-Z gates and (b) the minimum preparation depth. We assume only one-qubit and controlled-Z gates. The method exploits the fact that any graph state belongs to an equivalence class under local Clifford operations. We extend up to 12 qubits the classification of graph states according to their entanglement properties, and identify each class using only a reduced set of invariants. For any state, we provide a circuit with both properties (a) and (b), if it does exist, or, if it does not, one circuit with property (a) and one with property (b), including the explicit one-qubit gates needed.

  14. Radiation Induced Chromatin Conformation Changes Analysed by Fluorescent Localization Microscopy, Statistical Physics, and Graph Theory

    PubMed Central

    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

  15. Khovanov homology of graph-links

    SciTech Connect

    Nikonov, Igor M

    2012-08-31

    Graph-links arise as the intersection graphs of turning chord diagrams of links. Speaking informally, graph-links provide a combinatorial description of links up to mutations. Many link invariants can be reformulated in the language of graph-links. Khovanov homology, a well-known and useful knot invariant, is defined for graph-links in this paper (in the case of the ground field of characteristic two). Bibliography: 14 titles.

  16. GraphClust: alignment-free structural clustering of local RNA secondary structures

    PubMed Central

    Rose, Dominic; Backofen, Rolf

    2012-01-01

    Motivation: Clustering according to sequence–structure similarity has now become a generally accepted scheme for ncRNA annotation. Its application to complete genomic sequences as well as whole transcriptomes is therefore desirable but hindered by extremely high computational costs. Results: We present a novel linear-time, alignment-free method for comparing and clustering RNAs according to sequence and structure. The approach scales to datasets of hundreds of thousands of sequences. The quality of the retrieved clusters has been benchmarked against known ncRNA datasets and is comparable to state-of-the-art sequence–structure methods although achieving speedups of several orders of magnitude. A selection of applications aiming at the detection of novel structural ncRNAs are presented. Exemplarily, we predicted local structural elements specific to lincRNAs likely functionally associating involved transcripts to vital processes of the human nervous system. In total, we predicted 349 local structural RNA elements. Availability: The GraphClust pipeline is available on request. Contact: backofen@informatik.uni-freiburg.de Supplementary information: Supplementary data are available at Bioinformatics online. PMID:22689765

  17. Contact-Free Palm-Vein Recognition Based on Local Invariant Features

    PubMed Central

    Kang, Wenxiong; Liu, Yang; Wu, Qiuxia; Yue, Xishun

    2014-01-01

    Contact-free palm-vein recognition is one of the most challenging and promising areas in hand biometrics. In view of the existing problems in contact-free palm-vein imaging, including projection transformation, uneven illumination and difficulty in extracting exact ROIs, this paper presents a novel recognition approach for contact-free palm-vein recognition that performs feature extraction and matching on all vein textures distributed over the palm surface, including finger veins and palm veins, to minimize the loss of feature information. First, a hierarchical enhancement algorithm, which combines a DOG filter and histogram equalization, is adopted to alleviate uneven illumination and to highlight vein textures. Second, RootSIFT, a more stable local invariant feature extraction method in comparison to SIFT, is adopted to overcome the projection transformation in contact-free mode. Subsequently, a novel hierarchical mismatching removal algorithm based on neighborhood searching and LBP histograms is adopted to improve the accuracy of feature matching. Finally, we rigorously evaluated the proposed approach using two different databases and obtained 0.996% and 3.112% Equal Error Rates (EERs), respectively, which demonstrate the effectiveness of the proposed approach. PMID:24866176

  18. Local Production of Interferon Gamma by Invariant Natural Killer T cells Modulates Acute Lyme Carditis

    PubMed Central

    Olson, Chris M.; Bates, Tonya C.; Izadi, Hooman; Radolf, Justin D.; Huber, Sally A.; Boyson, Jonathan E.; Anguita, Juan

    2009-01-01

    The Lyme disease spirochete, Borrelia burgdorferi, is the only known human pathogen that directly activates invariant natural killer T (iNKT) cells. The number and activation kinetics of iNKT cells vary greatly among different strains of mice. We now report the role of the iNKT cell response in the pathogenesis of Lyme disease using C57Bl/6 mice, a strain with optimal iNKT cell activation that is resistant to the development of spirochetal-induced inflammation. During experimental infection of B6 mice with B. burgdorferi, iNKT cells localize to the inflamed heart where they are activated by CD1d-expressing macrophages. Activation of iNKT cells in vivo results in the production of IFNγ, which we demonstrate ameliorates the severity of murine Lyme carditis by at least two mechanisms. First, IFNγ enhances the recognition of B. burgdorferi by macrophages, leading to increased phagocytosis of the spirochete. Secondly, IFNγ activation of macrophages increases the surface expression of CD1d, thereby facilitating further iNKT activation. Collectively, our data demonstrate that in the resistant background, B6, iNKT cells modulate the severity of murine Lyme carditis through the action of IFNγ, which appears to self-renew through a positive feedback loop during infection. PMID:19265151

  19. Improved tests of local position invariance using 87Rb and 133Cs fountains.

    PubMed

    Guéna, J; Abgrall, M; Rovera, D; Rosenbusch, P; Tobar, M E; Laurent, Ph; Clairon, A; Bize, S

    2012-08-24

    We report tests of local position invariance based on measurements of the ratio of the ground state hyperfine frequencies of 133Cs and 87Rb in laser-cooled atomic fountain clocks. Measurements extending over 14 years set a stringent limit to a possible variation with time of this ratio: d ln(ν(Rb)/ν(Cs))/dt=(-1.39±0.91)×10(-16) yr(-1). This improves by a factor of 7.7 over our previous report [H. Marion et al., Phys. Rev. Lett. 90, 150801 (2003)]. Our measurements also set the first limit to a fractional variation of the Rb/Cs frequency ratio with gravitational potential at the level of c(2)d ln(ν(Rb)/ν(Cs))/dU=(0.11±1.04)×10(-6), providing a new stringent differential redshift test. The above limits equivalently apply to the fractional variation of the quantity α(-0.49)(g(Rb)/g(Cs)), which involves the fine-structure constant α and the ratio of the nuclear g-factors of the two alkalis. The link with variations of the light quark mass is also presented together with a global analysis combining other available highly accurate clock comparisons. PMID:23002732

  20. A matrix product algorithm for stochastic dynamics on locally tree-like graphs

    NASA Astrophysics Data System (ADS)

    Barthel, Thomas; de Bacco, Caterina; Franz, Silvio

    In this talk, I describe a novel algorithm for the efficient simulation of generic stochastic dynamics of classical degrees of freedom defined on the vertices of locally tree-like graphs. Such models correspond for example to spin-glass systems, Boolean networks, neural networks, or other technological, biological, and social networks. Building upon the cavity method and ideas from quantum many-body theory, the algorithm is based on a matrix product approximation of the so-called edge messages - conditional probabilities of vertex variable trajectories. The matrix product edge messages (MPEM) are constructed recursively. Computation costs and accuracy can be tuned by controlling the matrix dimensions of the MPEM in truncations. In contrast to Monte Carlo simulations, the approach has a better error scaling and works for both, single instances as well as the thermodynamic limit. Due to the absence of cancellation effects, observables with small expectation values can be evaluated accurately, allowing for the study of decay processes and temporal correlations with unprecedented accuracy. The method is demonstrated for the prototypical non-equilibrium Glauber dynamics of an Ising spin system. Reference: arXiv:1508.03295.

  1. Stable standing waves for a NLS on star graphs as local minimizers of the constrained energy

    NASA Astrophysics Data System (ADS)

    Adami, Riccardo; Cacciapuoti, Claudio; Finco, Domenico; Noja, Diego

    2016-05-01

    On a star graph made of N ≥ 3 halflines (edges) we consider a Schrödinger equation with a subcritical power-type nonlinearity and an attractive delta interaction located at the vertex. From previous works it is known that there exists a family of standing waves, symmetric with respect to the exchange of edges, that can be parametrized by the mass (or L2-norm) of its elements. Furthermore, if the mass is small enough, then the corresponding symmetric standing wave is a ground state and, consequently, it is orbitally stable. On the other hand, if the mass is above a threshold value, then the system has no ground state. Here we prove that orbital stability holds for every value of the mass, even if the corresponding symmetric standing wave is not a ground state, since it is anyway a local minimizer of the energy among functions with the same mass. The proof is based on a new technique that allows to restrict the analysis to functions made of pieces of soliton, reducing the problem to a finite-dimensional one. In such a way, we do not need to use direct methods of Calculus of Variations, nor linearization procedures.

  2. Closely Spaced MEG Source Localization and Functional Connectivity Analysis Using a New Prewhitening Invariance of Noise Space Algorithm

    PubMed Central

    Zhang, Junpeng; Cui, Yuan; Deng, Lihua; He, Ling; Zhang, Junran; Zhang, Jing; Zhou, Qun; Liu, Qi; Zhang, Zhiguo

    2016-01-01

    This paper proposed a prewhitening invariance of noise space (PW-INN) as a new magnetoencephalography (MEG) source analysis method, which is particularly suitable for localizing closely spaced and highly correlated cortical sources under real MEG noise. Conventional source localization methods, such as sLORETA and beamformer, cannot distinguish closely spaced cortical sources, especially under strong intersource correlation. Our previous work proposed an invariance of noise space (INN) method to resolve closely spaced sources, but its performance is seriously degraded under correlated noise between MEG sensors. The proposed PW-INN method largely mitigates the adverse influence of correlated MEG noise by projecting MEG data to a new space defined by the orthogonal complement of dominant eigenvectors of correlated MEG noise. Simulation results showed that PW-INN is superior to INN, sLORETA, and beamformer in terms of localization accuracy for closely spaced and highly correlated sources. Lastly, source connectivity between closely spaced sources can be satisfactorily constructed from source time courses estimated by PW-INN but not from results of other conventional methods. Therefore, the proposed PW-INN method is a promising MEG source analysis to provide a high spatial-temporal characterization of cortical activity and connectivity, which is crucial for basic and clinical research of neural plasticity. PMID:26819768

  3. Testing Local Position Invariance with Four Cesium-Fountain Primary Frequency Standards and Four NIST Hydrogen Masers

    SciTech Connect

    Ashby, N.; Heavner, T. P.; Jefferts, S. R.; Parker, T. E.; Radnaev, A. G.; Dudin, Y. O.

    2007-02-16

    We report the most sensitive tests to date of the assumption of local position invariance (LPI) underlying general relativity, based on a 7 yr comparison of cesium and hydrogen atomic clocks (frequency standards). The latest results place an upper limit that is over 20 times smaller than the previous most sensitive tests; this is consistent with the null shift predicted by LPI. The result is based on precise comparisons of frequencies of four hydrogen masers maintained by NIST, with four independent Cs fountain clocks--one at NIST and three in Europe--as the Sun's gravitational potential at Earth's surface varies due to Earth's orbital eccentricity.

  4. Lorentz invariance in shape dynamics

    NASA Astrophysics Data System (ADS)

    Carlip, S.; Gomes, Henrique

    2015-01-01

    Shape dynamics is a reframing of canonical general relativity in which time reparametrization invariance is ‘traded’ for a local conformal invariance. We explore the emergence of Lorentz invariance in this model in three contexts: as a maximal symmetry, an asymptotic symmetry and a local invariance.

  5. Universality of the local eigenvalue statistics for a class of unitary invariant random matrix ensembles

    SciTech Connect

    Pastur, L. |; Shcherbina, M.

    1997-01-01

    This paper is devoted to the rigorous proof of the universality conjecture of random matrix theory, according to which the limiting eigenvalue statistics of n x n random matrices within spectral intervals of O(n{sup -1}) is determined by the type of matrix (real symmetric, Hermitian, or quaternion real) and by the density of states. We prove this conjecture for a certain class of the Hermitian matrix ensembles that arise in the quantum field theory and have the unitary invariant distribution defined by a certain function (the potential in the quantum field theory) satisfying some regularity conditions.

  6. Classification of 4-qubit Entangled Graph States According to Bipartite Entanglement, Multipartite Entanglement and Non-local Properties

    NASA Astrophysics Data System (ADS)

    Assadi, Leila; Jafarpour, Mojtaba

    2016-07-01

    We use concurrence to study bipartite entanglement, Meyer-Wallach measure and its generalizations to study multi-partite entanglement and MABK and SASA inequalities to study the non-local properties of the 4-qubit entangled graph states, quantitatively. Then, we present 3 classifications, each one in accordance with one of the aforementioned properties. We also observe that the classification according to multipartite entanglement does exactly coincide with that according to nonlocal properties, but does not match with that according to bipartite entanglement. This observation signifies the fact that non-locality and multipartite entanglement enjoy the same basic underlying principles, while bipartite entanglement may not reveal the non-locality issue in its entirety.

  7. Simultaneous localization of multiple broadband non-impulsive acoustic sources in an ocean waveguide using the array invariant.

    PubMed

    Gong, Zheng; Ratilal, Purnima; Makris, Nicholas C

    2015-11-01

    The array invariant method, previously derived for instantaneous range and bearing estimation of a single broadband impulsive source in a horizontally stratified ocean waveguide, can be generalized to simultaneously localize multiple uncorrelated broadband noise sources that are not necessarily impulsive in the time domain by introducing temporal pulse compression and an image processing technique similar to the Radon transform. This can be done by estimating the range and bearing of broadband non-impulsive sources from measured beam-time migration lines of modal arrivals along a horizontal array arising from differences in modal group velocity and modal polar angle for each propagating mode. The generalized array invariant approach is used to estimate the range of a vertical source array and vocalizing humpback whales over wide areas from measurements made by a towed horizontal receiver array during the Gulf of Maine 2006 Experiment. The localization results are shown to have roughly 12% root-mean-squared errors from Global Positioning System measured ground truth positions for controlled source transmissions and less than 10% discrepancy from those obtained independently via moving array triangulation for vocalizing humpbacks, respectively. PMID:26627743

  8. Context-Invariant and Local Quasi Hidden Variable (qHV) Modelling Versus Contextual and Nonlocal HV Modelling

    NASA Astrophysics Data System (ADS)

    Loubenets, Elena R.

    2015-07-01

    For the probabilistic description of all the joint von Neumann measurements on a D-dimensional quantum system, we present the specific example of a context-invariant quasi hidden variable (qHV) model, proved in Loubenets (J Math Phys 56:032201, 2015) to exist for each Hilbert space. In this model, a quantum observable X is represented by a variety of random variables satisfying the functional condition required in quantum foundations but, in contrast to a contextual model, each of these random variables equivalently models X under all joint von Neumann measurements, regardless of their contexts. This, in particular, implies the specific local qHV (LqHV) model for an N-qudit state and allows us to derive the new exact upper bound on the maximal violation of 22-setting Bell-type inequalities of any type (either on correlation functions or on joint probabilities) under N-partite joint von Neumann measurements on an N-qudit state. For d = 2, this new upper bound coincides with the maximal violation by an N-qubit state of the Mermin-Klyshko inequality. Based on our results, we discuss the conceptual and mathematical advantages of context-invariant and local qHV modelling.

  9. Hyperspectral target detection using graph theory models and manifold geometry via an adaptive implementation of locally linear embedding

    NASA Astrophysics Data System (ADS)

    Ziemann, Amanda K.; Messinger, David W.

    2014-06-01

    Hyperspectral images comprise, by design, high dimensional image data. However, research has shown that for a d-dimensional hyperspectral image, it is typical for the data to inherently occupy an m-dimensional space, with m << d. In the remote sensing community, this has led to a recent increase in the use of non-linear manifold learning, which aims to characterize the embedded lower-dimensional, non-linear manifold upon which the hyperspectral data inherently lie. Classic hyperspectral data models include statistical, linear subspace, and linear mixture models, but these can place restrictive assumptions on the distribution of the data. With graph theory and manifold learning based models, the only assumption is that the data reside on an underlying manifold. In previous publications, we have shown that manifold coordinate approximation using locally linear embedding (LLE) is a viable pre-processing step for target detection with the Adaptive Cosine/Coherence Estimator (ACE) algorithm. Here, we improve upon that methodology using a more rigorous, data-driven implementation of LLE that incorporates the injection of a cloud" of target pixels and the Spectral Angle Mapper (SAM) detector. The LLE algorithm, which holds that the data is locally linear, is typically governed by a user defined parameter k, indicating the number of nearest neighbors to use in the initial graph model. We use an adaptive approach to building the graph that is governed by the data itself and does not rely upon user input. This implementation of LLE can yield greater separation between the target pixels and the background pixels in the manifold space. We present an analysis of target detection performance in the manifold coordinates using scene-derived target spectra and laboratory-measured target spectra across two different data sets.

  10. Invariant bandwidth of erbium in ZnO-PbO-tellurite glasses: Local probe/model

    SciTech Connect

    Ramamoorthy, Raj Kumar; Bhatnagar, Anil K.

    2014-04-24

    A series of [(70TeO{sub 2}−(30−x)ZnO−xPbO){sub 0.99}−(Er{sub 2}O{sub 3}){sub 0.01}; where x = 5, 10, 15 and 20] tellurite glasses, were prepared using the melt quenching technique. Crucial emission bandwidth of erbium at 1.5 μm has been derived and found to be the same for all the glasses, irrespective of PbO content. This identical bandwidth in all tellurite glasses is attributed to the presence of erbium in tellurium rich disordered environments. This result has been complemented through XANES spectra and the obtained invariant first shell of 6.5 oxygen atoms, confirm the unchanged environment in these glasses for all PbO content.

  11. Impossible Graphs.

    ERIC Educational Resources Information Center

    Noble, Tracy; And Others

    Graphs without a time axis, such as velocity-versus-position graphs, offer interesting possibilities for exploring graphing and motion. Relations depicted by these graphs are not limited to functions. Interviews with a high school student named Olivia, who uses a motion detector to create such graphs, indicate that she uses thought experiments as…

  12. Adaptive weighted local textural features for illumination, expression, and occlusion invariant face recognition

    NASA Astrophysics Data System (ADS)

    Cui, Chen; Asari, Vijayan K.

    2014-03-01

    Biometric features such as fingerprints, iris patterns, and face features help to identify people and restrict access to secure areas by performing advanced pattern analysis and matching. Face recognition is one of the most promising biometric methodologies for human identification in a non-cooperative security environment. However, the recognition results obtained by face recognition systems are a affected by several variations that may happen to the patterns in an unrestricted environment. As a result, several algorithms have been developed for extracting different facial features for face recognition. Due to the various possible challenges of data captured at different lighting conditions, viewing angles, facial expressions, and partial occlusions in natural environmental conditions, automatic facial recognition still remains as a difficult issue that needs to be resolved. In this paper, we propose a novel approach to tackling some of these issues by analyzing the local textural descriptions for facial feature representation. The textural information is extracted by an enhanced local binary pattern (ELBP) description of all the local regions of the face. The relationship of each pixel with respect to its neighborhood is extracted and employed to calculate the new representation. ELBP reconstructs a much better textural feature extraction vector from an original gray level image in different lighting conditions. The dimensionality of the texture image is reduced by principal component analysis performed on each local face region. Each low dimensional vector representing a local region is now weighted based on the significance of the sub-region. The weight of each sub-region is determined by employing the local variance estimate of the respective region, which represents the significance of the region. The final facial textural feature vector is obtained by concatenating the reduced dimensional weight sets of all the modules (sub-regions) of the face image

  13. Rotational speed invariant fault diagnosis in bearings using vibration signal imaging and local binary patterns.

    PubMed

    Khan, Sheraz Ali; Kim, Jong-Myon

    2016-04-01

    Structural vibrations of bearing housings are used for diagnosing fault conditions in bearings, primarily by searching for characteristic fault frequencies in the envelope power spectrum of the vibration signal. The fault frequencies depend on the non-stationary angular speed of the rotating shaft. This paper explores an imaging-based approach to achieve rotational speed independence. Cycle length segments of the rectified vibration signal are stacked to construct grayscale images which exhibit unique textures for each fault. These textures show insignificant variation with the rotational speed, which is confirmed by the classification results using their local binary pattern histograms. PMID:27106344

  14. Robust Eye Center Localization through Face Alignment and Invariant Isocentric Patterns

    PubMed Central

    Teng, Dongdong; Chen, Dihu; Tan, Hongzhou

    2015-01-01

    The localization of eye centers is a very useful cue for numerous applications like face recognition, facial expression recognition, and the early screening of neurological pathologies. Several methods relying on available light for accurate eye-center localization have been exploited. However, despite the considerable improvements that eye-center localization systems have undergone in recent years, only few of these developments deal with the challenges posed by the profile (non-frontal face). In this paper, we first use the explicit shape regression method to obtain the rough location of the eye centers. Because this method extracts global information from the human face, it is robust against any changes in the eye region. We exploit this robustness and utilize it as a constraint. To locate the eye centers accurately, we employ isophote curvature features, the accuracy of which has been demonstrated in a previous study. By applying these features, we obtain a series of eye-center locations which are candidates for the actual position of the eye-center. Among these locations, the estimated locations which minimize the reconstruction error between the two methods mentioned above are taken as the closest approximation for the eye centers locations. Therefore, we combine explicit shape regression and isophote curvature feature analysis to achieve robustness and accuracy, respectively. In practical experiments, we use BioID and FERET datasets to test our approach to obtaining an accurate eye-center location while retaining robustness against changes in scale and pose. In addition, we apply our method to non-frontal faces to test its robustness and accuracy, which are essential in gaze estimation but have seldom been mentioned in previous works. Through extensive experimentation, we show that the proposed method can achieve a significant improvement in accuracy and robustness over state-of-the-art techniques, with our method ranking second in terms of accuracy

  15. Coloring random graphs.

    PubMed

    Mulet, R; Pagnani, A; Weigt, M; Zecchina, R

    2002-12-23

    We study the graph coloring problem over random graphs of finite average connectivity c. Given a number q of available colors, we find that graphs with low connectivity admit almost always a proper coloring, whereas graphs with high connectivity are uncolorable. Depending on q, we find the precise value of the critical average connectivity c(q). Moreover, we show that below c(q) there exists a clustering phase c in [c(d),c(q)] in which ground states spontaneously divide into an exponential number of clusters and where the proliferation of metastable states is responsible for the onset of complexity in local search algorithms. PMID:12484862

  16. New Invariants in the Theory of Knots.

    ERIC Educational Resources Information Center

    Kauffman, Louis H.

    1988-01-01

    A diagrammatic approach to invariants of knots is the focus. Connections with graph theory, physics, and other topics are included, along with an explanation of how proofs of some old conjectures about alternating knots emerge from this work. (MNS)

  17. Higher-order graph wavelets and sparsity on circulant graphs

    NASA Astrophysics Data System (ADS)

    Kotzagiannidis, Madeleine S.; Dragotti, Pier Luigi

    2015-08-01

    The notion of a graph wavelet gives rise to more advanced processing of data on graphs due to its ability to operate in a localized manner, across newly arising data-dependency structures, with respect to the graph signal and underlying graph structure, thereby taking into consideration the inherent geometry of the data. In this work, we tackle the problem of creating graph wavelet filterbanks on circulant graphs for a sparse representation of certain classes of graph signals. The underlying graph can hereby be data-driven as well as fixed, for applications including image processing and social network theory, whereby clusters can be modelled as circulant graphs, respectively. We present a set of novel graph wavelet filter-bank constructions, which annihilate higher-order polynomial graph signals (up to a border effect) defined on the vertices of undirected, circulant graphs, and are localised in the vertex domain. We give preliminary results on their performance for non-linear graph signal approximation and denoising. Furthermore, we provide extensions to our previously developed segmentation-inspired graph wavelet framework for non-linear image approximation, by incorporating notions of smoothness and vanishing moments, which further improve performance compared to traditional methods.

  18. On designing heteroclinic networks from graphs

    NASA Astrophysics Data System (ADS)

    Ashwin, Peter; Postlethwaite, Claire

    2013-12-01

    Robust heteroclinic networks are invariant sets that can appear as attractors in symmetrically coupled or otherwise constrained dynamical systems. These networks may have a complicated structure determined to a large extent by the constraints and dimension of the system. As these networks are of great interest as dynamical models of biological and cognitive processes, it is useful to understand how particular directed graphs can be realised as attracting robust heteroclinic networks between states in phase space. This paper presents two methods of realising arbitrarily complex directed graphs as robust heteroclinic networks for flows generated by ODEs-we say the ODEs realise the graphs as heteroclinic networks between equilibria that represent the vertices. Suppose we have a directed graph on nv vertices with ne edges. The “simplex realisation” embeds the graph as an invariant set of a flow on an (nv-1)-simplex. This method realises the graph as long as it is one- and two-cycle free. The “cylinder realisation” embeds a graph as an invariant set of a flow on a (ne+1)-dimensional space. This method realises the graph as long as it is one-cycle free. In both cases we realise the graph as an invariant set within an attractor, and discuss some illustrative examples, including the influence of noise and parameters on the dynamics. In particular we show that the resulting heteroclinic network may or may not display “memory” of the vertices visited.

  19. Continuous-time quantum walks on star graphs

    SciTech Connect

    Salimi, S.

    2009-06-15

    In this paper, we investigate continuous-time quantum walk on star graphs. It is shown that quantum central limit theorem for a continuous-time quantum walk on star graphs for N-fold star power graph, which are invariant under the quantum component of adjacency matrix, converges to continuous-time quantum walk on K{sub 2} graphs (complete graph with two vertices) and the probability of observing walk tends to the uniform distribution.

  20. [Local population of Eritrichium caucasicum as an object of mathematical modelling. I. Life cycle graph and a nonautonomous matrix model].

    PubMed

    Logofet, D O; Belova, I N; Kazantseva, E S; Onipchenko, V G

    2016-01-01

    For the plant species, which is considered a short-lived perennial, we have composed a scale of ontogenetic stages and the life cycle graph (LCG) according to annual observations on permanent sample plots in an Alpine lichen heath during the 2009-2014 period. The LCG that reflects seed reproduction has been reduced to the one that avoids the stage of soil seed bank, yet preserves the arcs of annual recruitment. The corresponding matrix model of stage-structured population dynamics has four stages: juvenile plants (including seedlings), virginal, generative, and 'terminally generative' (the plants die after seed production). Model calibration reduces to directly calculating the rates of transition between stages and those of delays within stages from the data of only one time step, while keeping the two reproduction rates uncertain, yet confined to the quantitative bounds of observed recruitment. This has enabled us to determine a feasible range for the dominant eigenvalue of the model matrix, i.e., the quantitative bounds for the measure of how the local population adapts to its environment, at each of the five time steps, resulting in aformally nonautonomous model. To obtain 'age-specific parameters' from a stage-classified model, we have applied the technique that constructs a virtual absorbing Markov chain and calculates its fundamental matrix. In a nonautonomous model, the estimates of life expectancy also depend on the time of observation (that fixes certain environmental conditions), and vary from two to nearly seven years. The estimates reveal how specifically short lives the short-lived perennial, while their range motivates the task to average the model matrices over the whole period of observation. The model indicates that Eritrichium caucasicum plants spend the most part of their life span in the virginal stage under each of the environment conditions observed, thus revealing the place retention strategy by C. K6rner (2003), or the delayed

  1. Potential energy surface fitting by a statistically localized, permutationally invariant, local interpolating moving least squares method for the many-body potential: Method and application to N{sub 4}

    SciTech Connect

    Bender, Jason D.; Doraiswamy, Sriram; Candler, Graham V. E-mail: candler@aem.umn.edu; Truhlar, Donald G. E-mail: candler@aem.umn.edu

    2014-02-07

    Fitting potential energy surfaces to analytic forms is an important first step for efficient molecular dynamics simulations. Here, we present an improved version of the local interpolating moving least squares method (L-IMLS) for such fitting. Our method has three key improvements. First, pairwise interactions are modeled separately from many-body interactions. Second, permutational invariance is incorporated in the basis functions, using permutationally invariant polynomials in Morse variables, and in the weight functions. Third, computational cost is reduced by statistical localization, in which we statistically correlate the cutoff radius with data point density. We motivate our discussion in this paper with a review of global and local least-squares-based fitting methods in one dimension. Then, we develop our method in six dimensions, and we note that it allows the analytic evaluation of gradients, a feature that is important for molecular dynamics. The approach, which we call statistically localized, permutationally invariant, local interpolating moving least squares fitting of the many-body potential (SL-PI-L-IMLS-MP, or, more simply, L-IMLS-G2), is used to fit a potential energy surface to an electronic structure dataset for N{sub 4}. We discuss its performance on the dataset and give directions for further research, including applications to trajectory calculations.

  2. Index statistical properties of sparse random graphs

    NASA Astrophysics Data System (ADS)

    Metz, F. L.; Stariolo, Daniel A.

    2015-10-01

    Using the replica method, we develop an analytical approach to compute the characteristic function for the probability PN(K ,λ ) that a large N ×N adjacency matrix of sparse random graphs has K eigenvalues below a threshold λ . The method allows to determine, in principle, all moments of PN(K ,λ ) , from which the typical sample-to-sample fluctuations can be fully characterized. For random graph models with localized eigenvectors, we show that the index variance scales linearly with N ≫1 for |λ |>0 , with a model-dependent prefactor that can be exactly calculated. Explicit results are discussed for Erdös-Rényi and regular random graphs, both exhibiting a prefactor with a nonmonotonic behavior as a function of λ . These results contrast with rotationally invariant random matrices, where the index variance scales only as lnN , with an universal prefactor that is independent of λ . Numerical diagonalization results confirm the exactness of our approach and, in addition, strongly support the Gaussian nature of the index fluctuations.

  3. Graph Structure-Based Simultaneous Localization and Mapping Using a Hybrid Method of 2D Laser Scan and Monocular Camera Image in Environments with Laser Scan Ambiguity

    PubMed Central

    Oh, Taekjun; Lee, Donghwa; Kim, Hyungjin; Myung, Hyun

    2015-01-01

    Localization is an essential issue for robot navigation, allowing the robot to perform tasks autonomously. However, in environments with laser scan ambiguity, such as long corridors, the conventional SLAM (simultaneous localization and mapping) algorithms exploiting a laser scanner may not estimate the robot pose robustly. To resolve this problem, we propose a novel localization approach based on a hybrid method incorporating a 2D laser scanner and a monocular camera in the framework of a graph structure-based SLAM. 3D coordinates of image feature points are acquired through the hybrid method, with the assumption that the wall is normal to the ground and vertically flat. However, this assumption can be relieved, because the subsequent feature matching process rejects the outliers on an inclined or non-flat wall. Through graph optimization with constraints generated by the hybrid method, the final robot pose is estimated. To verify the effectiveness of the proposed method, real experiments were conducted in an indoor environment with a long corridor. The experimental results were compared with those of the conventional GMappingapproach. The results demonstrate that it is possible to localize the robot in environments with laser scan ambiguity in real time, and the performance of the proposed method is superior to that of the conventional approach. PMID:26151203

  4. Graph Structure-Based Simultaneous Localization and Mapping Using a Hybrid Method of 2D Laser Scan and Monocular Camera Image in Environments with Laser Scan Ambiguity.

    PubMed

    Oh, Taekjun; Lee, Donghwa; Kim, Hyungjin; Myung, Hyun

    2015-01-01

    Localization is an essential issue for robot navigation, allowing the robot to perform tasks autonomously. However, in environments with laser scan ambiguity, such as long corridors, the conventional SLAM (simultaneous localization and mapping) algorithms exploiting a laser scanner may not estimate the robot pose robustly. To resolve this problem, we propose a novel localization approach based on a hybrid method incorporating a 2D laser scanner and a monocular camera in the framework of a graph structure-based SLAM. 3D coordinates of image feature points are acquired through the hybrid method, with the assumption that the wall is normal to the ground and vertically flat. However, this assumption can be relieved, because the subsequent feature matching process rejects the outliers on an inclined or non-flat wall. Through graph optimization with constraints generated by the hybrid method, the final robot pose is estimated. To verify the effectiveness of the proposed method, real experiments were conducted in an indoor environment with a long corridor. The experimental results were compared with those of the conventional GMappingapproach. The results demonstrate that it is possible to localize the robot in environments with laser scan ambiguity in real time, and the performance of the proposed method is superior to that of the conventional approach. PMID:26151203

  5. Image deblurring based structural graph and nonlocal similarity regularization

    NASA Astrophysics Data System (ADS)

    Jiang, Fangfang; Chen, Huahua; Ye, Xueyi

    2013-07-01

    The distribution of image data points forms its geometrical structure. This structure characterizes the local variation, and provides valuable heuristics to the regularization of image restoration process. However, most of the existing approaches to sparse coding fail to consider this character of the image. In this paper, we address the deblurring problem of image restoration. We analyze the distribution of the input data points. Inspired by the theory of manifold learning algorithm, we build a k-NN graph to character the geometrical structure of the data, so the local manifold structure of the data can be explicitly taken into account. To enforce the invariance constraint, we introduce a patch-similarity based term into the cost function which penalizes the nonlocal invariance of the image. Experimental results have shown the effectiveness of the proposed scheme.

  6. Graphing Predictions

    ERIC Educational Resources Information Center

    Connery, Keely Flynn

    2007-01-01

    Graphing predictions is especially important in classes where relationships between variables need to be explored and derived. In this article, the author describes how his students sketch the graphs of their predictions before they begin their investigations on two laboratory activities: Distance Versus Time Cart Race Lab and Resistance; and…

  7. Measuring polynomial invariants of multiparty quantum states

    SciTech Connect

    Leifer, M.S.; Linden, N.; Winter, A.

    2004-05-01

    We present networks for directly estimating the polynomial invariants of multiparty quantum states under local transformations. The structure of these networks is closely related to the structure of the invariants themselves and this lends a physical interpretation to these otherwise abstract mathematical quantities. Specifically, our networks estimate the invariants under local unitary (LU) transformations and under stochastic local operations and classical communication (SLOCC). Our networks can estimate the LU invariants for multiparty states, where each party can have a Hilbert space of arbitrary dimension and the SLOCC invariants for multiqubit states. We analyze the statistical efficiency of our networks compared to methods based on estimating the state coefficients and calculating the invariants.

  8. A notion of graph likelihood and an infinite monkey theorem

    NASA Astrophysics Data System (ADS)

    Banerji, Christopher R. S.; Mansour, Toufik; Severini, Simone

    2014-01-01

    We play with a graph-theoretic analogue of the folklore infinite monkey theorem. We define a notion of graph likelihood as the probability that a given graph is constructed by a monkey in a number of time steps equal to the number of vertices. We present an algorithm to compute this graph invariant and closed formulas for some infinite classes. We have to leave the computational complexity of the likelihood as an open problem.

  9. Graph Theory

    SciTech Connect

    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.

  10. Algebraic distance on graphs.

    SciTech Connect

    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.

  11. Gauge invariants and bosonization

    NASA Astrophysics Data System (ADS)

    Kijowski, J.; Rudolph, G.; Rudolph, M.

    1998-12-01

    We present some results, which are part of our program of analyzing gauge theories with fermions in terms of local gauge invariant fields. In a first part the classical Dirac-Maxwell system is discussed. Next we develop a procedure which leads to a reduction of the functional integral to an integral over (bosonic) gauge invariant fields. We apply this procedure to the case of QED and the Schwinger model. In a third part we go some steps towards an analysis of the considered models. We construct effective (quantum) field theories which can be used to calculate vacuum expectation values of physical quantities.

  12. Graph-based surface extraction of the liver using locally adaptive priors for multimodal interventional image registration

    NASA Astrophysics Data System (ADS)

    Kadoury, Samuel; Wood, Bradford J.; Venkatesan, Aradhana M.; Ardon, Roberto; Jago, James; Kruecker, Jochen

    2012-02-01

    The 3D fusion of tracked ultrasound with a diagnostic CT image has multiple benefits in a variety of interventional applications for oncology. Still, manual registration is a considerable drawback to the clinical workflow and hinders the widespread clinical adoption of this technique. In this paper, we propose a method to allow for an image-based automated registration, aligning multimodal images of the liver. We adopt a model-based approach that rigidly matches segmented liver shapes from ultrasound (U/S) and diagnostic CT imaging. Towards this end, a novel method which combines a dynamic region-growing method with a graph-based segmentation framework is introduced to address the challenging problem of liver segmentation from U/S. The method is able to extract liver boundary from U/S images after a partial surface is generated near the principal vector from an electromagnetically tracked U/S liver sweep. The liver boundary is subsequently expanded by modeling the problem as a graph-cut minimization scheme, where cost functions used to detect optimal surface topology are determined from adaptive priors of neighboring surface points. This allows including boundaries affected by shadow areas by compensating for varying levels of contrast. The segmentation of the liver surface is performed in 3D space for increased accuracy and robustness. The method was evaluated in a study involving 8 patients undergoing biopsy or radiofrequency ablation of the liver, yielding promising surface segmentation results based on ground-truth comparison. The proposed extended segmentation technique improved the fiducial landmark registration error compared to a point-based registration (7.2mm vs. 10.2mm on average, respectively), while achieving tumor target registration errors that are statistically equivalent (p > 0.05) to state-of-the-art methods.

  13. Inverse scattering problem for quantum graph vertices

    SciTech Connect

    Cheon, Taksu; Turek, Ondrej; Exner, Pavel

    2011-06-15

    We demonstrate how the inverse scattering problem of a quantum star graph can be solved by means of diagonalization of the Hermitian unitary matrix when the vertex coupling is of the scale-invariant (or Fueloep-Tsutsui) form. This enables the construction of quantum graphs with desired properties in a tailor-made fashion. The procedure is illustrated on the example of quantum vertices with equal transmission probabilities.

  14. Graphing Reality

    NASA Astrophysics Data System (ADS)

    Beeken, Paul

    2014-11-01

    Graphing is an essential skill that forms the foundation of any physical science.1 Understanding the relationships between measurements ultimately determines which modeling equations are successful in predicting observations.2 Over the years, science and math teachers have approached teaching this skill with a variety of techniques. For secondary school instruction, the job of graphing skills falls heavily on physics teachers. By virtue of the nature of the topics we cover, it is our mission to develop this skill to the fine art that it is.

  15. Tractors, mass, and Weyl invariance

    NASA Astrophysics Data System (ADS)

    Gover, A. R.; Shaukat, A.; Waldron, A.

    2009-05-01

    Deser and Nepomechie established a relationship between masslessness and rigid conformal invariance by coupling to a background metric and demanding local Weyl invariance, a method which applies neither to massive theories nor theories which rely upon gauge invariances for masslessness. We extend this method to describe massive and gauge invariant theories using Weyl invariance. The key idea is to introduce a new scalar field which is constant when evaluated at the scale corresponding to the metric of physical interest. This technique relies on being able to efficiently construct Weyl invariant theories. This is achieved using tractor calculus—a mathematical machinery designed for the study of conformal geometry. From a physics standpoint, this amounts to arranging fields in multiplets with respect to the conformal group but with novel Weyl transformation laws. Our approach gives a mechanism for generating masses from Weyl weights. Breitenlohner-Freedman stability bounds for Anti-de Sitter theories arise naturally as do direct derivations of the novel Weyl invariant theories given by Deser and Nepomechie. In constant curvature spaces, partially massless theories—which rely on the interplay between mass and gauge invariance—are also generated by our method. Another simple consequence is conformal invariance of the maximal depth partially massless theories. Detailed examples for spins s⩽2 are given including tractor and component actions, on-shell and off-shell approaches and gauge invariances. For all spins s⩾2 we give tractor equations of motion unifying massive, massless, and partially massless theories.

  16. SLOCC invariants for multipartite mixed states

    NASA Astrophysics Data System (ADS)

    Jing, Naihuan; Li, Ming; Li-Jost, Xianqing; Zhang, Tinggui; Fei, Shao-Ming

    2014-05-01

    We construct a nontrivial set of invariants for any multipartite mixed states under the stochastic local operations and classical communication symmetry. These invariants are given by hyperdeterminants and independent of basis change. In particular, a family of d2 invariants for arbitrary d-dimensional even partite mixed states are explicitly given.

  17. Graphing Reality

    ERIC Educational Resources Information Center

    Beeken, Paul

    2014-01-01

    Graphing is an essential skill that forms the foundation of any physical science. Understanding the relationships between measurements ultimately determines which modeling equations are successful in predicting observations. Over the years, science and math teachers have approached teaching this skill with a variety of techniques. For secondary…

  18. The Role of Hepatic Invariant (I)NKT Cells in Systemic/Local Inflammation and Mortality During Polymicrobial Septic Shock1

    PubMed Central

    Hu, Caroline K.; Venet, Fabienne; Heffernan, David S.; Wang, Yvonne L.; Horner, Brian; Huang, Xin; Chung, Chun-Shiang; Gregory, Stephen H.; Ayala, Alfred

    2009-01-01

    Natural killer T (NKT)4 cells have been described as “innate regulatory cells” because of their rapid response to conserved glycolipids presented on CD1d via their invariant TCR. However, little is known about the contribution of the hepatic NKT cell to the development of a local and/or systemic immune response to acute septic challenge (cecal ligation & puncture; CLP). We found not only that mice deficient in invariant [i] NKT cells (Jα18 -/-) had a marked attenuation in CLP induced mortality, but also exhibited an oblation of the systemic inflammatory response (with little effect on splenic/ peritoneal immune responsiveness). Flow cytometric data indicated that following CLP, there was a marked decline in the % of CD3+αGalCer-CD1d-tetramer+ cells in the mouse C57BL/6J and Balb/c liver non-parenchymal cell population. This was associated with the marked activation of these cells (increased expression of CD69 and CD25) as well as a rise in the frequency of NKT cells positive for both Th1 and Th2 intracellular cytokines. In this respect, when mice were pre-treated in vivo with anti-CD1d blocking antibody we observed not only that this inhibited the systemic rise of IL-6 and IL-10 levels in septic mice and improved overall septic survival, but that the CLP induced changes in liver macrophage IL-6 and IL-10 expressions were inversely effected by this treatment. Together, these findings suggest that the activation of hepatic iNKT cells plays a critical role in regulating the innate immune/ systemic inflammatory response and survival in a model of acute septic shock. PMID:19201902

  19. Tight Lower Bound for Percolation Threshold on an Infinite Graph

    NASA Astrophysics Data System (ADS)

    Hamilton, Kathleen E.; Pryadko, Leonid P.

    2014-11-01

    We construct a tight lower bound for the site percolation threshold on an infinite graph, which becomes exact for an infinite tree. The bound is given by the inverse of the maximal eigenvalue of the Hashimoto matrix used to count nonbacktracking walks on the original graph. Our bound always exceeds the inverse spectral radius of the graph's adjacency matrix, and it is also generally tighter than the existing bound in terms of the maximum degree. We give a constructive proof for existence of such an eigenvalue in the case of a connected infinite quasitransitive graph, a graph-theoretic analog of a translationally invariant system.

  20. Influence of Third Invariant of Deviatoric Stress and Intermediate Principal Stress on Constitutive Models and Localization Conditions for High Porosity Sandstone

    NASA Astrophysics Data System (ADS)

    Challa, V.

    2015-12-01

    High porosity sandstone (HPS) is observed to fail, in field and laboratory settings, by the formation of localized bands. Bands perpendicular to the direction of the minimum principal stress (σIII), with pure compactant strain, are defined as compaction bands. Dilation bands form parallel to the σIII direction, with pure dilatant strain. Shear bands form at an angle to the σIII direction and have shear strain, with either compactant or dilatant strain normal to the band. Recent experimental evidence indicates that the behavior of HPS depends on the third stress invariant (J3) since it yields at a lower stress in extension, compared to loading under compression. In this work, existing constitutive models, which depend only on two stress invariants, were modified and new constitutive models, which incorporate the J3 dependence, were developed. Band orientation predictions were determined using the Rudnicki and Rice (1975) bifurcation theory. While HPS are typically tested under axisymmetric (AS) stress states in the laboratory, in the field non-AS states are more likely. The stress state is characterized by the intermediate principal stress (σII). Therefore, to investigate the influence of σIII on band orientation predictions, localization conditions were determined for non-AS stress states. The AS stress states are specialized cases where the dependence on J3 is inconsequential. Incorporating the J3 dependence significantly influenced localization conditions for stress states perturbed from AS compression, while the influence was small for stress states perturbed from AS extension. Under non-AS stress states, when a single yield surface constitutive model is appropriate, including the J3 dependence typically inhibits band formation, due to strongly negative critical hardening modulus (hcr). For load paths where a two yield surface constitutive model is applicable, with J3 dependence, shear bands were predicted. Compaction bands and dilation bands were predicted

  1. Graph models of habitat mosaics.

    PubMed

    Urban, Dean L; Minor, Emily S; Treml, Eric A; Schick, Robert S

    2009-03-01

    Graph theory is a body of mathematics dealing with problems of connectivity, flow, and routing in networks ranging from social groups to computer networks. Recently, network applications have erupted in many fields, and graph models are now being applied in landscape ecology and conservation biology, particularly for applications couched in metapopulation theory. In these applications, graph nodes represent habitat patches or local populations and links indicate functional connections among populations (i.e. via dispersal). Graphs are models of more complicated real systems, and so it is appropriate to review these applications from the perspective of modelling in general. Here we review recent applications of network theory to habitat patches in landscape mosaics. We consider (1) the conceptual model underlying these applications; (2) formalization and implementation of the graph model; (3) model parameterization; (4) model testing, insights, and predictions available through graph analyses; and (5) potential implications for conservation biology and related applications. In general, and for a variety of ecological systems, we find the graph model a remarkably robust framework for applications concerned with habitat connectivity. We close with suggestions for further work on the parameterization and validation of graph models, and point to some promising analytic insights. PMID:19161432

  2. Generalized graph states based on Hadamard matrices

    SciTech Connect

    Cui, Shawn X.; Yu, Nengkun; Zeng, Bei

    2015-07-15

    Graph states are widely used in quantum information theory, including entanglement theory, quantum error correction, and one-way quantum computing. Graph states have a nice structure related to a certain graph, which is given by either a stabilizer group or an encoding circuit, both can be directly given by the graph. To generalize graph states, whose stabilizer groups are abelian subgroups of the Pauli group, one approach taken is to study non-abelian stabilizers. In this work, we propose to generalize graph states based on the encoding circuit, which is completely determined by the graph and a Hadamard matrix. We study the entanglement structures of these generalized graph states and show that they are all maximally mixed locally. We also explore the relationship between the equivalence of Hadamard matrices and local equivalence of the corresponding generalized graph states. This leads to a natural generalization of the Pauli (X, Z) pairs, which characterizes the local symmetries of these generalized graph states. Our approach is also naturally generalized to construct graph quantum codes which are beyond stabilizer codes.

  3. Subgraph-Based Filterbanks for Graph Signals

    NASA Astrophysics Data System (ADS)

    Tremblay, Nicolas; Borgnat, Pierre

    2016-08-01

    We design a critically-sampled compact-support biorthogonal transform for graph signals, via graph filterbanks. Instead of partitioning the nodes in two sets so as to remove one every two nodes in the filterbank downsampling operations, the design is based on a partition of the graph in connected subgraphs. Coarsening is achieved by defining one "supernode" for each subgraph and the edges for this coarsened graph derives from the connectivity between the subgraphs. Unlike the "one every two nodes" downsampling on bipartite graphs, this coarsening operation does not have an exact formulation in the graph Fourier domain. Instead, we rely on the local Fourier bases of each subgraph to define filtering operations. We apply successfully this method to decompose graph signals, and show promising performance on compression and denoising.

  4. Homotopy invariance of η-invariants

    PubMed Central

    Weinberger, Shmuel

    1988-01-01

    Intersection homology and results related to the higher signature problem are applied to show that certain combinations of η-invariants of the signature operator are homotopy invariant in various circumstances. PMID:16593961

  5. Graph anomalies in cyber communications

    SciTech Connect

    Vander Wiel, Scott A; Storlie, Curtis B; Sandine, Gary; Hagberg, Aric A; Fisk, Michael

    2011-01-11

    Enterprises monitor cyber traffic for viruses, intruders and stolen information. Detection methods look for known signatures of malicious traffic or search for anomalies with respect to a nominal reference model. Traditional anomaly detection focuses on aggregate traffic at central nodes or on user-level monitoring. More recently, however, traffic is being viewed more holistically as a dynamic communication graph. Attention to the graph nature of the traffic has expanded the types of anomalies that are being sought. We give an overview of several cyber data streams collected at Los Alamos National Laboratory and discuss current work in modeling the graph dynamics of traffic over the network. We consider global properties and local properties within the communication graph. A method for monitoring relative entropy on multiple correlated properties is discussed in detail.

  6. Possible universal quantum algorithms for generalized Turaev-Viro invariants

    NASA Astrophysics Data System (ADS)

    Vélez, Mario; Ospina, Juan

    2011-05-01

    An emergent trend in quantum computation is the topological quantum computation (TQC). Briefly, TQC results from the application of quantum computation with the aim to solve the problems of quantum topology such as topological invariants for knots and links (Jones polynomials, HOMFLY polynomials, Khovanov polynomials); topological invariants for graphs (Tutte polynomial and Bollobás-Riordan polynomial); topological invariants for 3-manifolds (Reshetiskin-Turaev, Turaev-Viro and Turaer-Viro-Ocneanu invariants) and topological invariants for 4-manifolds( Crane-Yetter invariants). In a few words, TQC is concerned with the formulation of quantum algorithms for the computation of these topological invariants in quantum topology. Given that one of the fundamental achievements of quantum topology was the discovery of strong connections between monoidal categories and 3-dimensional manifolds, in TQC is possible and necessary to exploit such connections with the purpose to formulate universal quantum algorithms for topological invariants of 3-manifolds. In the present work we make an exploration of such possibilities. Specifically we search for universal quantum algorithms for generalized Turaev-Viro invariants of 3-manifolds such as the Turaev-Viro-Ocneanu invariants, the Kashaev-Baseilhac-Benedetti invariants of 3-manifolds with links and the Geer-Kashaev-Turaev invariants of 3-manifolds with a link and a principal bundle. We also look for physical systems (three dimensional topological insulators and three-dimensional gravity) over which implement the resulting universal topological quantum algorithms.

  7. Stereo Vision By Pyramidal Bli Graph Matching

    NASA Astrophysics Data System (ADS)

    Shen, Jun; Castan, Serge; Zhao, Jian

    1988-04-01

    We propose the pyramidal BLI (Binary Laplacian Image) graph matching method for stereo vision, which uses the local as well as the global similarities to assure a good precision of matching results and to eliminate the ambiguities. Because the BLI is detected by DRF method which has a fast realization and matching between graphs is fast, a pseudo-real time system is possible.

  8. Graphing Polar Curves

    ERIC Educational Resources Information Center

    Lawes, Jonathan F.

    2013-01-01

    Graphing polar curves typically involves a combination of three traditional techniques, all of which can be time-consuming and tedious. However, an alternative method--graphing the polar function on a rectangular plane--simplifies graphing, increases student understanding of the polar coordinate system, and reinforces graphing techniques learned…

  9. Graphing for Any Grade.

    ERIC Educational Resources Information Center

    Nibbelink, William

    1982-01-01

    An instructional sequence for teaching graphing that has been extensively field tested in kindergarten through grade six is detailed. The material begins with point graphs, employs a movable y-axis to begin with minimal clutter, and has graphs constructed before reading graphs is required. (MP)

  10. Path Separability of Graphs

    NASA Astrophysics Data System (ADS)

    Diot, Emilie; Gavoille, Cyril

    In this paper we investigate the structural properties of k-path separable graphs, that are the graphs that can be separated by a set of k shortest paths. We identify several graph families having such path separability, and we show that this property is closed under minor taking. In particular we establish a list of forbidden minors for 1-path separable graphs.

  11. Laplacian Estrada and normalized Laplacian Estrada indices of evolving graphs.

    PubMed

    Shang, Yilun

    2015-01-01

    Large-scale time-evolving networks have been generated by many natural and technological applications, posing challenges for computation and modeling. Thus, it is of theoretical and practical significance to probe mathematical tools tailored for evolving networks. In this paper, on top of the dynamic Estrada index, we study the dynamic Laplacian Estrada index and the dynamic normalized Laplacian Estrada index of evolving graphs. Using linear algebra techniques, we established general upper and lower bounds for these graph-spectrum-based invariants through a couple of intuitive graph-theoretic measures, including the number of vertices or edges. Synthetic random evolving small-world networks are employed to show the relevance of the proposed dynamic Estrada indices. It is found that neither the static snapshot graphs nor the aggregated graph can approximate the evolving graph itself, indicating the fundamental difference between the static and dynamic Estrada indices. PMID:25822506

  12. Laplacian Estrada and Normalized Laplacian Estrada Indices of Evolving Graphs

    PubMed Central

    Shang, Yilun

    2015-01-01

    Large-scale time-evolving networks have been generated by many natural and technological applications, posing challenges for computation and modeling. Thus, it is of theoretical and practical significance to probe mathematical tools tailored for evolving networks. In this paper, on top of the dynamic Estrada index, we study the dynamic Laplacian Estrada index and the dynamic normalized Laplacian Estrada index of evolving graphs. Using linear algebra techniques, we established general upper and lower bounds for these graph-spectrum-based invariants through a couple of intuitive graph-theoretic measures, including the number of vertices or edges. Synthetic random evolving small-world networks are employed to show the relevance of the proposed dynamic Estrada indices. It is found that neither the static snapshot graphs nor the aggregated graph can approximate the evolving graph itself, indicating the fundamental difference between the static and dynamic Estrada indices. PMID:25822506

  13. Gauge theories in terms of invariants

    NASA Astrophysics Data System (ADS)

    Kijowski, J.; Rudolph, G.; Rudolph, M.

    1997-12-01

    We discuss some aspects of our programme of investigating gauge theories (with fermions) in terms of local gauge invariant quantities. In the first part, the functional integral for quantum electrodynamics is discussed within our formulation. Next, the algebra of Grassmann algebra-valued invariants for one-flavour chromodynamics is investigated and, finally, the functional integral for this theory is derived within our framework.

  14. Multipartite invariant states. I. Unitary symmetry

    SciTech Connect

    Chruscinski, Dariusz; Kossakowski, Andrzej

    2006-06-15

    We propose a natural generalization of bipartite Werner and isotropic states to multipartite systems consisting of an arbitrary even number of d-dimensional subsystems (qudits). These generalized states are invariant under the action of local unitary operations. We study basic properties of multipartite invariant states and present necessary and sufficient separability criteria.

  15. Encoding the core electrons with graph concepts.

    PubMed

    Pogliani, Lionello

    2004-01-01

    The core electron problem of atoms in chemical graph studies has always been considered as a minor problem. Usually, chemical graphs had to encode just a small set of second row atoms, i.e., C, N, O, and F, thus, graph and, in some cases, pseudograph concepts were enough to "graph" encode the molecules at hand. Molecular connectivity theory, together with its side-branch the electrotopological state, introduced two "ad hoc" algorithms for the core electrons of higher-row atoms based, mainly, on quantum concepts alike. Recently, complete graphs, and, especially, odd complete graphs have been introduced to encode the core electrons of higher-row atoms. By the aid of these types of graphs a double-valued algorithm has been proposed for the valence delta, deltav, of any type of atoms of the periodic table with a principal quantum number n > or =2. The new algorithm is centered on an invariant suggested by the hand-shaking theorem, and the values it gives rise to parallel in some way the values derived by the aid of the two old "quantum" algorithms. A thorough comparative analysis of the newly proposed algorithms has been undertaken for atoms of the group 1A-7A of the periodic table. This comparative study includes the electronegativity, the size of the atoms, the first ionization energy, and the electron affinity. The given algorithm has also been tested with sequential complete graphs, while the even complete graphs give rise to conceptual difficulties. QSAR/QSPR studies do not show a clear-cut preference for any of the two values the algorithm gives rise to, even if recent results seem to prefer one of the two values. PMID:14741009

  16. Quantum graph as a quantum spectral filter

    SciTech Connect

    Turek, Ondrej; Cheon, Taksu

    2013-03-15

    We study the transmission of a quantum particle along a straight input-output line to which a graph {Gamma} is attached at a point. In the point of contact we impose a singularity represented by a certain properly chosen scale-invariant coupling with a coupling parameter {alpha}. We show that the probability of transmission along the line as a function of the particle energy tends to the indicator function of the energy spectrum of {Gamma} as {alpha}{yields}{infinity}. This effect can be used for a spectral analysis of the given graph {Gamma}. Its applications include a control of a transmission along the line and spectral filtering. The result is illustrated with an example where {Gamma} is a loop exposed to a magnetic field. Two more quantum devices are designed using other special scale-invariant vertex couplings. They can serve as a band-stop filter and as a spectral separator, respectively.

  17. Quantum snake walk on graphs

    SciTech Connect

    Rosmanis, Ansis

    2011-02-15

    I introduce a continuous-time quantum walk on graphs called the quantum snake walk, the basis states of which are fixed-length paths (snakes) in the underlying graph. First, I analyze the quantum snake walk on the line, and I show that, even though most states stay localized throughout the evolution, there are specific states that most likely move on the line as wave packets with momentum inversely proportional to the length of the snake. Next, I discuss how an algorithm based on the quantum snake walk might potentially be able to solve an extended version of the glued trees problem, which asks to find a path connecting both roots of the glued trees graph. To the best of my knowledge, no efficient quantum algorithm solving this problem is known yet.

  18. Generalizing twisted gauge invariance

    SciTech Connect

    Duenas-Vidal, Alvaro; Vazquez-Mozo, Miguel A.

    2009-05-01

    We discuss the twisting of gauge symmetry in noncommutative gauge theories and show how this can be generalized to a whole continuous family of twisted gauge invariances. The physical relevance of these twisted invariances is discussed.

  19. Invariant turbulence models

    NASA Astrophysics Data System (ADS)

    Bihlo, Alexander; Dos Santos Cardoso-Bihlo, Elsa Maria; Nave, Jean-Christophe; Popovych, Roman

    2012-11-01

    Various subgrid-scale closure models break the invariance of the Euler or Navier-Stokes equations and thus violate the geometric structure of these equations. A method is shown which allows one to systematically derive invariant turbulence models starting from non-invariant turbulence models and thus to correct artificial symmetry-breaking. The method is illustrated by finding invariant hyperdiffusion schemes to be applied in the two-dimensional turbulence problem.

  20. Multi-A Graph Patrolling and Partitioning

    NASA Astrophysics Data System (ADS)

    Elor, Y.; Bruckstein, A. M.

    2012-12-01

    We introduce a novel multi agent patrolling algorithm inspired by the behavior of gas filled balloons. Very low capability ant-like agents are considered with the task of patrolling an unknown area modeled as a graph. While executing the proposed algorithm, the agents dynamically partition the graph between them using simple local interactions, every agent assuming the responsibility for patrolling his subgraph. Balanced graph partition is an emergent behavior due to the local interactions between the agents in the swarm. Extensive simulations on various graphs (environments) showed that the average time to reach a balanced partition is linear with the graph size. The simulations yielded a convincing argument for conjecturing that if the graph being patrolled contains a balanced partition, the agents will find it. However, we could not prove this. Nevertheless, we have proved that if a balanced partition is reached, the maximum time lag between two successive visits to any vertex using the proposed strategy is at most twice the optimal so the patrol quality is at least half the optimal. In case of weighted graphs the patrol quality is at least (1)/(2){lmin}/{lmax} of the optimal where lmax (lmin) is the longest (shortest) edge in the graph.

  1. Computation of Open Gromov-Witten Invariants for Toric Calabi-Yau 3-Folds by Topological Recursion, a Proof of the BKMP Conjecture

    NASA Astrophysics Data System (ADS)

    Eynard, B.; Orantin, N.

    2015-07-01

    The BKMP conjecture (2006-2008) proposed a new method to compute closed and open Gromov-Witten invariants for every toric Calabi-Yau 3-folds, through a topological recursion based on mirror symmetry. So far, this conjecture has been verified to low genus for several toric CY3folds, and proved to all genus only for . In this article we prove the general case. Our proof is based on the fact that both sides of the conjecture can be naturally written in terms of combinatorial sums of weighted graphs: on the A-model side this is the localization formula, and on the B-model side the graphs encode the recursive algorithm of the topological recursion. One can slightly reorganize the set of graphs obtained in the B-side, so that it coincides with the one obtained by localization in the A-model. Then it suffices to compare the weights of vertices and edges of graphs on each side, which is done in two steps: the weights coincide in the large radius limit, due to the fact that the toric graph is the tropical limit of the mirror curve. Then the derivatives with respect to Kähler radius coincide due to the special geometry property implied by the topological recursion.

  2. Are Graphs Finally Surfacing?

    ERIC Educational Resources Information Center

    Beineke, Lowell W.

    1989-01-01

    Explored are various aspects of drawing graphs on surfaces. The Euler's formula, Kuratowski's theorem and the drawing of graphs in the plane with as few crossings as possible are discussed. Some applications including embedding of graphs and coloring of maps are included. (YP)

  3. Graphing Important People

    ERIC Educational Resources Information Center

    Reading Teacher, 2012

    2012-01-01

    The "Toolbox" column features content adapted from ReadWriteThink.org lesson plans and provides practical tools for classroom teachers. This issue's column features a lesson plan adapted from "Graphing Plot and Character in a Novel" by Lisa Storm Fink and "Bio-graph: Graphing Life Events" by Susan Spangler. Students retell biographic events…

  4. Graphing Inequalities, Connecting Meaning

    ERIC Educational Resources Information Center

    Switzer, J. Matt

    2014-01-01

    Students often have difficulty with graphing inequalities (see Filloy, Rojano, and Rubio 2002; Drijvers 2002), and J. Matt Switzer's students were no exception. Although students can produce graphs for simple inequalities, they often struggle when the format of the inequality is unfamiliar. Even when producing a correct graph of an…

  5. Graph-Plotting Routine

    NASA Technical Reports Server (NTRS)

    Kantak, Anil V.

    1987-01-01

    Plotter routine for IBM PC (AKPLOT) designed for engineers and scientists who use graphs as integral parts of their documentation. Allows user to generate graph and edit its appearance on cathode-ray tube. Graph may undergo many interactive alterations before finally dumped from screen to be plotted by printer. Written in BASIC.

  6. An Integrated Ransac and Graph Based Mismatch Elimination Approach for Wide-Baseline Image Matching

    NASA Astrophysics Data System (ADS)

    Hasheminasab, M.; Ebadi, H.; Sedaghat, A.

    2015-12-01

    In this paper we propose an integrated approach in order to increase the precision of feature point matching. Many different algorithms have been developed as to optimizing the short-baseline image matching while because of illumination differences and viewpoints changes, wide-baseline image matching is so difficult to handle. Fortunately, the recent developments in the automatic extraction of local invariant features make wide-baseline image matching possible. The matching algorithms which are based on local feature similarity principle, using feature descriptor as to establish correspondence between feature point sets. To date, the most remarkable descriptor is the scale-invariant feature transform (SIFT) descriptor , which is invariant to image rotation and scale, and it remains robust across a substantial range of affine distortion, presence of noise, and changes in illumination. The epipolar constraint based on RANSAC (random sample consensus) method is a conventional model for mismatch elimination, particularly in computer vision. Because only the distance from the epipolar line is considered, there are a few false matches in the selected matching results based on epipolar geometry and RANSAC. Aguilariu et al. proposed Graph Transformation Matching (GTM) algorithm to remove outliers which has some difficulties when the mismatched points surrounded by the same local neighbor structure. In this study to overcome these limitations, which mentioned above, a new three step matching scheme is presented where the SIFT algorithm is used to obtain initial corresponding point sets. In the second step, in order to reduce the outliers, RANSAC algorithm is applied. Finally, to remove the remained mismatches, based on the adjacent K-NN graph, the GTM is implemented. Four different close range image datasets with changes in viewpoint are utilized to evaluate the performance of the proposed method and the experimental results indicate its robustness and capability.

  7. Experimental Study of Quantum Graphs with Microwave Networks

    NASA Astrophysics Data System (ADS)

    Fu, Ziyuan; Koch, Trystan; Antonsen, Thomas; Ott, Edward; Anlage, Steven; Wave Chaos Team

    An experimental setup consisting of microwave networks is used to simulate quantum graphs. The networks are constructed from coaxial cables connected by T junctions. The networks are built for operation both at room temperature and superconducting versions that operate at cryogenic temperatures. In the experiments, a phase shifter is connected to one of the network bonds to generate an ensemble of quantum graphs by varying the phase delay. The eigenvalue spectrum is found from S-parameter measurements on one-port graphs. With the experimental data, the nearest-neighbor spacing statistics and the impedance statistics of the graphs are examined. It is also demonstrated that time-reversal invariance for microwave propagation in the graphs can be broken without increasing dissipation significantly by making nodes with circulators. Random matrix theory (RMT) successfully describes universal statistical properties of the system. We acknowledge support under contract AFOSR COE Grant FA9550-15-1-0171.

  8. Methods of visualizing graphs

    DOEpatents

    Wong, Pak C.; Mackey, Patrick S.; Perrine, Kenneth A.; Foote, Harlan P.; Thomas, James J.

    2008-12-23

    Methods for visualizing a graph by automatically drawing elements of the graph as labels are disclosed. In one embodiment, the method comprises receiving node information and edge information from an input device and/or communication interface, constructing a graph layout based at least in part on that information, wherein the edges are automatically drawn as labels, and displaying the graph on a display device according to the graph layout. In some embodiments, the nodes are automatically drawn as labels instead of, or in addition to, the label-edges.

  9. Horizontal visibility graphs generated by type-I intermittency

    NASA Astrophysics Data System (ADS)

    Núñez, Ángel M.; Luque, Bartolo; Lacasa, Lucas; Gómez, Jose Patricio; Robledo, Alberto

    2013-05-01

    The type-I intermittency route to (or out of) chaos is investigated within the horizontal visibility (HV) graph theory. For that purpose, we address the trajectories generated by unimodal maps close to an inverse tangent bifurcation and construct their associated HV graphs. We show how the alternation of laminar episodes and chaotic bursts imprints a fingerprint in the resulting graph structure. Accordingly, we derive a phenomenological theory that predicts quantitative values for several network parameters. In particular, we predict that the characteristic power-law scaling of the mean length of laminar trend sizes is fully inherited by the variance of the graph degree distribution, in good agreement with the numerics. We also report numerical evidence on how the characteristic power-law scaling of the Lyapunov exponent as a function of the distance to the tangent bifurcation is inherited in the graph by an analogous scaling of block entropy functionals defined on the graph. Furthermore, we are able to recast the full set of HV graphs generated by intermittent dynamics into a renormalization-group framework, where the fixed points of its graph-theoretical renormalization-group flow account for the different types of dynamics. We also establish that the nontrivial fixed point of this flow coincides with the tangency condition and that the corresponding invariant graph exhibits extremal entropic properties.

  10. Horizontal visibility graphs generated by type-I intermittency.

    PubMed

    Núñez, Ángel M; Luque, Bartolo; Lacasa, Lucas; Gómez, Jose Patricio; Robledo, Alberto

    2013-05-01

    The type-I intermittency route to (or out of) chaos is investigated within the horizontal visibility (HV) graph theory. For that purpose, we address the trajectories generated by unimodal maps close to an inverse tangent bifurcation and construct their associated HV graphs. We show how the alternation of laminar episodes and chaotic bursts imprints a fingerprint in the resulting graph structure. Accordingly, we derive a phenomenological theory that predicts quantitative values for several network parameters. In particular, we predict that the characteristic power-law scaling of the mean length of laminar trend sizes is fully inherited by the variance of the graph degree distribution, in good agreement with the numerics. We also report numerical evidence on how the characteristic power-law scaling of the Lyapunov exponent as a function of the distance to the tangent bifurcation is inherited in the graph by an analogous scaling of block entropy functionals defined on the graph. Furthermore, we are able to recast the full set of HV graphs generated by intermittent dynamics into a renormalization-group framework, where the fixed points of its graph-theoretical renormalization-group flow account for the different types of dynamics. We also establish that the nontrivial fixed point of this flow coincides with the tangency condition and that the corresponding invariant graph exhibits extremal entropic properties. PMID:23767578

  11. Hyperbolic graph generator

    NASA Astrophysics Data System (ADS)

    Aldecoa, Rodrigo; Orsini, Chiara; Krioukov, Dmitri

    2015-11-01

    Networks representing many complex systems in nature and society share some common structural properties like heterogeneous degree distributions and strong clustering. Recent research on network geometry has shown that those real networks can be adequately modeled as random geometric graphs in hyperbolic spaces. In this paper, we present a computer program to generate such graphs. Besides real-world-like networks, the program can generate random graphs from other well-known graph ensembles, such as the soft configuration model, random geometric graphs on a circle, or Erdős-Rényi random graphs. The simulations show a good match between the expected values of different network structural properties and the corresponding empirical values measured in generated graphs, confirming the accurate behavior of the program.

  12. Reconstruction of Graph Signals Through Percolation from Seeding Nodes

    NASA Astrophysics Data System (ADS)

    Segarra, Santiago; Marques, Antonio G.; Leus, Geert; Ribeiro, Alejandro

    2016-08-01

    New schemes to recover signals defined in the nodes of a graph are proposed. Our focus is on reconstructing bandlimited graph signals, which are signals that admit a sparse representation in a frequency domain related to the structure of the graph. Most existing formulations focus on estimating an unknown graph signal by observing its value on a subset of nodes. By contrast, in this paper, we study the problem of reconstructing a known graph signal using as input a graph signal that is non-zero only for a small subset of nodes (seeding nodes). The sparse signal is then percolated (interpolated) across the graph using a graph filter. Graph filters are a generalization of classical time-invariant systems and represent linear transformations that can be implemented distributedly across the nodes of the graph. Three setups are investigated. In the first one, a single simultaneous injection takes place on several nodes in the graph. In the second one, successive value injections take place on a single node. The third one is a generalization where multiple nodes inject multiple signal values. For noiseless settings, conditions under which perfect reconstruction is feasible are given, and the corresponding schemes to recover the desired signal are specified. Scenarios leading to imperfect reconstruction, either due to insufficient or noisy signal value injections, are also analyzed. Moreover, connections with classical interpolation in the time domain are discussed. The last part of the paper presents numerical experiments that illustrate the results developed through synthetic graph signals and two real-world signal reconstruction problems: influencing opinions in a social network and inducing a desired brain state in humans.

  13. Topologies on directed graphs

    NASA Technical Reports Server (NTRS)

    Lieberman, R. N.

    1972-01-01

    Given a directed graph, a natural topology is defined and relationships between standard topological properties and graph theoretical concepts are studied. In particular, the properties of connectivity and separatedness are investigated. A metric is introduced which is shown to be related to separatedness. The topological notions of continuity and homeomorphism. A class of maps is studied which preserve both graph and topological properties. Applications involving strong maps and contractions are also presented.

  14. Graph Generator Survey

    SciTech Connect

    Lothian, Josh; Powers, Sarah S; Sullivan, Blair D; Baker, Matthew B; Schrock, Jonathan; Poole, Stephen W

    2013-12-01

    The benchmarking effort within the Extreme Scale Systems Center at Oak Ridge National Laboratory seeks to provide High Performance Computing benchmarks and test suites of interest to the DoD sponsor. The work described in this report is a part of the effort focusing on graph generation. A previously developed benchmark, SystemBurn, allowed the emulation of dierent application behavior profiles within a single framework. To complement this effort, similar capabilities are desired for graph-centric problems. This report examines existing synthetic graph generator implementations in preparation for further study on the properties of their generated synthetic graphs.

  15. mpiGraph

    Energy Science and Technology Software Center (ESTSC)

    2007-05-22

    MpiGraph consists of an MPI application called mpiGraph written in C to measure message bandwidth and an associated crunch_mpiGraph script written in Perl to process the application output into an HTMO report. The mpiGraph application is designed to inspect the health and scalability of a high-performance interconnect while under heavy load. This is useful to detect hardware and software problems in a system, such as slow nodes, links, switches, or contention in switch routing. Itmore » is also useful to characterize how interconnect performance changes with different settings or how one interconnect type compares to another.« less

  16. mpiGraph

    SciTech Connect

    Moody, Adam

    2007-05-22

    MpiGraph consists of an MPI application called mpiGraph written in C to measure message bandwidth and an associated crunch_mpiGraph script written in Perl to process the application output into an HTMO report. The mpiGraph application is designed to inspect the health and scalability of a high-performance interconnect while under heavy load. This is useful to detect hardware and software problems in a system, such as slow nodes, links, switches, or contention in switch routing. It is also useful to characterize how interconnect performance changes with different settings or how one interconnect type compares to another.

  17. 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.

  18. Graph-Based Inter-Subject Pattern Analysis of fMRI Data

    PubMed Central

    Takerkart, Sylvain; Auzias, Guillaume; Thirion, Bertrand; Ralaivola, Liva

    2014-01-01

    In brain imaging, solving learning problems in multi-subjects settings is difficult because of the differences that exist across individuals. Here we introduce a novel classification framework based on group-invariant graphical representations, allowing to overcome the inter-subject variability present in functional magnetic resonance imaging (fMRI) data and to perform multivariate pattern analysis across subjects. Our contribution is twofold: first, we propose an unsupervised representation learning scheme that encodes all relevant characteristics of distributed fMRI patterns into attributed graphs; second, we introduce a custom-designed graph kernel that exploits all these characteristics and makes it possible to perform supervised learning (here, classification) directly in graph space. The well-foundedness of our technique and the robustness of the performance to the parameter setting are demonstrated through inter-subject classification experiments conducted on both artificial data and a real fMRI experiment aimed at characterizing local cortical representations. Our results show that our framework produces accurate inter-subject predictions and that it outperforms a wide range of state-of-the-art vector- and parcel-based classification methods. Moreover, the genericity of our method makes it is easily adaptable to a wide range of potential applications. The dataset used in this study and an implementation of our framework are available at http://dx.doi.org/10.6084/m9.figshare.1086317. PMID:25127129

  19. Graphs, matrices, and the GraphBLAS: Seven good reasons

    SciTech Connect

    Kepner, Jeremy; Bader, David; Buluç, Aydın; Gilbert, John; Mattson, Timothy; Meyerhenke, Henning

    2015-01-01

    The analysis of graphs has become increasingly important to a wide range of applications. Graph analysis presents a number of unique challenges in the areas of (1) software complexity, (2) data complexity, (3) security, (4) mathematical complexity, (5) theoretical analysis, (6) serial performance, and (7) parallel performance. Implementing graph algorithms using matrix-based approaches provides a number of promising solutions to these challenges. The GraphBLAS standard (istcbigdata.org/GraphBlas) is being developed to bring the potential of matrix based graph algorithms to the broadest possible audience. The GraphBLAS mathematically defines a core set of matrix-based graph operations that can be used to implement a wide class of graph algorithms in a wide range of programming environments. This paper provides an introduction to the GraphBLAS and describes how the GraphBLAS can be used to address many of the challenges associated with analysis of graphs.

  20. Graphs, matrices, and the GraphBLAS: Seven good reasons

    DOE PAGESBeta

    Kepner, Jeremy; Bader, David; Buluç, Aydın; Gilbert, John; Mattson, Timothy; Meyerhenke, Henning

    2015-01-01

    The analysis of graphs has become increasingly important to a wide range of applications. Graph analysis presents a number of unique challenges in the areas of (1) software complexity, (2) data complexity, (3) security, (4) mathematical complexity, (5) theoretical analysis, (6) serial performance, and (7) parallel performance. Implementing graph algorithms using matrix-based approaches provides a number of promising solutions to these challenges. The GraphBLAS standard (istcbigdata.org/GraphBlas) is being developed to bring the potential of matrix based graph algorithms to the broadest possible audience. The GraphBLAS mathematically defines a core set of matrix-based graph operations that can be used to implementmore » a wide class of graph algorithms in a wide range of programming environments. This paper provides an introduction to the GraphBLAS and describes how the GraphBLAS can be used to address many of the challenges associated with analysis of graphs.« less

  1. Fault-tolerant dynamic task graph scheduling

    SciTech Connect

    Kurt, Mehmet C.; Krishnamoorthy, Sriram; Agrawal, Kunal; Agrawal, Gagan

    2014-11-16

    In this paper, we present an approach to fault tolerant execution of dynamic task graphs scheduled using work stealing. In particular, we focus on selective and localized recovery of tasks in the presence of soft faults. We elicit from the user the basic task graph structure in terms of successor and predecessor relationships. The work stealing-based algorithm to schedule such a task graph is augmented to enable recovery when the data and meta-data associated with a task get corrupted. We use this redundancy, and the knowledge of the task graph structure, to selectively recover from faults with low space and time overheads. We show that the fault tolerant design retains the essential properties of the underlying work stealing-based task scheduling algorithm, and that the fault tolerant execution is asymptotically optimal when task re-execution is taken into account. Experimental evaluation demonstrates the low cost of recovery under various fault scenarios.

  2. Graphing Electric Potential.

    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)

  3. Exploring Graphs: WYSIWYG.

    ERIC Educational Resources Information Center

    Johnson, Millie

    1997-01-01

    Graphs from media sources and questions developed from them can be used in the middle school mathematics classroom. Graphs depict storage temperature on a milk carton; air pressure measurements on a package of shock absorbers; sleep-wake patterns of an infant; a dog's breathing patterns; and the angle, velocity, and radius of a leaning bicyclist…

  4. Making "Photo" Graphs

    ERIC Educational Resources Information Center

    Doto, Julianne; Golbeck, Susan

    2007-01-01

    Collecting data and analyzing the results of experiments is difficult for children. The authors found a surprising way to help their third graders make graphs and draw conclusions from their data: digital photographs. The pictures bridged the gap between an abstract graph and the plants it represented. With the support of the photos, students…

  5. Reflections on "The Graph"

    ERIC Educational Resources Information Center

    Petrosino, Anthony

    2012-01-01

    This article responds to arguments by Skidmore and Thompson (this issue of "Educational Researcher") that a graph published more than 10 years ago was erroneously reproduced and "gratuitously damaged" perceptions of the quality of education research. After describing the purpose of the original graph, the author counters assertions that the graph…

  6. Real World Graph Connectivity

    ERIC Educational Resources Information Center

    Lind, Joy; Narayan, Darren

    2009-01-01

    We present the topic of graph connectivity along with a famous theorem of Menger in the real-world setting of the national computer network infrastructure of "National LambdaRail". We include a set of exercises where students reinforce their understanding of graph connectivity by analysing the "National LambdaRail" network. Finally, we give…

  7. Walking Out Graphs

    ERIC Educational Resources Information Center

    Shen, Ji

    2009-01-01

    In the Walking Out Graphs Lesson described here, students experience several types of representations used to describe motion, including words, sentences, equations, graphs, data tables, and actions. The most important theme of this lesson is that students have to understand the consistency among these representations and form the habit of…

  8. ACTIVITIES: Graphs and Games

    ERIC Educational Resources Information Center

    Hirsch, Christian R.

    1975-01-01

    Using a set of worksheets, students will discover and apply Euler's formula regarding connected planar graphs and play and analyze the game of Sprouts. One sheet leads to the discovery of Euler's formula; another concerns traversability of a graph; another gives an example and a game involving these ideas. (Author/KM)

  9. Let's Do It: Making Graphs.

    ERIC Educational Resources Information Center

    Shaw, Jean M.

    1984-01-01

    Reasons for having students make graphs are noted. Then specific graphing topics and materials appropriate for young learners are presented, including life-sized, floor, clothespin, felt-face, block, and magnetic graphs, and polls of pupils. (MNS)

  10. Evolutionary stability on graphs

    PubMed Central

    Ohtsuki, Hisashi; Nowak, Martin A.

    2008-01-01

    Evolutionary stability is a fundamental concept in evolutionary game theory. A strategy is called an evolutionarily stable strategy (ESS), if its monomorphic population rejects the invasion of any other mutant strategy. Recent studies have revealed that population structure can considerably affect evolutionary dynamics. Here we derive the conditions of evolutionary stability for games on graphs. We obtain analytical conditions for regular graphs of degree k > 2. Those theoretical predictions are compared with computer simulations for random regular graphs and for lattices. We study three different update rules: birth-death (BD), death-birth (DB), and imitation (IM) updating. Evolutionary stability on sparse graphs does not imply evolutionary stability in a well-mixed population, nor vice versa. We provide a geometrical interpretation of the ESS condition on graphs. PMID:18295801

  11. Lorentz invariance with an invariant energy scale.

    PubMed

    Magueijo, João; Smolin, Lee

    2002-05-13

    We propose a modification of special relativity in which a physical energy, which may be the Planck energy, joins the speed of light as an invariant, in spite of a complete relativity of inertial frames and agreement with Einstein's theory at low energies. This is accomplished by a nonlinear modification of the action of the Lorentz group on momentum space, generated by adding a dilatation to each boost in such a way that the Planck energy remains invariant. The associated algebra has unmodified structure constants. We also discuss the resulting modifications of field theory and suggest a modification of the equivalence principle which determines how the new theory is embedded in general relativity. PMID:12005620

  12. Parallel (delta + 1) coloring of constant-degree graphs

    SciTech Connect

    Goldberg, A.V.; Plotkin, S.A.

    1986-12-01

    This paper presents parallel algorithms for coloring a constant-degree graph with a maximum degree of delta in (delta + 1) colors and for finding a maximal independent set in a constant-degree graph. Given a graph with n vertices, the algorithms run in O (lg*n) time on EREW PRAM with O(n) processors. The algorithms use only local communication and achieve the same complexity bounds when implemented in the distributed model of parallel computation.

  13. Quantum state representation based on combinatorial Laplacian matrix of star-relevant graph

    NASA Astrophysics Data System (ADS)

    Li, Jian-Qiang; Chen, Xiu-Bo; Yang, Yi-Xian

    2015-12-01

    In this paper the density matrices derived from combinatorial Laplacian matrix of graphs is considered. More specifically, the paper places emphasis on the star-relevant graph, which means adding certain edges on peripheral vertices of star graph. Initially, we provide the spectrum of the density matrices corresponding to star-like graph (i.e., adding an edge on star graph) and present that the Von Neumann entropy increases under the graph operation (adding an edge on star graph) and the graph operation cannot be simulated by local operation and classical communication (LOCC). Subsequently, we illustrate the spectrum of density matrices corresponding to star-alike graph (i.e., adding one edge on star-like graph) and exhibit that the Von Neumann entropy increases under the graph operation (adding an edge on star-like graph) and the graph operation cannot be simulated by LOCC. Finally, the spectrum of density matrices corresponding to star-mlike graph (i.e., adding m nonadjacent edges on the peripheral vertices of star graph) is demonstrated and the relation between the graph operation and Von Neumann entropy, LOCC is revealed in this paper.

  14. The Effect of Using Graphing Calculators in Complex Function Graphs

    ERIC Educational Resources Information Center

    Ocak, Mehmet Akif

    2008-01-01

    This study investigates the role of graphing calculators in multiple representations for knowledge transfer and the omission of oversimplification in complex function graphs. The main aim is to examine whether graphing calculators were used efficiently to see different cases and multiple perspectives among complex function graphs, or whether…

  15. A study on vague graphs.

    PubMed

    Rashmanlou, Hossein; Samanta, Sovan; Pal, Madhumangal; Borzooei, R A

    2016-01-01

    The main purpose of this paper is to introduce the notion of vague h-morphism on vague graphs and regular vague graphs. The action of vague h-morphism on vague strong regular graphs are studied. Some elegant results on weak and co weak isomorphism are derived. Also, [Formula: see text]-complement of highly irregular vague graphs are defined. PMID:27536517

  16. A Semantic Graph Query Language

    SciTech Connect

    Kaplan, I L

    2006-10-16

    Semantic graphs can be used to organize large amounts of information from a number of sources into one unified structure. A semantic query language provides a foundation for extracting information from the semantic graph. The graph query language described here provides a simple, powerful method for querying semantic graphs.

  17. Direct reciprocity on graphs

    PubMed Central

    Ohtsuki, Hisashi; Nowak, Martin A.

    2008-01-01

    Direct reciprocity is a mechanism for the evolution of cooperation based on the idea of repeated encounters between the same two individuals. Here we examine direct reciprocity in structured populations, where individuals occupy the vertices of a graph. The edges denote who interacts with whom. The graph represents spatial structure or a social network. For birth-death or pairwise comparison updating, we find that evolutionary stability of direct reciprocity is more restrictive on a graph than in a well-mixed population, but the condition for reciprocators to be advantageous is less restrictive on a graph. For death-birth and imitation updating, in contrast, both conditions are easier to fulfill on a graph. Moreover, for all four update mechanisms, reciprocators can dominate defectors on a graph, which is never possible in a well-mixed population. We also study the effect of an error rate, which increases with the number of links per individual; interacting with more people simultaneously enhances the probability of making mistakes. We provide analytic derivations for all results. PMID:17466339

  18. Commuting projections on graphs

    SciTech Connect

    Vassilevski, Panayot S.; Zikatanov, Ludmil T.

    2013-02-19

    For a given (connected) graph, we consider vector spaces of (discrete) functions defined on its vertices and its edges. These two spaces are related by a discrete gradient operator, Grad and its adjoint, ₋Div, referred to as (negative) discrete divergence. We also consider a coarse graph obtained by aggregation of vertices of the original one. Then a coarse vertex space is identified with the subspace of piecewise constant functions over the aggregates. We consider the ℓ2-projection QH onto the space of these piecewise constants. In the present paper, our main result is the construction of a projection π H from the original edge-space onto a properly constructed coarse edge-space associated with the edges of the coarse graph. The projections π H and QH commute with the discrete divergence operator, i.e., we have div π H = QH div. The respective pair of coarse edge-space and coarse vertexspace offer the potential to construct two-level, and by recursion, multilevel methods for the mixed formulation of the graph Laplacian which utilizes the discrete divergence operator. The performance of one two-level method with overlapping Schwarz smoothing and correction based on the constructed coarse spaces for solving such mixed graph Laplacian systems is illustrated on a number of graph examples.

  19. A new, analytic, non-perturbative, gauge-invariant formulation of realistic QCD

    SciTech Connect

    Fried, H. M.; Grandou, T.; Gabellini, Y.; Sheu, Y.-M.

    2012-09-26

    This Formulation [1], [2], [3] is New, in the sense that it is less than 3 years old. But it could have been done decades ago, since the input information existed, but was overlooked. It is Analytic in the sense that physically-reasonable approximations can be estimated with paper and pencil; and exact amplitudes can be calculated as Meijer G-functions of various orders. It is Non-Perturbative in the sense that sums over all possible gluon exchanges between any pair of quarks and/or antiquarks, including cubic and quartic gluon interactions, are exactly performed. These multiple gluon exchanges combine into 'Gluon Bundles' (GBs), as sums over Feynman graphs with finite numbers of exchanged gluons are replaced by {sup B}undle Graphs{sup .} In effect, gluons disappear from the formalism, and GBs remain as the effective carrier of all interactions between quark lines. A simple re-arrangement of the Schwinger/Symanzik functional solution for the Generating Functional of QCD - a rearrangement possible in QCD but not in QED - produces a formal statement of Gauge-Invariance, even though the formulation contains gauge-dependent gluon propagators. After the non-perturbative sums produce GBs, one sees explicit cancelation of all gauge-dependent gluon propagators; gauge-invariance is achieved as gauge-independence. A new insight into Realistic QCD appears in the non-perturbative domain, because quarks do not have individual asymptotic states; they are always asymptotically bound, and their transverse coordinates cannot, in principle, be measured exactly. 'Transverse Imprecision' is introduced into the basic Lagrangian, and quark-binding potentials for the construction of mesons and nucleons can then be defined and evaluated. And the greatest surprise of all: A new, non-perturbative property appears, called Effective Locality, with the result that all functional integrals reduce to (a few) sets of ordinary integrals, easy to estimate approximately, or calculate on a desk

  20. Clique graphs and overlapping communities

    NASA Astrophysics Data System (ADS)

    Evans, T. S.

    2010-12-01

    It is shown how to construct a clique graph in which properties of cliques of a fixed order in a given graph are represented by vertices in a weighted graph. Various definitions and motivations for these weights are given. The detection of communities or clusters is used to illustrate how a clique graph may be exploited. In particular a benchmark network is shown where clique graphs find the overlapping communities accurately while vertex partition methods fail.

  1. Reparametrization invariant collinear operators

    SciTech Connect

    Marcantonini, Claudio; Stewart, Iain W.

    2009-03-15

    In constructing collinear operators, which describe the production of energetic jets or energetic hadrons, important constraints are provided by reparametrization invariance (RPI). RPI encodes Lorentz invariance in a power expansion about a collinear direction, and connects the Wilson coefficients of operators at different orders in this expansion to all orders in {alpha}{sub s}. We construct reparametrization invariant collinear objects. The expansion of operators built from these objects provides an efficient way of deriving RPI relations and finding a minimal basis of operators, particularly when one has an observable with multiple collinear directions and/or soft particles. Complete basis of operators is constructed for pure glue currents at twist-4, and for operators with multiple collinear directions, including those appearing in e{sup +}e{sup -}{yields}3 jets, and for pp{yields}2 jets initiated via gluon fusion.

  2. Lattice invariants for knots

    SciTech Connect

    Janse Van Rensburg, E.J.

    1996-12-31

    The geometry of polygonal knots in the cubic lattice may be used to define some knot invariants. One such invariant is the minimal edge number, which is the minimum number of edges necessary (and sufficient) to construct a lattice knot of given type. In addition, one may also define the minimal (unfolded) surface number, and the minimal (unfolded) boundary number; these are the minimum number of 2-cells necessary to construct an unfolded lattice Seifert surface of a given knot type in the lattice, and the minimum number of edges necessary in a lattice knot to guarantee the existence of an unfolded lattice Seifert surface. In addition, I derive some relations amongst these invariants. 8 refs., 5 figs., 2 tabs.

  3. Invariance in vowel systems.

    PubMed

    Funabashi, Masatoshi

    2015-05-01

    This study applies information geometry of normal distribution to model Japanese vowels on the basis of the first and second formants. The distribution of Kullback-Leibler (KL) divergence and its decomposed components were investigated to reveal the statistical invariance in the vowel system. The results suggest that although significant variability exists in individual KL divergence distributions, the population distribution tends to converge into a specific log-normal distribution. This distribution can be considered as an invariant distribution for the standard-Japanese speaking population. Furthermore, it was revealed that the mean and variance components of KL divergence are linearly related in the population distribution. The significance of these invariant features is discussed. PMID:25994716

  4. Scale invariance in biophysics

    NASA Astrophysics Data System (ADS)

    Stanley, H. Eugene

    2000-06-01

    In this general talk, we offer an overview of some problems of interest to biophysicists, medical physicists, and econophysicists. These include DNA sequences, brain plaques in Alzheimer patients, heartbeat intervals, and time series giving price fluctuations in economics. These problems have the common feature that they exhibit features that appear to be scale invariant. Particularly vexing is the problem that some of these scale invariant phenomena are not stationary-their statistical properties vary from one time interval to the next or form one position to the next. We will discuss methods, such as wavelet methods and multifractal methods, to cope with these problems. .

  5. Multipartite invariant states. II. Orthogonal symmetry

    SciTech Connect

    Chruscinski, Dariusz; Kossakowski, Andrzej

    2006-06-15

    We construct a class of multipartite states possessing orthogonal symmetry. This new class contains multipartite states which are invariant under the action of local unitary operations introduced in our preceding paper [Phys. Rev. A 73, 062314 (2006)]. We study basic properties of multipartite symmetric states: separability criteria and multi-PPT conditions.

  6. BRST invariance in Coulomb gauge QCD

    NASA Astrophysics Data System (ADS)

    Andraši, A.; Taylor, J. C.

    2015-12-01

    In the Coulomb gauge, the Hamiltonian of QCD contains terms of order ħ2, identified by Christ and Lee, which are non-local but instantaneous. The question is addressed how do these terms fit in with BRST invariance. Our discussion is confined to the simplest, O(g4) , example.

  7. GraphPrints: Towards a Graph Analytic Method for Network Anomaly Detection

    SciTech Connect

    Harshaw, Chris R; Bridges, Robert A; Iannacone, Michael D; Reed, Joel W; Goodall, John R

    2016-01-01

    This paper introduces a novel graph-analytic approach for detecting anomalies in network flow data called \\textit{GraphPrints}. Building on foundational network-mining techniques, our method represents time slices of traffic as a graph, then counts graphlets\\textemdash small induced subgraphs that describe local topology. By performing outlier detection on the sequence of graphlet counts, anomalous intervals of traffic are identified, and furthermore, individual IPs experiencing abnormal behavior are singled-out. Initial testing of GraphPrints is performed on real network data with an implanted anomaly. Evaluation shows false positive rates bounded by 2.84\\% at the time-interval level, and 0.05\\% at the IP-level with 100\\% true positive rates at both.

  8. A combinatorial approach to diffeomorphism invariant quantum gauge theories

    SciTech Connect

    Zapata, J.A.

    1997-11-01

    Quantum gauge theory in the connection representation uses functions of holonomies as configuration observables. Physical observables (gauge and diffeomorphism invariant) are represented in the Hilbert space of physical states; physical states are gauge and diffeomorphism invariant distributions on the space of functions of the holonomies of the edges of a certain family of graphs. Then a family of graphs embedded in the space manifold (satisfying certain properties) induces a representation of the algebra of physical observables. We construct a quantum model from the set of piecewise linear graphs on a piecewise linear manifold, and another manifestly combinatorial model from graphs defined on a sequence of increasingly refined simplicial complexes. Even though the two models are different at the kinematical level, they provide unitarily equivalent representations of the algebra of physical observables in {ital separable} Hilbert spaces of physical states (their s-knot basis is countable). Hence, the combinatorial framework is compatible with the usual interpretation of quantum field theory. {copyright} {ital 1997 American Institute of Physics.}

  9. Rotation-invariant nonrigid point set matching in cluttered scenes.

    PubMed

    Lian, Wei; Zhang, Lei; Zhang, David

    2012-05-01

    This paper addresses the problem of rotation-invariant nonrigid point set matching. The shape context (SC) feature descriptor is used because of its strong discriminative nature, whereas edges in the graphs constructed by point sets are used to determine the orientations of SCs. Similar to lengths or directions, oriented SCs constructed this way can be regarded as attributes of edges. By matching edges between two point sets, rotation invariance is achieved. Two novel ways of constructing graphs on a model point set are proposed, aiming at making the orientations of SCs as robust to disturbances as possible. The structures of these graphs facilitate the use of dynamic programming (DP) for optimization. The strong discriminative nature of SC, the special structure of the model graphs, and the global optimality of DP make our methods robust to various types of disturbances, particularly clutters. The extensive experiments on both synthetic and real data validated the robustness of the proposed methods to various types of disturbances. They can robustly detect the desired shapes in complex and highly cluttered scenes. PMID:22514129

  10. Global surpluses of spin-base invariant fermions

    NASA Astrophysics Data System (ADS)

    Gies, Holger; Lippoldt, Stefan

    2015-04-01

    The spin-base invariant formalism of Dirac fermions in curved space maintains the essential symmetries of general covariance as well as similarity transformations of the Clifford algebra. We emphasize the advantages of the spin-base invariant formalism both from a conceptual as well as from a practical viewpoint. This suggests that local spin-base invariance should be added to the list of (effective) properties of (quantum) gravity theories. We find support for this viewpoint by the explicit construction of a global realization of the Clifford algebra on a 2-sphere which is impossible in the spin-base non-invariant vielbein formalism.

  11. ASK-GraphView: A large scale graph visualization system.

    PubMed

    Abello, James; van Ham, Frank; Krishnan, Neeraj

    2006-01-01

    We describe ASK-GraphView, a node-link-based graph visualization system that allows clustering and interactive navigation of large graphs, ranging in size up to 16 million edges. The system uses a scalable architecture and a series of increasingly sophisticated clustering algorithms to construct a hierarchy on an arbitrary, weighted undirected input graph. By lowering the interactivity requirements we can scale to substantially bigger graphs. The user is allowed to navigate this hierarchy in a top down manner by interactively expanding individual clusters. ASK-GraphView also provides facilities for filtering and coloring, annotation and cluster labeling. PMID:17080786

  12. New Graph Calculi for Planar Non-3-Colorable Graphs

    NASA Astrophysics Data System (ADS)

    Hanatani, Yoichi; Horiyama, Takashi; Iwama, Kazuo; Tamaki, Suguru

    The Hajós calculus is a nondeterministic procedure which generates the class of non-3-colorable graphs. If all non-3-colorable graphs can be constructed in polynomial steps by the calculus, then NP=co-NP holds. Up to date, however, it remains open whether there exists a family of graphs that cannot be generated in polynomial steps. To attack this problem, we propose two graph calculi PHC and PHC* that generate non-3-colorable planar graphs, where intermediate graphs in the calculi are also restricted to be planar. Then we prove that PHC and PHC* are sound and complete. We also show that PHC* can polynomially simulate PHC.

  13. Graphing. USMES Beginning "How To" Set.

    ERIC Educational Resources Information Center

    Agro, Sally; And Others

    In this set of eight booklets on graphing, primary grade students learn how to choose which graph to make and how to make a bar graph, bar graph histogram, conversion graph, line chart, line graph, scatter graph, and slope diagram. The major emphasis in all Unified Sciences and Mathematics for Elementary Schools (USMES) units is on open-ended,…

  14. From cognitive maps to cognitive graphs.

    PubMed

    Chrastil, Elizabeth R; Warren, William H

    2014-01-01

    We investigate the structure of spatial knowledge that spontaneously develops during free exploration of a novel environment. We present evidence that this structure is similar to a labeled graph: a network of topological connections between places, labeled with local metric information. In contrast to route knowledge, we find that the most frequent routes and detours to target locations had not been traveled during learning. Contrary to purely topological knowledge, participants typically traveled the shortest metric distance to a target, rather than topologically equivalent but longer paths. The results are consistent with the proposal that people learn a labeled graph of their environment. PMID:25389769

  15. Modular invariant inflation

    NASA Astrophysics Data System (ADS)

    Kobayashi, Tatsuo; Nitta, Daisuke; Urakawa, Yuko

    2016-08-01

    Modular invariance is a striking symmetry in string theory, which may keep stringy corrections under control. In this paper, we investigate a phenomenological consequence of the modular invariance, assuming that this symmetry is preserved as well as in a four dimensional (4D) low energy effective field theory. As a concrete setup, we consider a modulus field T whose contribution in the 4D effective field theory remains invariant under the modular transformation and study inflation drived by T. The modular invariance restricts a possible form of the scalar potenntial. As a result, large field models of inflation are hardly realized. Meanwhile, a small field model of inflation can be still accomodated in this restricted setup. The scalar potential traced during the slow-roll inflation mimics the hilltop potential Vht, but it also has a non-negligible deviation from Vht. Detecting the primordial gravitational waves predicted in this model is rather challenging. Yet, we argue that it may be still possible to falsify this model by combining the information in the reheating process which can be determined self-completely in this setup.

  16. Idiographic Measurement Invariance?

    ERIC Educational Resources Information Center

    Willoughby, Michael T.; Sideris, John

    2007-01-01

    In this article, the authors comment on Nesselroade, Gerstorf, Hardy, and Ram's efforts (this issue) to grapple with the challenge of accommodating idiographic assessment as it pertains to measurement invariance (MI). Although the authors are in complete agreement with the motivation for Nesselroade et al.'s work, the authors have concerns about…

  17. Riemann quasi-invariants

    SciTech Connect

    Pokhozhaev, Stanislav I

    2011-06-30

    The notion of Riemann quasi-invariants is introduced and their applications to several conservation laws are considered. The case of nonisentropic flow of an ideal polytropic gas is analysed in detail. Sufficient conditions for gradient catastrophes are obtained. Bibliography: 16 titles.

  18. Invariant measures on multimode quantum Gaussian states

    SciTech Connect

    Lupo, C.; Mancini, S.; De Pasquale, A.; Facchi, P.; Florio, G.; Pascazio, S.

    2012-12-15

    We derive the invariant measure on the manifold of multimode quantum Gaussian states, induced by the Haar measure on the group of Gaussian unitary transformations. To this end, by introducing a bipartition of the system in two disjoint subsystems, we use a parameterization highlighting the role of nonlocal degrees of freedom-the symplectic eigenvalues-which characterize quantum entanglement across the given bipartition. A finite measure is then obtained by imposing a physically motivated energy constraint. By averaging over the local degrees of freedom we finally derive the invariant distribution of the symplectic eigenvalues in some cases of particular interest for applications in quantum optics and quantum information.

  19. Metric Ranking of Invariant Networks with Belief Propagation

    SciTech Connect

    Tao, Changxia; Ge, Yong; Song, Qinbao; Ge, Yuan; Omitaomu, Olufemi A

    2014-01-01

    The management of large-scale distributed information systems relies on the effective use and modeling of monitoring data collected at various points in the distributed information systems. A promising approach is to discover invariant relationships among the monitoring data and generate invariant networks, where a node is a monitoring data source (metric) and a link indicates an invariant relationship between two monitoring data. Such an invariant network representation can help system experts to localize and diagnose the system faults by examining those broken invariant relationships and their related metrics, because system faults usually propagate among the monitoring data and eventually lead to some broken invariant relationships. However, at one time, there are usually a lot of broken links (invariant relationships) within an invariant network. Without proper guidance, it is difficult for system experts to manually inspect this large number of broken links. Thus, a critical challenge is how to effectively and efficiently rank metrics (nodes) of invariant networks according to the anomaly levels of metrics. The ranked list of metrics will provide system experts with useful guidance for them to localize and diagnose the system faults. To this end, we propose to model the nodes and the broken links as a Markov Random Field (MRF), and develop an iteration algorithm to infer the anomaly of each node based on belief propagation (BP). Finally, we validate the proposed algorithm on both realworld and synthetic data sets to illustrate its effectiveness.

  20. Graph ranking for exploratory gene data analysis

    PubMed Central

    2009-01-01

    Background Microarray technology has made it possible to simultaneously monitor the expression levels of thousands of genes in a single experiment. However, the large number of genes greatly increases the challenges of analyzing, comprehending and interpreting the resulting mass of data. Selecting a subset of important genes is inevitable to address the challenge. Gene selection has been investigated extensively over the last decade. Most selection procedures, however, are not sufficient for accurate inference of underlying biology, because biological significance does not necessarily have to be statistically significant. Additional biological knowledge needs to be integrated into the gene selection procedure. Results We propose a general framework for gene ranking. We construct a bipartite graph from the Gene Ontology (GO) and gene expression data. The graph describes the relationship between genes and their associated molecular functions. Under a species condition, edge weights of the graph are assigned to be gene expression level. Such a graph provides a mathematical means to represent both species-independent and species-dependent biological information. We also develop a new ranking algorithm to analyze the weighted graph via a kernelized spatial depth (KSD) approach. Consequently, the importance of gene and molecular function can be simultaneously ranked by a real-valued measure, KSD, which incorporates the global and local structure of the graph. Over-expressed and under-regulated genes also can be separately ranked. Conclusion The gene-function bigraph integrates molecular function annotations into gene expression data. The relevance of genes is described in the graph (through a common function). The proposed method provides an exploratory framework for gene data analysis. PMID:19811684

  1. The order of a homotopy invariant in the stable case

    SciTech Connect

    Podkorytov, Semen S

    2011-08-31

    Let X, Y be cell complexes, let U be an Abelian group, and let f:[X,Y]{yields}U be a homotopy invariant. By definition, the invariant f has order at most r if the characteristic function of the rth Cartesian power of the graph of a continuous map a:X{yields}Y determines the value f([a]) Z-linearly. It is proved that, in the stable case (that is, when dimX<2n-1, and Y is (n-1)-connected for some natural number n), for a finite cell complex X the order of the invariant f is equal to its degree with respect to the Curtis filtration of the group [X,Y]. Bibliography: 9 titles.

  2. Quantum Ergodicity on Graphs

    NASA Astrophysics Data System (ADS)

    Gnutzmann, S.; Keating, J. P.; Piotet, F.

    2008-12-01

    We investigate the equidistribution of the eigenfunctions on quantum graphs in the high-energy limit. Our main result is an estimate of the deviations from equidistribution for large well-connected graphs. We use an exact field-theoretic expression in terms of a variant of the supersymmetric nonlinear σ model. Our estimate is based on a saddle-point analysis of this expression and leads to a criterion for when equidistribution emerges asymptotically in the limit of large graphs. Our theory predicts a rate of convergence that is a significant refinement of previous estimates, long assumed to be valid for quantum chaotic systems, agreeing with them in some situations but not all. We discuss specific examples for which the theory is tested numerically.

  3. Subdominant pseudoultrametric on graphs

    SciTech Connect

    Dovgoshei, A A; Petrov, E A

    2013-08-31

    Let (G,w) be a weighted graph. We find necessary and sufficient conditions under which the weight w:E(G)→R{sup +} can be extended to a pseudoultrametric on V(G), and establish a criterion for the uniqueness of such an extension. We demonstrate that (G,w) is a complete k-partite graph, for k≥2, if and only if for any weight that can be extended to a pseudoultrametric, among all such extensions one can find the least pseudoultrametric consistent with w. We give a structural characterization of graphs for which the subdominant pseudoultrametric is an ultrametric for any strictly positive weight that can be extended to a pseudoultrametric. Bibliography: 14 titles.

  4. Invariant object recognition based on extended fragments.

    PubMed

    Bart, Evgeniy; Hegdé, Jay

    2012-01-01

    Visual appearance of natural objects is profoundly affected by viewing conditions such as viewpoint and illumination. Human subjects can nevertheless compensate well for variations in these viewing conditions. The strategies that the visual system uses to accomplish this are largely unclear. Previous computational studies have suggested that in principle, certain types of object fragments (rather than whole objects) can be used for invariant recognition. However, whether the human visual system is actually capable of using this strategy remains unknown. Here, we show that human observers can achieve illumination invariance by using object fragments that carry the relevant information. To determine this, we have used novel, but naturalistic, 3-D visual objects called "digital embryos." Using novel instances of whole embryos, not fragments, we trained subjects to recognize individual embryos across illuminations. We then tested the illumination-invariant object recognition performance of subjects using fragments. We found that the performance was strongly correlated with the mutual information (MI) of the fragments, provided that MI value took variations in illumination into consideration. This correlation was not attributable to any systematic differences in task difficulty between different fragments. These results reveal two important principles of invariant object recognition. First, the subjects can achieve invariance at least in part by compensating for the changes in the appearance of small local features, rather than of whole objects. Second, the subjects do not always rely on generic or pre-existing invariance of features (i.e., features whose appearance remains largely unchanged by variations in illumination), and are capable of using learning to compensate for appearance changes when necessary. These psychophysical results closely fit the predictions of earlier computational studies of fragment-based invariant object recognition. PMID:22936910

  5. Tests of Lorentz invariance: a 2013 update

    NASA Astrophysics Data System (ADS)

    Liberati, S.

    2013-07-01

    We present an updated review of Lorentz invariance tests in effective field theories (EFTs) in the matter as well as in the gravity sector. After a general discussion of the role of Lorentz invariance and a derivation of its transformations along the so-called von Ignatovski theorem, we present the dynamical frameworks developed within local EFT and the available constraints on the parameters governing the Lorentz breaking effects. In the end, we discuss two specific examples: the OPERA ‘affaire’ and the case of Hořava-Lifshitz gravity. The first case will serve as an example, and a caveat, of the practical application of the general techniques developed for constraining Lorentz invariance violation to a direct observation potentially showing these effects. The second case will show how the application of the same techniques to a specific quantum gravity scenario has far-reaching implications not foreseeable in a purely phenomenological EFT approach.

  6. Gauge-Invariant Formulation of Circular Dichroism.

    PubMed

    Raimbault, Nathaniel; de Boeij, Paul L; Romaniello, Pina; Berger, J A

    2016-07-12

    Standard formulations of magnetic response properties, such as circular dichroism spectra, are plagued by gauge dependencies, which can lead to unphysical results. In this work, we present a general gauge-invariant and numerically efficient approach for the calculation of circular dichroism spectra from the current density. First we show that in this formulation the optical rotation tensor, the response function from which circular dichroism spectra can be obtained, is independent of the origin of the coordinate system. We then demonstrate that its trace is independent of the gauge origin of the vector potential. We also show how gauge invariance can be retained in practical calculations with finite basis sets. As an example, we explain how our method can be applied to time-dependent current-density-functional theory. Finally, we report gauge-invariant circular dichroism spectra obtained using the adiabatic local-density approximation. The circular dichroism spectra we thus obtain are in good agreement with experiment. PMID:27295541

  7. Graphing Calculator Mini Course

    NASA Technical Reports Server (NTRS)

    Karnawat, Sunil R.

    1996-01-01

    The "Graphing Calculator Mini Course" project provided a mathematically-intensive technologically-based summer enrichment workshop for teachers of American Indian students on the Turtle Mountain Indian Reservation. Eleven such teachers participated in the six-day workshop in summer of 1996 and three Sunday workshops in the academic year. The project aimed to improve science and mathematics education on the reservation by showing teachers effective ways to use high-end graphing calculators as teaching and learning tools in science and mathematics courses at all levels. In particular, the workshop concentrated on applying TI-82's user-friendly features to understand the various mathematical and scientific concepts.

  8. Dimensionless, Scale Invariant, Edge Weight Metric for the Study of Complex Structural Networks

    PubMed Central

    Colon-Perez, Luis M.; Spindler, Caitlin; Goicochea, Shelby; Triplett, William; Parekh, Mansi; Montie, Eric; Carney, Paul R.; Price, Catherine; Mareci, Thomas H.

    2015-01-01

    High spatial and angular resolution diffusion weighted imaging (DWI) with network analysis provides a unique framework for the study of brain structure in vivo. DWI-derived brain connectivity patterns are best characterized with graph theory using an edge weight to quantify the strength of white matter connections between gray matter nodes. Here a dimensionless, scale-invariant edge weight is introduced to measure node connectivity. This edge weight metric provides reasonable and consistent values over any size scale (e.g. rodents to humans) used to quantify the strength of connection. Firstly, simulations were used to assess the effects of tractography seed point density and random errors in the estimated fiber orientations; with sufficient signal-to-noise ratio (SNR), edge weight estimates improve as the seed density increases. Secondly to evaluate the application of the edge weight in the human brain, ten repeated measures of DWI in the same healthy human subject were analyzed. Mean edge weight values within the cingulum and corpus callosum were consistent and showed low variability. Thirdly, using excised rat brains to study the effects of spatial resolution, the weight of edges connecting major structures in the temporal lobe were used to characterize connectivity in this local network. The results indicate that with adequate resolution and SNR, connections between network nodes are characterized well by this edge weight metric. Therefore this new dimensionless, scale-invariant edge weight metric provides a robust measure of network connectivity that can be applied in any size regime. PMID:26173147

  9. Graph for locked rotor current

    NASA Technical Reports Server (NTRS)

    Peck, R. R.

    1972-01-01

    Graph determines effect of stalled motor on a distribution system and eliminates hand calculation of amperage in emergencies. Graph is useful to any manufacturer, contractor, or maintenance department involved in electrical technology.

  10. Feature Tracking Using Reeb Graphs

    SciTech Connect

    Weber, Gunther H.; Bremer, Peer-Timo; Day, Marcus S.; Bell, John B.; Pascucci, Valerio

    2010-08-02

    Tracking features and exploring their temporal dynamics can aid scientists in identifying interesting time intervals in a simulation and serve as basis for performing quantitative analyses of temporal phenomena. In this paper, we develop a novel approach for tracking subsets of isosurfaces, such as burning regions in simulated flames, which are defined as areas of high fuel consumption on a temperature isosurface. Tracking such regions as they merge and split over time can provide important insights into the impact of turbulence on the combustion process. However, the convoluted nature of the temperature isosurface and its rapid movement make this analysis particularly challenging. Our approach tracks burning regions by extracting a temperature isovolume from the four-dimensional space-time temperature field. It then obtains isosurfaces for the original simulation time steps and labels individual connected 'burning' regions based on the local fuel consumption value. Based on this information, a boundary surface between burning and non-burning regions is constructed. The Reeb graph of this boundary surface is the tracking graph for burning regions.

  11. Multithreaded Algorithms for Graph Coloring

    SciTech Connect

    Catalyurek, Umit V.; Feo, John T.; Gebremedhin, Assefaw H.; Halappanavar, Mahantesh; Pothen, Alex

    2012-10-21

    Graph algorithms are challenging to parallelize when high performance and scalability are primary goals. Low concurrency, poor data locality, irregular access pattern, and high data access to computation ratio are among the chief reasons for the challenge. The performance implication of these features is exasperated on distributed memory machines. More success is being achieved on shared-memory, multi-core architectures supporting multithreading. We consider a prototypical graph problem, coloring, and show how a greedy algorithm for solving it can be e*ectively parallelized on multithreaded architectures. We present in particular two di*erent parallel algorithms. The first relies on speculation and iteration, and is suitable for any shared-memory, multithreaded system. The second uses data ow principles and is targeted at the massively multithreaded Cray XMT system. We benchmark the algorithms on three di*erent platforms and demonstrate scalable runtime performance. In terms of quality of solution, both algorithms use nearly the same number of colors as the serial algorithm.

  12. Cookies and Graphs

    ERIC Educational Resources Information Center

    Cooper, Carol

    1975-01-01

    Teachers of an integrated elementary classroom used cookie-sharing time as a learning experience for students. Responsible for dividing varying amounts of cookies daily, the students learned to translate their experiences to graphs of differing sophistication and analyses. Further interpretation and application were done by individual students…

  13. GraphLib

    Energy Science and Technology Software Center (ESTSC)

    2013-02-19

    This library is used in several LLNL projects, including STAT (the Stack Trace Analysis Tool for scalable debugging) and some modules in P^nMPI (a tool MPI tool infrastructure). It can also be used standalone for creating and manipulationg graphs, but its API is primarily tuned to support these other projects

  14. Graph-theoretical exorcism

    SciTech Connect

    Simmons, G.J.

    1985-01-01

    Given a graph G and an ordering phi of the vertices, V(G), we define a parsimonious proper coloring (PPC) of V(G) under phi to be a proper coloring of V(G) in the order phi, where a new color is introduced only when a vertex cannot be properly colored in its order with any of the colors already used.

  15. Coloring geographical threshold graphs

    SciTech Connect

    Bradonjic, Milan; Percus, Allon; Muller, Tobias

    2008-01-01

    We propose a coloring algorithm for sparse random graphs generated by the geographical threshold graph (GTG) model, a generalization of random geometric graphs (RGG). In a GTG, nodes are distributed in a Euclidean space, and edges are assigned according to a threshold function involving the distance between nodes as well as randomly chosen node weights. The motivation for analyzing this model is that many real networks (e.g., wireless networks, the Internet, etc.) need to be studied by using a 'richer' stochastic model (which in this case includes both a distance between nodes and weights on the nodes). Here, we analyze the GTG coloring algorithm together with the graph's clique number, showing formally that in spite of the differences in structure between GTG and RGG, the asymptotic behavior of the chromatic number is identical: {chi}1n 1n n / 1n n (1 + {omicron}(1)). Finally, we consider the leading corrections to this expression, again using the coloring algorithm and clique number to provide bounds on the chromatic number. We show that the gap between the lower and upper bound is within C 1n n / (1n 1n n){sup 2}, and specify the constant C.

  16. Body Motion and Graphing.

    ERIC Educational Resources Information Center

    Nemirovsky, Ricardo; Tierney, Cornelia; Wright, Tracy

    1998-01-01

    Analyzed two children's use of a computer-based motion detector to make sense of symbolic expressions (Cartesian graphs). Found three themes: (1) tool perspectives, efforts to understand graphical responses to body motion; (2) fusion, emergent ways of talking and behaving that merge symbols and referents; and (3) graphical spaces, when changing…

  17. Graphs in Real Time.

    ERIC Educational Resources Information Center

    Beckmann, Charlene E.; Rozanski, Kara

    1999-01-01

    Presents a lesson that uses a motion detector in order for students to experience the interplay between motion and its graphical representation of the slope. Focuses on the change in the appearance of the graph with regard to changing speed. (ASK)

  18. Line Graph Learning

    ERIC Educational Resources Information Center

    Pitts Bannister, Vanessa R.; Jamar, Idorenyin; Mutegi, Jomo W.

    2007-01-01

    In this article, the learning progress of one fifth-grade student is examined with regard to the development of her graph interpretation skills as she participated in the Junior Science Institute (JSI), a two-week, science intensive summer camp in which participants engaged in microbiology research and application. By showcasing the student's…

  19. Straight Line Graphs

    ERIC Educational Resources Information Center

    Krueger, Tom

    2010-01-01

    In this article, the author shares one effective lesson idea on straight line graphs that he applied in his lower ability Y9 class. The author wanted something interesting for his class to do, something that was fun and engaging with direct feedback, and something that worked because someone else had tried it before. In a word, the author admits…

  20. Physics on Graphs

    NASA Astrophysics Data System (ADS)

    Schrader, Robert

    This is an extended version of the talk given at the Nato Advanced Research Workshop: New Challenges in Complex System Physics, May 20-24, 2013 in Samarkand (Uzbekistan). We report on results on three topics in joint work with V. Kostrykin (Mainz, Germany) and J. Potthoff (Mannheim, Germany): Propagation of waves on graphs,

  1. Eigenvalue and graph-based object extraction from mobile laser scanning point clouds

    NASA Astrophysics Data System (ADS)

    Bremer, M.; Wichmann, V.; Rutzinger, M.

    2013-10-01

    The mapping of road environments is an important task, providing important input data for a broad range of scientific disciplines. Pole-like objects, their visibility and their influence onto local light and traffic noise conditions are of particular interest for traffic safety, public health and ecological issues. Detailed knowledge can support the improvement of traffic management, noise reducing infrastructure or the planning of photovoltaic panels. Mobile Mapping Systems coupled with computer aided mapping work-flows allow an effective data acquisition and provision. We present a classification work flow focussing on pole-like objects. It uses rotation and scale invariant point and object features for classification, avoiding planar segmentation and height slicing steps. Single objects are separated by connected component and Dijkstra-path analysis. Trees and artificial objects are separated using a graph based approach considering the branching levels of the given geometries. For the focussed semantic groups, classification accuracies higher than 0.9 are achieved. This includes both the quality of object aggregation and separation, where the combination of Dijkstrapath aggregation and graph-based classification shows good results. For planar objects the classification accuracies are lowered, recommending the usage of planar segmentation for classification and subdivision issues as presented by other authors. The presented work-flow provides sufficient input data for further 3D reconstructions and tree modelling.

  2. View Invariant Gait Recognition

    NASA Astrophysics Data System (ADS)

    Seely, Richard D.; Goffredo, Michela; Carter, John N.; Nixon, Mark S.

    Recognition by gait is of particular interest since it is the biometric that is available at the lowest resolution, or when other biometrics are (intentionally) obscured. Gait as a biometric has now shown increasing recognition capability. There are many approaches and these show that recognition can achieve excellent performance on current large databases. The majority of these approaches are planar 2D, largely since the early large databases featured subjects walking in a plane normal to the camera view. To extend deployment capability, we need viewpoint invariant gait biometrics. We describe approaches where viewpoint invariance is achieved by 3D approaches or in 2D. In the first group, the identification relies on parameters extracted from the 3D body deformation during walking. These methods use several video cameras and the 3D reconstruction is achieved after a camera calibration process. On the other hand, the 2D gait biometric approaches use a single camera, usually positioned perpendicular to the subject’s walking direction. Because in real surveillance scenarios a system that operates in an unconstrained environment is necessary, many of the recent gait analysis approaches are orientated toward view-invariant gait recognition.

  3. Quantum walks on quotient graphs

    SciTech Connect

    Krovi, Hari; Brun, Todd A.

    2007-06-15

    A discrete-time quantum walk on a graph {gamma} is the repeated application of a unitary evolution operator to a Hilbert space corresponding to the graph. If this unitary evolution operator has an associated group of symmetries, then for certain initial states the walk will be confined to a subspace of the original Hilbert space. Symmetries of the original graph, given by its automorphism group, can be inherited by the evolution operator. We show that a quantum walk confined to the subspace corresponding to this symmetry group can be seen as a different quantum walk on a smaller quotient graph. We give an explicit construction of the quotient graph for any subgroup H of the automorphism group and illustrate it with examples. The automorphisms of the quotient graph which are inherited from the original graph are the original automorphism group modulo the subgroup H used to construct it. The quotient graph is constructed by removing the symmetries of the subgroup H from the original graph. We then analyze the behavior of hitting times on quotient graphs. Hitting time is the average time it takes a walk to reach a given final vertex from a given initial vertex. It has been shown in earlier work [Phys. Rev. A 74, 042334 (2006)] that the hitting time for certain initial states of a quantum walks can be infinite, in contrast to classical random walks. We give a condition which determines whether the quotient graph has infinite hitting times given that they exist in the original graph. We apply this condition for the examples discussed and determine which quotient graphs have infinite hitting times. All known examples of quantum walks with hitting times which are short compared to classical random walks correspond to systems with quotient graphs much smaller than the original graph; we conjecture that the existence of a small quotient graph with finite hitting times is necessary for a walk to exhibit a quantum speedup.

  4. Temporal Representation in Semantic Graphs

    SciTech Connect

    Levandoski, J J; Abdulla, G M

    2007-08-07

    A wide range of knowledge discovery and analysis applications, ranging from business to biological, make use of semantic graphs when modeling relationships and concepts. Most of the semantic graphs used in these applications are assumed to be static pieces of information, meaning temporal evolution of concepts and relationships are not taken into account. Guided by the need for more advanced semantic graph queries involving temporal concepts, this paper surveys the existing work involving temporal representations in semantic graphs.

  5. Graph-matching model using Gibbsian modeling: application to map/SPOT image road networks for map updating

    NASA Astrophysics Data System (ADS)

    Descombes, Xavier; Hivernat, Christine; Randriamasy, Sabine; Zerubia, Josiane B.

    1999-06-01

    We consider herein the matching between two graphs representing road networks. This problem is embedded into a labeling framework. One graph is taken as a reference. A Gibbsian model is proposed to label the other graph. The labels are defined by the noes of the second graph. The potentials are defined by the angle between the nodes and the length of the associated features. Therefore, the model is invariant by translation and rotation. We apply this model to match a road network extracted from a SPOT image on the road network of a cartographic database. This matching provides some information for map updating.

  6. A Clustering Graph Generator

    SciTech Connect

    Winlaw, Manda; De Sterck, Hans; Sanders, Geoffrey

    2015-10-26

    In very simple terms a network can be de ned as a collection of points joined together by lines. Thus, networks can be used to represent connections between entities in a wide variety of elds including engi- neering, science, medicine, and sociology. Many large real-world networks share a surprising number of properties, leading to a strong interest in model development research and techniques for building synthetic networks have been developed, that capture these similarities and replicate real-world graphs. Modeling these real-world networks serves two purposes. First, building models that mimic the patterns and prop- erties of real networks helps to understand the implications of these patterns and helps determine which patterns are important. If we develop a generative process to synthesize real networks we can also examine which growth processes are plausible and which are not. Secondly, high-quality, large-scale network data is often not available, because of economic, legal, technological, or other obstacles [7]. Thus, there are many instances where the systems of interest cannot be represented by a single exemplar network. As one example, consider the eld of cybersecurity, where systems require testing across diverse threat scenarios and validation across diverse network structures. In these cases, where there is no single exemplar network, the systems must instead be modeled as a collection of networks in which the variation among them may be just as important as their common features. By developing processes to build synthetic models, so-called graph generators, we can build synthetic networks that capture both the essential features of a system and realistic variability. Then we can use such synthetic graphs to perform tasks such as simulations, analysis, and decision making. We can also use synthetic graphs to performance test graph analysis algorithms, including clustering algorithms and anomaly detection algorithms.

  7. A Note on Hamiltonian Graphs

    ERIC Educational Resources Information Center

    Skurnick, Ronald; Davi, Charles; Skurnick, Mia

    2005-01-01

    Since 1952, several well-known graph theorists have proven numerous results regarding Hamiltonian graphs. In fact, many elementary graph theory textbooks contain the theorems of Ore, Bondy and Chvatal, Chvatal and Erdos, Posa, and Dirac, to name a few. In this note, the authors state and prove some propositions of their own concerning Hamiltonian…

  8. Random Walks on Random Graphs

    NASA Astrophysics Data System (ADS)

    Cooper, Colin; Frieze, Alan

    The aim of this article is to discuss some of the notions and applications of random walks on finite graphs, especially as they apply to random graphs. In this section we give some basic definitions, in Section 2 we review applications of random walks in computer science, and in Section 3 we focus on walks in random graphs.

  9. Editing graphs for maximum effect

    SciTech Connect

    Murphy, P.W.; Rhiner, R.W.

    1991-01-08

    The paper contains over eighty rules for editing graphs, arranged under nine major headings in a logical sequence for editing all the graphs in a manuscript. It is excerpted from a monograph used at the Lawrence Livermore National Laboratory to train beginning technical editors in editing graphs; a corresponding Hypercard stack is also used in this training. 6 refs., 4 figs.

  10. Mining and Indexing Graph Databases

    ERIC Educational Resources Information Center

    Yuan, Dayu

    2013-01-01

    Graphs are widely used to model structures and relationships of objects in various scientific and commercial fields. Chemical molecules, proteins, malware system-call dependencies and three-dimensional mechanical parts are all modeled as graphs. In this dissertation, we propose to mine and index those graph data to enable fast and scalable search.…

  11. Kevin Bacon and Graph Theory

    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…

  12. Topic Model for Graph Mining.

    PubMed

    Xuan, Junyu; Lu, Jie; Zhang, Guangquan; Luo, Xiangfeng

    2015-12-01

    Graph mining has been a popular research area because of its numerous application scenarios. Many unstructured and structured data can be represented as graphs, such as, documents, chemical molecular structures, and images. However, an issue in relation to current research on graphs is that they cannot adequately discover the topics hidden in graph-structured data which can be beneficial for both the unsupervised learning and supervised learning of the graphs. Although topic models have proved to be very successful in discovering latent topics, the standard topic models cannot be directly applied to graph-structured data due to the "bag-of-word" assumption. In this paper, an innovative graph topic model (GTM) is proposed to address this issue, which uses Bernoulli distributions to model the edges between nodes in a graph. It can, therefore, make the edges in a graph contribute to latent topic discovery and further improve the accuracy of the supervised and unsupervised learning of graphs. The experimental results on two different types of graph datasets show that the proposed GTM outperforms the latent Dirichlet allocation on classification by using the unveiled topics of these two models to represent graphs. PMID:25616091

  13. Recursive Feature Extraction in Graphs

    Energy Science and Technology Software Center (ESTSC)

    2014-08-14

    ReFeX extracts recursive topological features from graph data. The input is a graph as a csv file and the output is a csv file containing feature values for each node in the graph. The features are based on topological counts in the neighborhoods of each nodes, as well as recursive summaries of neighbors' features.

  14. Correlated Percolation, Fractal Structures, and Scale-Invariant Distribution of Clusters in Natural Images.

    PubMed

    Saremi, Saeed; Sejnowski, Terrence J

    2016-05-01

    Natural images are scale invariant with structures at all length scales.We formulated a geometric view of scale invariance in natural images using percolation theory, which describes the behavior of connected clusters on graphs.We map images to the percolation model by defining clusters on a binary representation for images. We show that critical percolating structures emerge in natural images and study their scaling properties by identifying fractal dimensions and exponents for the scale-invariant distributions of clusters. This formulation leads to a method for identifying clusters in images from underlying structures as a starting point for image segmentation. PMID:26415153

  15. Correlated Percolation, Fractal Structures, and Scale-Invariant Distribution of Clusters in Natural Images

    PubMed Central

    Saremi, Saeed; Sejnowski, Terrence J.

    2016-01-01

    Natural images are scale invariant with structures at all length scales. We formulated a geometric view of scale invariance in natural images using percolation theory, which describes the behavior of connected clusters on graphs. We map images to the percolation model by defining clusters on a binary representation for images. We show that critical percolating structures emerge in natural images and study their scaling properties by identifying fractal dimensions and exponents for the scale-invariant distributions of clusters. This formulation leads to a method for identifying clusters in images from underlying structures as a starting point for image segmentation. PMID:26415153

  16. Self-organization in a model of economic system with scale invariant interactions

    NASA Astrophysics Data System (ADS)

    Pis`mak, Yu. M.

    2001-10-01

    The method of constructing the local scale invariant stochastic models is proposed. The possible extension of minimal scale-invariant interaction principle for stochastic systems is formulated. A simple scale invariant model that possesses an economical interpretation is considered. Essential characteristics of its self-organization mechanisms are discussed.

  17. Data Structures and Algorithms for Graph Based Remote Sensed Image Content Storage and Retrieval

    SciTech Connect

    Grant, C W

    2004-06-24

    The Image Content Engine (ICE) project at Lawrence Livermore National Laboratory (LLNL) extracts, stores and allows queries of image content on multiple levels. ICE is designed for multiple application domains. The domain explored in this work is aerial and satellite surveillance imagery. The highest level of semantic information used in ICE is graph based. After objects are detected and classified, they are grouped based in their interrelations. The graph representing a locally related set of objects is called a 'graphlet'. Graphlets are interconnected into a larger graph which covers an entire set of images. Queries based on graph properties are notoriously difficult due the inherent complexity of the graph isomorphism and sub-graph isomorphism problems. ICE exploits limitations in graph and query structure and uses a set of auxiliary data structures to quickly process a useful set of graph based queries. These queries could not be processed using semantically lower level (tile and object based) queries.

  18. What is a complex graph?

    NASA Astrophysics Data System (ADS)

    Kim, Jongkwang; Wilhelm, Thomas

    2008-04-01

    Many papers published in recent years show that real-world graphs G(n,m) ( n nodes, m edges) are more or less “complex” in the sense that different topological features deviate from random graphs. Here we narrow the definition of graph complexity and argue that a complex graph contains many different subgraphs. We present different measures that quantify this complexity, for instance C1e, the relative number of non-isomorphic one-edge-deleted subgraphs (i.e. DECK size). However, because these different subgraph measures are computationally demanding, we also study simpler complexity measures focussing on slightly different aspects of graph complexity. We consider heuristically defined “product measures”, the products of two quantities which are zero in the extreme cases of a path and clique, and “entropy measures” quantifying the diversity of different topological features. The previously defined network/graph complexity measures Medium Articulation and Offdiagonal complexity ( OdC) belong to these two classes. We study OdC measures in some detail and compare it with our new measures. For all measures, the most complex graph G has a medium number of edges, between the edge numbers of the minimum and the maximum connected graph n-1graph complexity measures are characterized with the help of different example graphs. For all measures the corresponding time complexity is given. Finally, we discuss the complexity of 33 real-world graphs of different biological, social and economic systems with the six computationally most simple measures (including OdC). The complexities of the real graphs are compared with average complexities of two different random graph versions: complete random graphs (just fixed n,m) and rewired graphs with fixed node degrees.

  19. Graphing. USMES Intermediate "How To" Set.

    ERIC Educational Resources Information Center

    Agro, Sally; And Others

    In this set of six booklets on graphing, intermediate grade students learn how to choose which kind of graph to make; make bar graphs, histograms, line graphs, and conversion graphs; and use graphs to compare two sets of data. The major emphasis in all Unified Sciences and Mathematics for Elementary Schools (USMES) units is on open-ended,…

  20. Random graphs with hidden color.

    PubMed

    Söderberg, Bo

    2003-07-01

    We propose and investigate a unifying class of sparse random graph models, based on a hidden coloring of edge-vertex incidences, extending an existing approach, random graphs with a given degree distribution, in a way that admits a nontrivial correlation structure in the resulting graphs. The approach unifies a number of existing random graph ensembles within a common general formalism, and allows for the analytic calculation of observable graph characteristics. In particular, generating function techniques are used to derive the size distribution of connected components (clusters) as well as the location of the percolation threshold where a giant component appears. PMID:12935185

  1. Spectral fluctuations of quantum graphs

    SciTech Connect

    Pluhař, Z.; Weidenmüller, H. A.

    2014-10-15

    We prove the Bohigas-Giannoni-Schmit conjecture in its most general form for completely connected simple graphs with incommensurate bond lengths. We show that for graphs that are classically mixing (i.e., graphs for which the spectrum of the classical Perron-Frobenius operator possesses a finite gap), the generating functions for all (P,Q) correlation functions for both closed and open graphs coincide (in the limit of infinite graph size) with the corresponding expressions of random-matrix theory, both for orthogonal and for unitary symmetry.

  2. The Nakayama Automorphism of the Almost Calabi-Yau Algebras Associated to SU(3) Modular Invariants

    NASA Astrophysics Data System (ADS)

    Evans, David E.; Pugh, Mathew

    2012-05-01

    We determine the Nakayama automorphism of the almost Calabi-Yau algebra A associated to the braided subfactors or nimrep graphs associated to each SU(3) modular invariant. We use this to determine a resolution of A as an A- A bimodule, which will yield a projective resolution of A.

  3. Scaling Semantic Graph Databases in Size and Performance

    SciTech Connect

    Morari, Alessandro; Castellana, Vito G.; Villa, Oreste; Tumeo, Antonino; Weaver, Jesse R.; Haglin, David J.; Choudhury, Sutanay; Feo, John T.

    2014-08-06

    In this paper we present SGEM, a full software system for accelerating large-scale semantic graph databases on commodity clusters. Unlike current approaches, SGEM addresses semantic graph databases by only employing graph methods at all the levels of the stack. On one hand, this allows exploiting the space efficiency of graph data structures and the inherent parallelism of graph algorithms. These features adapt well to the increasing system memory and core counts of modern commodity clusters. On the other hand, however, these systems are optimized for regular computation and batched data transfers, while graph methods usually are irregular and generate fine-grained data accesses with poor spatial and temporal locality. Our framework comprises a SPARQL to data parallel C compiler, a library of parallel graph methods and a custom, multithreaded runtime system. We introduce our stack, motivate its advantages with respect to other solutions and show how we solved the challenges posed by irregular behaviors. We present the result of our software stack on the Berlin SPARQL benchmarks with datasets up to 10 billion triples (a triple corresponds to a graph edge), demonstrating scaling in dataset size and in performance as more nodes are added to the cluster.

  4. Gauge invariant quantum cosmology

    NASA Technical Reports Server (NTRS)

    Berger, Beverly K.

    1987-01-01

    The study of boundary conditions, the Hamiltonian constraint, reparameterization-invariance, and quantum dynamics, is presently approached by means of the path-integral quantization of minisuperspace models. The separation of the wave functions for expansion and contraction by the Feynman boundary conditions is such that there can be no interference between them. This is implemented by the choice of a contour in the complex plane, in order to define the phase of the square-root Arnowitt, Deser, and Misner (1960) Hamiltonian for expansion, collapse, and the classically forbidden region.

  5. Graphs in molecular biology

    PubMed Central

    Huber, Wolfgang; Carey, Vincent J; Long, Li; Falcon, Seth; Gentleman, Robert

    2007-01-01

    Graph theoretical concepts are useful for the description and analysis of interactions and relationships in biological systems. We give a brief introduction into some of the concepts and their areas of application in molecular biology. We discuss software that is available through the Bioconductor project and present a simple example application to the integration of a protein-protein interaction and a co-expression network. PMID:17903289

  6. An Unusual Exponential Graph

    ERIC Educational Resources Information Center

    Syed, M. Qasim; Lovatt, Ian

    2014-01-01

    This paper is an addition to the series of papers on the exponential function begun by Albert Bartlett. In particular, we ask how the graph of the exponential function y = e[superscript -t/t] would appear if y were plotted versus ln t rather than the normal practice of plotting ln y versus t. In answering this question, we find a new way to…

  7. Community detection in graphs

    NASA Astrophysics Data System (ADS)

    Fortunato, Santo

    2010-02-01

    The modern science of networks has brought significant advances to our understanding of complex systems. One of the most relevant features of graphs representing real systems is community structure, or clustering, i.e. the organization of vertices in clusters, with many edges joining vertices of the same cluster and comparatively few edges joining vertices of different clusters. Such clusters, or communities, can be considered as fairly independent compartments of a graph, playing a similar role like, e.g., the tissues or the organs in the human body. Detecting communities is of great importance in sociology, biology and computer science, disciplines where systems are often represented as graphs. This problem is very hard and not yet satisfactorily solved, despite the huge effort of a large interdisciplinary community of scientists working on it over the past few years. We will attempt a thorough exposition of the topic, from the definition of the main elements of the problem, to the presentation of most methods developed, with a special focus on techniques designed by statistical physicists, from the discussion of crucial issues like the significance of clustering and how methods should be tested and compared against each other, to the description of applications to real networks.

  8. Random graphs containing arbitrary distributions of subgraphs

    NASA Astrophysics Data System (ADS)

    Karrer, Brian; Newman, M. E. J.

    2010-12-01

    Traditional random graph models of networks generate networks that are locally treelike, meaning that all local neighborhoods take the form of trees. In this respect such models are highly unrealistic, most real networks having strongly nontreelike neighborhoods that contain short loops, cliques, or other biconnected subgraphs. In this paper we propose and analyze a class of random graph models that incorporates general subgraphs, allowing for nontreelike neighborhoods while still remaining solvable for many fundamental network properties. Among other things we give solutions for the size of the giant component, the position of the phase transition at which the giant component appears, and percolation properties for both site and bond percolation on networks generated by the model.

  9. The relation between the waveguide invariant and array invariant.

    PubMed

    Song, H C; Cho, Chomgun

    2015-08-01

    The waveguide invariant β is based on the dependence of group speed on phase speed and summarizes the robust interference phenomenon in the range-frequency plane. Over the last decade the elegant approach has been utilized for various applications including passive source ranging. Separately, the array invariant approach [Lee and Makris, J. Acoust. Soc. Am. 119, 336-351 (2006)] has been proposed for a robust source-range estimator from beam-time intensity data using either a horizontal or vertical array. In this paper, it is shown that the array invariant can be derived from the waveguide invariant theory assuming β=1. PMID:26328705

  10. Entanglement, Invariants, and Phylogenetics

    NASA Astrophysics Data System (ADS)

    Sumner, J. G.

    2007-10-01

    This thesis develops and expands upon known techniques of mathematical physics relevant to the analysis of the popular Markov model of phylogenetic trees required in biology to reconstruct the evolutionary relationships of taxonomic units from biomolecular sequence data. The techniques of mathematical physics are plethora and have been developed for some time. The Markov model of phylogenetics and its analysis is a relatively new technique where most progress to date has been achieved by using discrete mathematics. This thesis takes a group theoretical approach to the problem by beginning with a remarkable mathematical parallel to the process of scattering in particle physics. This is shown to equate to branching events in the evolutionary history of molecular units. The major technical result of this thesis is the derivation of existence proofs and computational techniques for calculating polynomial group invariant functions on a multi-linear space where the group action is that relevant to a Markovian time evolution. The practical results of this thesis are an extended analysis of the use of invariant functions in distance based methods and the presentation of a new reconstruction technique for quartet trees which is consistent with the most general Markov model of sequence evolution.