Generalized Ramsey numbers through adiabatic quantum optimization
NASA Astrophysics Data System (ADS)
Ranjbar, Mani; Macready, William G.; Clark, Lane; Gaitan, Frank
2016-06-01
Ramsey theory is an active research area in combinatorics whose central theme is the emergence of order in large disordered structures, with Ramsey numbers marking the threshold at which this order first appears. For generalized Ramsey numbers r(G, H), the emergent order is characterized by graphs G and H. In this paper we: (i) present a quantum algorithm for computing generalized Ramsey numbers by reformulating the computation as a combinatorial optimization problem which is solved using adiabatic quantum optimization; and (ii) determine the Ramsey numbers r({{T}}m,{{T}}n) for trees of order m,n = 6,7,8 , most of which were previously unknown.
On the Ramsey numbers for complete distance graphs with vertices in {l_brace}0,1{r_brace}{sup n}
Mikhailov, Kirill A; Raigorodskii, Andrei M
2009-12-31
A new problem of Ramsey type is posed for complete distance graphs in R{sup n} with vertices in the Boolean cube. This problem is closely related to the classical Nelson-Erdos-Hadwiger problem on the chromatic number of a space. Several quite sharp estimates are obtained for certain numerical characteristics that appear in the framework of the problem. Bibliography: 15 titles.
On Ramsey (P3, P6)-minimal graphs
NASA Astrophysics Data System (ADS)
Rahmadani, Desi; Baskoro, Edy Tri; Assiyatun, Hilda
2016-02-01
Finding all Ramsey (G, H)-minimal graphs for a certain pair of graphs G and H is an interesting and difficult problem. Even though, it is just for small graphs G and H. In this paper, we determine some Ramsey (P3, P6)-minimal graphs of small order. We also characterize all such Ramsey minimal graphs of order 6 by using their degree sequences. We prove that Ramsey (P3, P6)-minimal graphs have diameter at least two. We construct an infinite class of trees [6] which provides Ramsey (P3, P6)-minimal graphs.
Determining Ramsey numbers on a quantum computer
NASA Astrophysics Data System (ADS)
Wang, Hefeng
2016-03-01
We present a quantum algorithm for computing the Ramsey numbers whose computational complexity grows superexponentially with the number of vertices of a graph on a classical computer. The problem is mapped to a decision problem on a quantum computer, and a probe qubit is coupled to a register that represents the problem and detects the energy levels of the problem Hamiltonian. The decision problem is solved by detecting the decay dynamics of the probe qubit.
Restricted size Ramsey number for P3 versus small paths
NASA Astrophysics Data System (ADS)
Silaban, Denny Riama; Baskoro, E. T.; Uttunggadewa, Saladin
2016-02-01
Let F, G, and H be simple graphs. We say F → (G, H) if for every 2-coloring of the edges of F there exist a monochromatic G or H in F. The Ramsey number r(G, H) is defined as min {|V (F)| : F → (G, H)}, the size Ramsey number r̂(G, H) is defined as min {|E(F)| : F → (G, H)}, and the restricted size Ramsey number r*(G, H) is defined as min {|E(F)| : F → (G, H), |V (F)| = r(G, H)}. In this paper we give a lower bound for the restricted size Ramsey number for a path P3 versus Pn. We also give the upper bound and the exact restricted size Ramsey number for some small values of n.
On Ramsey (3K2, K3) - minimal graphs
NASA Astrophysics Data System (ADS)
Wijaya, Kristiana; Baskoro, Edy Tri; Assiyatun, Hilda; Suprijanto, Djoko
2016-02-01
The Ramsey graph theory has many interesting applications, such as in the fields of communications, information retrieval, and decision making. One of growing topics in Ramsey theory is Ramsey minimal graph. For any given graphs G and H, find graphs F such that any red-blue coloring of all edges of F contains either a red copy of G or a blue copy of H. If this condition is not satisfied by the graph F - e, then we call the graph F as a Ramsey (G, H) - minimal. In this paper, we derive the properties of (3K2, K3) - minimal graphs. We, then, characterize all Ramsey (3K2, K3) - minimal graphs.
Connected size Ramsey numbers of matchings and stars
NASA Astrophysics Data System (ADS)
Rahadjeng, Budi; Baskoro, Edy Tri; Assiyatun, Hilda
2016-02-01
Let F, G, and H be finite, simple, and undirected graphs. The notation F → (G, H) means that if the edge set of F is arbitrarily colored by red or blue, then there always exists either a red copy of G or a blue copy of H. The connected size Ramsey number r̂c(G, H) is min{|E(F)| : F → (G, H), F is connected}. In this paper, we determine the connected size Ramsey numbers r̂c(nK2, mK2), for n, m ≥ 2. Furthermore, an upper bound of r̂c(nK2, K1,m), for n ≥ 2 and m ≥ 3, and the exact value of r̂c(nK2, K1,m), for n = 2, 3, are presented.
On size tripartite Ramsey numbers of P3 versus mK1,n
NASA Astrophysics Data System (ADS)
Lusiani, Anie; Baskoro, Edy Tri; Saputro, Suhadi Wido
2016-02-01
Let Kl×t be a complete, balanced, multipartite graph consisting of l partite sets and t vertices in each partite set. For simple graphs G and H, the size multipartite Ramsey number mj (G, H) is the smallest natural number t such that any arbitrary red-blue coloring on the edges of Kl×t contains a red G or a blue H as a subgraph. In particular, if j = 3 then m3(G, H) is called the size tripartite Ramsey number of G and H. In this paper, we determine the exact values of the size tripartite numbers m3(P3, mK1,n) for all integers m ≥ 1 and n ≥ 3, where P3 is a path of order 3 and mK1,n is a disjoint union of m copies of a star K1,n.
Rainbow connection number of rocket graphs
NASA Astrophysics Data System (ADS)
Susilawati, Salman, A. N. M.
2015-09-01
All graphs in this paper are simple, finite, and undirected. The concept of rainbow coloring was introduced by Chartrand et al2. Let G be a non trivial connected graph. For k ∈ℕ , we define a coloring c :E (G )→{1 ,2 ,…,k } of the edges of G such that the adjacent can be colored the same. A path P in G is a rainbow path if no two edges of P are colored the same. A path connecting two vertices u and u in G is called u-v path. A graph G is said rainbow-connected if for every two vertices u and u of G, there exist a rainbow u-v path. In this case, the coloring c is called the rainbow k-coloring of G. The minimum k such that G has rainbow k-coloring is called the rainbow connection number of G. Clearly that diam(G )≤r c (G ) where diam(G) denotes the diameter of G. In this paper we determine the rainbow connection number of rocket graphs.
Recognition of Graphs with Convex Quadratic Stability Number
NASA Astrophysics Data System (ADS)
Pacheco, Maria F.; Cardoso, Domingos M.
2009-09-01
A stable set of a graph is a set of mutually non-adjacent vertices. The determination of a maximum size stable set, which is called maximum stable set, and the determination of its size, which is called stability number, are central combinatorial optimization problems. However, given a nonnegative integer k, to determine if a graph G has a stable set of size k is NP-complete. In this paper we deal with graphs for which the stability number can be determined by solving a convex quadratic programming problem. Such graphs were introduced in [13] and are called graphs with convex-QP stability number. A few algorithmic techniques for the recognition of this type of graphs in particular families are presented.
Colour mathematics: with graphs and numbers
NASA Astrophysics Data System (ADS)
Lo Presto, Michael C.
2009-07-01
The different combinations involved in additive and subtractive colour mixing can often be difficult for students to remember. Using transmission graphs for filters of the primary colours and a numerical scheme to write out the relationships are good exercises in analytical thinking that can help students recall the combinations rather than just attempting to memorize them.
Colour Mathematics: With Graphs and Numbers
ERIC Educational Resources Information Center
LoPresto, Michael C.
2009-01-01
The different combinations involved in additive and subtractive colour mixing can often be difficult for students to remember. Using transmission graphs for filters of the primary colours and a numerical scheme to write out the relationships are good exercises in analytical thinking that can help students recall the combinations rather than just…
The rainbow connection number of some subdivided roof graphs
NASA Astrophysics Data System (ADS)
Susanti, Bety Hayat; Salman, A. N. M.; Simanjuntak, Rinovia
2016-02-01
Let G be an edge-colored graph where adjacent edges may have the same color. A path in G is called rainbow if its edges have distinct colors. A graph G is rainbow connected if any two distinct vertices in G are connected by a rainbow path. The smallest number of colors that are needed in order to make G rainbow connected is called the rainbow connection number of G, denoted by rc(G). In this paper, we determine the rainbow connection number of some subdivided roof graphs.
NASA Astrophysics Data System (ADS)
Kupavskii, A. B.
2014-02-01
We study distance graphs with exponentially large chromatic numbers and without k-cliques, that is, complete subgraphs of size k. Explicit constructions of such graphs use vectors in the integer lattice. For a large class of graphs we find a sharp threshold for containing a k-clique. This enables us to improve the lower bounds for the maximum of the chromatic numbers of such graphs. We give a new probabilistic approach to the construction of distance graphs without k-cliques, and this yields better lower bounds for the maximum of the chromatic numbers for large k.
The (strong) rainbow connection number of stellar graphs
NASA Astrophysics Data System (ADS)
Shulhany, M. A.; Salman, A. N. M.
2016-02-01
Let G = (V,E) be a simple, connected, and finite graph. A function c from E to {1, 2, …, k} is said rainbow k-coloring of G, if for any pair of vertices u and v in V, there exists au - vpath whose edges have different colors. The rainbow connection number of G, denoted by rc(G), is the smallest positive integer k such that Ghas a rainbow k-coloring. Furthermore, such the function c is said strong rainbow k-coloring, if for any pair of vertices u and v in V, there exists a rainbow u-v path with its length is equal to distance betweenu and v. The smallest positive integer k such that G has a strong rainbow k-coloring is defined as the strong rainbow connection number, denoted by src(G).In this paper, we introduce a new class of graphs, namely stellar graphs. A stellar graph on 2mn+1 vertices, denoted by Stm,n, is the corona product of a trivial graph and mcopies ladder graph on 2n vertices (K1⊙m.Ln). We determine the (strong) rainbow connection number of stellar graphs.
On Vertex Covering Transversal Domination Number of Regular Graphs
Vasanthi, R.; Subramanian, K.
2016-01-01
A simple graph G = (V, E) is said to be r-regular if each vertex of G is of degree r. The vertex covering transversal domination number γvct(G) is the minimum cardinality among all vertex covering transversal dominating sets of G. In this paper, we analyse this parameter on different kinds of regular graphs especially for Qn and H3,n. Also we provide an upper bound for γvct of a connected cubic graph of order n ≥ 8. Then we try to provide a more stronger relationship between γ and γvct. PMID:27119089
Locating-chromatic number for a graph of two components
NASA Astrophysics Data System (ADS)
Welyyanti, Des; Simanjuntak, Rinovia; Uttunggadewa, Saladin; Baskoro, Edy Tri
2016-02-01
The study of locating-chromatic number of a graph initiated by Chartrand et al. [5] is only limited for connected graphs. In 2014, Welyyanti et al. extended this notion so that the locating-chromatic number can also be applied to disconnected graphs. Let c be a k-coloring of a disconnected graph H(V, E) and ∏ = {C1,C2, …, Ck} be the partition of V (H) induced by c, where Ci is the set of all vertices receiving color i. The color code c∏(v) of a vertex v ∈ H is the ordered k-tuple (d(v,C1), d(v,C2), …, d(v,Ck)), where d(v,Ci) = min{d(v, x)|x ∈ Ci} and d(v,Ci) < ∞ for all i ∈ [1, k]. If all vertices of H have distinct color codes, then c is called a locating-coloring of H. The locating-chromatic number of H, denoted by χ'L(H ) , is the smallest k such that H admits a locating-coloring with k colors, otherwise we say that χ'L(H )=∞ . In this paper, we determine locating-chromatic number of a graph with two components where each component has the locating-chromatic number 3.
Spatiotemporal Directional Number Transitional Graph for Dynamic Texture Recognition.
Rivera, Adín Ramírez; Chae, Oksam
2015-10-01
Spatiotemporal image descriptors are gaining attention in the image research community for better representation of dynamic textures. In this paper, we introduce a dynamic-micro-texture descriptor, i.e., spatiotemporal directional number transitional graph (DNG), which describes both the spatial structure and motion of each local neighborhood by capturing the direction of natural flow in the temporal domain. We use the structure of the local neighborhood, given by its principal directions, and compute the transition of such directions between frames. Moreover, we present the statistics of the direction transitions in a transitional graph, which acts as a signature for a given spatiotemporal region in the dynamic texture. Furthermore, we create a sequence descriptor by dividing the spatiotemporal volume into several regions, computing a transitional graph for each of them, and represent the sequence as a set of graphs. Our results validate the robustness of the proposed descriptor in different scenarios for expression recognition and dynamic texture analysis. PMID:26340258
Computing the Edge-Neighbour-Scattering Number of Graphs
NASA Astrophysics Data System (ADS)
Wei, Zongtian; Qi, Nannan; Yue, Xiaokui
2013-11-01
A set of edges X is subverted from a graph G by removing the closed neighbourhood N[X] from G. We denote the survival subgraph by G=X. An edge-subversion strategy X is called an edge-cut strategy of G if G=X is disconnected, a single vertex, or empty. The edge-neighbour-scattering number of a graph G is defined as ENS(G) = max{ω(G/X)-|X| : X is an edge-cut strategy of G}, where w(G=X) is the number of components of G=X. This parameter can be used to measure the vulnerability of networks when some edges are failed, especially spy networks and virus-infected networks. In this paper, we prove that the problem of computing the edge-neighbour-scattering number of a graph is NP-complete and give some upper and lower bounds for this parameter.
An α-cut chromatic number of a total uncertain graph and its properties
NASA Astrophysics Data System (ADS)
Rosyida, Isnaini; Widodo, Indrati, Ch. Rini; Sugeng, Kiki A.
2016-02-01
A graph is called an edge uncertain graph if the edges are not deterministic but exist with some belief degrees described by uncertain measure. A new definition for total uncertain graph is first introduced in this paper, that is an uncertain graph in which the vertices and the edges are not deterministic. Further, we give a concept of an α-cut of a total uncertain graph and investigate some of its properties. We color a total uncertain graph via the α-cut, and obtain α-cut chromatic numbers for all α ∈ [0, 1]. Some properties of the α-cut chromatic number are also verified.
Detecting independent and recurrent copy number aberrations using interval graphs
Wu, Hsin-Ta; Hajirasouliha, Iman; Raphael, Benjamin J.
2014-01-01
Motivation: Somatic copy number aberrations (SCNAs) are frequent in cancer genomes, but many of these are random, passenger events. A common strategy to distinguish functional aberrations from passengers is to identify those aberrations that are recurrent across multiple samples. However, the extensive variability in the length and position of SCNAs makes the problem of identifying recurrent aberrations notoriously difficult. Results: We introduce a combinatorial approach to the problem of identifying independent and recurrent SCNAs, focusing on the key challenging of separating the overlaps in aberrations across individuals into independent events. We derive independent and recurrent SCNAs as maximal cliques in an interval graph constructed from overlaps between aberrations. We efficiently enumerate all such cliques, and derive a dynamic programming algorithm to find an optimal selection of non-overlapping cliques, resulting in a very fast algorithm, which we call RAIG (Recurrent Aberrations from Interval Graphs). We show that RAIG outperforms other methods on simulated data and also performs well on data from three cancer types from The Cancer Genome Atlas (TCGA). In contrast to existing approaches that employ various heuristics to select independent aberrations, RAIG optimizes a well-defined objective function. We show that this allows RAIG to identify rare aberrations that are likely functional, but are obscured by overlaps with larger passenger aberrations. Availability: http://compbio.cs.brown.edu/software. Contact: braphael@brown.edu Supplementary information: Supplementary data are available at Bioinformatics online. PMID:24931984
Decomposition Optimization for Minimizing Label Overflow in Prime Number Graph Labeling
NASA Astrophysics Data System (ADS)
Kim, Jaehoon; Park, Seog
Recently, a graph labeling technique based on prime numbers has been suggested for reducing the costly transitive closure computations in RDF query languages. The suggested prime number graph labeling provides the benefit of fast query processing by a simple divisibility test of labels. However, it has an inherent problem that originates with the nature of prime numbers. Since each prime number must be used exclusively, labels can become significantly large. Therefore, in this paper, we introduce a novel optimization technique to effectively reduce the problem of label overflow. The suggested idea is based on graph decomposition. When label overflow occurs, the full graph is divided into several sub-graphs, and nodes in each sub-graph are separately labeled. Through experiments, we also analyze the effectiveness of the graph decomposition optimization, which is evaluated by the number of divisions.
Locating-coloring on Halin graphs with a certain number of inner faces
NASA Astrophysics Data System (ADS)
Purwasih, I. A.; Baskoro, E. T.; Assiyatun, H.; Suprijanto, D.
2016-02-01
For any tree T with at least four vertices and no vertices of degree two, define a Halin graph H(T) as a planar graph constructed from an embedding of T in a plane by connecting all the leaves (the vertices of degree 1) of T to form a cycle C that passes around T in the natural cyclic order defined by the embedding of T . The study of the properties of a Halin graph has received much attention. For instances, it has been shown that every Halin graph is 3-connected and Hamiltonian. A Halin graph has also treewidth at most three, so that many graph optimization problems that are NP-complete for arbitrary planar graphs may be solved in linear time on Halin graphs using dynamic programming. In this paper, we characterize all Halin graphs with 3,4,5,6, and 7 inner faces and give their locating-chromatic number. Furthermore, we show that there exist a Halin graph having locating-chromatic number k ≥ 4 with r ≥max {3 ,(k/-2) 3-(k-2 ) 2 2 +1 } inner faces.
Mitra, Tapan; Sorger, Gerhard
2013-09-01
Studying a one-sector economy populated by finitely many heterogeneous households that are subject to no-borrowing constraints, we confirm a conjecture by Frank P. Ramsey according to which, in the long run, society would be divided into the set of patient households who own the entire capital stock and impatient ones without any physical wealth. More specifically, we prove (i) that there exists a unique steady state equilibrium that is globally asymptotically stable and (ii) that along every equilibrium the most patient household owns the entire capital of the economy after some finite time. Furthermore, we prove that despite the presence of the no-borrowing constraints all equilibria are efficient. Our results are derived for the continuous-time formulation of the model that was originally used by Ramsey, and they stand in stark contrast to results that - over the last three decades - have been found in the discrete-time version of the model. PMID:24926104
Graph of Total Number of Oligos Within Windows of a Sequence
Stavropoulos, Nick A.
1995-11-28
SEQWIN is user-friendly software which graphs the total number of oligos present in a sequence. The sequence is scanned one window at a time; windows can be overlapping. Each bar on the graph represents a single window down the sequence. The user specifies the sequence of interest and a list of oligos as program input. If the sequence is known, locations of specific structure or sequences can be specified and compared with the bars on a graph. The window size, amount of overlap of the windows, number of windows to be considered, and the starting position of the first window used can be adjusted at the user's discretion.
2010-01-01
Background Understanding of secondary metabolic pathway in plant is essential for finding druggable candidate enzymes. However, there are many enzymes whose functions are not yet discovered in organism-specific metabolic pathways. Towards identifying the functions of those enzymes, assignment of EC numbers to the enzymatic reactions they catalyze plays a key role, since EC numbers represent the categorization of enzymes on one hand, and the categorization of enzymatic reactions on the other hand. Results We propose reaction graph kernels for automatically assigning EC numbers to unknown enzymatic reactions in a metabolic network. Reaction graph kernels compute similarity between two chemical reactions considering the similarity of chemical compounds in reaction and their relationships. In computational experiments based on the KEGG/REACTION database, our method successfully predicted the first three digits of the EC number with 83% accuracy. We also exhaustively predicted missing EC numbers in plant's secondary metabolism pathway. The prediction results of reaction graph kernels on 36 unknown enzymatic reactions are compared with an expert's knowledge. Using the same data for evaluation, we compared our method with E-zyme, and showed its ability to assign more number of accurate EC numbers. Conclusion Reaction graph kernels are a new metric for comparing enzymatic reactions. PMID:20122204
Graph of Total Number of Oligos Within Windows of a Sequence
Energy Science and Technology Software Center (ESTSC)
1995-11-28
SEQWIN is user-friendly software which graphs the total number of oligos present in a sequence. The sequence is scanned one window at a time; windows can be overlapping. Each bar on the graph represents a single window down the sequence. The user specifies the sequence of interest and a list of oligos as program input. If the sequence is known, locations of specific structure or sequences can be specified and compared with the bars onmore » a graph. The window size, amount of overlap of the windows, number of windows to be considered, and the starting position of the first window used can be adjusted at the user's discretion.« less
ERIC Educational Resources Information Center
Earnest, Darrell Steven
2012-01-01
This dissertation explores fifth and eighth grade students' interpretations of three kinds of mathematical representations: number lines, the Cartesian plane, and graphs of linear functions. Two studies were conducted. In Study 1, I administered the paper-and-pencil Linear Representations Assessment (LRA) to examine students'…
ERIC Educational Resources Information Center
Earnest, Darrell
2015-01-01
This article reports on students' problem-solving approaches across three representations--number lines, coordinate planes, and function graphs--the axes of which conventional mathematics treats in terms of consistent geometric and numeric coordinations. I consider these representations to be a part of a "hierarchical representational…
Distance graphs having large chromatic numbers and containing no cliques or cycles of a given size
Demekhin, Evgenii E; Raigorodskii, Andrei M; Rubanov, Oleg I
2013-04-30
It is established that there exist sequences of distance graphs G{sub n} subset of R{sup n}, with chromatic numbers which grow exponentially, but, at the same time, without cliques or cycles of a given size. Bibliography: 42 titles.
NASA Technical Reports Server (NTRS)
Butler, Ricky W.; Sjogren, Jon A.
1998-01-01
This paper documents the NASA Langley PVS graph theory library. The library provides fundamental definitions for graphs, subgraphs, walks, paths, subgraphs generated by walks, trees, cycles, degree, separating sets, and four notions of connectedness. Theorems provided include Ramsey's and Menger's and the equivalence of all four notions of connectedness.
Two-frequency Ramsey interferometry
Seidel, D.; Muga, J. G.
2007-02-15
We investigate Ramsey interferometry for two separated fields oscillating with different frequencies. It is shown that the interplay between average and relative detuning leads to interference effects not present in the standard, single-frequency setup. For a large free-flight time of ground-state atoms before entering the first field region, the Ramsey fringes with respect to the relative detuning become much narrower than the usual ones. The stability of these effects with respect to phase or velocity fluctuations is discussed.
Graph Embedding Techniques for Bounding Condition Numbers of Incomplete Factor Preconditioning
NASA Technical Reports Server (NTRS)
Guattery, Stephen
1997-01-01
We extend graph embedding techniques for bounding the spectral condition number of preconditioned systems involving symmetric, irreducibly diagonally dominant M-matrices to systems where the preconditioner is not diagonally dominant. In particular, this allows us to bound the spectral condition number when the preconditioner is based on an incomplete factorization. We provide a review of previous techniques, describe our extension, and give examples both of a bound for a model problem, and of ways in which our techniques give intuitive way of looking at incomplete factor preconditioners.
Pulse defect immune Ramsey spectroscopy
NASA Astrophysics Data System (ADS)
Sanner, Christian; Huntemann, Nils; Kuznetsov, Sergey; Lipphardt, Burghard; Tamm, Christian; Peik, Ekkehard
2016-05-01
We show that a balanced version of Ramsey's method of separated oscillatory fields is well suited for measuring unperturbed transition frequencies of atomic reference transitions that suffer from significant clock shifts in the presence of the oscillatory drive fields. Using the example of the strongly light shift affected Yb 171 + octupole transition we experimentally demonstrate the feasibility of this concept and show that no systematic clock shifts are incurred for arbitrarily detuned drive pulses. Unlike composite pulse approaches as proposed in balanced Ramsey spectroscopy can provide universal immunity to a variety of pulse aberrations and drive pulse induced shifts including phase chirps and pulse-synchronous intensity variations. In this context we also devise an experimental method addressing issues related to motional heating of the confined ion. Furthermore we report on the status of an Yb + experiment searching for signatures of spatial anisotropy.
Oblakov, Konstantin I; Oblakova, Tat'yana A
2012-10-31
The paper is devoted to the characteristic of a graph that is the minimal (over all embeddings of the graph into a space of given dimension) number of points that belong to the same hyperplane. Upper and lower estimates for this number are given that linearly depend on the dimension of the space. For trees a more precise upper estimate is obtained, which asymptotically coincides with the lower one for large dimension of the space. Bibliography: 9 titles.
ERIC Educational Resources Information Center
Lane, David M.; Sandor, Aniko
2009-01-01
Statistical graphs are commonly used in scientific publications. Unfortunately, graphs in psychology journals rarely portray distributional information beyond central tendency, and few graphs portray inferential statistics. Moreover, those that do portray inferential information generally do not portray it in a way that is useful for interpreting…
More than numbers: the power of graphs in meta-analysis.
Bax, Leon; Ikeda, Noriaki; Fukui, Naohito; Yaju, Yukari; Tsuruta, Harukazu; Moons, Karel G M
2009-01-15
In meta-analysis, the assessment of graphs is widely used in an attempt to identify or rule out heterogeneity and publication bias. A variety of graphs are available for this purpose. To date, however, there has been no comparative evaluation of the performance of these graphs. With the objective of assessing the reproducibility and validity of graph ratings, the authors simulated 100 meta-analyses from 4 scenarios that covered situations with and without heterogeneity and publication bias. From each meta-analysis, the authors produced 11 types of graphs (box plot, weighted box plot, standardized residual histogram, normal quantile plot, forest plot, 3 kinds of funnel plots, trim-and-fill plot, Galbraith plot, and L'Abbé plot), and 3 reviewers assessed the resulting 1,100 plots. The intraclass correlation coefficients (ICCs) for reproducibility of the graph ratings ranged from poor (ICC = 0.34) to high (ICC = 0.91). Ratings of the forest plot and the standardized residual histogram were best associated with parameter heterogeneity. Association between graph ratings and publication bias (censorship of studies) was poor. Meta-analysts should be selective in the graphs they choose for the exploration of their data. PMID:19064649
Anderson, Eric C; Ng, Thomas C
2016-02-01
We develop a computational framework for addressing pedigree inference problems using small numbers (80-400) of single nucleotide polymorphisms (SNPs). Our approach relaxes the assumptions, which are commonly made, that sampling is complete with respect to the pedigree and that there is no genotyping error. It relies on representing the inferred pedigree as a factor graph and invoking the Sum-Product algorithm to compute and store quantities that allow the joint probability of the data to be rapidly computed under a large class of rearrangements of the pedigree structure. This allows efficient MCMC sampling over the space of pedigrees, and, hence, Bayesian inference of pedigree structure. In this paper we restrict ourselves to inference of pedigrees without loops using SNPs assumed to be unlinked. We present the methodology in general for multigenerational inference, and we illustrate the method by applying it to the inference of full sibling groups in a large sample (n=1157) of Chinook salmon typed at 95 SNPs. The results show that our method provides a better point estimate and estimate of uncertainty than the currently best-available maximum-likelihood sibling reconstruction method. Extensions of this work to more complex scenarios are briefly discussed. PMID:26450523
Conditional ramsey spectroscopy with synchronized atoms.
Xu, Minghui; Holland, M J
2015-03-13
We investigate Ramsey spectroscopy performed on a synchronized ensemble of two-level atoms. The synchronization is induced by the collective coupling of the atoms to a heavily damped mode of an optical cavity. We show that, in principle, with this synchronized system it is possible to observe Ramsey fringes indefinitely, even in the presence of spontaneous emission and other sources of individual-atom dephasing. This could have important consequences for atomic clocks and a wide range of precision metrology applications. PMID:25815931
Single-atom and two-atom Ramsey interferometry with quantized fields
Agarwal, G.S.; Pathak, P.K.; Scully, M.O.
2003-04-01
Implications of field quantization on Ramsey interferometry are discussed and general conditions for the occurrence of interference are obtained. Interferences do not occur if the fields in two Ramsey zones have a precise number of photons. However, in this case we show how an analog of Hanbury-Brown Twiss photon-photon correlation interferometry can be used to discern a variety of interference effects as the two independent Ramsey zones get entangled by the passage of the first atom. Interferences are restored by working with fields at a single-photon level. Generation of entangled states including states such as vertical bar 2,0>+e{sup i{theta}} vertical bar 0,2> is discussed.
Ramsey County commercial, industrial, institutional waste reduction and recycling program
Lyman-Onkka, C.
1995-09-01
The Ramsey County Commercial, Industrial, Institutional Waste Reduction and Recycling Program was developed (1) to raise awareness of waste reduction and recycling opportunities for businesses, (2) to make information available to businesses, (3) to provide technical assistance to small and medium sized businesses on waste reduction and recycling, and (4) to raise awareness of Ramsey County as a technical resource. Ramsey County was founded in 1849 and is named for Alexander Ramsey, the first governor of the Minnesota Territory. Ramsey County is the smallest, most urban of all 87 counties in Minnesota. With 170 square miles and a 1990 population of 485,000, Ramsey has the most people per square mile of any county in Minnesota. There are 19 cities within the County, the largest is Saint Paul with a 1990 population of 272,000. There are no unincorporated areas in Ramsey County. This report describes the efforts directed towards raising the awareness of the county waste management, recycling program.
Mitra, Tapan; Sorger, Gerhard
2013-01-01
Studying a one-sector economy populated by finitely many heterogeneous households that are subject to no-borrowing constraints, we confirm a conjecture by Frank P. Ramsey according to which, in the long run, society would be divided into the set of patient households who own the entire capital stock and impatient ones without any physical wealth. More specifically, we prove (i) that there exists a unique steady state equilibrium that is globally asymptotically stable and (ii) that along every equilibrium the most patient household owns the entire capital of the economy after some finite time. Furthermore, we prove that despite the presence of the no-borrowing constraints all equilibria are efficient. Our results are derived for the continuous-time formulation of the model that was originally used by Ramsey, and they stand in stark contrast to results that – over the last three decades – have been found in the discrete-time version of the model. PMID:24926104
Ramsey interference in a multilevel quantum system
NASA Astrophysics Data System (ADS)
Lee, J. P.; Bennett, A. J.; Skiba-Szymanska, J.; Ellis, D. J. P.; Farrer, I.; Ritchie, D. A.; Shields, A. J.
2016-02-01
We report Ramsey interference in the excitonic population of a negatively charged quantum dot measured in resonant fluorescence. Our experiments show that the decay time of the Ramsey interference is limited by the spectral width of the transition. Applying a vertical magnetic field induces Zeeman split transitions that can be addressed by changing the laser detuning to reveal two-, three-, and four-level system behavior. We show that under finite field the phase-sensitive control of two optical pulses from a single laser can be used to prepare both population and spin states simultaneously. We also demonstrate the coherent optical manipulation of a trapped spin in a quantum dot in a Faraday geometry magnetic field.
NASA Astrophysics Data System (ADS)
Lai, Pik-Yin
Methods of statistical mechanics are applied to two important NP-complete combinatorial optimization problems. The first is the chromatic number problem which seeks the minimal number of colors necessary to color a graph such that no two sites connected by an edge have the same color. The second is partitioning of a graph into q equal subgraphs so as to minimize inter-subgraph connections. Both models are mapped into a frustrated Potts model which is related to the q-state Potts spin glass. For the first problem, we obtain very good agreement with numerical simulations and theoretical bounds using the annealed approximation. The quenched model is also discussed. For the second problem we obtain analytic and numerical results by evaluating the ground state energy of the q = 3 and 4 Potts spin glass using Parisi's replica symmetry breaking. We also performed some numerical simulations to test the theoretical result and obtained very good agreement. In the second part of the thesis, we simulate the Ising spin-glass model on a random lattice with a finite (average) coordination number and also on the Bethe lattice with various different boundary conditions. In particular, we calculate the overlap function P(q) for two independent samples. For the random lattice, the results are consistent with a spin-glass transition above which P(q) converges to a Dirac delta -function for large N (number of sites) and below which P(q) has in addition a long tail similar to previous results obtained for the infinite ranged model. For the Bethe lattice, we obtain results in the interior by discarding the two outer shells of the Cayley tree when calculating the thermal averages. For fixed (uncorrelated) boundary conditions, P(q) seems to converge to a delta -function even below the spin-glass transition whereas for a "closed" lattice (correlated boundary conditions) P(q) has a long tail similar to its behavior in the random lattice case.
NASA Technical Reports Server (NTRS)
Schatten, K. H.; Scherrer, P. H.; Svalgaard, L.; Wilcox, J. M.
1978-01-01
On physical grounds it is suggested that the sun's polar field strength near a solar minimum is closely related to the following cycle's solar activity. Four methods of estimating the sun's polar magnetic field strength near solar minimum are employed to provide an estimate of cycle 21's yearly mean sunspot number at solar maximum of 140 plus or minus 20. This estimate is considered to be a first order attempt to predict the cycle's activity using one parameter of physical importance.
Ramsey interferometry with an atom laser.
Döring, D; Debs, J E; Robins, N P; Figl, C; Altin, P A; Close, J D
2009-11-01
We present results on a free-space atom interferometer operating on the first order magnetically insensitive |F = 1,mF = 0) --> |F = 2,mF = 0) ground state transition of Bose-condensed (87)Rb atoms. A pulsed atom laser is output-coupled from a Bose-Einstein condensate and propagates through a sequence of two internal state beam splitters, realized via coherent Raman transitions between the two interfering states. We observe Ramsey fringes with a visibility close to 100% and determine the current and the potentially achievable interferometric phase sensitivity. This system is well suited to testing recent proposals for generating and detecting squeezed atomic states. PMID:19997295
Graphs, matrices, and the GraphBLAS: Seven good reasons
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.
Graphs, matrices, and the GraphBLAS: Seven good reasons
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
A Semantic Graph Query Language
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.
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…
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
A Robust Ramsey Interferometer for Atomic Timekeeping in Dynamic Environments
NASA Astrophysics Data System (ADS)
Kotru, Krish; Brown, Justin; Butts, David; Choy, Jennifer; Galfond, Marissa; Johnson, David M.; Kinast, Joseph; Timmons, Brian; Stoner, Richard
2014-05-01
We present a laser-based approach to atomic timekeeping, in which atomic phase information is extracted using modified Raman pulses in a Ramsey sequence. We overcome systematic effects associated with differential AC Stark shifts by employing atom optics derived from Raman adiabatic rapid passage (ARP). ARP drives coherent transfer between two hyperfine ground states by sweeping the frequency difference of two optical fields and maintaining a large single-photon detuning. Compared to resonant, pulsed Raman transitions, ARP atom optics afford a >150x reduction in sensitivity to differential AC Stark shifts in a Ramsey interferometer. We also demonstrate that ARP preserves fringe contrast in Ramsey interferometers for cloud displacements reaching the 1/e2 intensity radius of the laser beam. ARP can thus be expected to improve the robustness of clock interferometers operating in dynamic environments. Copyright ©2014 by The Charles Stark Draper Laboratory, Inc. All rights reserved.
Robust Ramsey sequences with Raman adiabatic rapid passage
NASA Astrophysics Data System (ADS)
Kotru, Krish; Brown, Justin M.; Butts, David L.; Kinast, Joseph M.; Stoner, Richard E.
2014-11-01
We present a method for robust timekeeping in which alkali-metal atoms are interrogated in a Ramsey sequence based on stimulated Raman transitions with optical photons. To suppress systematic effects introduced by differential ac Stark shifts and optical intensity gradients, we employ atom optics derived from Raman adiabatic rapid passage (ARP). Raman ARP drives coherent transfer between the alkali-metal hyperfine ground states via a sweep of the Raman detuning through the two-photon resonance. Our experimental implementation of Raman ARP reduced the phase sensitivity of Ramsey sequences to Stark shifts in 133Cs atoms by about two orders of magnitude, relative to fixed-frequency Raman transitions. This technique also preserved Ramsey fringe contrast for cloud displacements reaching the 1 /e2 intensity radius of the laser beam. In a magnetically unshielded apparatus, second-order Zeeman shifts limited the fractional frequency uncertainty to ˜3.5 ×10-12 after about 2500 s of averaging.
Ramsey fringes and time-domain multiple-slit interference from vacuum.
Akkermans, Eric; Dunne, Gerald V
2012-01-20
Sequences of alternating-sign time-dependent electric field pulses lead to coherent interference effects in Schwinger vacuum pair production, producing a Ramsey interferometer, an all-optical time-domain realization of the multiple-slit interference effect, directly from the quantum vacuum. The interference, obeying fermionic quantum statistics, is manifest in the momentum dependence of the number of produced electrons and positrons along the linearly polarized electric field. The central value grows like N(2) for N pulses [i.e., N "slits"], and the functional form is well described by a coherent multiple-slit expression. This behavior is generic for many driven quantum systems. PMID:22400718
Federal Register 2010, 2011, 2012, 2013, 2014
2013-07-19
... Surface Transportation Board Ramsey County Regional Railroad Authority--Acquisition Exemption--Right to Restore Rail Service Over a Railbanked Right-of-Way in Ramsey County, Minn. Ramsey County Regional..., and milepost 6.52, approximately 50 feet north of Beam Avenue in the City (the line), in Ramsey...
Ramsey patterns for multiquantum transitions in fountain experiments
McColm, D. |
1996-12-01
Ramsey patterns for radio-frequency multiquantum transitions among Zeeman levels of the ground state of thallium, cesium, and francium have been calculated. The narrowing of these patterns observed earlier by Gould is predicted to occur only when both static electric and magnetic fields are present. {copyright} {ital 1996 The American Physical Society.}
Anoka Ramsey Community College, Exploring America's Communities. Progress Report.
ERIC Educational Resources Information Center
Anoka Ramsey Community Coll., Coon Rapids, MN.
In 1996, Minnesota's Anoka Ramsey Community College (ARCC) participated in the Exploring America's Communities project sponsored by the American Association of Community Colleges. The project works to strengthen the teaching and learning of American History, literature, and culture at U.S. community colleges. The grant application from the ARCC…
Ramsey interferometry with a two-level generalized Tonks-Girardeau gas
Mousavi, S. V.; Campo, A. del; Lizuain, I.; Muga, J. G.
2007-09-15
We propose a solvable generalization of the Tonks-Girardeau model that describes a coherent one-dimensional (1D) gas of cold two-level bosons which interact with two external fields in a Ramsey interferometer. They also interact among themselves by idealized, infinitely strong contact potentials, with interchange of momentum and internal state. We study the corresponding Ramsey fringes and the quantum projection noise which, essentially unaffected by the interactions, remains that for ideal bosons. The dual system of this gas, an ideal gas of two-level fermions coupled by the interaction with the separated fields, produces the same fringes and noise fluctuations. The cases of time-separated and spatially separated fields are studied. For spatially separated fields the fringes may be broadened slightly by increasing the number of particles, but only for large particle numbers far from present experiments with Tonks-Girardeau gases. The uncertainty in the determination of the atomic transition frequency diminishes, essentially with the inverse root of the particle number. The difficulties to implement the model experimentally and possible shortcomings of strongly interacting 1D gases for frequency standards and atomic clocks are discussed.
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-1
Hyper-Ramsey spectroscopy of optical clock transitions
Yudin, V. I.; Taichenachev, A. V.; Oates, C. W.; Barber, Z. W.; Lemke, N. D.; Ludlow, A. D.; Sterr, U.; Lisdat, Ch.; Riehle, F.
2010-07-15
We present nonstandard optical Ramsey schemes that use pulses individually tailored in duration, phase, and frequency to cancel spurious frequency shifts related to the excitation itself. In particular, the field shifts and their uncertainties can be radically suppressed (by two to four orders of magnitude) in comparison with the usual Ramsey method (using two equal pulses) as well as with single-pulse Rabi spectroscopy. Atom interferometers and optical clocks based on two-photon transitions, heavily forbidden transitions, or magnetically induced spectroscopy could significantly benefit from this method. In the latter case, these frequency shifts can be suppressed considerably below a fractional level of 10{sup -17}. Moreover, our approach opens the door for high-precision optical clocks based on direct frequency comb spectroscopy.
A Fast Ramsey-Bordé Interferometer with Cold Lithium
NASA Astrophysics Data System (ADS)
Copenhaver, Eric; Cassella, Kayleigh; Mueller, Holger
2016-05-01
We demonstrate light-pulse interferometry with bosonic lithium in both Mach-Zehnder and Ramsey-Bordé geometries. We capture 12 million Li-7 atoms at 200 μK and build a fast interferometer with (~ 100 ns) stimulated Raman pulses and short interrogation times (tens to hundreds of microseconds). We achieve approximately 20 % of the maximum fringe contrast, which is limited to 25 % by non-interfering atomic trajectories. The contrast decays at a rate consistent with the limit set by thermal expansion out of the Raman beam. The signal in a Ramsey-Bordé interferometer scales inversely with mass and highlights the advantage of interferometry with light atoms like lithium. This allows for a measurement of the fine structure constant with shorter interrogation times than interferometers based on heavier atoms. Additionally, fast interferometers may have applications in the detection of high frequency signals resulting from exotic physics.
Generalized hyper-Ramsey resonance with separated oscillating fields
NASA Astrophysics Data System (ADS)
Zanon-Willette, T.; Yudin, V. I.; Taichenachev, A. V.
2015-08-01
An exact generalization of the Ramsey transition probability is derived to improve ultrahigh precision measurement and quantum state engineering when a particle is subjected to independently-tailored separated oscillating fields. The phase shift accumulated at the end of the interrogation scheme and associated with the particle wave function is offering a very high-level control of quantum states throughout various laser parameters conditions. The generalized hyper-Ramsey resonance based on independent manipulation of interaction time, field amplitude, phase, and frequency detuning is presented to increase performances in the next generation of atomic, molecular, and nuclear clocks, to upgrade high-resolution frequency measurement in Penning trap mass spectrometry and for a better control of light-induced frequency shifts in matter-wave interferometer or quantum information processing.
Ramsey-type spectroscopy in the XUV spectral region
Pirri, A.; Sali, E.; Cavalieri, S.; Corsi, C.; Bellini, M.; Eramo, R.
2010-02-02
We report an experimental and theoretical investigation of Ramsey-type spectroscopy with high-order harmonic generation applied to autoionizing states of Krypton. The ionization yield, detected by an ion-mass spectrometer, shows the characteristic quantum interference pattern. The behaviour of the fringe contrast was interpreted on the basis of a simple analytic model, which reproduces the experimental data without any free parameter.
Ramsey resonance of coherent population trapping in slow rubidium beam
NASA Astrophysics Data System (ADS)
Sokolov, I. M.
2016-03-01
We calculate the coherent population trapping (CPT) resonance in slow beam of rubidium 87 atoms caused by of their interaction with bichromatic electromagnetic field in two separated spatial domains. In the case of monovelocity beam we study the properties of the CPT resonance depending on type of working transitions, velocity of the atomic beam, intensity and polarization of electromagnetic fields, and space separation in Ramsey scheme.
A Robust Ramsey Interferometer for Atomic Timekeeping in Dynamic Environments
NASA Astrophysics Data System (ADS)
Kotru, Krish; Brown, Justin; Butts, David; Choy, Jennifer; Galfond, Marissa; Johnson, David M.; Kinast, Joseph; Timmons, Brian; Stoner, Richard
2014-05-01
We present a laser-based approach to atomic timekeeping, in which atomic phase information is extracted using modified Raman pulses in a Ramsey sequence. We overcome systematic effects associated with differential AC Stark shifts and variations in laser beam intensity by employing atom optics derived from Raman adiabatic rapid passage (ARP). This technique drives coherent transfer between two hyperfine ground states by sweeping the frequency difference of two optical fields and maintaining a large single-photon detuning. Compared to a Raman-pulse Ramsey interferometer, we show a >150x reduction in sensitivity to differential AC Stark shifts. We also demonstrate that ARP preserves fringe contrast in Ramsey interferometers for cloud displacements reaching the 1/e2 intensity radius of the laser beam. Deviations of the phase in response to changes in duration, rate, and range of the ARP frequency sweep are bounded to <7 mrad, implying a per-shot fractional frequency uncertainty of 1e-11 for an interrogation time of 10 ms. These characteristics are expected to improve the robustness of clock interferometers operating in dynamic environments. Copyright ©2014 by The Charles Stark Draper Laboratory, Inc. All rights reserved.
Random graphs with hidden color.
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
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…
ERIC Educational Resources Information Center
Auspos, Patricia; Miller, Cynthia; Hunter, Jo Anna
This report examines implementation and impacts of Ramsey County's Minnesota Family Investment Program (MFIP), a "work first" program. Chapter 1 lists key findings, provides an overview of the Ramsey County variant (MFIP-R) evaluation, and policy relevance of MFIP-R. Chapter 2 describes key features of MFIP-R and compares them with features of…
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.
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
Commuting projections on graphs
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 Q_{H} 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 Q_{H} commute with the discrete divergence operator, i.e., we have div π _{H} = Q_{H} 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.
Fault-tolerant Hahn-Ramsey interferometry with pulse sequences of alternating detuning
NASA Astrophysics Data System (ADS)
Vitanov, Nikolay V.; Gloger, Timm F.; Kaufmann, Peter; Kaufmann, Delia; Collath, Thomas; Tanveer Baig, M.; Johanning, Michael; Wunderlich, Christof
2015-03-01
A scheme for efficient correction of driving-field frequency drifts in Ramsey interferometry is proposed. The two off-resonant π /2 pulses of duration T used in the traditional Ramsey setup are supplemented with an additional pulse of duration 2 T (approximate π pulse), which is applied midway between the Ramsey pulses and has a detuning of opposite sign to theirs. This scheme, which resembles a Hahn's spin-echo pulse embedded into the Ramsey setup, corrects small-to-moderate random errors in the detuning of the driving field. This allows the observation of Ramsey fringes of high contrast even with a noisy driving field or in inhomogeneously broadened atomic ensembles. The contrast is further improved by replacing the refocusing 2 T pulse by a composite π pulse. We demonstrate the validity of the concept by comparing experimental results from usual Ramsey measurements with Hahn-Ramsey measurements. These experimental results are obtained from microwave-optical double-resonance spectroscopy on 171Yb+ ions in a segmented linear Paul trap. In the same way, we verify qualitatively the predicted advantage from using a composite π pulse for refocusing.
Improving Ramsey spectroscopy in the extreme-ultraviolet region with a random-sampling approach
Eramo, R.; Bellini, M.; Corsi, C.; Liontos, I.; Cavalieri, S.
2011-04-15
Ramsey-like techniques, based on the coherent excitation of a sample by delayed and phase-correlated pulses, are promising tools for high-precision spectroscopic tests of QED in the extreme-ultraviolet (xuv) spectral region, but currently suffer experimental limitations related to long acquisition times and critical stability issues. Here we propose a random subsampling approach to Ramsey spectroscopy that, by allowing experimentalists to reach a given spectral resolution goal in a fraction of the usual acquisition time, leads to substantial improvements in high-resolution spectroscopy and may open the way to a widespread application of Ramsey-like techniques to precision measurements in the xuv spectral region.
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.
Evaluation of Graph Pattern Matching Workloads in Graph Analysis Systems
Hong, Seokyong; Sukumar, Sreenivas Rangan; Vatsavai, Raju
2016-01-01
Graph analysis has emerged as a powerful method for data scientists to represent, integrate, query, and explore heterogeneous data sources. As a result, graph data management and mining became a popular area of research, and led to the development of plethora of systems in recent years. Unfortunately, the number of emerging graph analysis systems and the wide range of applications, coupled with a lack of apples-to-apples comparisons, make it difficult to understand the trade-offs between different systems and the graph operations for which they are designed. A fair comparison of these systems is a challenging task for the following reasons: multiple data models, non-standardized serialization formats, various query interfaces to users, and diverse environments they operate in. To address these key challenges, in this paper we present a new benchmark suite by extending the Lehigh University Benchmark (LUBM) to cover the most common capabilities of various graph analysis systems. We provide the design process of the benchmark, which generalizes the workflow for data scientists to conduct the desired graph analysis on different graph analysis systems. Equipped with this extended benchmark suite, we present performance comparison for nine subgraph pattern retrieval operations over six graph analysis systems, namely NetworkX, Neo4j, Jena, Titan, GraphX, and uRiKA. Through the proposed benchmark suite, this study reveals both quantitative and qualitative findings in (1) implications in loading data into each system; (2) challenges in describing graph patterns for each query interface; and (3) different sensitivity of each system to query selectivity. We envision that this study will pave the road for: (i) data scientists to select the suitable graph analysis systems, and (ii) data management system designers to advance graph analysis systems.
Coloring geographical threshold graphs
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.
RAMSEYS DRAFT WILDERNESS STUDY AREA AND ADDITION, VIRGINIA.
Lesure, Frank G.; Mory, Peter C.
1984-01-01
Mineral-resource surveys of the Ramseys Draft Wilderness Study Area and adjoining roadless area addition in George Washington National Forest in the western valley and ridge province, Augusta and Highland Counties, Virginia, were done. The surveys outlined three small areas containing anomalous amounts of copper, lead, and zinc related to stratabound red-bed copper mineralization, but these occurrences are not large and are not considered as having mineral-resource potential. The area contains abundant sandstone suitable for construction materials and shale suitable for making brick, tile, and other low-grade ceramic products, but these commodities occur in abundance outside the wilderness study area. Structural conditions are probably favorable for the accumulation of natural gas, but exploratory drilling has not been done sufficiently near the area to evaluate the gas potential.
Multiphoton- and simultaneous conjugate Ramsey-Borde atom interferometers
Mueller, Holger; Chiow, Sheng-wey; Herrmann, Sven; Chu, Steven
2008-03-06
We report on our experiment to measure h/M, the ratio of the Planck constant to the mass of Cs atoms, and thereby the fine-structure constant. The target accuracy is 1 part per billion or better. We focus on two recent milestones: (i) The first realization of atom interferometers based on light-pulse beam splitters that transfer the momentum of up to 12 photon pairs, which increases the useful signal (matter wave phase shift) by a factor of 144 compared to the beam splitters used in the best present atom interferometers. Moreover, they lead to a cancellation of important systematic effects. (ii) The first realization of a simultaneous pair of conjugate Ramsey-Borde interferometers. In these, the relative sign of the inertial term is reversed so that it can be cancelled. Simultaneous operation means that this holds for a time-dependent inertial term (vibrations) too, which promises a substantial improvement in the signal to noise ratio.
Magnetic tensor gradiometry using Ramsey interferometry of spinor condensates
NASA Astrophysics Data System (ADS)
Wood, A. A.; Bennie, L. M.; Duong, A.; Jasperse, M.; Turner, L. D.; Anderson, R. P.
2015-11-01
We have realized a magnetic tensor gradiometer by interferometrically measuring the relative phase between two spatially separated Bose-Einstein condensates (BECs). We perform simultaneous Ramsey interferometry of the proximate 87Rb spin-1 condensates in free fall and infer their relative Larmor phase, and thus the differential magnetic-field strength, with a common-mode phase noise suppression exceeding 50 dB . By appropriately biasing the magnetic field and separating the BECs along orthogonal directions, we measure in vacuo the magnetic-field-gradient tensor of ambient and applied magnetic fields with a nominal precision of 0.30 nT mm-1 and a sensor volume of 2 ×10-5mm3 . We predict a spin-projection noise-limited magnetic energy resolution of order ˜10 ℏ for typical Zeeman coherence times of trapped condensates with this scheme, even with the low measurement duty cycle of current BEC experiments.
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…
Park, Young-Ho; Lee, Soo Heyong; Park, Sang Eon; Lee, Ho Seong; Kwon, Taeg Yong
2007-04-23
The authors report on a method to determine the Rabi frequency and transit time distribution of atoms that are essential for proper operation of atomic beam frequency standards. Their method, which employs alternative regularized inverse on two Ramsey spectra measured at different microwave powers, can be used for the frequency standards with short Ramsey cavity as well as long ones. The authors demonstrate that uncertainty in Rabi frequency obtained from their method is 0.02%.
Optical Ramsey spectroscopy of a single trapped {sup 88}Sr{sup +} ion
Letchumanan, V.; Gill, P.; Sinclair, A.G.; Riis, E.
2004-09-01
Coherent optical spectroscopy has been performed on the narrow 5s {sup 2}S{sub 1/2}-4d {sup 2}D{sub 5/2} quadrupole transition in a single Doppler-cooled and trapped {sup 88}Sr{sup +} ion. High-contrast optical Ramsey spectra have been observed with fringe visibilities up to {approx}90%. The visibility decreased as the free precession period was increased, and was limited by the interrogation laser's coherence. The effect of varying the relative phase of the second Ramsey pulse was investigated. By measuring the difference in excitation probability on reversing a 90 deg. relative phase shift between the two Ramsey pulses, we have demonstrated Ramsey's anti-symmetric line shape in the optical domain. A significant advantage of this line shape is the zero crossing at line center and the independence of this center frequency on drifts in signal amplitude. This optical Ramsey line shape is suitable for stabilizing a local oscillator to an atomic reference transition in an optical frequency standard. All observed optical Ramsey signals are well described by a model using the optical Bloch equations.
Raberto, Marco; Rapallo, Fabio; Scalas, Enrico
2011-01-01
In this paper, we outline a model of graph (or network) dynamics based on two ingredients. The first ingredient is a Markov chain on the space of possible graphs. The second ingredient is a semi-Markov counting process of renewal type. The model consists in subordinating the Markov chain to the semi-Markov counting process. In simple words, this means that the chain transitions occur at random time instants called epochs. The model is quite rich and its possible connections with algebraic geometry are briefly discussed. Moreover, for the sake of simplicity, we focus on the space of undirected graphs with a fixed number of nodes. However, in an example, we present an interbank market model where it is meaningful to use directed graphs or even weighted graphs. PMID:21887245
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.
Yang, Jing; Yun, Peter; Tian, Yuan; Tan, Bozhong; Gu, Sihong
2014-03-07
A scheme for a Ramsey-coherent population trapping (CPT) atomic clock that eliminates the acousto-optic modulator (AOM) is proposed and experimentally studied. Driven by a periodically microwave modulated current, the vertical-cavity surface-emitting laser emits a continuous beam that switches between monochromatic and multichromatic modes. Ramsey-CPT interference has been studied with this mode-switching beam. In eliminating the AOM, which is used to generate pulsed laser in conventional Ramsey-CPT atomic clock, the physics package of the proposed scheme is virtually the same as that of a conventional compact CPT atomic clock, although the resource budget for the electronics will slightly increase as a microwave switch should be added. By evaluating and comparing experimentally recorded signals from the two Ramsey-CPT schemes, the short-term frequency stability of the proposed scheme was found to be 46% better than the scheme with AOM. The experimental results suggest that the implementation of a compact Ramsey-CPT atomic clock promises better frequency stability.
Learning Financial Reports From Mixed Symbolic-Spatial Graphs
ERIC Educational Resources Information Center
Tanlamai, Uthai; Soongswang, Oranuj
2011-01-01
Mixed visuals of numbers and graphs are available in various financial reports that demonstrate the financial status and risks of a firm. GWN (graphs with numbers) and TWG (table of numbers with graphs) were used as two alternative visuals derived from the actual data of two large public companies, one from food manufacturing industry (food) and…
The Feynman Identity for Planar Graphs
NASA Astrophysics Data System (ADS)
da Costa, G. A. T. F.
2016-08-01
The Feynman identity (FI) of a planar graph relates the Euler polynomial of the graph to an infinite product over the equivalence classes of closed nonperiodic signed cycles in the graph. The main objectives of this paper are to compute the number of equivalence classes of nonperiodic cycles of given length and sign in a planar graph and to interpret the data encoded by the FI in the context of free Lie superalgebras. This solves in the case of planar graphs a problem first raised by Sherman and sets the FI as the denominator identity of a free Lie superalgebra generated from a graph. Other results are obtained. For instance, in connection with zeta functions of graphs.
Hierarchical structure of the logical Internet graph
NASA Astrophysics Data System (ADS)
Ge, Zihui; Figueiredo, Daniel R.; Jaiswal, Sharad; Gao, Lixin
2001-07-01
The study of the Internet topology has recently received much attention from the research community. In particular, the observation that the network graph has interesting properties, such as power laws, that might be explored in a myriad of ways. Most of the work in characterizing the Internet graph is based on the physical network graph, i.e., the connectivity graph. In this paper we investigate how logical relationships between nodes of the AS graph can be used to gain insight to its structure. We characterize the logical graph using various metrics and identify the presence of power laws in the number of customers that a provider has. Using these logical relationships we define a structural model of the AS graph. The model highlights the hierarchical nature of logical relationships and the preferential connection to larger providers. We also investigate the consistency of this model over time and observe interesting properties of the hierarchical structure.
The Bryant-Anthony-Ramsey (B-A-R) Project: An Evaluation. Report C-73-2.
ERIC Educational Resources Information Center
Mueller, Mildred K.
The Bryant-Anthony-Ramsey (B-A-R) Project is a desegregation/integration project aimed at assuring a smooth transition from a predominately segregated school environment to a desegregated or integrated environment. The Bryant, Anthony, and Ramsey Junior High Schools are participants in a desegregation effort that is one part of an overall…
Graph Coloring Used to Model Traffic Lights.
ERIC Educational Resources Information Center
Williams, John
1992-01-01
Two scheduling problems, one involving setting up an examination schedule and the other describing traffic light problems, are modeled as colorings of graphs consisting of a set of vertices and edges. The chromatic number, the least number of colors necessary for coloring a graph, is employed in the solutions. (MDH)
Optical Ramsey spectroscopy in a rotating frame: Sagnac effect in a matter-wave interferometer
Riehle, F.; Kisters, T.; Witte, A.; Helmcke, J. ); Borde, C.J. Laboratoire de Physique des Lasers, Universite Paris, Villetaneuse, France )
1991-07-08
A calcium atomic beam excited in an optical Ramsey geometry was rotated about an axis perpendicular to the plane defined by the laser beams and the atomic beam. A frequency shift of the Ramsey fringes of several kHz has been measured which is proportional to the rotation frequency of the apparatus and to the distance between the laser beams. The results can be interpreted in three equivalent ways as the Sagnac effect in a calcium-atomic-beam interferometer: in the rotating frame of the laser beams either along straight paths or along the curved trajectories of the atoms, or in the inertial atomic frame.
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…
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)
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.
Smalter, Aaron; Huan, Jun Luke; Jia, Yi; Lushington, Gerald
2010-01-01
Graph data mining is an active research area. Graphs are general modeling tools to organize information from heterogeneous sources and have been applied in many scientific, engineering, and business fields. With the fast accumulation of graph data, building highly accurate predictive models for graph data emerges as a new challenge that has not been fully explored in the data mining community. In this paper, we demonstrate a novel technique called graph pattern diffusion (GPD) kernel. Our idea is to leverage existing frequent pattern discovery methods and to explore the application of kernel classifier (e.g., support vector machine) in building highly accurate graph classification. In our method, we first identify all frequent patterns from a graph database. We then map subgraphs to graphs in the graph database and use a process we call "pattern diffusion" to label nodes in the graphs. Finally, we designed a graph alignment algorithm to compute the inner product of two graphs. We have tested our algorithm using a number of chemical structure data. The experimental results demonstrate that our method is significantly better than competing methods such as those kernel functions based on paths, cycles, and subgraphs. PMID:20431140
Inferring Pedigree Graphs from Genetic Distances
NASA Astrophysics Data System (ADS)
Tamura, Takeyuki; Ito, Hiro
In this paper, we study a problem of inferring blood relationships which satisfy a given matrix of genetic distances between all pairs of n nodes. Blood relationships are represented by our proposed graph class, which is called a pedigree graph. A pedigree graph is a directed acyclic graph in which the maximum indegree is at most two. We show that the number of pedigree graphs which satisfy the condition of given genetic distances may be exponential, but they can be represented by one directed acyclic graph with n nodes. Moreover, an O(n3) time algorithm which solves the problem is also given. Although phylogenetic trees and phylogenetic networks are similar data structures to pedigree graphs, it seems that inferring methods for phylogenetic trees and networks cannot be applied to infer pedigree graphs since nodes of phylogenetic trees and networks represent species whereas nodes of pedigree graphs represent individuals. We also show an O(n2) time algorithm which detects a contradiction between a given pedigreee graph and distance matrix of genetic distances.
Single Parent Families: A Needs Assessment Survey of Single Parents, Ramsey County, Minnesota.
ERIC Educational Resources Information Center
Chase, Richard A.; And Others
This report provides findings of an in-person survey of single parents in Ramsey County, Minnesota. The report is organized into seven chapters. Chapter 1 provides a current demographic, educational, and economic profile of single parents and examines whether the backgrounds of single parents relate to their present conditions. Chapter 2 describes…
ERIC Educational Resources Information Center
Sandell, Elizabeth J., Ed.
This report describes the initial plan, participants, and evaluation of Saint Paul (Minnesota) Children's Initiative (SPCI) during 1993. The SPCI is a family-community program to improve child health, child development, school performance, and to enhance family functioning through formal and informal support systems in Saint Paul/Ramsey county. At…
An Evaluation of the Pilot Child Care Sliding Fee Program in Ramsey County.
ERIC Educational Resources Information Center
Ramsey County Child Care Council, Inc., St. Paul, Minn.
This study was designed to assess the monetary and human costs and benefits of the Pilot Child Care Sliding Fee Program in Ramsey County, Minnesota. A 21-item questionnaire was used to survey 53 of the 161 families who had participated in the program. The vast majority of the sample consisted of single, female, working-parent families with from…
Lost Innocent and Sacrificial Delegate: The JonBenet Ramsey Murder.
ERIC Educational Resources Information Center
Conrad, Joann
1999-01-01
Analyzes murder case of 6-year-old JonBenet Ramsey as emblematic of American cultural fascination with images of the innocence of children and the perfect family, and of a change in cultural self-awareness as these images prove illusionary. Considers the role of mass media in marketing a cultural fascination with sexualized images of children and…
Report on Child Care Services in Ramsey County: Fees Charged and Rates of Utilization.
ERIC Educational Resources Information Center
Ramsey County Child Care Council, Inc., St. Paul, Minn.
This report describes the second annual survey of utilization of child care services (day care homes and day care centers) in Ramsey County, Minnesota. Information about fees charged is included. Data from day care homes and centers were collected by mail or telephone. The rate of utilization of child care services was determined by county, county…
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.
Fast generation of sparse random kernel graphs
Hagberg, Aric; Lemons, Nathan; Du, Wen -Bo
2015-09-10
The development of kernel-based inhomogeneous random graphs has provided models that are flexible enough to capture many observed characteristics of real networks, and that are also mathematically tractable. We specify a class of inhomogeneous random graph models, called random kernel graphs, that produces sparse graphs with tunable graph properties, and we develop an efficient generation algorithm to sample random instances from this model. As real-world networks are usually large, it is essential that the run-time of generation algorithms scales better than quadratically in the number of vertices n. We show that for many practical kernels our algorithm runs in timemore » at most ο(n(logn)²). As an example, we show how to generate samples of power-law degree distribution graphs with tunable assortativity.« less
Fast generation of sparse random kernel graphs
Hagberg, Aric; Lemons, Nathan; Du, Wen -Bo
2015-09-10
The development of kernel-based inhomogeneous random graphs has provided models that are flexible enough to capture many observed characteristics of real networks, and that are also mathematically tractable. We specify a class of inhomogeneous random graph models, called random kernel graphs, that produces sparse graphs with tunable graph properties, and we develop an efficient generation algorithm to sample random instances from this model. As real-world networks are usually large, it is essential that the run-time of generation algorithms scales better than quadratically in the number of vertices n. We show that for many practical kernels our algorithm runs in time at most ο(n(logn)²). As an example, we show how to generate samples of power-law degree distribution graphs with tunable assortativity.
Fast Generation of Sparse Random Kernel Graphs
2015-01-01
The development of kernel-based inhomogeneous random graphs has provided models that are flexible enough to capture many observed characteristics of real networks, and that are also mathematically tractable. We specify a class of inhomogeneous random graph models, called random kernel graphs, that produces sparse graphs with tunable graph properties, and we develop an efficient generation algorithm to sample random instances from this model. As real-world networks are usually large, it is essential that the run-time of generation algorithms scales better than quadratically in the number of vertices n. We show that for many practical kernels our algorithm runs in time at most 𝒪(n(logn)2). As a practical example we show how to generate samples of power-law degree distribution graphs with tunable assortativity. PMID:26356296
Subvoxel accurate graph search using non-Euclidean graph space.
Abràmoff, Michael D; Wu, Xiaodong; Lee, Kyungmoo; Tang, Li
2014-01-01
Graph search is attractive for the quantitative analysis of volumetric medical images, and especially for layered tissues, because it allows globally optimal solutions in low-order polynomial time. However, because nodes of graphs typically encode evenly distributed voxels of the volume with arcs connecting orthogonally sampled voxels in Euclidean space, segmentation cannot achieve greater precision than a single unit, i.e. the distance between two adjoining nodes, and partial volume effects are ignored. We generalize the graph to non-Euclidean space by allowing non-equidistant spacing between nodes, so that subvoxel accurate segmentation is achievable. Because the number of nodes and edges in the graph remains the same, running time and memory use are similar, while all the advantages of graph search, including global optimality and computational efficiency, are retained. A deformation field calculated from the volume data adaptively changes regional node density so that node density varies with the inverse of the expected cost. We validated our approach using optical coherence tomography (OCT) images of the retina and 3-D MR of the arterial wall, and achieved statistically significant increased accuracy. Our approach allows improved accuracy in volume data acquired with the same hardware, and also, preserved accuracy with lower resolution, more cost-effective, image acquisition equipment. The method is not limited to any specific imaging modality and readily extensible to higher dimensions. PMID:25314272
Loops in Reeb Graphs of 2-Manifolds
Cole-McLaughlin, K; Edelsbrunner, H; Harer, J; Natarajan, V; Pascucci, V
2004-12-16
Given a Morse function f over a 2-manifold with or without boundary, the Reeb graph is obtained by contracting the connected components of the level sets to points. We prove tight upper and lower bounds on the number of loops in the Reeb graph that depend on the genus, the number of boundary components, and whether or not the 2-manifold is orientable. We also give an algorithm that constructs the Reeb graph in time O(n log n), where n is the number of edges in the triangulation used to represent the 2-manifold and the Morse function.
Loops in Reeb Graphs of 2-Manifolds
Cole-McLaughlin, K; Edelsbrunner, H; Harer, J; Natarajan, V; Pascucci, V
2003-02-11
Given a Morse function f over a 2-manifold with or without boundary, the Reeb graph is obtained by contracting the connected components of the level sets to points. We prove tight upper and lower bounds on the number of loops in the Reeb graph that depend on the genus, the number of boundary components, and whether or not the 2-manifold is orientable. We also give an algorithm that constructs the Reeb graph in time O(n log n), where n is the number of edges in the triangulation used to represent the 2-manifold and the Morse function.
Fibonacci Identities, Matrices, and Graphs
ERIC Educational Resources Information Center
Huang, Danrun
2005-01-01
General strategies used to help discover, prove, and generalize identities for Fibonacci numbers are described along with some properties about the determinants of square matrices. A matrix proof for identity (2) that has received immense attention from many branches of mathematics, like linear algebra, dynamical systems, graph theory and others…
Acyclic colorings of graphs with bounded degree
NASA Astrophysics Data System (ADS)
Fiedorowicz, Anna; Sidorowicz, Elżbieta
2016-07-01
A $k$-colouring (not necessarily proper) of vertices of a graph is called {\\it acyclic}, if for every pair of distinct colours $i$ and $j$ the subgraph induced by the edges whose endpoints have colours $i$ and $j$ is acyclic. In the paper we consider some generalised acyclic $k$-colourings, namely, we require that each colour class induces an acyclic or bounded degree graph. Mainly we focus on graphs with maximum degree 5. We prove that any such graph has an acyclic $5$-colouring such that each colour class induces an acyclic graph with maximum degree at most 4. We prove that the problem of deciding whether a graph $G$ has an acyclic 2-colouring in which each colour class induces a graph with maximum degree at most 3 is NP-complete, even for graphs with maximum degree 5. We also give a linear-time algorithm for an acyclic $t$-improper colouring of any graph with maximum degree $d$ assuming that the number of colors is large enough.
Optimal preparation of graph states
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.
ERIC Educational Resources Information Center
VanDoren, Sandra Shaffer
This paper describes the cataloging, shelf arrangement, and preservation of Wayne State University's Eloise Ramsey collection of children's books. It also outlines Wayne State's efforts to consolidate the collection and to make it accessible to the public. (FM)
XV-3 in Ames Reseach Center 40x80ft wind tunnel with K. Edenborough and B. Ramsey, engineers
NASA Technical Reports Server (NTRS)
1966-01-01
XV-3 in Ames Reseach Center 40x80ft wind tunnel with K. Edenborough and B. Ramsey, engineers Published in The History of the XV-15 Tilt Rotor Research Aircraft (from Concept to Flight NASA SP-2000-4517)
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)
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…
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…
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.
NASA Astrophysics Data System (ADS)
Prudente, Matthew James
Given a graph G with pebbles on the vertices, we define a pebbling move as removing two pebbles from a vertex u, placing one pebble on a neighbor v, and discarding the other pebble, like a toll. The pebbling number pi( G) is the least number of pebbles needed so that every arrangement of pi(G) pebbles can place a pebble on any vertex through a sequence of pebbling moves. We introduce a new variation on graph pebbling called two-player pebbling. In this, players called the mover and the defender alternate moves, with the stipulation that the defender cannot reverse the previous move. The mover wins only if they can place a pebble on a specified vertex and the defender wins if the mover cannot. We define η(G), analogously, as the minimum number of pebbles such that given every configuration of the η( G) pebbles and every specified vertex r, the mover has a winning strategy. First, we will investigate upper bounds for η( G) on various classes of graphs and find a certain structure for which the defender has a winning strategy, no matter how many pebbles are in a configuration. Then, we characterize winning configurations for both players on a special class of diameter 2 graphs. Finally, we show winning configurations for the mover on paths using a recursive argument.
Detecting alternative graph clusterings.
Mandala, Supreet; Kumara, Soundar; Yao, Tao
2012-07-01
The problem of graph clustering or community detection has enjoyed a lot of attention in complex networks literature. A quality function, modularity, quantifies the strength of clustering and on maximization yields sensible partitions. However, in most real world networks, there are an exponentially large number of near-optimal partitions with some being very different from each other. Therefore, picking an optimal clustering among the alternatives does not provide complete information about network topology. To tackle this problem, we propose a graph perturbation scheme which can be used to identify an ensemble of near-optimal and diverse clusterings. We establish analytical properties of modularity function under the perturbation which ensures diversity. Our approach is algorithm independent and therefore can leverage any of the existing modularity maximizing algorithms. We numerically show that our methodology can systematically identify very different partitions on several existing data sets. The knowledge of diverse partitions sheds more light into the topological organization and helps gain a more complete understanding of the underlying complex network. PMID:23005495
Detecting alternative graph clusterings
NASA Astrophysics Data System (ADS)
Mandala, Supreet; Kumara, Soundar; Yao, Tao
2012-07-01
The problem of graph clustering or community detection has enjoyed a lot of attention in complex networks literature. A quality function, modularity, quantifies the strength of clustering and on maximization yields sensible partitions. However, in most real world networks, there are an exponentially large number of near-optimal partitions with some being very different from each other. Therefore, picking an optimal clustering among the alternatives does not provide complete information about network topology. To tackle this problem, we propose a graph perturbation scheme which can be used to identify an ensemble of near-optimal and diverse clusterings. We establish analytical properties of modularity function under the perturbation which ensures diversity. Our approach is algorithm independent and therefore can leverage any of the existing modularity maximizing algorithms. We numerically show that our methodology can systematically identify very different partitions on several existing data sets. The knowledge of diverse partitions sheds more light into the topological organization and helps gain a more complete understanding of the underlying complex network.
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.
Coloring random graphs and maximizing local diversity.
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
Composite pulses in Hyper-Ramsey spectroscopy for the next generation of atomic clocks
NASA Astrophysics Data System (ADS)
Zanon-Willette, T.; Minissale, M.; Yudin, V. I.; Taichenachev, A. V.
2016-06-01
The next generation of atomic frequency standards based on an ensemble of neutral atoms or a single-ion will provide very stringent tests in metrology, applied and fundamental physics requiring a new step in very precise control of external systematic corrections. In the proceedings of the 8th Symposium on Frequency Standards and Metrology, we present a generalization of the recent Hyper-Ramsey spectroscopy with separated oscillating fields using composites pulses in order to suppress field frequency shifts induced by the interrogation laser itself. Sequences of laser pulses including specific selection of phases, frequency detunings and durations are elaborated to generate spectroscopic signals with a strong reduction of the light-shift perturbation by off resonant states. New optical clocks based on weakly allowed or completely forbidden transitions in atoms, ions, molecules and nuclei will benefit from these generalized Ramsey schemes to reach relative accuracies well below the 10-18 level.
Accessing Rydberg-dressed interactions using many-body Ramsey dynamics
NASA Astrophysics Data System (ADS)
Mukherjee, Rick; Killian, Thomas; Hazzard, Kaden
2016-05-01
We demonstrate that Ramsey spectroscopy can be used to observe Rydberg-dressed interactions in a many-body system. Our scheme operates comfortably within experimentally measured lifetimes, and accesses a regime where quantum superpositions are crucial. We build a spin-1/2 from one level that is Rydberg-dressed and another that is not. These levels may be hyperfine or long-lived electronic states. An Ising spin model governs the Ramsey dynamics, for which we derive an exact solution. Due to the structure of Rydberg interactions, the dynamics differs significantly from that in other spin systems. As one example, spin echo can increase the rate at which coherence decays. The results are relevant for the current ongoing experiments, including those at Rice University.
Effect of atomic diffusion on the Raman-Ramsey coherent population trapping resonances
NASA Astrophysics Data System (ADS)
Kuchina, Elena; Mikhailov, Eugeniy E.; Novikova, Irina
2016-04-01
We experimentally investigated the characteristics of two-photon transmission resonances in Rb vapor cells with different amount of buffer gas under the conditions of steady-state coherent population trapping (CPT) and pulsed Raman-Ramsey (RR-) CPT interrogation scheme. We particularly focused on the influence of the Rb atoms diffusing in and out of the laser beam. We showed that this effect modifies the shape of both CPT and Raman-Ramsey resonances, as well as their projected performance for CPT clock applications. In particular we found that at moderate buffer gas pressures RR-CPT did not improved the projected atomic clock stability compare to the regular steady-state CPT resonance.
Zanon, T.; Guerandel, S.; Clercq, E. de; Holleville, D.; Dimarcq, N.; Clairon, A.
2005-05-20
We report the observation of Raman-Ramsey fringes using a double lambda scheme creating coherent population trapping in an atomic ensemble combined with pulsed optical radiations. The observation was made in a Cs vapor mixed with N{sub 2} buffer gas in a closed cell. The double lambda scheme is created with lin perpendicular lin polarized laser beams leading to higher contrast than the usual simple lambda scheme. The pulsed trapping technique leads to narrow fringe widths scaling as 1/(2T) with high contrasts which are no longer limited by the saturation effect. This technique operates in a different way from the classical Ramsey sequence: the signal is done by applying a long trapping pulse to prepare the atomic state superposition, and fringe detection is accomplished by optical transmission during a short second trapping pulse without any perturbation of the dark state.
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.
Abele, H.; Jenke, T.; Leeb, H.; Schmiedmayer, J.
2010-03-15
We propose to apply Ramsey's method of separated oscillating fields to the spectroscopy of the quantum states in the gravity potential above a horizontal mirror. This method allows a precise measurement of quantum mechanical phaseshifts of a Schroedinger wave packet bouncing off a hard surface in the gravitational field of the Earth. Measurements with ultracold neutrons will offer a sensitivity to Newton's law or hypothetical short-ranged interactions, which is about 21 orders of magnitude below the energy scale of electromagnetism.
Study of field shifts of Ramsey resonances on ultracold atoms and ions
Tabatchikova, K. S.; Taichenachev, A. V.; Dmitriev, A. K.; Yudin, V. I.
2015-02-15
The effect of the finite laser radiation line width and spontaneous relaxation of levels on the efficiency of the suppression of the field shift of the central resonance for the generalized Ramsey scheme with pulses of different lengths and with a phase jump in the second pulse has been considered. The optimal parameters of the scheme corresponding to the minimum frequency shift and maximum amplitude of the resonance have been determined.
Historical overview of Ramsey spectroscopy and its relevance on Time and Frequency Metrology
NASA Astrophysics Data System (ADS)
Amaral, M. M.; Tarelho, L. V. G.; de Souza, M. A.; Baratto, A. C.; Garcia, G. A.; Muller, S. T.; De Martin, J., Jr.; Rodriguez, A. S.; Bebeachibuli, A.; Magalhães, D. V.
2016-07-01
A brief overview of the historical evolution of the method of successive oscillatory fields developed by Norman Ramsey, and some different implementations of the decurrent methodology are presented. We use time and frequency standards, from Cs atomic beams to optical standards, as examples. The scientific progress and the technological implementation achieved through a partnership between USP-SC and INMETRO are shown on the characterization of each time and frequency standard.
On the Kirchhoff Index of Graphs
NASA Astrophysics Data System (ADS)
Das, Kinkar C.
2013-09-01
Let G be a connected graph of order n with Laplacian eigenvalues μ1 ≥ μ2 ≥ ... ≥ μn-1 > mn = 0. The Kirchhoff index of G is defined as [xxx] In this paper. we give lower and upper bounds on Kf of graphs in terms on n, number of edges, maximum degree, and number of spanning trees. Moreover, we present lower and upper bounds on the Nordhaus-Gaddum-type result for the Kirchhoff index.
Enabling Graph Appliance for Genome Assembly
Singh, Rina; Graves, Jeffrey A; Lee, Sangkeun; Sukumar, Sreenivas R; Shankar, Mallikarjun
2015-01-01
In recent years, there has been a huge growth in the amount of genomic data available as reads generated from various genome sequencers. The number of reads generated can be huge, ranging from hundreds to billions of nucleotide, each varying in size. Assembling such large amounts of data is one of the challenging computational problems for both biomedical and data scientists. Most of the genome assemblers developed have used de Bruijn graph techniques. A de Bruijn graph represents a collection of read sequences by billions of vertices and edges, which require large amounts of memory and computational power to store and process. This is the major drawback to de Bruijn graph assembly. Massively parallel, multi-threaded, shared memory systems can be leveraged to overcome some of these issues. The objective of our research is to investigate the feasibility and scalability issues of de Bruijn graph assembly on Cray s Urika-GD system; Urika-GD is a high performance graph appliance with a large shared memory and massively multithreaded custom processor designed for executing SPARQL queries over large-scale RDF data sets. However, to the best of our knowledge, there is no research on representing a de Bruijn graph as an RDF graph or finding Eulerian paths in RDF graphs using SPARQL for potential genome discovery. In this paper, we address the issues involved in representing a de Bruin graphs as RDF graphs and propose an iterative querying approach for finding Eulerian paths in large RDF graphs. We evaluate the performance of our implementation on real world ebola genome datasets and illustrate how genome assembly can be accomplished with Urika-GD using iterative SPARQL queries.
Understanding the role of spin-motion coupling in Ramsey spectroscopy
NASA Astrophysics Data System (ADS)
Koller, Andrew; Beverland, Michael; Mundinger, Joshua; Gorshkov, Alexey; Rey, Ana Maria
2014-05-01
Ramsey spectroscopy has become a powerful technique for probing non-equilibrium dynamics of internal (pseudospin) degrees of freedom of interacting systems. In many theoretical treatments, the key to understanding the dynamics has been to assume the external (motional) degrees of freedom are decoupled from the pseudospin degrees of freedom. Determining the validity of this approximation - known as the spin model approximation - has not been addressed in detail. We shed light in this direction by calculating Ramsey dynamics exactly for two interacting spin-1/2 particles in a harmonic trap. We find that in 1D the spin model assumption works well over a wide range of experimentally-relevant conditions, but can fail at time scales longer than those set by the mean interaction energy. Surprisingly, in 2D a modified version of the spin model is exact to first order in the interaction strength. This analysis is important for a correct interpretation of Ramsey spectroscopy and has broad applications ranging from precision measurements to quantum information and to fundamental probes of many-body systems. Supported by NSF, ARO-DARPA-OLE, AFOSR, NIST, the Lee A. DuBridge and Gordon and Betty Moore Foundations, and the NDSEG program.
Vortices and superfields on a graph
Kan, Nahomi; Kobayashi, Koichiro; Shiraishi, Kiyoshi
2009-08-15
We extend the dimensional deconstruction by utilizing the knowledge of graph theory. In the dimensional deconstruction, one uses the moose diagram to exhibit the structure of the 'theory space'. We generalize the moose diagram to a general graph with oriented edges. In the present paper, we consider only the U(1) gauge symmetry. We also introduce supersymmetry into our model by use of superfields. We suppose that vector superfields reside at the vertices and chiral superfields at the edges of a given graph. Then we can consider multivector, multi-Higgs models. In our model, [U(1)]{sup p} (where p is the number of vertices) is broken to a single U(1). Therefore, for specific graphs, we get vortexlike classical solutions in our model. We show some examples of the graphs admitting the vortex solutions of simple structure as the Bogomolnyi solution.
Vortices and superfields on a graph
NASA Astrophysics Data System (ADS)
Kan, Nahomi; Kobayashi, Koichiro; Shiraishi, Kiyoshi
2009-08-01
We extend the dimensional deconstruction by utilizing the knowledge of graph theory. In the dimensional deconstruction, one uses the moose diagram to exhibit the structure of the “theory space.” We generalize the moose diagram to a general graph with oriented edges. In the present paper, we consider only the U(1) gauge symmetry. We also introduce supersymmetry into our model by use of superfields. We suppose that vector superfields reside at the vertices and chiral superfields at the edges of a given graph. Then we can consider multivector, multi-Higgs models. In our model, [U(1)]p (where p is the number of vertices) is broken to a single U(1). Therefore, for specific graphs, we get vortexlike classical solutions in our model. We show some examples of the graphs admitting the vortex solutions of simple structure as the Bogomolnyi solution.
Pattern vectors from algebraic graph theory.
Wilson, Richard C; Hancock, Edwin R; Luo, Bin
2005-07-01
Graph structures have proven computationally cumbersome for pattern analysis. The reason for this is that, before graphs can be converted to pattern vectors, correspondences must be established between the nodes of structures which are potentially of different size. To overcome this problem, in this paper, we turn to the spectral decomposition of the Laplacian matrix. We show how the elements of the spectral matrix for the Laplacian can be used to construct symmetric polynomials that are permutation invariants. The coefficients of these polynomials can be used as graph features which can be encoded in a vectorial manner. We extend this representation to graphs in which there are unary attributes on the nodes and binary attributes on the edges by using the spectral decomposition of a Hermitian property matrix that can be viewed as a complex analogue of the Laplacian. To embed the graphs in a pattern space, we explore whether the vectors of invariants can be embedded in a low-dimensional space using a number of alternative strategies, including principal components analysis (PCA), multidimensional scaling (MDS), and locality preserving projection (LPP). Experimentally, we demonstrate that the embeddings result in well-defined graph clusters. Our experiments with the spectral representation involve both synthetic and real-world data. The experiments with synthetic data demonstrate that the distances between spectral feature vectors can be used to discriminate between graphs on the basis of their structure. The real-world experiments show that the method can be used to locate clusters of graphs. PMID:16013758
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.
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.
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.
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
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.
Models of random graph hierarchies
NASA Astrophysics Data System (ADS)
Paluch, Robert; Suchecki, Krzysztof; Hołyst, Janusz A.
2015-10-01
We introduce two models of inclusion hierarchies: random graph hierarchy (RGH) and limited random graph hierarchy (LRGH). In both models a set of nodes at a given hierarchy level is connected randomly, as in the Erdős-Rényi random graph, with a fixed average degree equal to a system parameter c. Clusters of the resulting network are treated as nodes at the next hierarchy level and they are connected again at this level and so on, until the process cannot continue. In the RGH model we use all clusters, including those of size 1, when building the next hierarchy level, while in the LRGH model clusters of size 1 stop participating in further steps. We find that in both models the number of nodes at a given hierarchy level h decreases approximately exponentially with h. The height of the hierarchy H, i.e. the number of all hierarchy levels, increases logarithmically with the system size N, i.e. with the number of nodes at the first level. The height H decreases monotonically with the connectivity parameter c in the RGH model and it reaches a maximum for a certain c max in the LRGH model. The distribution of separate cluster sizes in the LRGH model is a power law with an exponent about - 1.25. The above results follow from approximate analytical calculations and have been confirmed by numerical simulations.
Topological structure of dictionary graphs
NASA Astrophysics Data System (ADS)
Fukś, Henryk; Krzemiński, Mark
2009-09-01
We investigate the topological structure of the subgraphs of dictionary graphs constructed from WordNet and Moby thesaurus data. In the process of learning a foreign language, the learner knows only a subset of all words of the language, corresponding to a subgraph of a dictionary graph. When this subgraph grows with time, its topological properties change. We introduce the notion of the pseudocore and argue that the growth of the vocabulary roughly follows decreasing pseudocore numbers—that is, one first learns words with a high pseudocore number followed by smaller pseudocores. We also propose an alternative strategy for vocabulary growth, involving decreasing core numbers as opposed to pseudocore numbers. We find that as the core or pseudocore grows in size, the clustering coefficient first decreases, then reaches a minimum and starts increasing again. The minimum occurs when the vocabulary reaches a size between 103 and 104. A simple model exhibiting similar behavior is proposed. The model is based on a generalized geometric random graph. Possible implications for language learning are discussed.
On the Adjacent Eccentric Distance Sum Index of Graphs
Qu, Hui; Cao, Shujuan
2015-01-01
For a given graph G, ε(v) and deg(v) denote the eccentricity and the degree of the vertex v in G, respectively. The adjacent eccentric distance sum index of a graph G is defined as ξsv(G)=∑v∈V(G)ε(v)D(v)deg(v), where D(v)=∑u∈V(G)d(u,v) is the sum of all distances from the vertex v. In this paper we derive some bounds for the adjacent eccentric distance sum index in terms of some graph parameters, such as independence number, covering number, vertex connectivity, chromatic number, diameter and some other graph topological indices. PMID:26091095
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)
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…
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…
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…
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…
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…
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)
Object Discovery: Soft Attributed Graph Mining.
Zhang, Quanshi; Song, Xuan; Shao, Xiaowei; Zhao, Huijing; Shibasaki, Ryosuke
2016-03-01
We categorize this research in terms of its contribution to both graph theory and computer vision. From the theoretical perspective, this study can be considered as the first attempt to formulate the idea of mining maximal frequent subgraphs in the challenging domain of messy visual data, and as a conceptual extension to the unsupervised learning of graph matching. We define a soft attributed pattern (SAP) to represent the common subgraph pattern among a set of attributed relational graphs (ARGs), considering both their structure and attributes. Regarding the differences between ARGs with fuzzy attributes and conventional labeled graphs, we propose a new mining strategy that directly extracts the SAP with the maximal graph size without applying node enumeration. Given an initial graph template and a number of ARGs, we develop an unsupervised method to modify the graph template into the maximal-size SAP. From a practical perspective, this research develops a general platform for learning the category model (i.e., the SAP) from cluttered visual data (i.e., the ARGs) without labeling "what is where," thereby opening the possibility for a series of applications in the era of big visual data. Experiments demonstrate the superior performance of the proposed method on RGB/RGB-D images and videos. PMID:27046496
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)
Evolutionary stability on graphs
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
On the Spectral Gap of a Quantum Graph
NASA Astrophysics Data System (ADS)
Kennedy, James B.; Kurasov, Pavel; Malenová, Gabriela; Mugnolo, Delio
2016-09-01
We consider the problem of finding universal bounds of "isoperimetric" or "isodiametric" type on the spectral gap of the Laplacian on a metric graph with natural boundary conditions at the vertices, in terms of various analytical and combinatorial properties of the graph: its total length, diameter, number of vertices and number of edges. We investigate which combinations of parameters are necessary to obtain non-trivial upper and lower bounds and obtain a number of sharp estimates in terms of these parameters. We also show that, in contrast to the Laplacian matrix on a combinatorial graph, no bound depending only on the diameter is possible. As a special case of our results on metric graphs, we deduce estimates for the normalised Laplacian matrix on combinatorial graphs which, surprisingly, are sometimes sharper than the ones obtained by purely combinatorial methods in the graph theoretical literature.
Kitagawa, Takuya; Pielawa, Susanne; Demler, Eugene; Imambekov, Adilet; Schmiedmayer, Joerg; Gritsev, Vladimir
2010-06-25
We theoretically analyze Ramsey interference experiments in one-dimensional quasicondensates and obtain explicit expressions for the time evolution of full distribution functions of fringe contrast. We show that distribution functions contain unique signatures of the many-body mechanism of decoherence. We argue that Ramsey interference experiments provide a powerful tool for analyzing strongly correlated nature of 1D interacting systems.
Ramsey spectroscopy of high-contrast CPT resonances with push-pull optical pumping in Cs vapor.
Liu, X; Mérolla, J-M; Guérandel, S; de Clercq, E; Boudot, R
2013-05-20
We report on the detection of high-contrast and narrow Coherent Population Trapping (CPT) Ramsey fringes in a Cs vapor cell using a simple-architecture laser system. The latter allows the combination of push-pull optical pumping (PPOP) and a temporal Ramsey-like pulsed interrogation. An originality of the optics package is the use of a single Mach-Zehnder electro-optic modulator (MZ EOM) both for optical sidebands generation and light switch for pulsed interaction. Typical Ramsey fringes with a linewidth of 166 Hz and a contrast of 33 % are detected in a cm-scale buffer-gas filled Cs vapor cell. This technique could be interesting for the development of high-performance and low power consumption compact vapor cell clocks based on CPT. PMID:23736464
Jotkowitz, A
2008-10-01
Due to the worldwide shortage of organs for transplantation, there has been an increased use of organs obtained after circulatory death alone. A protocol for this procedure has recently been approved by a major transplant consortium. This development raises serious moral and ethical concerns. Two renowned theologians of the previous generation, Paul Ramsey and Moshe Feinstein, wrote extensively on the ethical issues relating to transplantation, and their work has much relevance to current moral dilemmas. Their writings relating to definition of death, organ transplantation and the care of the terminally ill are briefly presented, and their potential application to the moral problem of organ donation after circulatory death is discussed. PMID:18827098
Raman-Ramsey multizone spectroscopy in a pure rubidium vapor cell
Failache, H.; Lenci, L.; Lezama, A.
2010-02-15
In view of application to a miniaturized spectroscopy system, we consider an optical setup that splits a laser beam into several parallel narrow light sheets allowing an effective beam expansion and consequently longer atom-light interaction times. We analyze the multizone coherent population trapping (MZCPT) spectroscopy of alkali-metal-vapor atoms, without buffer gas, in the presence of a split light beam. We show that the MZCPT signal is largely insensitive to intensity broadening. Experimentally observed spectra are in qualitative agreement with the predictions of a simplified model that describes each spectrum as an integral over the atomic velocity distribution of Ramsey multizone spectra.
The Ramsey phase-change hypothesis. [for development of earth core
NASA Technical Reports Server (NTRS)
Lyttleton, R. A.
1978-01-01
Ramsey's (1948, 1949, 1950, 1954) arguments for the phase-change interpretation of the nature of the terrestrial core are summarized. Some of the successes of the phase-change theory in accounting for hitherto unexplained properties of earth's interior are discussed. Evidence in favor of the phase-change theory is reviewed, and calculations are examined which indicate that the liquid-core material is far more compressible at any relevant pressure than is the mantle material. Implications of the phase-change theory for Venus, Mars, Mercury, and the moon are considered.
Modified hyper-Ramsey methods for the elimination of probe shifts in optical clocks
NASA Astrophysics Data System (ADS)
Hobson, R.; Bowden, W.; King, S. A.; Baird, P. E. G.; Hill, I. R.; Gill, P.
2016-01-01
We develop a method of modified hyper-Ramsey spectroscopy in optical clocks, achieving complete immunity to the frequency shifts induced by the probing fields themselves. Using particular pulse sequences with tailored phases, frequencies, and durations, we can derive an error signal centered exactly at the unperturbed atomic resonance with a steep discriminant which is robust against variations in the probe shift. We experimentally investigate the scheme using the magnetically induced 1S0-3P0 transition in 88Sr, demonstrating automatic suppression of a sizable 2 ×10-13 probe Stark shift to below 1 ×10-16 even with very large errors in shift compensation.
Encoding the core electrons with graph concepts.
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
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…
Ramsey effects in coherent resonances at closed transition Fg = 2 → Fe = 3 of 87Rb
NASA Astrophysics Data System (ADS)
Grujić, Z. D.; Lekić, M. M.; Radonjić, M.; Arsenović, D.; Jelenković, B. M.
2012-12-01
Experimental and theoretical investigations show the strong effect of the pump beam, spatially separated from the probe beam, on the probe's electromagnetically induced absorption (EIA) and nonlinear magneto-optical rotation (NMOR). Linearly polarized pump and probe laser beams are locked to the Fg = 2 → Fe = 3 transition of the 87Rb D2 line and pass a vacuum Rb gas cell coaxially. We show that the observed narrowing of EIA and NMOR resonances is due to the Ramsey effect. Linewidths of the resonances decrease when the size of the dark region between pump and probe lasers increases. Variation of the angle between pump and probe linear polarizations strongly influences the phases of atomic coherences generated by the pump beam and consequently the line-shapes of the probe EIA and NMOR resonances. Complete change of the resonance sign is possible if the phases of the ground state coherences, Δmg = 2, are altered by π. The central EIA fringe becomes less pronounced if the probe intensity increases, due to the larger probe contribution to atomic evolution. Ramsey-like interference is a manifestation of the evolution of ground state Zeeman coherences, required for EIA, in the dark region in the presence of a small magnetic field.
ERIC Educational Resources Information Center
Schlick, Deborah
Concerns about the growing waiting list for the child care assistance program in Ramsey County, Minnesota precipitated a telephone survey study of the experiences and attitudes of families on the waiting list. Participating in the study were 270 families randomly selected as a representative sample of individuals on the waiting list for March…
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
On the rainbow coloring for some graph operations
NASA Astrophysics Data System (ADS)
Dafik, Agustin, Ika Hesti; Fajariyato, Anang; Alfarisi, Ridho
2016-02-01
Let G = (V, E) be a nontrivial, finite, simple and undirected connected graph on which is defined a coloring f : E(G) → {1,2, …, k}, k ∈ N. The adjacent edges may be colored the same colors. A path in an edge colored graph is said to be a rainbow path if no two edges on the path have the same color. An edge colored graph G is rainbow connected if there exists a rainbow u - v path for every two vertices u and v of G. The rainbow connection number of a graph G, denoted by rc(G), is the smallest number of k colors required to edge color the graph such that the graph is rainbow connected. In this paper, we determine the exact values of rainbow connection number of some special graph operations, namely cartesian product, tensor product, composition of two special graphs and also amalgamation of special graphs. The result shows that all exact values of rc(G) attain a lower bound of the rainbow connectivity, namely diam(G).
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.
Quasiperiodic graphs at the onset of chaos.
Luque, B; Cordero-Gracia, M; Gómez, M; Robledo, A
2013-12-01
We examine the connectivity fluctuations across networks obtained when the horizontal visibility (HV) algorithm is used on trajectories generated by nonlinear circle maps at the quasiperiodic transition to chaos. The resultant HV graph is highly anomalous as the degrees fluctuate at all scales with amplitude that increases with the size of the network. We determine families of Pesin-like identities between entropy growth rates and generalized graph-theoretical Lyapunov exponents. An irrational winding number with pure periodic continued fraction characterizes each family. We illustrate our results for the so-called golden, silver, and bronze numbers. PMID:24483542
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.
Quasiperiodic Graphs: Structural Design, Scaling and Entropic Properties
NASA Astrophysics Data System (ADS)
Luque, B.; Ballesteros, F. J.; Núñez, A. M.; Robledo, A.
2013-04-01
A novel class of graphs, here named quasiperiodic, are constructed via application of the Horizontal Visibility algorithm to the time series generated along the quasiperiodic route to chaos. We show how the hierarchy of mode-locked regions represented by the Farey tree is inherited by their associated graphs. We are able to establish, via Renormalization Group (RG) theory, the architecture of the quasiperiodic graphs produced by irrational winding numbers with pure periodic continued fraction. Finally, we demonstrate that the RG fixed-point degree distributions are recovered via optimization of a suitably defined graph entropy.
Two linear time, low overhead algorithms for graph layout
Energy Science and Technology Software Center (ESTSC)
2008-01-10
The software comprises two algorithms designed to perform a 2D layout of a graph structure in time linear with respect to the vertices and edges in the graph, whereas most other layout algorithms have a running time that is quadratic with respect to the number of vertices or greater. Although these layout algorithms run in a fraction of the time as their competitors, they provide competitive results when applied to most real-world graphs. These algorithmsmore » also have a low constant running time and small memory footprint, making them useful for small to large graphs.« less
A Graph Search Heuristic for Shortest Distance Paths
Chow, E
2005-03-24
This paper presents a heuristic for guiding A* search for finding the shortest distance path between two vertices in a connected, undirected, and explicitly stored graph. The heuristic requires a small amount of data to be stored at each vertex. The heuristic has application to quickly detecting relationships between two vertices in a large information or knowledge network. We compare the performance of this heuristic with breadth-first search on graphs with various topological properties. The results show that one or more orders of magnitude improvement in the number of vertices expanded is possible for large graphs, including Poisson random graphs.
Laplacian Estrada and normalized Laplacian Estrada indices of evolving graphs.
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
Laplacian Estrada and Normalized Laplacian Estrada Indices of Evolving Graphs
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
ASK-GraphView: A large scale graph visualization system.
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
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.
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,…
A Theory of Graphs for Reading Comprehension and Writing Communication.
ERIC Educational Resources Information Center
Fry, Edward
Graphs are increasingly being used in written communication and writers expect readers to understand them. One definition of graphs--information transmitted by position of point, line or area on a two dimensional surface--excludes displays composed chiefly of numbers or words such as tables or outlines. However, it does include time lines, flow…
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).
Probing Real-Space and Time-Resolved Correlation Functions with Many-Body Ramsey Interferometry
NASA Astrophysics Data System (ADS)
Knap, Michael; Kantian, Adrian; Giamarchi, Thierry; Bloch, Immanuel; Lukin, Mikhail D.; Demler, Eugene
2013-10-01
We propose to use Ramsey interferometry and single-site addressability, available in synthetic matter such as cold atoms or trapped ions, to measure real-space and time-resolved spin correlation functions. These correlation functions directly probe the excitations of the system, which makes it possible to characterize the underlying many-body states. Moreover, they contain valuable information about phase transitions where they exhibit scale invariance. We also discuss experimental imperfections and show that a spin-echo protocol can be used to cancel slow fluctuations in the magnetic field. We explicitly consider examples of the two-dimensional, antiferromagnetic Heisenberg model and the one-dimensional, long-range transverse field Ising model to illustrate the technique.
Ramsey-like measurement of the decoherence rate between Zeeman sublevels
NASA Astrophysics Data System (ADS)
Shuker, M.; Firstenberg, O.; Sagi, Y.; Ben-Kish, A.; Davidson, N.; Ron, A.
2008-12-01
Two-photon processes that involve different sublevels of the ground state of an atom, are highly sensitive to depopulation and decoherence within the ground state. For example, the spectral width of electromagnetically induced transparency resonances in a Λ -type system, are strongly affected by the ground-state depopulation and decoherence rates. We present a direct measurement of decay rates between hyperfine and Zeeman sublevels in the ground state of Rb87 vapor. Similar to the relaxation-in-the-dark technique, pumping lasers are used to prealign the atomic vapor in a well-defined quantum state. The free propagation of the atomic state is monitored using a Ramsey-like method. Coherence times in the range 1-10ms were measured for room temperature atomic vapor. In the range of the experimental parameters used in this study, the dominant process inducing Zeeman decoherence is the spin-exchange collisions between rubidium atoms.
Quantum-projection-noise-limited interferometry with coherent atoms in a Ramsey-type setup
Doering, D.; McDonald, G.; Debs, J. E.; Figl, C.; Altin, P. A.; Bachor, H.-A.; Robins, N. P.; Close, J. D.
2010-04-15
Every measurement of the population in an uncorrelated ensemble of two-level systems is limited by what is known as the quantum projection noise limit. Here, we present quantum-projection-noise-limited performance of a Ramsey-type interferometer using freely propagating coherent atoms. The experimental setup is based on an electro-optic modulator in an inherently stable Sagnac interferometer, optically coupling the two interfering atomic states via a two-photon Raman transition. Going beyond the quantum projection noise limit requires the use of reduced quantum uncertainty (squeezed) states. The experiment described demonstrates atom interferometry at the fundamental noise level and allows the observation of possible squeezing effects in an atom laser, potentially leading to improved sensitivity in atom interferometers.
Probe light-shift elimination in generalized hyper-Ramsey quantum clocks
NASA Astrophysics Data System (ADS)
Zanon-Willette, T.; de Clercq, E.; Arimondo, E.
2016-04-01
We present an interrogation scheme for the next generation of quantum clocks to suppress frequency shifts induced by laser probing fields that are themselves based on generalized hyper-Ramsey resonances. Sequences of composite laser pulses with a specific selection of phases, frequency detunings, and durations are combined to generate a very efficient and robust frequency locking signal with an almost perfect elimination of the light shift from off-resonant states and to decouple the unperturbed frequency measurement from the laser's intensity. The frequency lock point generated from synthesized error signals using either π /4 or 3 π /4 laser phase steps during the intermediate pulse is tightly protected against large laser-pulse area variations and errors in potentially applied frequency shift compensations. Quantum clocks based on weakly allowed or completely forbidden optical transitions in atoms, ions, molecules, and nuclei will benefit from these hyperstable laser frequency stabilization schemes to reach relative accuracies below the 10-18 level.
Space Time Reversal Experiment by Use of Pulsed Neutron Ramsey Resonance
Masuda, Y.; Jeong, S. C.; Watanabe, Y.; Skoy, V.; Ino, T.
2007-06-13
We have developed a pulsed neutron Ramsey resonance for a T-violation experiment on polarized neutron transmission through a polarized nuclear target. Two separated oscillatory fields were placed in a pulsed neutron beam line, which were synchronized with a neutron pulse for precision neutron spin manipulation. We observed neutron Larmor precession between the two oscillatory fields as a function of a neutron time of flight (TOF). We modulated the phase of the second oscillatory field with respect to the first oscillatory field. The effect of the phase modulation was found in a neutron intensity modulation as a function of the TOF. From the neutron intensity modulation, the neutron spin direction as well as the neutron velocity between the two oscillatory fields was precisely obtained.
Forster, Jean; Poupart, John; Rhodes, Kristine; Peterson-Hickey, Melanie; Lamont, Genelle; D'Silva, Joanne; Erickson, Darin
2016-01-01
In 2013, it was estimated that the prevalence of cigarette smoking among American Indians was 36.5%, the highest of all racial/ethnic groups in the continental United States (1). Among American Indians, considerable cultural and geographic variation in cigarette smoking exists. Smoking prevalence among American Indians is lowest in the Southwest and highest in the Upper Midwest/Northern Plains (2). Little information is available about tobacco use among urban American Indians, who might not have ever lived on a reservation or be enrolled in or affiliated with a tribe. In Minnesota, a significant proportion of American Indians reside in urban areas. Among Minnesota's residents who identify as American Indian alone or in combination with another race, 30% live in Hennepin County and Ramsey County, which encompass Minneapolis and St. Paul, respectively (collectively known as the Twin Cities). The predominant tribes (Ojibwe [Chippewa] and Dakota/Lakota/Nakota [Sioux]) traditionally have used locally grown tobacco (Nicotiana rustica), red willow, and other plants for religious ceremonies, although nonceremonial tobacco is often substituted for traditional plants. To assess prevalence of cigarette smoking among this population, it is important to distinguish ceremonial tobacco use (smoked or used in other ways) from nonceremonial tobacco use. To obtain estimates of cigarette smoking prevalence among American Indians in Hennepin and Ramsey counties, the American Indian Adult Tobacco Survey was administered to 964 American Indian residents in 2011, using respondent-driven sampling. Among all participants, 59% were current smokers, 19% were former smokers, and 22% had never smoked. Approximately 40% of employed participants reported that someone smoked in their workplace area during the preceding week. High prevalences of cigarette smoking and secondhand smoke exposure among urban American Indians in Minnesota underscores the need for a comprehensive and culturally
On the length of the drift region in the Ramsey cavity
NASA Technical Reports Server (NTRS)
Thomann, Pierre
1990-01-01
The interaction of atoms in a beam with the microwave field in a separated field geometry such as a Ramsey cavity is generally described in terms of the three regions traversed successively by the atoms, namely two interaction regions of length (l) separated by a drift, or free precession, region of length L. For a monokinetic beam of velocity v, the linewidth of the central fringe in the Ramsey resonance pattern is usually expressed as delta omega equals pi v/L. A more detailed calculation shows, however, that the linewidth is equal to pi v/L asterisk, where the equivalent drift L asterisk is larger than L by an amount of the order of l/L. The correction depends on the field distribution in the interaction regions. Its origin lies in the fact that atomic precession is not limited to the field-free regions but also occurs in the interaction regions, where atomic coherence builds up or decreases continuously. Although the correction to the equivalent length of the drift region is small, it may be relevant to the evaluation of the second-order Doppler effect bias in primary cesium-beam standards to the extent that the atomic velocity is deduced from the lineshape and from the geometrical parameters of the cavity. It is shown that in current and projected standards with atoms of average thermal velocity, use of corrected dimensions may lead to a change of the calculated bias of the order of 10(exp -14), which is significant at the levels of accuracy considered nowadays.
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.
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.
Subdominant pseudoultrametric on graphs
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.
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.
Labeled Graph Kernel for Behavior Analysis.
Zhao, Ruiqi; Martinez, Aleix M
2016-08-01
Automatic behavior analysis from video is a major topic in many areas of research, including computer vision, multimedia, robotics, biology, cognitive science, social psychology, psychiatry, and linguistics. Two major problems are of interest when analyzing behavior. First, we wish to automatically categorize observed behaviors into a discrete set of classes (i.e., classification). For example, to determine word production from video sequences in sign language. Second, we wish to understand the relevance of each behavioral feature in achieving this classification (i.e., decoding). For instance, to know which behavior variables are used to discriminate between the words apple and onion in American Sign Language (ASL). The present paper proposes to model behavior using a labeled graph, where the nodes define behavioral features and the edges are labels specifying their order (e.g., before, overlaps, start). In this approach, classification reduces to a simple labeled graph matching. Unfortunately, the complexity of labeled graph matching grows exponentially with the number of categories we wish to represent. Here, we derive a graph kernel to quickly and accurately compute this graph similarity. This approach is very general and can be plugged into any kernel-based classifier. Specifically, we derive a Labeled Graph Support Vector Machine (LGSVM) and a Labeled Graph Logistic Regressor (LGLR) that can be readily employed to discriminate between many actions (e.g., sign language concepts). The derived approach can be readily used for decoding too, yielding invaluable information for the understanding of a problem (e.g., to know how to teach a sign language). The derived algorithms allow us to achieve higher accuracy results than those of state-of-the-art algorithms in a fraction of the time. We show experimental results on a variety of problems and datasets, including multimodal data. PMID:26415154
Graph ranking for exploratory gene data analysis
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
Graphing techniques for materials laboratory using Excel
NASA Technical Reports Server (NTRS)
Kundu, Nikhil K.
1994-01-01
Engineering technology curricula stress hands on training and laboratory practices in most of the technical courses. Laboratory reports should include analytical as well as graphical evaluation of experimental data. Experience shows that many students neither have the mathematical background nor the expertise for graphing. This paper briefly describes the procedure and data obtained from a number of experiments such as spring rate, stress concentration, endurance limit, and column buckling for a variety of materials. Then with a brief introduction to Microsoft Excel the author explains the techniques used for linear regression and logarithmic graphing.
Polynomial iterative algorithms for coloring and analyzing random graphs.
Braunstein, A; Mulet, R; Pagnani, A; Weigt, M; Zecchina, R
2003-09-01
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 with a one-step replica-symmetry breaking approximation 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. Furthermore, we extended our considerations to the case of single instances showing consistent results. This leads us to propose a different algorithm that is able to color in polynomial time random graphs in the hard but colorable region, i.e., when c in [c(d),c(q)]. PMID:14524921
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.
NASA Astrophysics Data System (ADS)
Sui, Xiukai; Wu, Bin; Wang, Long
2015-12-01
The likelihood that a mutant fixates in the wild population, i.e., fixation probability, has been intensively studied in evolutionary game theory, where individuals' fitness is frequency dependent. However, it is of limited interest when it takes long to take over. Thus the speed of evolution becomes an important issue. In general, it is still unclear how fixation times are affected by the population structure, although the fixation times have already been addressed in the well-mixed populations. Here we theoretically address this issue by pair approximation and diffusion approximation on regular graphs. It is shown (i) that under neutral selection, both unconditional and conditional fixation time are shortened by increasing the number of neighbors; (ii) that under weak selection, for the simplified prisoner's dilemma game, if benefit-to-cost ratio exceeds the degree of the graph, then the unconditional fixation time of a single cooperator is slower than that in the neutral case; and (iii) that under weak selection, for the conditional fixation time, limited neighbor size dilutes the counterintuitive stochastic slowdown which was found in well-mixed populations. Interestingly, we find that all of our results can be interpreted as that in the well-mixed population with a transformed payoff matrix. This interpretation is also valid for both death-birth and birth-death processes on graphs. This interpretation bridges the fixation time in the structured population and that in the well-mixed population. Thus it opens the avenue to investigate the challenging fixation time in structured populations by the known results in well-mixed populations.
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…
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
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.
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…
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)
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…
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…
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,
Clustering gene expression data using graph separators.
Kaba, Bangaly; Pinet, Nicolas; Lelandais, Gaëlle; Sigayret, Alain; Berry, Anne
2007-01-01
Recent work has used graphs to modelize expression data from microarray experiments, in view of partitioning the genes into clusters. In this paper, we introduce the use of a decomposition by clique separators. Our aim is to improve the classical clustering methods in two ways: first we want to allow an overlap between clusters, as this seems biologically sound, and second we want to be guided by the structure of the graph to define the number of clusters. We test this approach with a well-known yeast database (Saccharomyces cerevisiae). Our results are good, as the expression profiles of the clusters we find are very coherent. Moreover, we are able to organize into another graph the clusters we find, and order them in a fashion which turns out to respect the chronological order defined by the the sporulation process. PMID:18391236
Using Combinatorica/Mathematica for Student Projects in Random Graph Theory
ERIC Educational Resources Information Center
Pfaff, Thomas J.; Zaret, Michele
2006-01-01
We give an example of a student project that experimentally explores a topic in random graph theory. We use the "Combinatorica" package in "Mathematica" to estimate the minimum number of edges needed in a random graph to have a 50 percent chance that the graph is connected. We provide the "Mathematica" code and compare it to the known theoretical…
Graphs as a Problem-Solving Tool in 1-D Kinematics
ERIC Educational Resources Information Center
Desbien, Dwain M.
2008-01-01
In this age of the microcomputer-based lab (MBL), students are quite accustomed to looking at graphs of position, velocity, and acceleration versus time. A number of textbooks argue convincingly that the slope of the velocity graph gives the acceleration, the area under the velocity graph yields the displacement, and the area under the…
Quantum walks on quotient graphs
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.
Temporal Representation in Semantic Graphs
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.
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…
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.
Editing graphs for maximum effect
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.
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.…
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…
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
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.
Light effects in the atomic-motion-induced Ramsey narrowing of dark resonances in wall-coated cells
Breschi, E.; Schori, C.; Di Domenico, G.; Mileti, G.; Kazakov, G.; Litvinov, A.; Matisov, B.
2010-12-15
We report on light shift and broadening in the atomic-motion-induced Ramsey narrowing of dark resonances prepared in alkali-metal vapors contained in wall-coated cells without buffer gas. The atomic-motion-induced Ramsey narrowing is due to the free motion of the polarized atomic spins in and out of the optical interaction region before spin relaxation. As a consequence of this effect, we observe a narrowing of the dark resonance linewidth as well as a reduction of the ground states' light shift when the volume of the interaction region decreases at constant optical intensity. The results can be intuitively interpreted as a dilution of the intensity effect similar to a pulsed interrogation due to the atomic motion. Finally the influence of this effect on the performance of compact atomic clocks is discussed.
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,…
Multithreaded Algorithms for Graph Coloring
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.
Spectral fluctuations of quantum graphs
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.
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
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…
A system for routing arbitrary directed graphs on SIMD architectures
NASA Technical Reports Server (NTRS)
Tomboulian, Sherryl
1987-01-01
There are many problems which can be described in terms of directed graphs that contain a large number of vertices where simple computations occur using data from connecting vertices. A method is given for parallelizing such problems on an SIMD machine model that is bit-serial and uses only nearest neighbor connections for communication. Each vertex of the graph will be assigned to a processor in the machine. Algorithms are given that will be used to implement movement of data along the arcs of the graph. This architecture and algorithms define a system that is relatively simple to build and can do graph processing. All arcs can be transversed in parallel in time O(T), where T is empirically proportional to the diameter of the interconnection network times the average degree of the graph. Modifying or adding a new arc takes the same time as parallel traversal.
Entanglement witnesses for graph states: General theory and examples
Jungnitsch, Bastian; Moroder, Tobias; Guehne, Otfried
2011-09-15
We present a general theory for the construction of witnesses that detect genuine multipartite entanglement in graph states. First, we present explicit witnesses for all graph states of up to six qubits which are better than all criteria so far. Therefore, lower fidelities are required in experiments that aim at the preparation of graph states. Building on these results, we develop analytical methods to construct two different types of entanglement witnesses for general graph states. For many classes of states, these operators exhibit white noise tolerances that converge to 1 when increasing the number of particles. We illustrate our approach for states such as the linear and the 2D cluster state. Finally, we study an entanglement monotone motivated by our approach for graph states.
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.
NASA Astrophysics Data System (ADS)
Rudinger, Kenneth; Gamble, John King; Wellons, Mark; Bach, Eric; Friesen, Mark; Joynt, Robert; Coppersmith, S. N.
2012-08-01
We investigate the quantum dynamics of particles on graphs (“quantum random walks”), with the aim of developing quantum algorithms for determining if two graphs are isomorphic (related to each other by a relabeling of vertices). We focus on quantum random walks of multiple noninteracting particles on strongly regular graphs (SRGs), a class of graphs with high symmetry that is known to have pairs of graphs that are hard to distinguish. Previous work has already demonstrated analytically that two-particle noninteracting quantum walks cannot distinguish nonisomorphic SRGs of the same family. Here, we demonstrate numerically that three-particle noninteracting quantum walks have significant, but not universal, distinguishing power for pairs of SRGs, proving a fundamental difference between the distinguishing power of two-particle and three-particle noninteracting walks. We show analytically why this distinguishing power is possible, whereas it is forbidden for two-particle noninteracting walks. Based on sampling of SRGs with up to 64 vertices, we find no difference in the distinguishing power of bosonic and fermionic walks. In addition, we find that the four-fermion noninteracting walk has greater distinguishing power than the three-particle walk on SRGs, showing that increasing the particle number increases the distinguishing power. However, we also show analytically that no noninteracting walk with a fixed number of particles can distinguish all SRGs, thus demonstrating a potential fundamental difference in the distinguishing power of interacting versus noninteracting walks.
Join-Graph Propagation Algorithms
Mateescu, Robert; Kask, Kalev; Gogate, Vibhav; Dechter, Rina
2010-01-01
The paper investigates parameterized approximate message-passing schemes that are based on bounded inference and are inspired by Pearl's belief propagation algorithm (BP). We start with the bounded inference mini-clustering algorithm and then move to the iterative scheme called Iterative Join-Graph Propagation (IJGP), that combines both iteration and bounded inference. Algorithm IJGP belongs to the class of Generalized Belief Propagation algorithms, a framework that allowed connections with approximate algorithms from statistical physics and is shown empirically to surpass the performance of mini-clustering and belief propagation, as well as a number of other state-of-the-art algorithms on several classes of networks. We also provide insight into the accuracy of iterative BP and IJGP by relating these algorithms to well known classes of constraint propagation schemes. PMID:20740057
Improving Attack Graph Visualization through Data Reduction and Attack Grouping
John Homer; Ashok Varikuti; Xinming Ou; Miles A. McQueen
2008-09-01
Various tools exist to analyze enterprise network systems and to produce attack graphs detailing how attackers might penetrate into the system. These attack graphs, however, are often complex and difficult to comprehend fully, and a human user may find it problematic to reach appropriate configuration decisions. This paper presents methodologies that can 1) automatically identify portions of an attack graph that do not help a user to understand the core security problems and so can be trimmed, and 2) automatically group similar attack steps as virtual nodes in a model of the network topology, to immediately increase the understandability of the data. We believe both methods are important steps toward improving visualization of attack graphs to make them more useful in configuration management for large enterprise networks. We implemented our methods using one of the existing attack-graph toolkits. Initial experimentation shows that the proposed approaches can 1) significantly reduce the complexity of attack graphs by trimming a large portion of the graph that is not needed for a user to understand the security problem, and 2) significantly increase the accessibility and understandability of the data presented in the attack graph by clearly showing, within a generated visualization of the network topology, the number and type of potential attacks to which each host is exposed.
Graph Coarsening for Path Finding in Cybersecurity Graphs
Hogan, Emilie A.; Johnson, John R.; Halappanavar, Mahantesh
2013-01-01
n the pass-the-hash attack, hackers repeatedly steal password hashes and move through a computer network with the goal of reaching a computer with high level administrative privileges. In this paper we apply graph coarsening in network graphs for the purpose of detecting hackers using this attack or assessing the risk level of the network's current state. We repeatedly take graph minors, which preserve the existence of paths in the graph, and take powers of the adjacency matrix to count the paths. This allows us to detect the existence of paths as well as find paths that have high risk of being used by adversaries.
Horizontal visibility graphs from integer sequences
NASA Astrophysics Data System (ADS)
Lacasa, Lucas
2016-09-01
The horizontal visibility graph (HVG) is a graph-theoretical representation of a time series and builds a bridge between dynamical systems and graph theory. In recent years this representation has been used to describe and theoretically compare different types of dynamics and has been applied to characterize empirical signals, by extracting topological features from the associated HVGs which have shown to be informative on the class of dynamics. Among some other measures, it has been shown that the degree distribution of these graphs is a very informative feature that encapsulates nontrivial information of the series's generative dynamics. In particular, the HVG associated to a bi-infinite real-valued series of independent and identically distributed random variables is a universal exponential law P(k)=(1/3){(2/3)}k-2, independent of the series marginal distribution. Most of the current applications have however only addressed real-valued time series, as no exact results are known for the topological properties of HVGs associated to integer-valued series. In this paper we explore this latter situation and address univariate time series where each variable can only take a finite number n of consecutive integer values. We are able to construct an explicit formula for the parametric degree distribution {P}n(k), which we prove to converge to the continuous case for large n and deviates otherwise. A few applications are then considered.
Cactus Graphs for Genome Comparisons
NASA Astrophysics Data System (ADS)
Paten, Benedict; Diekhans, Mark; Earl, Dent; St. John, John; Ma, Jian; Suh, Bernard; Haussler, David
We introduce a data structure, analysis and visualization scheme called a cactus graph for comparing sets of related genomes. Cactus graphs capture some of the advantages of de Bruijn and breakpoint graphs in one unified framework. They naturally decompose the common substructures in a set of related genomes into a hierarchy of chains that can be visualized as multiple alignments and nets that can be visualized in circular genome plots.
Thiruvengadam, Muthu; Yang, Chang-Hsien
2009-10-01
Lisianthus [Eustoma grandiflorum (Raf.) Shinn] is a popular cut flower crop throughout the world, and the demand for this plant for cut flowers and potted plants has been increasing worldwide. Recent advances in genetic engineering have enabled the transformation and regeneration of plants to become a powerful tool for improvement of lisianthus. We have established a highly efficient plant regeneration system and Agrobacterium-mediated genetic transformation of E. grandiflorum. The greatest shoot regeneration frequency and number of shoot buds per explant are observed on media supplemented with 6-Benzylaminopurine (BAP) and alpha-Naphthalene acetic acid (NAA). We report an efficient plant regeneration system using leaf explants via organogenesis with high efficiency of transgenic plants (15%) in culture of 11 weeks' duration. Further ectopic expression of two MADS box genes, LMADS1-M from lily (Lilium longiflorum) and OMADS1 from orchid (Oncidium Gower Ramsey), was performed in E. grandiflorum. Conversion of second whorl petals into sepal-like structures and alteration of third whorl stamen formation were observed in the transgenic E. grandiflorum plants ectopically expressing 35S::LMADS1-M. 35S::OMADS1 transgenic E. grandiflorum plants flowered significantly earlier than non-transgenic plants. This is the first report on the ectopic expression of two MADS box genes in E. grandiflorum using a simple and highly efficient gene transfer protocol. Our results reveal the potential for floral modification in E. grandiflorum through genetic transformation. PMID:19639326
NASA Technical Reports Server (NTRS)
Burleigh, Scott C.
2011-01-01
Contact Graph Routing (CGR) is a dynamic routing system that computes routes through a time-varying topology of scheduled communication contacts in a network based on the DTN (Delay-Tolerant Networking) architecture. It is designed to enable dynamic selection of data transmission routes in a space network based on DTN. This dynamic responsiveness in route computation should be significantly more effective and less expensive than static routing, increasing total data return while at the same time reducing mission operations cost and risk. The basic strategy of CGR is to take advantage of the fact that, since flight mission communication operations are planned in detail, the communication routes between any pair of bundle agents in a population of nodes that have all been informed of one another's plans can be inferred from those plans rather than discovered via dialogue (which is impractical over long one-way-light-time space links). Messages that convey this planning information are used to construct contact graphs (time-varying models of network connectivity) from which CGR automatically computes efficient routes for bundles. Automatic route selection increases the flexibility and resilience of the space network, simplifying cross-support and reducing mission management costs. Note that there are no routing tables in Contact Graph Routing. The best route for a bundle destined for a given node may routinely be different from the best route for a different bundle destined for the same node, depending on bundle priority, bundle expiration time, and changes in the current lengths of transmission queues for neighboring nodes; routes must be computed individually for each bundle, from the Bundle Protocol agent's current network connectivity model for the bundle s destination node (the contact graph). Clearly this places a premium on optimizing the implementation of the route computation algorithm. The scalability of CGR to very large networks remains a research topic
The first eigenvalue of the p- Laplacian on quantum graphs
NASA Astrophysics Data System (ADS)
Del Pezzo, Leandro M.; Rossi, Julio D.
2016-01-01
We study the first eigenvalue of the p- Laplacian (with 1
graph with Dirichlet or Kirchoff boundary conditions on the nodes. We find lower and upper bounds for this eigenvalue when we prescribe the total sum of the lengths of the edges and the number of Dirichlet nodes of the graph. Also we find a formula for the shape derivative of the first eigenvalue (assuming that it is simple) when we perturb the graph by changing the length of an edge. Finally, we study in detail the limit cases p→ ∞ and p→ 1.
Graph-based algorithms for Boolean function manipulation
Bryant, R.E.
1986-08-01
In this paper the authors present a new data structure for representing Boolean functions and an associated set of manipulation algorithms. Although a function requires, in the worst case, a graph of size exponential in the number of arguments, many of the functions encountered in typical applications have a more reasonable representation. The algorithms have time complexity proportional to the sizes of the graphs being operated on, and hence are quite efficient as long as the graphs do not grow too large. The authors present experimental results from applying these algorithms to problems in logic design verification that demonstrate the practicality of the approach.
DNA solution of a graph coloring problem.
Liu, Yachun; Xu, Jin; Pan, Linqiang; Wang, Shiying
2002-01-01
The graph-theoretic parameter that has probably received the most attention over the years is the chromatic number. As is well-known, the coloring problem is an NP-Complete problem. In this paper, it has been solved by means of molecular biology techniques. The algorithm is highly parallel and has satisfactory fidelity. This work shows further evidence for the ability of DNA computing to solve NP-Complete problems. PMID:12086509
Fracture and Fragmentation of Simplicial Finite Elements Meshes using Graphs
Mota, A; Knap, J; Ortiz, M
2006-10-18
An approach for the topological representation of simplicial finite element meshes as graphs is presented. It is shown that by using a graph, the topological changes induced by fracture reduce to a few, local kernel operations. The performance of the graph representation is demonstrated and analyzed, using as reference the 3D fracture algorithm by Pandolfi and Ortiz [22]. It is shown that the graph representation initializes in O(N{sub E}{sup 1.1}) time and fractures in O(N{sub I}{sup 1.0}) time, while the reference implementation requires O(N{sub E}{sup 2.1}) time to initialize and O(N{sub I}{sup 1.9}) time to fracture, where NE is the number of elements in the mesh and N{sub I} is the number of interfaces to fracture.
Voter model on the two-clique graph.
Masuda, Naoki
2014-07-01
I examine the mean consensus time (i.e., exit time) of the voter model in the so-called two-clique graph. The two-clique graph is composed of two cliques interconnected by some links and considered as a toy model of networks with community structure or multilayer networks. I analytically show that, as the number of interclique links per node is varied, the mean consensus time experiences a crossover between a fast consensus regime [i.e., O(N)] and a slow consensus regime [i.e., O(N(2))], where N is the number of nodes. The fast regime is consistent with the result for homogeneous well-mixed graphs such as the complete graph. The slow regime appears only when the entire network has O(1) interclique links. The present results suggest that the effect of community structure on the consensus time of the voter model is fairly limited. PMID:25122337
Statistics of Gaussian packets on metric and decorated graphs
Chernyshev, V. L.; Shafarevich, A. I.
2014-01-01
We study a semiclassical asymptotics of the Cauchy problem for a time-dependent Schrödinger equation on metric and decorated graphs with a localized initial function. A decorated graph is a topological space obtained from a graph via replacing vertices with smooth Riemannian manifolds. The main term of an asymptotic solution at an arbitrary finite time is a sum of Gaussian packets and generalized Gaussian packets (localized near a certain set of codimension one). We study the number of packets as time tends to infinity. We prove that under certain assumptions this number grows in time as a polynomial and packets fill the graph uniformly. We discuss a simple example of the opposite situation: in this case, a numerical experiment shows a subexponential growth. PMID:24344346
Voter model on the two-clique graph
NASA Astrophysics Data System (ADS)
Masuda, Naoki
2014-07-01
I examine the mean consensus time (i.e., exit time) of the voter model in the so-called two-clique graph. The two-clique graph is composed of two cliques interconnected by some links and considered as a toy model of networks with community structure or multilayer networks. I analytically show that, as the number of interclique links per node is varied, the mean consensus time experiences a crossover between a fast consensus regime [i.e., O (N)] and a slow consensus regime [i.e., O (N2)], where N is the number of nodes. The fast regime is consistent with the result for homogeneous well-mixed graphs such as the complete graph. The slow regime appears only when the entire network has O (1) interclique links. The present results suggest that the effect of community structure on the consensus time of the voter model is fairly limited.
Graph Visualization for RDF Graphs with SPARQL-EndPoints
Energy Science and Technology Software Center (ESTSC)
2014-07-11
RDF graphs are hard to visualize as triples. This software module is a web interface that connects to a SPARQL endpoint and retrieves graph data that the user can explore interactively and seamlessly. The software written in python and JavaScript has been tested to work on screens as little as the smart phones to large screens such as EVEREST.
Maunz, Peter Lukas Wilhelm; Sterk, Jonathan David; Lobser, Daniel; Parekh, Ojas D.; Ryan-Anderson, Ciaran
2016-01-01
In recent years, advanced network analytics have become increasingly important to na- tional security with applications ranging from cyber security to detection and disruption of ter- rorist networks. While classical computing solutions have received considerable investment, the development of quantum algorithms to address problems, such as data mining of attributed relational graphs, is a largely unexplored space. Recent theoretical work has shown that quan- tum algorithms for graph analysis can be more efficient than their classical counterparts. Here, we have implemented a trapped-ion-based two-qubit quantum information proces- sor to address these goals. Building on Sandia's microfabricated silicon surface ion traps, we have designed, realized and characterized a quantum information processor using the hyperfine qubits encoded in two 171 Yb + ions. We have implemented single qubit gates using resonant microwave radiation and have employed Gate set tomography (GST) to characterize the quan- tum process. For the first time, we were able to prove that the quantum process surpasses the fault tolerance thresholds of some quantum codes by demonstrating a diamond norm distance of less than 1 . 9 x 10 [?] 4 . We used Raman transitions in order to manipulate the trapped ions' motion and realize two-qubit gates. We characterized the implemented motion sensitive and insensitive single qubit processes and achieved a maximal process infidelity of 6 . 5 x 10 [?] 5 . We implemented the two-qubit gate proposed by Molmer and Sorensen and achieved a fidelity of more than 97 . 7%.
Quantization of gauge fields, graph polynomials and graph homology
Kreimer, Dirk; Sars, Matthias; Suijlekom, Walter D. van
2013-09-15
We review quantization of gauge fields using algebraic properties of 3-regular graphs. We derive the Feynman integrand at n loops for a non-abelian gauge theory quantized in a covariant gauge from scalar integrands for connected 3-regular graphs, obtained from the two Symanzik polynomials. The transition to the full gauge theory amplitude is obtained by the use of a third, new, graph polynomial, the corolla polynomial. This implies effectively a covariant quantization without ghosts, where all the relevant signs of the ghost sector are incorporated in a double complex furnished by the corolla polynomial–we call it cycle homology–and by graph homology. -- Highlights: •We derive gauge theory Feynman from scalar field theory with 3-valent vertices. •We clarify the role of graph homology and cycle homology. •We use parametric renormalization and the new corolla polynomial.
Quantitative analysis of electrically detected Ramsey fringes in P-doped Si
NASA Astrophysics Data System (ADS)
Greenland, P. T.; Matmon, G.; Villis, B. J.; Bowyer, E. T.; Li, Juerong; Murdin, B. N.; van der Meer, A. F. G.; Redlich, B.; Pidgeon, C. R.; Aeppli, G.
2015-10-01
This work describes detection of the laser preparation and subsequent coherent manipulation of the quantum states of orbital levels of donors in doped Si, by measuring the voltage drop across an irradiated Si sample. This electrical signal, which arises from thermal ionization of excited orbital states, and which is detected on a millisecond time scale by a voltmeter, leads to much more sensitive detection than can be had using optical methods, but has not before been quantitatively described from first principles. We present here a unified theory which relates the voltage drop across the sample to the wave function of the excited donors, and compare its predictions to experiments in which pairs of picosecond pulses from the Dutch free-electron laser FELIX are used to resonantly and coherently excite P donors in Si. Although the voltage drop varies on a millisecond time scale we are able to measure Ramsey oscillation of the excitation on a picosecond time scale, thus confirming that the donor wave function, and not just its excited state population, is crucial in determining the electrical signal. We are also able to extract the recombination rate coefficient to the ground state of the donor as well as the photoionization cross section of the excited state and phonon induced thermal ionization rate from the excited state. These quantities, which were previously of limited interest, are here shown to be important in the description of electrical detection, which, in our unoptimized configuration, is sensitive enough to enable us to detect the excitation of ˜107 donors.
Bootstrap Percolation in Power-Law Random Graphs
NASA Astrophysics Data System (ADS)
Amini, Hamed; Fountoulakis, Nikolaos
2014-04-01
A bootstrap percolation process on a graph is an "infection" process which evolves in rounds. Initially, there is a subset of infected nodes and in each subsequent round each uninfected node which has at least infected neighbours becomes infected and remains so forever. The parameter is fixed. Such processes have been used as models for the spread of ideas or trends within a network of individuals. We analyse this process in the case where the underlying graph is an inhomogeneous random graph, which exhibits a power-law degree distribution, and initially there are randomly infected nodes. The main focus of this paper is the number of vertices that will have been infected by the end of the process. The main result of this work is that if the degree sequence of the random graph follows a power law with exponent , where , then a sublinear number of initially infected vertices is enough to spread the infection over a linear fraction of the nodes of the random graph, with high probability. More specifically, we determine explicitly a critical function such that with the following property. Assuming that is the number of vertices of the underlying random graph, if , then the process does not evolve at all, with high probability as grows, whereas if , then there is a constant such that, with high probability, the final set of infected vertices has size at least . This behaviour is in sharp contrast with the case where the underlying graph is a random graph with . It follows from an observation of Balogh and Bollobás that in this case if the number of initially infected vertices is sublinear, then there is lack of evolution of the process. It turns out that when the maximum degree is , then depends also on . But when the maximum degree is , then.
Generating functions for modular graphs and Burgers's equation
NASA Astrophysics Data System (ADS)
Artamkin, I. V.
2005-12-01
It is shown that the generating functions of modular graphs satisfy Burgers's equations, which enable one to obtain in a unified way the generating functions for the virtual Euler characteristic and the Poincaré polynomial of the moduli space of punctured curves \\overline M_{g,n} and for the number (with weights 1/\\vert{\\operatorname{Aut} G}\\vert) of modular graphs G of a definite type.
Graph-Based Dynamic Assignment Of Multiple Processors
NASA Technical Reports Server (NTRS)
Hayes, Paul J.; Andrews, Asa M.
1994-01-01
Algorithm-to-architecture mapping model (ATAMM) is strategy minimizing time needed to periodically execute graphically described, data-driven application algorithm on multiple data processors. Implemented as operating system managing flow of data and dynamically assigns nodes of graph to processors. Predicts throughput versus number of processors available to execute given application algorithm. Includes rules ensuring application algorithm represented by graph executed periodically without deadlock and in shortest possible repetition time. ATAMM proves useful in maximizing effectiveness of parallel computing systems.
Guide to graphing data and taking action.
1992-01-01
3 kinds of graphs are presented as instructional examples of how to display data collected on family planning (FP) programs. The first is a trend analysis of new acceptors and requires monthly summaries of new acceptors serviced by the clinic. The objective is to gauge declines or increases over time in new acceptors for each contraceptive method offered. The second graph requires a monthly summary of new acceptors by method mix. The third graph needs data on the reason for attending the particular FP clinic. IEC activities can be enhanced with this information. In the example for graph 1, new acceptors over an 18-month-period are plotted on one axis by monthly units, and the other axis by number of new acceptors. The connection of dots reflects the trend over time. There is a specific example with data from Yena clinic over a 12-month-period; the interpretations and possible actions are indicated. Instructions for presenting a pie chart are also given for new acceptors by method mix; the example is given for data from Yena Clinic and possible interpretations and actions are indicated. A visual presentation of the data worksheet needed for a pie chart is provided. Calculations must be made for the fraction of new acceptors out of total acceptors and the percent of total new acceptors for each method. An explanation is given for constructing a bar chart; again an example is given of a completed bar chart with data and the accompanying data sheet. A checklist identifies important guidelines for developing and using line graphs, bar charts, and pie charts. PMID:12318345
Young Students Investigate Number Cubes.
ERIC Educational Resources Information Center
Friedlander, Alex
1997-01-01
Describes a series of learning activities built around number cubes. Sample activities introduce elementary properties of the cube, the magic rule of seven, and basic concepts related to graphs in the plane coordinate system. (PVD)