Open Graphs and Computational Reasoning

Directory of Open Access Journals (Sweden)

Lucas Dixon

2010-06-01

Full Text Available We present a form of algebraic reasoning for computational objects which are expressed as graphs. Edges describe the flow of data between primitive operations which are represented by vertices. These graphs have an interface made of half-edges (edges which are drawn with an unconnected end and enjoy rich compositional principles by connecting graphs along these half-edges. In particular, this allows equations and rewrite rules to be specified between graphs. Particular computational models can then be encoded as an axiomatic set of such rules. Further rules can be derived graphically and rewriting can be used to simulate the dynamics of a computational system, e.g. evaluating a program on an input. Examples of models which can be formalised in this way include traditional electronic circuits as well as recent categorical accounts of quantum information.

Rewrite systems for integer arithmetic

NARCIS (Netherlands)

H.R. Walters (Pum); H. Zantema (Hans)

1995-01-01

textabstractWe present three term rewrite systems for integer arithmetic with addition, multiplication, and, in two cases, subtraction. All systems are ground confluent and terminating; termination is proved by semantic labelling and recursive path order. The first system represents numbers by

Rewrite systems for integer arithmetic

NARCIS (Netherlands)

Walters, H.R.; Zantema, H.

1994-01-01

We present three term rewrite systems for integer arithmetic with addition, multiplication, and, in two cases, subtraction. All systems are ground con uent and terminating; termination is proved by semantic labelling and recursive path order. The first system represents numbers by successor and

A Modal Logic for Termgraph Rewriting

OpenAIRE

Balbiani, Ph.; Echahed, R.; Herzig, A.

2010-01-01

We propose a modal logic tailored to describe graph transformations and discuss some of its properties. We focus on a particular class of graphs called termgraphs. They are first-order terms augmented with sharing and cycles. Termgraphs allow one to describe classical data-structures (possibly with pointers) such as doubly-linked lists, circular lists etc. We show how the proposed logic can faithfully describe (i) termgraphs as well as (ii) the application of a termgraph rewrite rule (i.e. ma...

Undecidability Results for Bisimilarity on Prefix Rewrite Systems

DEFF Research Database (Denmark)

Jancar, Petr; Srba, Jiri

2006-01-01

We answer an open question related to bisimilarity checking on labelled transition systems generated by prefix rewrite rules on words. Stirling (1996, 1998) proved the decidability of bisimilarity for normed pushdown processes. This result was substantially extended by Senizergues (1998, 2005) who...... language) was left open; this was repeatedly indicated by both Stirling and Senizergues. Here we answer the question negatively, i.e., we show undecidability of bisimilarity on Type -1 systems, even in the normed case. We complete the picture by considering classes of systems that use rewrite rules...

Graph-based Operational Semantics of a Lazy Functional Languages

DEFF Research Database (Denmark)

Rose, Kristoffer Høgsbro

1992-01-01

Presents Graph Operational Semantics (GOS): a semantic specification formalism based on structural operational semantics and term graph rewriting. Demonstrates the method by specifying the dynamic ...

Hierarchical graphs for rule-based modeling of biochemical systems

Directory of Open Access Journals (Sweden)

Hu Bin

2011-02-01

Full Text Available Abstract Background In rule-based modeling, graphs are used to represent molecules: a colored vertex represents a component of a molecule, a vertex attribute represents the internal state of a component, and an edge represents a bond between components. Components of a molecule share the same color. Furthermore, graph-rewriting rules are used to represent molecular interactions. A rule that specifies addition (removal of an edge represents a class of association (dissociation reactions, and a rule that specifies a change of a vertex attribute represents a class of reactions that affect the internal state of a molecular component. A set of rules comprises an executable model that can be used to determine, through various means, the system-level dynamics of molecular interactions in a biochemical system. Results For purposes of model annotation, we propose the use of hierarchical graphs to represent structural relationships among components and subcomponents of molecules. We illustrate how hierarchical graphs can be used to naturally document the structural organization of the functional components and subcomponents of two proteins: the protein tyrosine kinase Lck and the T cell receptor (TCR complex. We also show that computational methods developed for regular graphs can be applied to hierarchical graphs. In particular, we describe a generalization of Nauty, a graph isomorphism and canonical labeling algorithm. The generalized version of the Nauty procedure, which we call HNauty, can be used to assign canonical labels to hierarchical graphs or more generally to graphs with multiple edge types. The difference between the Nauty and HNauty procedures is minor, but for completeness, we provide an explanation of the entire HNauty algorithm. Conclusions Hierarchical graphs provide more intuitive formal representations of proteins and other structured molecules with multiple functional components than do the regular graphs of current languages for

Graph Algorithm Animation with Grrr

OpenAIRE

Rodgers, Peter; Vidal, Natalia

2000-01-01

We discuss geometric positioning, highlighting of visited nodes and user defined highlighting that form the algorithm animation facilities in the Grrr graph rewriting programming language. The main purpose of animation was initially for the debugging and profiling of Grrr code, but recently it has been extended for the purpose of teaching algorithms to undergraduate students. The animation is restricted to graph based algorithms such as graph drawing, list manipulation or more traditional gra...

Binary decision diagrams by shared rewriting

NARCIS (Netherlands)

Pol, J. van de; Zantema, H.

2000-01-01

BDDs provide an established technique for propositional formula manipulation. In this paper we re-develope the basic BDD theory using standard rewriting techniques. Since a BDD is a DAG instead of a tree we need a notion of shared rewriting and develope appropriate theory. A rewriting system is

Lifting Term Rewriting Derivations in Constructor Systems by Using Generators

Directory of Open Access Journals (Sweden)

Adrián Riesco

2015-01-01

Full Text Available Narrowing is a procedure that was first studied in the context of equational E-unification and that has been used in a wide range of applications. The classic completeness result due to Hullot states that any term rewriting derivation starting from an instance of an expression can be "lifted" to a narrowing derivation, whenever the substitution employed is normalized. In this paper we adapt the generator- based extra-variables-elimination transformation used in functional-logic programming to overcome that limitation, so we are able to lift term rewriting derivations starting from arbitrary instances of expressions. The proposed technique is limited to left-linear constructor systems and to derivations reaching a ground expression. We also present a Maude-based implementation of the technique, using natural rewriting for the on-demand evaluation strategy.

Comparison between state graphs and fault trees for sequential and repairable systems

International Nuclear Information System (INIS)

Soussan, D.; Saignes, P.

1996-01-01

In French PSA (Probabilistic Safety Assessment) 1300 for the 1300 Mwe PWR plants carried out by EDF, sequential and reparable systems are modeled with state graphs. This method is particularly convenient for modeling dynamic systems with long-term missions but induces a bad traceability and understandability of models. In the objective of providing elements for rewriting PSA 1300 with only boolean models, EDF has asked CEA to participate to a methodological study. The aim is to carry out a feasibility study of transposition of state graphs models into fault trees on Component Cooling System and Essential Service Water System (CCS/ESWS) and to draw a methodological guide for transposition. The study realized on CCS/ESWS involves two main axes: quantification of cold source loss (as an accident sequence initiating event, called H1); quantification of the CCS/ESWS missions in accident sequences. The subject of this article is to show that this transformation is applicable with minimum distortions of the results and to determine the hypotheses, the conditions and the limits of application of this conversion. (authors). 2 refs

Parallel object-oriented term rewriting : the booleans

NARCIS (Netherlands)

Rodenburg, P.H.; Vrancken, J.L.M.

As a first case study in parallel object-oriented term rewriting, we give two implementations of term rewriting algorithms for boolean terms, using the parallel object-oriented features of the language Pool-T. The term rewriting systems are specified in the specification formalism

Phase structure rewrite systems in information retrieval

Science.gov (United States)

Klingbiel, P. H.

1985-01-01

Operational level automatic indexing requires an efficient means of normalizing natural language phrases. Subject switching requires an efficient means of translating one set of authorized terms to another. A phrase structure rewrite system called a Lexical Dictionary is explained that performs these functions. Background, operational use, other applications and ongoing research are explained.

A Rewritable, Random-Access DNA-Based Storage System.

Science.gov (United States)

Yazdi, S M Hossein Tabatabaei; Yuan, Yongbo; Ma, Jian; Zhao, Huimin; Milenkovic, Olgica

2015-09-18

We describe the first DNA-based storage architecture that enables random access to data blocks and rewriting of information stored at arbitrary locations within the blocks. The newly developed architecture overcomes drawbacks of existing read-only methods that require decoding the whole file in order to read one data fragment. Our system is based on new constrained coding techniques and accompanying DNA editing methods that ensure data reliability, specificity and sensitivity of access, and at the same time provide exceptionally high data storage capacity. As a proof of concept, we encoded parts of the Wikipedia pages of six universities in the USA, and selected and edited parts of the text written in DNA corresponding to three of these schools. The results suggest that DNA is a versatile media suitable for both ultrahigh density archival and rewritable storage applications.

On-Chip Fluorescence Switching System for Constructing a Rewritable Random Access Data Storage Device.

Science.gov (United States)

Nguyen, Hoang Hiep; Park, Jeho; Hwang, Seungwoo; Kwon, Oh Seok; Lee, Chang-Soo; Shin, Yong-Beom; Ha, Tai Hwan; Kim, Moonil

2018-01-10

We report the development of on-chip fluorescence switching system based on DNA strand displacement and DNA hybridization for the construction of a rewritable and randomly accessible data storage device. In this study, the feasibility and potential effectiveness of our proposed system was evaluated with a series of wet experiments involving 40 bits (5 bytes) of data encoding a 5-charactered text (KRIBB). Also, a flexible data rewriting function was achieved by converting fluorescence signals between "ON" and "OFF" through DNA strand displacement and hybridization events. In addition, the proposed system was successfully validated on a microfluidic chip which could further facilitate the encoding and decoding process of data. To the best of our knowledge, this is the first report on the use of DNA hybridization and DNA strand displacement in the field of data storage devices. Taken together, our results demonstrated that DNA-based fluorescence switching could be applicable to construct a rewritable and randomly accessible data storage device through controllable DNA manipulations.

A Rewriting Logic Approach to Type Inference

Science.gov (United States)

Ellison, Chucky; Şerbănuţă, Traian Florin; Roşu, Grigore

Meseguer and Roşu proposed rewriting logic semantics (RLS) as a programing language definitional framework that unifies operational and algebraic denotational semantics. RLS has already been used to define a series of didactic and real languages, but its benefits in connection with defining and reasoning about type systems have not been fully investigated. This paper shows how the same RLS style employed for giving formal definitions of languages can be used to define type systems. The same term-rewriting mechanism used to execute RLS language definitions can now be used to execute type systems, giving type checkers or type inferencers. The proposed approach is exemplified by defining the Hindley-Milner polymorphic type inferencer mathcal{W} as a rewrite logic theory and using this definition to obtain a type inferencer by executing it in a rewriting logic engine. The inferencer obtained this way compares favorably with other definitions or implementations of mathcal{W}. The performance of the executable definition is within an order of magnitude of that of highly optimized implementations of type inferencers, such as that of OCaml.

Simulation and Verification of Synchronous Set Relations in Rewriting Logic

Science.gov (United States)

Rocha, Camilo; Munoz, Cesar A.

2011-01-01

This paper presents a mathematical foundation and a rewriting logic infrastructure for the execution and property veri cation of synchronous set relations. The mathematical foundation is given in the language of abstract set relations. The infrastructure consists of an ordersorted rewrite theory in Maude, a rewriting logic system, that enables the synchronous execution of a set relation provided by the user. By using the infrastructure, existing algorithm veri cation techniques already available in Maude for traditional asynchronous rewriting, such as reachability analysis and model checking, are automatically available to synchronous set rewriting. The use of the infrastructure is illustrated with an executable operational semantics of a simple synchronous language and the veri cation of temporal properties of a synchronous system.

Strategy-Driven Exploration for Rule-Based Models of Biochemical Systems with Porgy

OpenAIRE

Andrei , Oana; Fernández , Maribel; Kirchner , Hélène; Pinaud , Bruno

2016-01-01

This paper presents Porgy – an interactive visual environment for rule-based modelling of biochemical systems. We model molecules and molecule interactions as port graphs and port graph rewrite rules, respectively. We use rewriting strategies to control which rules to apply, and where and when to apply them. Our main contributions to rule-based modelling of biochemical systems lie in the strategy language and the associated visual and interactive features offered by Porgy. These features faci...

Symbolic Evaluation Graphs and Term Rewriting — A General Methodology for Analyzing Logic Programs

DEFF Research Database (Denmark)

Giesl, J.; Ströder, T.; Schneider-Kamp, P.

2013-01-01

There exist many powerful techniques to analyze termination and complexity of term rewrite systems (TRSs). Our goal is to use these techniques for the analysis of other programming languages as well. For instance, approaches to prove termination of definite logic programs by a transformation...... to TRSs have been studied for decades. However, a challenge is to handle languages with more complex evaluation strategies (such as Prolog, where predicates like the cut influence the control flow). We present a general methodology for the analysis of such programs. Here, the logic program is first...... information on the termination or complexity of the original logic program. More information can be found in the full paper [1]. © 2013 Springer-Verlag....

Meaningless terms in rewriting

NARCIS (Netherlands)

Kennaway, R.; Oostrom, V. van; Vries, F.-J. de

We present an axiomatic approach to the concept of meaninglessness in finite and transfinite term rewriting and lambda calculus. We justify our axioms in several ways. They can be intuitively justified from the viewpoint of rewriting as computation. They are shown to imply important properties

Let the Rewriter Beware.

Science.gov (United States)

Charrow, Veda R.

Translating legal and bureaucratic language into plain, comprehensible English is not amenable to simple rules and procedures. Rewriting comprehensibly requires specialized knowledge about language and an awareness of a number of misconceptions and pitfalls. This paper discusses what not to do in rewriting, based upon rewritten documents presently…

Increasing the rewriting speed of optical rewritable e-paper by selecting proper liquid crystals

International Nuclear Information System (INIS)

Geng Yu; Sun Jiatong; Kwok Hoi Sing; Murauski Anatoli; Chigrinov Vladimir

2012-01-01

The effect of interaction between liquid crystal (LC) and photoalignment material on the speed of optical rewriting process is investigated. The theoretical analysis shows that a smaller frank elastic constant K 22 of liquid crystal corresponds to a larger twist angle, which gives rise to a larger rewriting speed. Six different LC cells with the same boundary conditions (one substrate is covered with rubbed polyimide (PI) and the other with photo sensitive rewritable sulfuric dye 1(SD1)) are tested experimentally under the same illumination intensity (450 nm, 80 mW/cm 2 ). The results demonstrate that with a suitable liquid crystal, the LC optical rewriting speed for e-paper application can be obviously improved. For two well known LC materials E7 (K 22 is larger) and 5CB (K 22 is smaller), they require 11 s and 6 s corresponding to change alignment direction for generating image information. (general)

Four Complete Datatype Defining Rewrite Systems for an Abstract Datatype of Natural Numbers

NARCIS (Netherlands)

Bergstra, J.A.

2014-01-01

Natural numbers with zero, one, successor, addition and multiplication, constitute a classic example of an abstract datatype amenable for equational initial algebra specification. Datatype defining rewrite systems provide a specification which at the same time is a complete, that is confluent and

Parallel Execution of Multi Set Constraint Rewrite Rules

DEFF Research Database (Denmark)

Sulzmann, Martin; Lam, Edmund Soon Lee

2008-01-01

that the underlying constraint rewrite implementation executes rewrite steps in parallel on increasingly popular becoming multi-core architectures. We design and implement efficient algorithms which allow for the parallel execution of multi-set constraint rewrite rules. Our experiments show that we obtain some......Multi-set constraint rewriting allows for a highly parallel computational model and has been used in a multitude of application domains such as constraint solving, agent specification etc. Rewriting steps can be applied simultaneously as long as they do not interfere with each other.We wish...

Sub-Circuit Selection and Replacement Algorithms Modeled as Term Rewriting Systems

Science.gov (United States)

2008-12-16

of Defense, or the United States Government . AFIT/GCO/ENG/09-02 Sub-circuit Selection and Replacement Algorithms Modeled as Term Rewriting Systems... unicorns and random programs”. Communications and Computer Networks, 24–30. 2005. 87 Vita Eric D. Simonaire graduated from Granite Baptist Church School in...Service to attend the Air Force Institute of Technol- ogy in 2007. Upon graduation, he will serve the federal government in an Information Assurance

Higher-order rewriting and partial evaluation

DEFF Research Database (Denmark)

Danvy, Olivier; Rose, Kristoffer H.

1998-01-01

We demonstrate the usefulness of higher-order rewriting techniques for specializing programs, i.e., for partial evaluation. More precisely, we demonstrate how casting program specializers as combinatory reduction systems (CRSs) makes it possible to formalize the corresponding program...

Hydrochromic molecular switches for water-jet rewritable paper

Science.gov (United States)

Sheng, Lan; Li, Minjie; Zhu, Shaoyin; Li, Hao; Xi, Guan; Li, Yong-Gang; Wang, Yi; Li, Quanshun; Liang, Shaojun; Zhong, Ke; Zhang, Sean Xiao-An

2014-01-01

The days of rewritable paper are coming, printers of the future will use water-jet paper. Although several kinds of rewritable paper have been reported, practical usage of them is rare. Herein, a new rewritable paper for ink-free printing is proposed and demonstrated successfully by using water as the sole trigger to switch hydrochromic dyes on solid media. Water-jet prints with various colours are achieved with a commercial desktop printer based on these hydrochromic rewritable papers. The prints can be erased and rewritten dozens of times with no significant loss in colour quality. This rewritable paper is promising in that it can serve an eco-friendly information display to meet the increasing global needs for environmental protection.

Confluence via strong normalisation in an algebraic λ-calculus with rewriting

Directory of Open Access Journals (Sweden)

Pablo Buiras

2012-03-01

Full Text Available The linear-algebraic lambda-calculus and the algebraic lambda-calculus are untyped lambda-calculi extended with arbitrary linear combinations of terms. The former presents the axioms of linear algebra in the form of a rewrite system, while the latter uses equalities. When given by rewrites, algebraic lambda-calculi are not confluent unless further restrictions are added. We provide a type system for the linear-algebraic lambda-calculus enforcing strong normalisation, which gives back confluence. The type system allows an abstract interpretation in System F.

An Efficient Compiler for Weighted Rewrite Rules

OpenAIRE

Mohri, Mehryar; Sproat, Richard

1996-01-01

Context-dependent rewrite rules are used in many areas of natural language and speech processing. Work in computational phonology has demonstrated that, given certain conditions, such rewrite rules can be represented as finite-state transducers (FSTs). We describe a new algorithm for compiling rewrite rules into FSTs. We show the algorithm to be simpler and more efficient than existing algorithms. Further, many of our applications demand the ability to compile weighted rules into weighted FST...

Port-Hamiltonian Systems on Open Graphs

NARCIS (Netherlands)

Schaft, A.J. van der; Maschke, B.M.

2010-01-01

In this talk we discuss how to define in an intrinsic manner port-Hamiltonian dynamics on open graphs. Open graphs are graphs where some of the vertices are boundary vertices (terminals), which allow interconnection with other systems. We show that a directed graph carries two natural Dirac

Bond graph modeling of centrifugal compression systems

OpenAIRE

Uddin, Nur; Gravdahl, Jan Tommy

2015-01-01

A novel approach to model unsteady fluid dynamics in a compressor network by using a bond graph is presented. The model is intended in particular for compressor control system development. First, we develop a bond graph model of a single compression system. Bond graph modeling offers a different perspective to previous work by modeling the compression system based on energy flow instead of fluid dynamics. Analyzing the bond graph model explains the energy flow during compressor surge. Two pri...

System dynamics and control with bond graph modeling

CERN Document Server

Kypuros, Javier

2013-01-01

Part I Dynamic System ModelingIntroduction to System DynamicsIntroductionSystem Decomposition and Model ComplexityMathematical Modeling of Dynamic SystemsAnalysis and Design of Dynamic SystemsControl of Dynamic SystemsDiagrams of Dynamic SystemsA Graph-Centered Approach to ModelingSummaryPracticeExercisesBasic Bond Graph ElementsIntroductionPower and Energy VariablesBasic 1-Port ElementsBasic 2-Ports ElementsJunction ElementsSimple Bond Graph ExamplesSummaryPracticeExercisesBond Graph Synthesis and Equation DerivationIntroductionGeneral GuidelinesMechanical TranslationMechanical RotationElectrical CircuitsHydraulic CircuitsMixed SystemsState Equation DerivationState-Space RepresentationsAlgebraic Loops and Derivative CausalitySummaryPracticeExercisesImpedance Bond GraphsIntroductionLaplace Transform of the State-Space EquationBasic 1-Port ImpedancesImpedance Bond Graph SynthesisJunctions, Transformers, and GyratorsEffort and Flow DividersSign ChangesTransfer Function DerivationAlternative Derivation of Transf...

Infinitary Rewriting - Theory and Applications

DEFF Research Database (Denmark)

Bahr, Patrick

2009-01-01

Infinitary rewriting generalises usual finitary rewriting by providing infinite reduction sequences with a notion of convergence. The idea of -- at least conceptually -- assigning a meaning to infinite derivations is well-known, for example, from lazy functional programming or from process calculi...... that are used to formalise infinite reduction sequences: The well-established metric approach as well as an alternative approach using partial orders. Both methods together with the consequent infinitary versions of confluence and termination properties are analysed on an abstract level. Based on this, we argue...

The Pi-0-2-Completeness of most of the Properties of Rewriting You Care About (and Productivity)

DEFF Research Database (Denmark)

Simonsen, Jakob Grue

2009-01-01

Most of the standard pleasant properties of term rewriting systems are undecidable; to wit: local confluence, confluence, normalization, termination, and completeness. Mere undecidability is insufficient to rule out a number of possibly useful properties: For instance, if the set of normalizing...... term rewriting systems were recursively enumerable, there would be a program yielding “yes” in finite time if applied to any normalizing term rewriting system. The contribution of this paper is to show (the uniform version of) each member of the list of properties above (as well as the property...... of being a productive specification of a stream) complete for the class $\\Pi^0_2$. Thus, there is neither a program that can enumerate the set of rewriting systems enjoying any one of the properties, nor is there a program enumerating the set of systems that do not. For normalization and termination we...

Values Education through Aggadic Stories: The Didactic Rewriter as Interpreter

Science.gov (United States)

Weinstein, Sara

2016-01-01

Didactic rewrites of aggadic stories are an important resource in values education. This study, geared primarily toward teachers involved in choosing curricular materials, investigates how the didactic rewriter actually becomes an interpreter, rather than a mere transmitter, of the original text. The personal values of the rewriters can influence…

Herdable Systems Over Signed, Directed Graphs

KAUST Repository

Ruf, Sebastian F.; Egerstedt, Magnus; Shamma, Jeff S.

2018-01-01

This paper considers the notion of herdability, a set-based reachability condition, which asks whether the state of a system can be controlled to be element-wise larger than a non-negative threshold. The basic theory of herdable systems is presented, including a necessary and sufficient condition for herdability. This paper then considers the impact of the underlying graph structure of a linear system on the herdability of the system, for the case where the graph is represented as signed and directed. By classifying nodes based on the length and sign of walks from an input, we find a class of completely herdable systems as well as provide a complete characterization of nodes that can be herded in systems with an underlying graph that is a directed out-branching rooted at a single input.

Herdable Systems Over Signed, Directed Graphs

KAUST Repository

Ruf, Sebastian F.

2018-04-11

This paper considers the notion of herdability, a set-based reachability condition, which asks whether the state of a system can be controlled to be element-wise larger than a non-negative threshold. The basic theory of herdable systems is presented, including a necessary and sufficient condition for herdability. This paper then considers the impact of the underlying graph structure of a linear system on the herdability of the system, for the case where the graph is represented as signed and directed. By classifying nodes based on the length and sign of walks from an input, we find a class of completely herdable systems as well as provide a complete characterization of nodes that can be herded in systems with an underlying graph that is a directed out-branching rooted at a single input.

Use of Attack Graphs in Security Systems

Directory of Open Access Journals (Sweden)

Vivek Shandilya

2014-01-01

Full Text Available Attack graphs have been used to model the vulnerabilities of the systems and their potential exploits. The successful exploits leading to the partial/total failure of the systems are subject of keen security interest. Considerable effort has been expended in exhaustive modeling, analyses, detection, and mitigation of attacks. One prominent methodology involves constructing attack graphs of the pertinent system for analysis and response strategies. This not only gives the simplified representation of the system, but also allows prioritizing the security properties whose violations are of greater concern, for both detection and repair. We present a survey and critical study of state-of-the-art technologies in attack graph generation and use in security system. Based on our research, we identify the potential, challenges, and direction of the current research in using attack graphs.

SPARQL Query Re-writing Using Partonomy Based Transformation Rules

Science.gov (United States)

Jain, Prateek; Yeh, Peter Z.; Verma, Kunal; Henson, Cory A.; Sheth, Amit P.

Often the information present in a spatial knowledge base is represented at a different level of granularity and abstraction than the query constraints. For querying ontology's containing spatial information, the precise relationships between spatial entities has to be specified in the basic graph pattern of SPARQL query which can result in long and complex queries. We present a novel approach to help users intuitively write SPARQL queries to query spatial data, rather than relying on knowledge of the ontology structure. Our framework re-writes queries, using transformation rules to exploit part-whole relations between geographical entities to address the mismatches between query constraints and knowledge base. Our experiments were performed on completely third party datasets and queries. Evaluations were performed on Geonames dataset using questions from National Geographic Bee serialized into SPARQL and British Administrative Geography Ontology using questions from a popular trivia website. These experiments demonstrate high precision in retrieval of results and ease in writing queries.

Triangulation in rewriting

NARCIS (Netherlands)

Oostrom, V. van; Zantema, Hans

2012-01-01

We introduce a process, dubbed triangulation, turning any rewrite relation into a confluent one. It is more direct than usual completion, in the sense that objects connected by a peak are directly oriented rather than their normal forms. We investigate conditions under which this process preserves

Optimizing graph algorithms on pregel-like systems

KAUST Repository

Salihoglu, Semih

2014-03-01

We study the problem of implementing graph algorithms efficiently on Pregel-like systems, which can be surprisingly challenging. Standard graph algorithms in this setting can incur unnecessary inefficiencies such as slow convergence or high communication or computation cost, typically due to structural properties of the input graphs such as large diameters or skew in component sizes. We describe several optimization techniques to address these inefficiencies. Our most general technique is based on the idea of performing some serial computation on a tiny fraction of the input graph, complementing Pregel\\'s vertex-centric parallelism. We base our study on thorough implementations of several fundamental graph algorithms, some of which have, to the best of our knowledge, not been implemented on Pregel-like systems before. The algorithms and optimizations we describe are fully implemented in our open-source Pregel implementation. We present detailed experiments showing that our optimization techniques improve runtime significantly on a variety of very large graph datasets.

Partial order infinitary term rewriting

DEFF Research Database (Denmark)

Bahr, Patrick

2014-01-01

We study an alternative model of infinitary term rewriting. Instead of a metric on terms, a partial order on partial terms is employed to formalise convergence of reductions. We consider both a weak and a strong notion of convergence and show that the metric model of convergence coincides with th...... to the metric setting -- orthogonal systems are both infinitarily confluent and infinitarily normalising in the partial order setting. The unique infinitary normal forms that the partial order model admits are Böhm trees....

Dynamical systems and algebra associated with seperated graphs

DEFF Research Database (Denmark)

Lolk, Matias

In this thesis, we study partial dynamical systems and graph algebras arising from nitely separated graphs. The thesis consists of an introduction followed by three papers, the rst of which is joint work with Pere Ara. In Article [A], we introduce convex subshifts, an abstract generalisation...... of the partial dynamical systems associated with nite separated graphs. We dene notions of a nite and innite type convex subshift and show that all such dynamical systems arise from a nite bipartite separated graph up to a suitable type of equivalence. We then study various aspects of the ideal structure...

Rewriting Logic Semantics of a Plan Execution Language

Science.gov (United States)

Dowek, Gilles; Munoz, Cesar A.; Rocha, Camilo

2009-01-01

The Plan Execution Interchange Language (PLEXIL) is a synchronous language developed by NASA to support autonomous spacecraft operations. In this paper, we propose a rewriting logic semantics of PLEXIL in Maude, a high-performance logical engine. The rewriting logic semantics is by itself a formal interpreter of the language and can be used as a semantic benchmark for the implementation of PLEXIL executives. The implementation in Maude has the additional benefit of making available to PLEXIL designers and developers all the formal analysis and verification tools provided by Maude. The formalization of the PLEXIL semantics in rewriting logic poses an interesting challenge due to the synchronous nature of the language and the prioritized rules defining its semantics. To overcome this difficulty, we propose a general procedure for simulating synchronous set relations in rewriting logic that is sound and, for deterministic relations, complete. We also report on the finding of two issues at the design level of the original PLEXIL semantics that were identified with the help of the executable specification in Maude.

Automated termination proofs for logic programs by term rewriting

NARCIS (Netherlands)

Schneider-Kamp, P.; Giesl, J.; Serebrenik, A.; Thiemann, R.

2009-01-01

There are two kinds of approaches for termination analysis of logic programs: "transformational" and "direct" ones. Direct approaches prove termination directly on the basis of the logic program. Transformational approaches transform a logic program into a Term Rewrite System (TRS) and then analyze

Interacting particle systems on graphs

Science.gov (United States)

Sood, Vishal

In this dissertation, the dynamics of socially or biologically interacting populations are investigated. The individual members of the population are treated as particles that interact via links on a social or biological network represented as a graph. The effect of the structure of the graph on the properties of the interacting particle system is studied using statistical physics techniques. In the first chapter, the central concepts of graph theory and social and biological networks are presented. Next, interacting particle systems that are drawn from physics, mathematics and biology are discussed in the second chapter. In the third chapter, the random walk on a graph is studied. The mean time for a random walk to traverse between two arbitrary sites of a random graph is evaluated. Using an effective medium approximation it is found that the mean first-passage time between pairs of sites, as well as all moments of this first-passage time, are insensitive to the density of links in the graph. The inverse of the mean-first passage time varies non-monotonically with the density of links near the percolation transition of the random graph. Much of the behavior can be understood by simple heuristic arguments. Evolutionary dynamics, by which mutants overspread an otherwise uniform population on heterogeneous graphs, are studied in the fourth chapter. Such a process underlies' epidemic propagation, emergence of fads, social cooperation or invasion of an ecological niche by a new species. The first part of this chapter is devoted to neutral dynamics, in which the mutant genotype does not have a selective advantage over the resident genotype. The time to extinction of one of the two genotypes is derived. In the second part of this chapter, selective advantage or fitness is introduced such that the mutant genotype has a higher birth rate or a lower death rate. This selective advantage leads to a dynamical competition in which selection dominates for large populations

Rewriting and suppressing UMLS terms for improved biomedical term identification

Directory of Open Access Journals (Sweden)

Hettne Kristina M

2010-03-01

Full Text Available Abstract Background Identification of terms is essential for biomedical text mining.. We concentrate here on the use of vocabularies for term identification, specifically the Unified Medical Language System (UMLS. To make the UMLS more suitable for biomedical text mining we implemented and evaluated nine term rewrite and eight term suppression rules. The rules rely on UMLS properties that have been identified in previous work by others, together with an additional set of new properties discovered by our group during our work with the UMLS. Our work complements the earlier work in that we measure the impact on the number of terms identified by the different rules on a MEDLINE corpus. The number of uniquely identified terms and their frequency in MEDLINE were computed before and after applying the rules. The 50 most frequently found terms together with a sample of 100 randomly selected terms were evaluated for every rule. Results Five of the nine rewrite rules were found to generate additional synonyms and spelling variants that correctly corresponded to the meaning of the original terms and seven out of the eight suppression rules were found to suppress only undesired terms. Using the five rewrite rules that passed our evaluation, we were able to identify 1,117,772 new occurrences of 14,784 rewritten terms in MEDLINE. Without the rewriting, we recognized 651,268 terms belonging to 397,414 concepts; with rewriting, we recognized 666,053 terms belonging to 410,823 concepts, which is an increase of 2.8% in the number of terms and an increase of 3.4% in the number of concepts recognized. Using the seven suppression rules, a total of 257,118 undesired terms were suppressed in the UMLS, notably decreasing its size. 7,397 terms were suppressed in the corpus. Conclusions We recommend applying the five rewrite rules and seven suppression rules that passed our evaluation when the UMLS is to be used for biomedical term identification in MEDLINE. A software

Rewriting the language of creativity

DEFF Research Database (Denmark)

Glaveanu, Vlad Petre

2013-01-01

For the past 5 decades the psychology of creativity has been influenced by what is known as the 4 P's of creative expression: person, process, product, and press. This conceptual schema, initially proposed by Rhodes (1961), helped researchers structure their thinking about the phenomenon. However......, it also supported an individualistic, static, and oftentimes disjointed vision of creativity. The present article aims to rewrite this fundamental language of the discipline by using terms that explicitly endorse a systemic, contextual, and dynamic approach. The 5 A's framework—actor, action, artifact...

Specification and Verification of Web Applications in Rewriting Logic

Science.gov (United States)

Alpuente, María; Ballis, Demis; Romero, Daniel

This paper presents a Rewriting Logic framework that formalizes the interactions between Web servers and Web browsers through a communicating protocol abstracting HTTP. The proposed framework includes a scripting language that is powerful enough to model the dynamics of complex Web applications by encompassing the main features of the most popular Web scripting languages (e.g. PHP, ASP, Java Servlets). We also provide a detailed characterization of browser actions (e.g. forward/backward navigation, page refresh, and new window/tab openings) via rewrite rules, and show how our models can be naturally model-checked by using the Linear Temporal Logic of Rewriting (LTLR), which is a Linear Temporal Logic specifically designed for model-checking rewrite theories. Our formalization is particularly suitable for verification purposes, since it allows one to perform in-depth analyses of many subtle aspects related to Web interaction. Finally, the framework has been completely implemented in Maude, and we report on some successful experiments that we conducted by using the Maude LTLR model-checker.

Optimizing graph algorithms on pregel-like systems

KAUST Repository

Salihoglu, Semih; Widom, Jennifer

2014-01-01

We study the problem of implementing graph algorithms efficiently on Pregel-like systems, which can be surprisingly challenging. Standard graph algorithms in this setting can incur unnecessary inefficiencies such as slow convergence or high

Printable and Rewritable Full Block Copolymer Structural Color.

Science.gov (United States)

Kang, Han Sol; Lee, Jinseong; Cho, Suk Man; Park, Tae Hyun; Kim, Min Ju; Park, Chanho; Lee, Seung Won; Kim, Kang Lib; Ryu, Du Yeol; Huh, June; Thomas, Edwin L; Park, Cheolmin

2017-08-01

Structural colors (SCs) of photonic crystals (PCs) arise from selective constructive interference of incident light. Here, an ink-jet printable and rewritable block copolymer (BCP) SC display is demonstrated, which can be quickly written and erased over 50 times with resolution nearly equivalent to that obtained with a commercial office ink-jet printer. Moreover, the writing process employs an easily modified printer for position- and concentration-controlled deposition of a single, colorless, water-based ink containing a reversible crosslinking agent, ammonium persulfate. Deposition of the ink onto a self-assembled BCP PC film comprising a 1D stack of alternating layers enables differential swelling of the written BCP film and produces a full-colored SC display of characters and images. Furthermore, the information can be readily erased and the system can be reset by application of hydrogen bromide. Subsequently, new information can be rewritten, resulting in a chemically rewritable BCP SC display. © 2017 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.

Weak convergence and uniform normalization in infinitary rewriting

DEFF Research Database (Denmark)

Simonsen, Jakob Grue

2010-01-01

the starkly surprising result that for any orthogonal system with finitely many rules, the system is weakly normalizing under weak convergence if{f} it is strongly normalizing under weak convergence if{f} it is weakly normalizing under strong convergence if{f} it is strongly normalizing under strong...... convergence. As further corollaries, we derive a number of new results for weakly convergent rewriting: Systems with finitely many rules enjoy unique normal forms, and acyclic orthogonal systems are confluent. Our results suggest that it may be possible to recover some of the positive results for strongly...

Graph modeling systems and methods

Science.gov (United States)

Neergaard, Mike

2015-10-13

An apparatus and a method for vulnerability and reliability modeling are provided. The method generally includes constructing a graph model of a physical network using a computer, the graph model including a plurality of terminating vertices to represent nodes in the physical network, a plurality of edges to represent transmission paths in the physical network, and a non-terminating vertex to represent a non-nodal vulnerability along a transmission path in the physical network. The method additionally includes evaluating the vulnerability and reliability of the physical network using the constructed graph model, wherein the vulnerability and reliability evaluation includes a determination of whether each terminating and non-terminating vertex represents a critical point of failure. The method can be utilized to evaluate wide variety of networks, including power grid infrastructures, communication network topologies, and fluid distribution systems.

Bond graph model-based fault diagnosis of hybrid systems

CERN Document Server

Borutzky, Wolfgang

2015-01-01

This book presents a bond graph model-based approach to fault diagnosis in mechatronic systems appropriately represented by a hybrid model. The book begins by giving a survey of the fundamentals of fault diagnosis and failure prognosis, then recalls state-of-art developments referring to latest publications, and goes on to discuss various bond graph representations of hybrid system models, equations formulation for switched systems, and simulation of their dynamic behavior. The structured text: • focuses on bond graph model-based fault detection and isolation in hybrid systems; • addresses isolation of multiple parametric faults in hybrid systems; • considers system mode identification; • provides a number of elaborated case studies that consider fault scenarios for switched power electronic systems commonly used in a variety of applications; and • indicates that bond graph modelling can also be used for failure prognosis. In order to facilitate the understanding of fault diagnosis and the presented...

Dynamic graph system for a semantic database

Science.gov (United States)

Mizell, David

2015-01-27

A method and system in a computer system for dynamically providing a graphical representation of a data store of entries via a matrix interface is disclosed. A dynamic graph system provides a matrix interface that exposes to an application program a graphical representation of data stored in a data store such as a semantic database storing triples. To the application program, the matrix interface represents the graph as a sparse adjacency matrix that is stored in compressed form. Each entry of the data store is considered to represent a link between nodes of the graph. Each entry has a first field and a second field identifying the nodes connected by the link and a third field with a value for the link that connects the identified nodes. The first, second, and third fields represent the rows, column, and elements of the adjacency matrix.

Mapping Modular SOS to Rewriting Logic

DEFF Research Database (Denmark)

Braga, Christiano de Oliveira; Haeusler, Edward Hermann; Meseguer, José

2003-01-01

and verification of MSOS specifications, we have defined a mapping, named , from MSOS to rewriting logic (RWL), a logic which has been proposed as a logical and semantic framework. We have proven the correctness of and implemented it as a prototype, the MSOS-SL Interpreter, in the Maude system, a high......Modular SOS (MSOS) is a framework created to improve the modularity of structural operational semantics specifications, a formalism frequently used in the fields of programming languages semantics and process algebras. With the objective of defining formal tools to support the execution...

ARTICLE Robust Diagnosis of Mechatronics System by Bond Graph Approach

Directory of Open Access Journals (Sweden)

Abderrahmene Sellami

2018-03-01

Full Text Available This article presents design of a robust diagnostic system based on bond graph model for a mechatronic system. Mechatronics is the synergistic and systemic combination of mechanics, electronics and computer science. The design of a mechatronic system modeled by the bond graph model becomes easier and more generous. The bond graph tool is a unified graphical language for all areas of engineering sciences and confirmed as a structured approach to modeling and simulation of multidisciplinary systems.

Proposal of New Rewritable Printing Media Using Electrophoresis and Confirmation of Its Mechanism

Science.gov (United States)

Hoshino, Yasushi; Ogura, Masahiro; Sano, Takayuki

2004-10-01

A new rewritable printing media using electrophoresis and selective heating is proposed to contribute to the reduction in paper consumption by printers. The mechanism is that when a heated part of the rewritable media is melted, white particles in that part of the media are able to move by electrophoresis. The media is initialized by heating its entire surface under the condition of voltage application and imaging is carried out by selective heating under the condition of an applied reversed-polarity voltage. Using a mixture system of carnauba wax and particles coated with titanium oxide (TiO2), the feasibility of the mechanism is confirmed.

Fingerprint recognition system by use of graph matching

Science.gov (United States)

Shen, Wei; Shen, Jun; Zheng, Huicheng

2001-09-01

Fingerprint recognition is an important subject in biometrics to identify or verify persons by physiological characteristics, and has found wide applications in different domains. In the present paper, we present a finger recognition system that combines singular points and structures. The principal steps of processing in our system are: preprocessing and ridge segmentation, singular point extraction and selection, graph representation, and finger recognition by graphs matching. Our fingerprint recognition system is implemented and tested for many fingerprint images and the experimental result are satisfactory. Different techniques are used in our system, such as fast calculation of orientation field, local fuzzy dynamical thresholding, algebraic analysis of connections and fingerprints representation and matching by graphs. Wed find that for fingerprint database that is not very large, the recognition rate is very high even without using a prior coarse category classification. This system works well for both one-to-few and one-to-many problems.

Bond Graph Modeling and Simulation of Mechatronic Systems

DEFF Research Database (Denmark)

Habib, Tufail; Nielsen, Kjeld; Jørgensen, Kaj Asbjørn

2012-01-01

One of the demanding steps in the design and development of Mechatronic systems is to develop the initial model to visualize the response of a system. The Bond Graph (BG) method is a graphical approach for the design of multidomain systems. That is ideal for visualizing the essential characterist......One of the demanding steps in the design and development of Mechatronic systems is to develop the initial model to visualize the response of a system. The Bond Graph (BG) method is a graphical approach for the design of multidomain systems. That is ideal for visualizing the essential...

Monotonic Set-Extended Prefix Rewriting and Verification of Recursive Ping-Pong Protocols

DEFF Research Database (Denmark)

Delzanno, Giorgio; Esparza, Javier; Srba, Jiri

2006-01-01

of messages) some verification problems become decidable. In particular we give an algorithm to decide control state reachability, a problem related to security properties like secrecy and authenticity. The proof is via a reduction to a new prefix rewriting model called Monotonic Set-extended Prefix rewriting...

Automatic Generation of Supervisory Control System Software Using Graph Composition

Science.gov (United States)

Nakata, Hideo; Sano, Tatsuro; Kojima, Taizo; Seo, Kazuo; Uchida, Tomoyuki; Nakamura, Yasuaki

This paper describes the automatic generation of system descriptions for SCADA (Supervisory Control And Data Acquisition) systems. The proposed method produces various types of data and programs for SCADA systems from equipment definitions using conversion rules. At first, this method makes directed graphs, which represent connections between the equipment, from equipment definitions. System descriptions are generated using the conversion rules, by analyzing these directed graphs, and finding the groups of equipment that involve similar operations. This method can make the conversion rules multi levels by using the composition of graphs, and can reduce the number of rules. The developer can define and manage these rules efficiently.

Modular Implementation of Programming Languages and a Partial-Order Approach to Infinitary Rewriting

DEFF Research Database (Denmark)

Bahr, Patrick

2012-01-01

In this dissertation we investigate two independent areas of research. In the first part, we develop techniques for implementing programming languages in a modular fashion. Within this problem domain, we focus on operations on typed abstract syntax trees with the goal of developing a framework...... that facilitates the definition, manipulation and composition of such operations. The result of our work is a comprehensive combinator library that provides these facilities. What sets our approach apart is the use of recursion schemes derived from tree automata in order to implement operations on abstract syntax...... trees. The second part is concerned with infinitary rewriting, a field that studies transfinite rewrite sequences. We extend the established theory of infinitary rewriting in two ways: (1) a novel approach to convergence in infinitary rewriting that replaces convergence in a metric space with the limit...

A Hybrid Approach to Processing Big Data Graphs on Memory-Restricted Systems

KAUST Repository

Harshvardhan,

2015-05-01

With the advent of big-data, processing large graphs quickly has become increasingly important. Most existing approaches either utilize in-memory processing techniques that can only process graphs that fit completely in RAM, or disk-based techniques that sacrifice performance. In this work, we propose a novel RAM-Disk hybrid approach to graph processing that can scale well from a single shared-memory node to large distributed-memory systems. It works by partitioning the graph into sub graphs that fit in RAM and uses a paging-like technique to load sub graphs. We show that without modifying the algorithms, this approach can scale from small memory-constrained systems (such as tablets) to large-scale distributed machines with 16, 000+ cores.

GraphStore: A Distributed Graph Storage System for Big Data Networks

Science.gov (United States)

Martha, VenkataSwamy

2013-01-01

Networks, such as social networks, are a universal solution for modeling complex problems in real time, especially in the Big Data community. While previous studies have attempted to enhance network processing algorithms, none have paved a path for the development of a persistent storage system. The proposed solution, GraphStore, provides an…

Journalism's Rewriting of History in Reporting the Arab Spring

DEFF Research Database (Denmark)

Jørndrup, Hanne

2012-01-01

Investigation of journalism’s role as writer and rewriter of the record of political episodes of world importance is central to this article, which takes an empirical approach in choosing the Danish press coverage of The Arab Spring as its starting point. The article analyses how a number...... and circumstances that put Tunisia and Egypt on the Danish media’s agenda in the year before the Arab revolutions as a starting point. The central point of this comparison is to convey how journalism, while describing contemporary events of The Arab Spring, at the same time rewrites its own prior commentary...

Rewritable azobenzene polyester for polarization holographic data storage

DEFF Research Database (Denmark)

Kerekes, A; Sajti, Sz.; Loerincz, Emoeke

2000-01-01

Optical storage properties of thin azobenzene side-chain polyester films were examined by polarization holographic measurements. The new amorphous polyester film is the candidate material for the purpose of rewritable holographic memory system. Temporal formation of anisotropic and topographic...... gratings was studied in case of films with and without a hard protective layer. We showed that the dominant contribution to the diffraction efficiency comes from the anisotropy in case of expositions below 1 sec even for high incident intensity. The usage of the same wavelength for writing, reading...

Rewritable 3D bit optical data storage in a PMMA-based photorefractive polymer

Energy Technology Data Exchange (ETDEWEB)

Day, D.; Gu, M. [Swinburne Univ. of Tech., Hawthorn, Vic. (Australia). Centre for Micro-Photonics; Smallridge, A. [Victoria Univ., Melbourne (Australia). School of Life Sciences and Technology

2001-07-04

A cheap, compact, and rewritable high-density optical data storage system for CD and DVD applications is presented by the authors. Continuous-wave illumination under two-photon excitation in a new poly(methylmethacrylate) (PMMA) based photorefractive polymer allows 3D bit storage of sub-Tbyte data. (orig.)

Bond graph modeling and LQG/LTR controller design of magnetically levitation systems

International Nuclear Information System (INIS)

Kim, Jong Shik; Park, Jeon Soo

1991-01-01

A logical and systematic procedure to derive a mathematical model for magnetically levitation (MAGLEV) systems with a combined lift and guidance is developed by using bond graph modeling techniques. First, bond graph is contructed for the 1 st -dimensional MAGLEV system in which three subsystems (energy feeding, track and vehicle) are considered. And, the 2 nd -dimensional MAGLEV system in which lift and guidance dynamics are coupled is modeled by using the concept of multi-port field in bond graph languages. Finally, the LQG/LTR control system is designed for a multivariable MAGLEV system with stagger configuration type. In this paper, it has been shown that the bond graph is an excellent effective method for modeling multi-energy domain systems such as MAGLEV systems with uncertainties such as mass variations, track irregularities and wind gusts. (Author)

Bond graph modeling and LQG/LTR controller design of magnetically levitation systems

Energy Technology Data Exchange (ETDEWEB)

Kim, Jong Shik; Park, Jeon Soo [Busan National Univ. (Korea, Republic of)

1991-09-01

A logical and systematic procedure to derive a mathematical model for magnetically levitation (MAGLEV) systems with a combined lift and guidance is developed by using bond graph modeling techniques. First, bond graph is contructed for the 1{sup st}-dimensional MAGLEV system in which three subsystems (energy feeding, track and vehicle) are considered. And, the 2{sup nd}-dimensional MAGLEV system in which lift and guidance dynamics are coupled is modeled by using the concept of multi-port field in bond graph languages. Finally, the LQG/LTR control system is designed for a multivariable MAGLEV system with stagger configuration type. In this paper, it has been shown that the bond graph is an excellent effective method for modeling multi-energy domain systems such as MAGLEV systems with uncertainties such as mass variations, track irregularities and wind gusts. (Author).

PathSys: integrating molecular interaction graphs for systems biology

Directory of Open Access Journals (Sweden)

Raval Alpan

2006-02-01

Full Text Available Abstract Background The goal of information integration in systems biology is to combine information from a number of databases and data sets, which are obtained from both high and low throughput experiments, under one data management scheme such that the cumulative information provides greater biological insight than is possible with individual information sources considered separately. Results Here we present PathSys, a graph-based system for creating a combined database of networks of interaction for generating integrated view of biological mechanisms. We used PathSys to integrate over 14 curated and publicly contributed data sources for the budding yeast (S. cerevisiae and Gene Ontology. A number of exploratory questions were formulated as a combination of relational and graph-based queries to the integrated database. Thus, PathSys is a general-purpose, scalable, graph-data warehouse of biological information, complete with a graph manipulation and a query language, a storage mechanism and a generic data-importing mechanism through schema-mapping. Conclusion Results from several test studies demonstrate the effectiveness of the approach in retrieving biologically interesting relations between genes and proteins, the networks connecting them, and of the utility of PathSys as a scalable graph-based warehouse for interaction-network integration and a hypothesis generator system. The PathSys's client software, named BiologicalNetworks, developed for navigation and analyses of molecular networks, is available as a Java Web Start application at http://brak.sdsc.edu/pub/BiologicalNetworks.

A rewriting view of simple typing

NARCIS (Netherlands)

Stump, A.; Zantema, H.; Kimmell, G.; El Haj Omar, R.

2012-01-01

This paper shows how a recently developed view of typing as small-step abstract reduction, due to Kuan, MacQueen, and Findler, can be used to recast the development of simple type theory from a rewriting perspective. We show how standard meta-theoretic results can be proved in a completely new way,

A rewriting view of simple typing

NARCIS (Netherlands)

Stump, A.; Zantema, H.; Kimmell, G.; El Haj Omar, R.

2013-01-01

This paper shows how a recently developed view of typing as small-step abstract reduction, due to Kuan, MacQueen, and Findler, can be used to recast the development of simple type theory from a rewriting perspective. We show how standard meta-theoretic results can be proved in a completely new way,

A flexible optically re-writable color liquid crystal display

Science.gov (United States)

Zhang, Yihong; Sun, Jiatong; Liu, Yang; Shang, Jianhua; Liu, Hao; Liu, Huashan; Gong, Xiaohui; Chigrinov, Vladimir; Kowk, Hoi Sing

2018-03-01

It is very difficult to make a liquid crystal display (LCD) that is flexible. However, for an optically re-writable LCD (ORWLCD), only the spacers and the substrates need to be flexible because the driving unit and the display unit are separate and there are no electronics in the display part of ORWLCD. In this paper, three flexible-spacer methods are proposed to achieve this goal. A cholesteric liquid crystal colored mirror with a polarizer behind it is used as the colored reflective backboard of an ORWLCD. Polyethersulfone substrates and flexible spacers are used to make the optically re-writable cell insensitive to mechanical force.

Bond graphs : an integrating tool for design of mechatronic systems

International Nuclear Information System (INIS)

Ould Bouamama, B.

2011-01-01

Bond graph is a powerful tool well known for dynamic modelling of multi physical systems: This is the only modelling technique to generate automatically state space or non-linear models using dedicated software tools (CAMP-G, 20-Sim, Symbols, Dymola...). Recently several fundamental theories have been developed for using a bond graph model not only for modeling but also as a real integrated tool from conceptual ideas to optimal practical realization of mechatronic system. This keynote presents a synthesis of those new theories which exploit some particular properties (such as causal, structural and behavioral) of this graphical methodology. Based on a pedagogical example, it will be shown how from a physical system (not a transfer function or state equation) and using only one representation (Bond graph), the following results can be performed: modeling (formal state equations generation), Control analysis (observability, controllability, Structural I/O decouplability, dynamic decoupling,...) diagnosis analysis (automatic generation of robust fault indicators, sensor placement, structural diagnosability) and finally sizing of actuators. The presentation will be illustrated by real industrial applications. Limits and perspectives of bond graph theory conclude the keynote.

Using Behavior Over Time Graphs to Spur Systems Thinking Among Public Health Practitioners.

Science.gov (United States)

Calancie, Larissa; Anderson, Seri; Branscomb, Jane; Apostolico, Alexsandra A; Lich, Kristen Hassmiller

2018-02-01

Public health practitioners can use Behavior Over Time (BOT) graphs to spur discussion and systems thinking around complex challenges. Multiple large systems, such as health care, the economy, and education, affect chronic disease rates in the United States. System thinking tools can build public health practitioners' capacity to understand these systems and collaborate within and across sectors to improve population health. BOT graphs show a variable, or variables (y axis) over time (x axis). Although analyzing trends is not new to public health, drawing BOT graphs, annotating the events and systemic forces that are likely to influence the depicted trends, and then discussing the graphs in a diverse group provides an opportunity for public health practitioners to hear each other's perspectives and creates a more holistic understanding of the key factors that contribute to a trend. We describe how BOT graphs are used in public health, how they can be used to generate group discussion, and how this process can advance systems-level thinking. Then we describe how BOT graphs were used with groups of maternal and child health (MCH) practitioners and partners (N = 101) during a training session to advance their thinking about MCH challenges. Eighty-six percent of the 84 participants who completed an evaluation agreed or strongly agreed that they would use this BOT graph process to engage stakeholders in their home states and jurisdictions. The BOT graph process we describe can be applied to a variety of public health issues and used by practitioners, stakeholders, and researchers.

A Hybrid Approach to Processing Big Data Graphs on Memory-Restricted Systems

KAUST Repository

Harshvardhan,; West, Brandon; Fidel, Adam; Amato, Nancy M.; Rauchwerger, Lawrence

2015-01-01

that sacrifice performance. In this work, we propose a novel RAM-Disk hybrid approach to graph processing that can scale well from a single shared-memory node to large distributed-memory systems. It works by partitioning the graph into sub graphs that fit in RAM

Fault diagnosis of air conditioning systems based on qualitative bond graph

International Nuclear Information System (INIS)

Ghiaus, C.

1999-01-01

The bond graph method represents a unified approach for modeling engineering systems. The main idea is that power transfer bonds the components of a system. The bond graph model is the same for both quantitative representation, in which parameters have numerical values, and qualitative approach, in which they are classified qualitatively. To infer the cause of faults using a qualitative method, a system of qualitative equations must be solved. However, the characteristics of qualitative operators require specific methods for solving systems of equations having qualitative variables. This paper proposes both a method for recursively solving the qualitative system of equations derived from bond graph, and a bond graph model of a direct-expansion, mechanical vapor-compression air conditioning system. Results from diagnosing two faults in a real air conditioning system are presented and discussed. Occasionally, more than one fault candidate is inferred for the same set of qualitative values derived from measurements. In these cases, additional information is required to localize the fault. Fault diagnosis is initiated by a fault detection mechanism which also classifies the quantitative measurements into qualitative values; the fault detection is not presented here. (author)

Proxy Graph: Visual Quality Metrics of Big Graph Sampling.

Science.gov (United States)

Nguyen, Quan Hoang; Hong, Seok-Hee; Eades, Peter; Meidiana, Amyra

2017-06-01

Data sampling has been extensively studied for large scale graph mining. Many analyses and tasks become more efficient when performed on graph samples of much smaller size. The use of proxy objects is common in software engineering for analysis and interaction with heavy objects or systems. In this paper, we coin the term 'proxy graph' and empirically investigate how well a proxy graph visualization can represent a big graph. Our investigation focuses on proxy graphs obtained by sampling; this is one of the most common proxy approaches. Despite the plethora of data sampling studies, this is the first evaluation of sampling in the context of graph visualization. For an objective evaluation, we propose a new family of quality metrics for visual quality of proxy graphs. Our experiments cover popular sampling techniques. Our experimental results lead to guidelines for using sampling-based proxy graphs in visualization.

Graph-related optimization and decision support systems

CERN Document Server

Krichen, Saoussen

2014-01-01

Constrained optimization is a challenging branch of operations research that aims to create a model which has a wide range of applications in the supply chain, telecommunications and medical fields. As the problem structure is split into two main components, the objective is to accomplish the feasible set framed by the system constraints. The aim of this book is expose optimization problems that can be expressed as graphs, by detailing, for each studied problem, the set of nodes and the set of edges.  This graph modeling is an incentive for designing a platform that integrates all optimizatio

Elementary Particle Spectroscopy in Regular Solid Rewrite

International Nuclear Information System (INIS)

Trell, Erik

2008-01-01

The Nilpotent Universal Computer Rewrite System (NUCRS) has operationalized the radical ontological dilemma of Nothing at All versus Anything at All down to the ground recursive syntax and principal mathematical realisation of this categorical dichotomy as such and so governing all its sui generis modalities, leading to fulfilment of their individual terms and compass when the respective choice sequence operations are brought to closure. Focussing on the general grammar, NUCRS by pure logic and its algebraic notations hence bootstraps Quantum Mechanics, aware that it ''is the likely keystone of a fundamental computational foundation'' also for e.g. physics, molecular biology and neuroscience. The present work deals with classical geometry where morphology is the modality, and ventures that the ancient regular solids are its specific rewrite system, in effect extensively anticipating the detailed elementary particle spectroscopy, and further on to essential structures at large both over the inorganic and organic realms. The geodetic antipode to Nothing is extension, with natural eigenvector the endless straight line which when deployed according to the NUCRS as well as Plotelemeian topographic prescriptions forms a real three-dimensional eigenspace with cubical eigenelements where observed quark-skewed quantum-chromodynamical particle events self-generate as an Aristotelean phase transition between the straight and round extremes of absolute endlessness under the symmetry- and gauge-preserving, canonical coset decomposition SO(3)xO(5) of Lie algebra SU(3). The cubical eigen-space and eigen-elements are the parental state and frame, and the other solids are a range of transition matrix elements and portions adapting to the spherical root vector symmetries and so reproducibly reproducing the elementary particle spectroscopy, including a modular, truncated octahedron nano-composition of the Electron which piecemeal enter into molecular structures or compressed to each

Bond graphs for modelling, control and fault diagnosis of engineering systems

CERN Document Server

2017-01-01

This book presents theory and latest application work in Bond Graph methodology with a focus on: • Hybrid dynamical system models, • Model-based fault diagnosis, model-based fault tolerant control, fault prognosis • and also addresses • Open thermodynamic systems with compressible fluid flow, • Distributed parameter models of mechanical subsystems. In addition, the book covers various applications of current interest ranging from motorised wheelchairs, in-vivo surgery robots, walking machines to wind-turbines.The up-to-date presentation has been made possible by experts who are active members of the worldwide bond graph modelling community. This book is the completely revised 2nd edition of the 2011 Springer compilation text titled Bond Graph Modelling of Engineering Systems – Theory, Applications and Software Support. It extends the presentation of theory and applications of graph methodology by new developments and latest research results. Like the first edition, this book addresses readers in a...

Solving Graph Laplacian Systems Through Recursive Bisections and Two-Grid Preconditioning

Energy Technology Data Exchange (ETDEWEB)

Ponce, Colin [Cornell Univ., Ithaca, NY (United States); Vassilevski, Panayot S. [Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States)

2016-02-18

We present a parallelizable direct method for computing the solution to graph Laplacian-based linear systems derived from graphs that can be hierarchically bipartitioned with small edge cuts. For a graph of size n with constant-size edge cuts, our method decomposes a graph Laplacian in time O(n log n), and then uses that decomposition to perform a linear solve in time O(n log n). We then use the developed technique to design a preconditioner for graph Laplacians that do not have this property. Finally, we augment this preconditioner with a two-grid method that accounts for much of the preconditioner's weaknesses. We present an analysis of this method, as well as a general theorem for the condition number of a general class of two-grid support graph-based preconditioners. Numerical experiments illustrate the performance of the studied methods.

Engineering system dynamics a unified graph-centered approach

CERN Document Server

Brown, Forbes T

2006-01-01

For today's students, learning to model the dynamics of complex systems is increasingly important across nearly all engineering disciplines. First published in 2001, Forbes T. Brown's Engineering System Dynamics: A Unified Graph-Centered Approach introduced students to a unique and highly successful approach to modeling system dynamics using bond graphs. Updated with nearly one-third new material, this second edition expands this approach to an even broader range of topics. What's New in the Second Edition? In addition to new material, this edition was restructured to build students' competence in traditional linear mathematical methods before they have gone too far into the modeling that still plays a pivotal role. New topics include magnetic circuits and motors including simulation with magnetic hysteresis; extensive new material on the modeling, analysis, and simulation of distributed-parameter systems; kinetic energy in thermodynamic systems; and Lagrangian and Hamiltonian methods. MATLAB(R) figures promi...

Mizan: A system for dynamic load balancing in large-scale graph processing

KAUST Repository

Khayyat, Zuhair

2013-01-01

Pregel [23] was recently introduced as a scalable graph mining system that can provide significant performance improvements over traditional MapReduce implementations. Existing implementations focus primarily on graph partitioning as a preprocessing step to balance computation across compute nodes. In this paper, we examine the runtime characteristics of a Pregel system. We show that graph partitioning alone is insufficient for minimizing end-to-end computation. Especially where data is very large or the runtime behavior of the algorithm is unknown, an adaptive approach is needed. To this end, we introduce Mizan, a Pregel system that achieves efficient load balancing to better adapt to changes in computing needs. Unlike known implementations of Pregel, Mizan does not assume any a priori knowledge of the structure of the graph or behavior of the algorithm. Instead, it monitors the runtime characteristics of the system. Mizan then performs efficient fine-grained vertex migration to balance computation and communication. We have fully implemented Mizan; using extensive evaluation we show that - especially for highly-dynamic workloads - Mizan provides up to 84% improvement over techniques leveraging static graph pre-partitioning. © 2013 ACM.

Handbook of graph grammars and computing by graph transformation

CERN Document Server

Engels, G; Kreowski, H J; Rozenberg, G

1999-01-01

Graph grammars originated in the late 60s, motivated by considerations about pattern recognition and compiler construction. Since then, the list of areas which have interacted with the development of graph grammars has grown quite impressively. Besides the aforementioned areas, it includes software specification and development, VLSI layout schemes, database design, modeling of concurrent systems, massively parallel computer architectures, logic programming, computer animation, developmental biology, music composition, visual languages, and many others.The area of graph grammars and graph tran

Graph topology and gap topology for unstable systems

NARCIS (Netherlands)

Zhu, S.Q.

1989-01-01

A reformation is provided of the graph topology and the gap topology for a general setting (including lumped linear time-invariant systems and distributed linear time-invariant systems) in the frequency domain. Some essential properties and their comparisons are clearly presented in the

Mechatronic modeling and simulation using bond graphs

CERN Document Server

Das, Shuvra

2009-01-01

Introduction to Mechatronics and System ModelingWhat Is Mechatronics?What Is a System and Why Model Systems?Mathematical Modeling Techniques Used in PracticeSoftwareBond Graphs: What Are They?Engineering SystemsPortsGeneralized VariablesBond GraphsBasic Components in SystemsA Brief Note about Bond Graph Power DirectionsSummary of Bond Direction RulesDrawing Bond Graphs for Simple Systems: Electrical and MechanicalSimplification Rules for Junction StructureDrawing Bond Graphs for Electrical SystemsDrawing Bond Graphs for Mechanical SystemsCausalityDrawing Bond Graphs for Hydraulic and Electronic Components and SystemsSome Basic Properties and Concepts for FluidsBond Graph Model of Hydraulic SystemsElectronic SystemsDeriving System Equations from Bond GraphsSystem VariablesDeriving System EquationsTackling Differential CausalityAlgebraic LoopsSolution of Model Equations and Their InterpretationZeroth Order SystemsFirst Order SystemsSecond Order SystemTransfer Functions and Frequency ResponsesNumerical Solution ...

A rewritable, reprogrammable, dual light-responsive polymer actuator

NARCIS (Netherlands)

Gelebart, A.H.; Mulder, D.J.; Vantomme, G.; Schenning, A.P.H.J.; Broer, D.J.

2017-01-01

We report on the fabrication of a rewritable and reprogrammable dual-photoresponsive liquid crystalline-based actuator containing an azomerocyanine dye that can be locally converted into the hydroxyazopyridinium form by acid treatment. Each dye absorbs at a different wavelength giving access to

Moving picture recording and observation of femtosecond light pulse propagation using a rewritable holographic material

Energy Technology Data Exchange (ETDEWEB)

Yamamoto, Seiji; Takimoto, Tetsuya; Tosa, Kazuya; Kakue, Takashi [Graduate School of Science and Technology, Kyoto Institute of Technology, Matsugasaki, Sakyo, Kyoto 606-8585 (Japan); Awatsuji, Yasuhiro, E-mail: awatsuji@kit.ac.jp [Graduate School of Science and Technology, Kyoto Institute of Technology, Matsugasaki, Sakyo, Kyoto 606-8585 (Japan); Nishio, Kenzo [Advanced Technology Center, Kyoto Institute of Technology, Matsugasaki, Sakyo, Kyoto 606-8585 (Japan); Ura, Shogo [Graduate School of Science and Technology, Kyoto Institute of Technology, Matsugasaki, Sakyo, Kyoto 606-8585 (Japan); Kubota, Toshihiro [Kubota Holography Laboratory, Corporation, Nishihata 34-1-609, Ogura, Uji 611-0042 (Japan)

2011-08-01

We succeeded in recording and observing femtosecond light pulse propagation as a form of moving picture by means of light-in-flight recording by holography using a rewritable holographic material, for the first time. We used a femtosecond pulsed laser whose center wavelength and duration were 800 nm and {approx}120 fs, respectively. A photo-conductor plastic hologram was used as a rewritable holographic material. The femtosecond light pulse was collimated and obliquely incident to the diffuser plate. The behavior of the cross-section between the collimated femtosecond light pulse and the diffuser plate was recorded on the photo-conductor plastic hologram. We experimentally obtained a spatially and temporally continuous moving picture of the femtosecond light pulse propagation for 58.3 ps. Meanwhile, we also investigated the rewritable performance of the photo-conductor plastic hologram. As a result, we confirmed that ten-time rewriting was possible for a photo-conductor plastic hologram.

Identifying Vulnerabilities and Hardening Attack Graphs for Networked Systems

Energy Technology Data Exchange (ETDEWEB)

Saha, Sudip; Vullinati, Anil K.; Halappanavar, Mahantesh; Chatterjee, Samrat

2016-09-15

We investigate efficient security control methods for protecting against vulnerabilities in networked systems. A large number of interdependent vulnerabilities typically exist in the computing nodes of a cyber-system; as vulnerabilities get exploited, starting from low level ones, they open up the doors to more critical vulnerabilities. These cannot be understood just by a topological analysis of the network, and we use the attack graph abstraction of Dewri et al. to study these problems. In contrast to earlier approaches based on heuristics and evolutionary algorithms, we study rigorous methods for quantifying the inherent vulnerability and hardening cost for the system. We develop algorithms with provable approximation guarantees, and evaluate them for real and synthetic attack graphs.

Graph Generator Survey

Energy Technology Data Exchange (ETDEWEB)

Lothian, Joshua [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States); Powers, Sarah S. [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States); Sullivan, Blair D. [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States); Baker, Matthew B. [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States); Schrock, Jonathan [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States); Poole, Stephen W. [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States)

2013-10-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 different 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.

Bond graph modelling of engineering systems: theory, applications and software support

National Research Council Canada - National Science Library

Borutzky, Wolfgang; Margolis, Donald L

2011-01-01

... way such that analytical or computer response predictions can be straightforwardly carried out. Bond graphs are a concise pictorial representation of all types of interacting energetic systems. In my experience working with engineers on the development of complex systems it is obvious that these systems suffer from thermal problems, structural problems, vibration and noise problems, and control and stability issues that do not fit into a single discipline. Bond graphs provide the link by which all these different ...

Fundamentals of algebraic graph transformation

CERN Document Server

Ehrig, Hartmut; Prange, Ulrike; Taentzer, Gabriele

2006-01-01

Graphs are widely used to represent structural information in the form of objects and connections between them. Graph transformation is the rule-based manipulation of graphs, an increasingly important concept in computer science and related fields. This is the first textbook treatment of the algebraic approach to graph transformation, based on algebraic structures and category theory. Part I is an introduction to the classical case of graph and typed graph transformation. In Part II basic and advanced results are first shown for an abstract form of replacement systems, so-called adhesive high-level replacement systems based on category theory, and are then instantiated to several forms of graph and Petri net transformation systems. Part III develops typed attributed graph transformation, a technique of key relevance in the modeling of visual languages and in model transformation. Part IV contains a practical case study on model transformation and a presentation of the AGG (attributed graph grammar) tool envir...

Zero Forcing Sets and Controllability of Dynamical Systems Defined on Graphs

NARCIS (Netherlands)

Monshizadeh Naini, Nima; Zhang, Shuo; Camlibel, M. Kanat

In this technical note, controllability of systems defined on graphs is discussed. We consider the problem of controllability of the network for a family of matrices carrying the structure of an underlying directed graph. A one-to-one correspondence between the set of leaders rendering the network

X-Graphs: Language and Algorithms for Heterogeneous Graph Streams

Science.gov (United States)

2017-09-01

are widely used by academia and industry. 15. SUBJECT TERMS Data Analytics, Graph Analytics, High-Performance Computing 16. SECURITY CLASSIFICATION...form the core of the DeepDive Knowledge Construction System. 2 INTRODUCTION The goal of the X-Graphs project was to develop computational techniques...memory multicore machine. Ringo is based on Snap.py and SNAP, and uses Python . Ringo now allows the integration of Delite DSL Framework Graph

Study of a class of photovoltaic systems using a bond graph approach. Modeling, analysis and control; Etude d'une classe de systemes photovoltaiques par une approche bond graph. Modelisation, analyse et commande

Energy Technology Data Exchange (ETDEWEB)

Andoulsi, R.

2001-12-01

We present in this thesis a study of a class of photovoltaic system by a bond graph approach. This study concerns the modelling, the analysis and the control of some configurations including PV generator, DC/DC converters and DC motor-pumps. The modelling of the different elements of a photovoltaic system is an indispensable stage that must precede all application of sizing, identification or simulation. However, theses PV systems are of hybrid type and their modelling is complex. It is why we use a unified modelling approach based on the bond graph technique. This methodology is completely systematic and has a sufficient flexibility for allowing the introduction of different components in the system. In the first chapter, we recall the principle of functioning of a photovoltaic generator and we treat mainly the MPPT (Maximum Power Point Tracking) working. In the second chapter, we elaborate bond graph models of various photovoltaic system configurations. For the PV source, we elaborate, in a first stage, a complete model taking into account the various physical phenomena influencing the quality of the PV source. In a second stage, we deduce a reduced bond graph model more easy to use for analysis and control purposes. For the DC/DC converters, we recall the bond graph modelling of switching elements and the average bond graph of the DC/DC converters developed in the literature. Thus, we deduce the bond graphs models of the various DC/DC converters to be used. The third chapter presents a dynamic study of some configurations stability in linear procedure. In the fourth chapter, we study the feasibility of non linear controllers by input/output linearization for some configurations of PV systems. In this study, we use the concept of inverse bond graph to determine, by a bond graph approach, the expression of the control input and the nature of the stability of the internal dynamics (dynamics of zeros). The fifth chapter is dedicated for the presentation of some

Introduction to quantum graphs

CERN Document Server

Berkolaiko, Gregory

2012-01-01

A "quantum graph" is a graph considered as a one-dimensional complex and equipped with a differential operator ("Hamiltonian"). Quantum graphs arise naturally as simplified models in mathematics, physics, chemistry, and engineering when one considers propagation of waves of various nature through a quasi-one-dimensional (e.g., "meso-" or "nano-scale") system that looks like a thin neighborhood of a graph. Works that currently would be classified as discussing quantum graphs have been appearing since at least the 1930s, and since then, quantum graphs techniques have been applied successfully in various areas of mathematical physics, mathematics in general and its applications. One can mention, for instance, dynamical systems theory, control theory, quantum chaos, Anderson localization, microelectronics, photonic crystals, physical chemistry, nano-sciences, superconductivity theory, etc. Quantum graphs present many non-trivial mathematical challenges, which makes them dear to a mathematician's heart. Work on qu...

Scalable Parallel Distributed Coprocessor System for Graph Searching Problems with Massive Data

Directory of Open Access Journals (Sweden)

Wanrong Huang

2017-01-01

Full Text Available The Internet applications, such as network searching, electronic commerce, and modern medical applications, produce and process massive data. Considerable data parallelism exists in computation processes of data-intensive applications. A traversal algorithm, breadth-first search (BFS, is fundamental in many graph processing applications and metrics when a graph grows in scale. A variety of scientific programming methods have been proposed for accelerating and parallelizing BFS because of the poor temporal and spatial locality caused by inherent irregular memory access patterns. However, new parallel hardware could provide better improvement for scientific methods. To address small-world graph problems, we propose a scalable and novel field-programmable gate array-based heterogeneous multicore system for scientific programming. The core is multithread for streaming processing. And the communication network InfiniBand is adopted for scalability. We design a binary search algorithm to address mapping to unify all processor addresses. Within the limits permitted by the Graph500 test bench after 1D parallel hybrid BFS algorithm testing, our 8-core and 8-thread-per-core system achieved superior performance and efficiency compared with the prior work under the same degree of parallelism. Our system is efficient not as a special acceleration unit but as a processor platform that deals with graph searching applications.

Mechanical system reliability analysis using a combination of graph theory and Boolean function

International Nuclear Information System (INIS)

Tang, J.

2001-01-01

A new method based on graph theory and Boolean function for assessing reliability of mechanical systems is proposed. The procedure for this approach consists of two parts. By using the graph theory, the formula for the reliability of a mechanical system that considers the interrelations of subsystems or components is generated. Use of the Boolean function to examine the failure interactions of two particular elements of the system, followed with demonstrations of how to incorporate such failure dependencies into the analysis of larger systems, a constructive algorithm for quantifying the genuine interconnections between the subsystems or components is provided. The combination of graph theory and Boolean function provides an effective way to evaluate the reliability of a large, complex mechanical system. A numerical example demonstrates that this method an effective approaches in system reliability analysis

System Response Analysis and Model Order Reduction, Using Conventional Method, Bond Graph Technique and Genetic Programming

Directory of Open Access Journals (Sweden)

Lubna Moin

2009-04-01

Full Text Available This research paper basically explores and compares the different modeling and analysis techniques and than it also explores the model order reduction approach and significance. The traditional modeling and simulation techniques for dynamic systems are generally adequate for single-domain systems only, but the Bond Graph technique provides new strategies for reliable solutions of multi-domain system. They are also used for analyzing linear and non linear dynamic production system, artificial intelligence, image processing, robotics and industrial automation. This paper describes a unique technique of generating the Genetic design from the tree structured transfer function obtained from Bond Graph. This research work combines bond graphs for model representation with Genetic programming for exploring different ideas on design space tree structured transfer function result from replacing typical bond graph element with their impedance equivalent specifying impedance lows for Bond Graph multiport. This tree structured form thus obtained from Bond Graph is applied for generating the Genetic Tree. Application studies will identify key issues and importance for advancing this approach towards becoming on effective and efficient design tool for synthesizing design for Electrical system. In the first phase, the system is modeled using Bond Graph technique. Its system response and transfer function with conventional and Bond Graph method is analyzed and then a approach towards model order reduction is observed. The suggested algorithm and other known modern model order reduction techniques are applied to a 11th order high pass filter [1], with different approach. The model order reduction technique developed in this paper has least reduction errors and secondly the final model retains structural information. The system response and the stability analysis of the system transfer function taken by conventional and by Bond Graph method is compared and

Mizan: Optimizing Graph Mining in Large Parallel Systems

KAUST Repository

Kalnis, Panos

2012-03-01

Extracting information from graphs, from nding shortest paths to complex graph mining, is essential for many ap- plications. Due to the shear size of modern graphs (e.g., social networks), processing must be done on large paral- lel computing infrastructures (e.g., the cloud). Earlier ap- proaches relied on the MapReduce framework, which was proved inadequate for graph algorithms. More recently, the message passing model (e.g., Pregel) has emerged. Although the Pregel model has many advantages, it is agnostic to the graph properties and the architecture of the underlying com- puting infrastructure, leading to suboptimal performance. In this paper, we propose Mizan, a layer between the users\\' code and the computing infrastructure. Mizan considers the structure of the input graph and the architecture of the in- frastructure in order to: (i) decide whether it is bene cial to generate a near-optimal partitioning of the graph in a pre- processing step, and (ii) choose between typical point-to- point message passing and a novel approach that puts com- puting nodes in a virtual overlay ring. We deployed Mizan on a small local Linux cluster, on the cloud (256 virtual machines in Amazon EC2), and on an IBM Blue Gene/P supercomputer (1024 CPUs). We show that Mizan executes common algorithms on very large graphs 1-2 orders of mag- nitude faster than MapReduce-based implementations and up to one order of magnitude faster than implementations relying on Pregel-like hash-based graph partitioning.

Modeling, Control and Analyze of Multi-Machine Drive Systems using Bond Graph Technique

Directory of Open Access Journals (Sweden)

J. Belhadj

2006-03-01

Full Text Available In this paper, a system viewpoint method has been investigated to study and analyze complex systems using Bond Graph technique. These systems are multimachine multi-inverter based on Induction Machine (IM, well used in industries like rolling mills, textile, and railway traction. These systems are multi-domains, multi-scales time and present very strong internal and external couplings, with non-linearity characterized by a high model order. The classical study with analytic model is difficult to manipulate and it is limited to some performances. In this study, a “systemic approach” is presented to design these kinds of systems, using an energetic representation based on Bond Graph formalism. Three types of multimachine are studied with their control strategies. The modeling is carried out by Bond Graph and results are discussed to show the performances of this methodology

Information Graph Flow: A Geometric Approximation of Quantum and Statistical Systems

Science.gov (United States)

Vanchurin, Vitaly

2018-05-01

Given a quantum (or statistical) system with a very large number of degrees of freedom and a preferred tensor product factorization of the Hilbert space (or of a space of distributions) we describe how it can be approximated with a very low-dimensional field theory with geometric degrees of freedom. The geometric approximation procedure consists of three steps. The first step is to construct weighted graphs (we call information graphs) with vertices representing subsystems (e.g., qubits or random variables) and edges representing mutual information (or the flow of information) between subsystems. The second step is to deform the adjacency matrices of the information graphs to that of a (locally) low-dimensional lattice using the graph flow equations introduced in the paper. (Note that the graph flow produces very sparse adjacency matrices and thus might also be used, for example, in machine learning or network science where the task of graph sparsification is of a central importance.) The third step is to define an emergent metric and to derive an effective description of the metric and possibly other degrees of freedom. To illustrate the procedure we analyze (numerically and analytically) two information graph flows with geometric attractors (towards locally one- and two-dimensional lattices) and metric perturbations obeying a geometric flow equation. Our analysis also suggests a possible approach to (a non-perturbative) quantum gravity in which the geometry (a secondary object) emerges directly from a quantum state (a primary object) due to the flow of the information graphs.

Graph-based modelling in engineering

CERN Document Server

Rysiński, Jacek

2017-01-01

This book presents versatile, modern and creative applications of graph theory in mechanical engineering, robotics and computer networks. Topics related to mechanical engineering include e.g. machine and mechanism science, mechatronics, robotics, gearing and transmissions, design theory and production processes. The graphs treated are simple graphs, weighted and mixed graphs, bond graphs, Petri nets, logical trees etc. The authors represent several countries in Europe and America, and their contributions show how different, elegant, useful and fruitful the utilization of graphs in modelling of engineering systems can be. .

Summary: beyond fault trees to fault graphs

International Nuclear Information System (INIS)

Alesso, H.P.; Prassinos, P.; Smith, C.F.

1984-09-01

Fault Graphs are the natural evolutionary step over a traditional fault-tree model. A Fault Graph is a failure-oriented directed graph with logic connectives that allows cycles. We intentionally construct the Fault Graph to trace the piping and instrumentation drawing (P and ID) of the system, but with logical AND and OR conditions added. Then we evaluate the Fault Graph with computer codes based on graph-theoretic methods. Fault Graph computer codes are based on graph concepts, such as path set (a set of nodes traveled on a path from one node to another) and reachability (the complete set of all possible paths between any two nodes). These codes are used to find the cut-sets (any minimal set of component failures that will fail the system) and to evaluate the system reliability

Graph theoretical calculation of systems reliability with semi-Markov processes

International Nuclear Information System (INIS)

Widmer, U.

1984-06-01

The determination of the state probabilities and related quantities of a system characterized by an SMP (or a homogeneous MP) can be performed by means of graph-theoretical methods. The calculation procedures for semi-Markov processes based on signal flow graphs are reviewed. Some methods from electrotechnics are adapted in order to obtain a representation of the state probabilities by means of trees. From this some formulas are derived for the asymptotic state probabilities and for the mean life-time in reliability considerations. (Auth.)

STABILITY OF LINEAR MULTIAGENT SCALAR SYSTEMS AND ITS DEPENDENCE ON CONNECTIVITY GRAPH

Directory of Open Access Journals (Sweden)

S. I. Tomashevich

2014-03-01

Full Text Available Multiagent systems are now finding increasingly wide applications in various engineering fields such as energy, transportation, robotics, aviation and others. There are two main aspects to be focused on when organizing multiagent systems: the dynamics of the agents themselves and the ways of their interaction. This interaction is determined by the structure of information connections between agents. Thus, there are several key points of multiagent systems study: the dynamics of individual agents and shape of the information graph. Formation dynamics, in general, is determined by a set of properties of agents and connectivity graph. The paper deals with the relationship between dynamics of agents and Laplace matrix, which is used to set the graph connections. The present research is based on the results given in the known paper by A. Fax and R. Murray (IEEE Trans. AC, 2004. An illustrative example is given, and the application problem of studying the formation dynamics consisting of the group of quadrocopters is presented. Information exchange between agents is determined in the paper by means of the conventional set of graphs. The paper presents an interpretation of the stability conditions and the method of system performance improvement based on these conditions. Motion of quadrocopters group along the flight height is used as an example for methodology application. The simulation results demonstrate the basic dependencies between the information graph shape (and, consequently, the eigenvalues of the Laplacian, which describes this graph and formation stability. Simulation and consideration of Nyquist diagram connection with the key points give an indication of the system stability and take steps to change the control laws. Necessary conditions for the formation stability are obtained on the basis of this research method. Research result makes it possible to create local control laws for agents to ensure the stability of motion in the selected

MARKOV GRAPHS OF ONE–DIMENSIONAL DYNAMICAL SYSTEMS AND THEIR DISCRETE ANALOGUES AND THEIR DISCRETE ANALOGUES

Directory of Open Access Journals (Sweden)

SERGIY KOZERENKO

2016-04-01

Full Text Available One feature of the famous Sharkovsky’s theorem is that it can be proved using digraphs of a special type (the so–called Markov graphs. The most general definition assigns a Markov graph to every continuous map from the topological graph to itself. We show that this definition is too broad, i.e. every finite digraph can be viewed as a Markov graph of some one–dimensional dynamical system on a tree. We therefore consider discrete analogues of Markov graphs for vertex maps on combinatorial trees and characterize all maps on trees whose discrete Markov graphs are of the following types: complete, complete bipartite, the disjoint union of cycles, with every arc being a loop.

Mapping Between Semantic Graphs and Sentences in Grammar Induction System

Directory of Open Access Journals (Sweden)

Laszlo Kovacs

2010-06-01

Full Text Available The proposed transformation module performs mapping be-
tween two di®erent knowledge representation forms used in grammar induction systems. The kernel knowledge representation form is a special predicate centered conceptual graph called ECG. The ECG provides a semantic-based, language independent description of the environment. The other base representation form is some kind of language. The sentences of the language should meet the corresponding grammatical rules. The pilot project demonstrates the functionality of a translator module using this transformation engine between the ECG graph and the Hungarian language.

A Modal-Logic Based Graph Abstraction

NARCIS (Netherlands)

Bauer, J.; Boneva, I.B.; Kurban, M.E.; Rensink, Arend; Ehrig, H; Heckel, R.; Rozenberg, G.; Taentzer, G.

2008-01-01

Infinite or very large state spaces often prohibit the successful verification of graph transformation systems. Abstract graph transformation is an approach that tackles this problem by abstracting graphs to abstract graphs of bounded size and by lifting application of productions to abstract

Ant-based extraction of rules in simple decision systems over ontological graphs

Directory of Open Access Journals (Sweden)

Pancerz Krzysztof

2015-06-01

Full Text Available In the paper, the problem of extraction of complex decision rules in simple decision systems over ontological graphs is considered. The extracted rules are consistent with the dominance principle similar to that applied in the dominancebased rough set approach (DRSA. In our study, we propose to use a heuristic algorithm, utilizing the ant-based clustering approach, searching the semantic spaces of concepts presented by means of ontological graphs. Concepts included in the semantic spaces are values of attributes describing objects in simple decision systems

Using Graph and Vertex Entropy to Compare Empirical Graphs with Theoretical Graph Models

Directory of Open Access Journals (Sweden)

Tomasz Kajdanowicz

2016-09-01

Full Text Available Over the years, several theoretical graph generation models have been proposed. Among the most prominent are: the Erdős–Renyi random graph model, Watts–Strogatz small world model, Albert–Barabási preferential attachment model, Price citation model, and many more. Often, researchers working with real-world data are interested in understanding the generative phenomena underlying their empirical graphs. They want to know which of the theoretical graph generation models would most probably generate a particular empirical graph. In other words, they expect some similarity assessment between the empirical graph and graphs artificially created from theoretical graph generation models. Usually, in order to assess the similarity of two graphs, centrality measure distributions are compared. For a theoretical graph model this means comparing the empirical graph to a single realization of a theoretical graph model, where the realization is generated from the given model using an arbitrary set of parameters. The similarity between centrality measure distributions can be measured using standard statistical tests, e.g., the Kolmogorov–Smirnov test of distances between cumulative distributions. However, this approach is both error-prone and leads to incorrect conclusions, as we show in our experiments. Therefore, we propose a new method for graph comparison and type classification by comparing the entropies of centrality measure distributions (degree centrality, betweenness centrality, closeness centrality. We demonstrate that our approach can help assign the empirical graph to the most similar theoretical model using a simple unsupervised learning method.

Large-Scale Graph Processing Using Apache Giraph

KAUST Repository

Sakr, Sherif

2017-01-07

This book takes its reader on a journey through Apache Giraph, a popular distributed graph processing platform designed to bring the power of big data processing to graph data. Designed as a step-by-step self-study guide for everyone interested in large-scale graph processing, it describes the fundamental abstractions of the system, its programming models and various techniques for using the system to process graph data at scale, including the implementation of several popular and advanced graph analytics algorithms.

Large-Scale Graph Processing Using Apache Giraph

KAUST Repository

Sakr, Sherif; Orakzai, Faisal Moeen; Abdelaziz, Ibrahim; Khayyat, Zuhair

2017-01-01

This book takes its reader on a journey through Apache Giraph, a popular distributed graph processing platform designed to bring the power of big data processing to graph data. Designed as a step-by-step self-study guide for everyone interested in large-scale graph processing, it describes the fundamental abstractions of the system, its programming models and various techniques for using the system to process graph data at scale, including the implementation of several popular and advanced graph analytics algorithms.

State space model extraction of thermohydraulic systems – Part I: A linear graph approach

International Nuclear Information System (INIS)

Uren, K.R.; Schoor, G. van

2013-01-01

Thermohydraulic simulation codes are increasingly making use of graphical design interfaces. The user can quickly and easily design a thermohydraulic system by placing symbols on the screen resembling system components. These components can then be connected to form a system representation. Such system models may then be used to obtain detailed simulations of the physical system. Usually this kind of simulation models are too complex and not ideal for control system design. Therefore, a need exists for automated techniques to extract lumped parameter models useful for control system design. The goal of this first paper, in a two part series, is to propose a method that utilises a graphical representation of a thermohydraulic system, and a lumped parameter modelling approach, to extract state space models. In this methodology each physical domain of the thermohydraulic system is represented by a linear graph. These linear graphs capture the interaction between all components within and across energy domains – hydraulic, thermal and mechanical. These linear graphs are analysed using a graph-theoretic approach to derive reduced order state space models. These models capture the dominant dynamics of the thermohydraulic system and are ideal for control system design purposes. The proposed state space model extraction method is demonstrated by considering a U-tube system. A non-linear state space model is extracted representing both the hydraulic and thermal domain dynamics of the system. The simulated state space model is compared with a Flownex ® model of the U-tube. Flownex ® is a validated systems thermal-fluid simulation software package. - Highlights: • A state space model extraction methodology based on graph-theoretic concepts. • An energy-based approach to consider multi-domain systems in a common framework. • Allow extraction of transparent (white-box) state space models automatically. • Reduced order models containing only independent state

Augmented marked graphs

CERN Document Server

Cheung, King Sing

2014-01-01

Petri nets are a formal and theoretically rich model for the modelling and analysis of systems. A subclass of Petri nets, augmented marked graphs possess a structure that is especially desirable for the modelling and analysis of systems with concurrent processes and shared resources.This monograph consists of three parts: Part I provides the conceptual background for readers who have no prior knowledge on Petri nets; Part II elaborates the theory of augmented marked graphs; finally, Part III discusses the application to system integration. The book is suitable as a first self-contained volume

A Feynman graph selection tool in GRACE system

International Nuclear Information System (INIS)

Yuasa, Fukuko; Ishikawa, Tadashi; Kaneko, Toshiaki

2001-01-01

We present a Feynman graph selection tool grcsel, which is an interpreter written in C language. In the framework of GRACE, it enables us to get a subset of Feynman graphs according to given conditions

Politics of rewriting: what did Achebe really do? | Molande | Journal ...

African Journals Online (AJOL)

Politics of rewriting: what did Achebe really do? Bright Molande. Abstract. No Abstract. Full Text: EMAIL FREE FULL TEXT EMAIL FREE FULL TEXT · DOWNLOAD FULL TEXT DOWNLOAD FULL TEXT · AJOL African Journals Online. HOW TO USE AJOL... for Researchers · for Librarians · for Authors · FAQ's · More about ...

Mal-Netminer: Malware Classification Approach Based on Social Network Analysis of System Call Graph

Directory of Open Access Journals (Sweden)

Jae-wook Jang

2015-01-01

Full Text Available As the security landscape evolves over time, where thousands of species of malicious codes are seen every day, antivirus vendors strive to detect and classify malware families for efficient and effective responses against malware campaigns. To enrich this effort and by capitalizing on ideas from the social network analysis domain, we build a tool that can help classify malware families using features driven from the graph structure of their system calls. To achieve that, we first construct a system call graph that consists of system calls found in the execution of the individual malware families. To explore distinguishing features of various malware species, we study social network properties as applied to the call graph, including the degree distribution, degree centrality, average distance, clustering coefficient, network density, and component ratio. We utilize features driven from those properties to build a classifier for malware families. Our experimental results show that “influence-based” graph metrics such as the degree centrality are effective for classifying malware, whereas the general structural metrics of malware are less effective for classifying malware. Our experiments demonstrate that the proposed system performs well in detecting and classifying malware families within each malware class with accuracy greater than 96%.

Survey of Approaches to Generate Realistic Synthetic Graphs

Energy Technology Data Exchange (ETDEWEB)

Lim, Seung-Hwan [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States); Lee, Sangkeun [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States); Powers, Sarah S [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States); Shankar, Mallikarjun [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States); Imam, Neena [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States)

2016-10-01

A graph is a flexible data structure that can represent relationships between entities. As with other data analysis tasks, the use of realistic graphs is critical to obtaining valid research results. Unfortunately, using the actual ("real-world") graphs for research and new algorithm development is difficult due to the presence of sensitive information in the data or due to the scale of data. This results in practitioners developing algorithms and systems that employ synthetic graphs instead of real-world graphs. Generating realistic synthetic graphs that provide reliable statistical confidence to algorithmic analysis and system evaluation involves addressing technical hurdles in a broad set of areas. This report surveys the state of the art in approaches to generate realistic graphs that are derived from fitted graph models on real-world graphs.

An Expert System toward Buiding An Earth Science Knowledge Graph

Science.gov (United States)

Zhang, J.; Duan, X.; Ramachandran, R.; Lee, T. J.; Bao, Q.; Gatlin, P. N.; Maskey, M.

2017-12-01

In this ongoing work, we aim to build foundations of Cognitive Computing for Earth Science research. The goal of our project is to develop an end-to-end automated methodology for incrementally constructing Knowledge Graphs for Earth Science (KG4ES). These knowledge graphs can then serve as the foundational components for building cognitive systems in Earth science, enabling researchers to uncover new patterns and hypotheses that are virtually impossible to identify today. In addition, this research focuses on developing mining algorithms needed to exploit these constructed knowledge graphs. As such, these graphs will free knowledge from publications that are generated in a very linear, deterministic manner, and structure knowledge in a way that users can both interact and connect with relevant pieces of information. Our major contributions are two-fold. First, we have developed an end-to-end methodology for constructing Knowledge Graphs for Earth Science (KG4ES) using existing corpus of journal papers and reports. One of the key challenges in any machine learning, especially deep learning applications, is the need for robust and large training datasets. We have developed techniques capable of automatically retraining models and incrementally building and updating KG4ES, based on ever evolving training data. We also adopt the evaluation instrument based on common research methodologies used in Earth science research, especially in Atmospheric Science. Second, we have developed an algorithm to infer new knowledge that can exploit the constructed KG4ES. In more detail, we have developed a network prediction algorithm aiming to explore and predict possible new connections in the KG4ES and aid in new knowledge discovery.

Quantum information processing with graph states

International Nuclear Information System (INIS)

Schlingemann, Dirk-Michael

2005-04-01

Graph states are multiparticle states which are associated with graphs. Each vertex of the graph corresponds to a single system or particle. The links describe quantum correlations (entanglement) between pairs of connected particles. Graph states were initiated independently by two research groups: On the one hand, graph states were introduced by Briegel and Raussendorf as a resource for a new model of one-way quantum computing, where algorithms are implemented by a sequence of measurements at single particles. On the other hand, graph states were developed by the author of this thesis and ReinhardWerner in Braunschweig, as a tool to build quantum error correcting codes, called graph codes. The connection between the two approaches was fully realized in close cooperation of both research groups. This habilitation thesis provides a survey of the theory of graph codes, focussing mainly, but not exclusively on the author's own research work. We present the theoretical and mathematical background for the analysis of graph codes. The concept of one-way quantum computing for general graph states is discussed. We explicitly show how to realize the encoding and decoding device of a graph code on a one-way quantum computer. This kind of implementation is to be seen as a mathematical description of a quantum memory device. In addition to that, we investigate interaction processes, which enable the creation of graph states on very large systems. Particular graph states can be created, for instance, by an Ising type interaction between next neighbor particles which sits at the points of an infinitely extended cubic lattice. Based on the theory of quantum cellular automata, we give a constructive characterization of general interactions which create a translationally invariant graph state. (orig.)

Model-Based Requirements Management in Gear Systems Design Based On Graph-Based Design Languages

Directory of Open Access Journals (Sweden)

Kevin Holder

2017-10-01

Full Text Available For several decades, a wide-spread consensus concerning the enormous importance of an in-depth clarification of the specifications of a product has been observed. A weak clarification of specifications is repeatedly listed as a main cause for the failure of product development projects. Requirements, which can be defined as the purpose, goals, constraints, and criteria associated with a product development project, play a central role in the clarification of specifications. The collection of activities which ensure that requirements are identified, documented, maintained, communicated, and traced throughout the life cycle of a system, product, or service can be referred to as “requirements engineering”. These activities can be supported by a collection and combination of strategies, methods, and tools which are appropriate for the clarification of specifications. Numerous publications describe the strategy and the components of requirements management. Furthermore, recent research investigates its industrial application. Simultaneously, promising developments of graph-based design languages for a holistic digital representation of the product life cycle are presented. Current developments realize graph-based languages by the diagrams of the Unified Modelling Language (UML, and allow the automatic generation and evaluation of multiple product variants. The research presented in this paper seeks to present a method in order to combine the advantages of a conscious requirements management process and graph-based design languages. Consequently, the main objective of this paper is the investigation of a model-based integration of requirements in a product development process by means of graph-based design languages. The research method is based on an in-depth analysis of an exemplary industrial product development, a gear system for so-called “Electrical Multiple Units” (EMU. Important requirements were abstracted from a gear system

Mirroring the Object of the Lesson: The Creative Process of Scriptural Rewriting as an Effective Practice for Teaching Sacred Texts

Science.gov (United States)

Palmer, Carmen

2018-01-01

This paper introduces Rewritten Scripture and scriptural rewriting as a creative process that, when mirrored in a teaching exercise, may serve as an effective practice in teaching sacred texts. Observing changes made between scripture and its rewriting may allow readers to identify different contexts among these texts. Furthermore, the act of…

A CLASSIFIER SYSTEM USING SMOOTH GRAPH COLORING

Directory of Open Access Journals (Sweden)

JORGE FLORES CRUZ

2017-01-01

Full Text Available Unsupervised classifiers allow clustering methods with less or no human intervention. Therefore it is desirable to group the set of items with less data processing. This paper proposes an unsupervised classifier system using the model of soft graph coloring. This method was tested with some classic instances in the literature and the results obtained were compared with classifications made with human intervention, yielding as good or better results than supervised classifiers, sometimes providing alternative classifications that considers additional information that humans did not considered.

On the graph and systems analysis of reversible chemical reaction networks with mass action kinetics

NARCIS (Netherlands)

Rao, Shodhan; Jayawardhana, Bayu; Schaft, Arjan van der

2012-01-01

Motivated by the recent progresses on the interplay between the graph theory and systems theory, we revisit the analysis of reversible chemical reaction networks described by mass action kinetics by reformulating it using the graph knowledge of the underlying networks. Based on this formulation, we

Foxing the Child: The Cultural Transmission of Pedagogical Norms and Values in Dutch Rewritings of Literary Classics for Children 1850-1950

Science.gov (United States)

Parlevliet, Sanne

2012-01-01

This article examines the reciprocity between children's literature and educational ideals in Dutch rewritings of international literary classics published for children between 1850 and 1950. It analyses the assumed pedagogical power of rewritings of international literary classics for children from the perspective of three theoretical concepts:…

On a conjecture concerning helly circle graphs

Directory of Open Access Journals (Sweden)

Durán Guillermo

2003-01-01

Full Text Available We say that G is an e-circle graph if there is a bijection between its vertices and straight lines on the cartesian plane such that two vertices are adjacent in G if and only if the corresponding lines intersect inside the circle of radius one. This definition suggests a method for deciding whether a given graph G is an e-circle graph, by constructing a convenient system S of equations and inequations which represents the structure of G, in such a way that G is an e-circle graph if and only if S has a solution. In fact, e-circle graphs are exactly the circle graphs (intersection graphs of chords in a circle, and thus this method provides an analytic way for recognizing circle graphs. A graph G is a Helly circle graph if G is a circle graph and there exists a model of G by chords such that every three pairwise intersecting chords intersect at the same point. A conjecture by Durán (2000 states that G is a Helly circle graph if and only if G is a circle graph and contains no induced diamonds (a diamond is a graph formed by four vertices and five edges. Many unsuccessful efforts - mainly based on combinatorial and geometrical approaches - have been done in order to validate this conjecture. In this work, we utilize the ideas behind the definition of e-circle graphs and restate this conjecture in terms of an equivalence between two systems of equations and inequations, providing a new, analytic tool to deal with it.

Interaction graphs

DEFF Research Database (Denmark)

Seiller, Thomas

2016-01-01

Interaction graphs were introduced as a general, uniform, construction of dynamic models of linear logic, encompassing all Geometry of Interaction (GoI) constructions introduced so far. This series of work was inspired from Girard's hyperfinite GoI, and develops a quantitative approach that should...... be understood as a dynamic version of weighted relational models. Until now, the interaction graphs framework has been shown to deal with exponentials for the constrained system ELL (Elementary Linear Logic) while keeping its quantitative aspect. Adapting older constructions by Girard, one can clearly define...... "full" exponentials, but at the cost of these quantitative features. We show here that allowing interpretations of proofs to use continuous (yet finite in a measure-theoretic sense) sets of states, as opposed to earlier Interaction Graphs constructions were these sets of states were discrete (and finite...

Graph Aggregation

NARCIS (Netherlands)

Endriss, U.; Grandi, U.

Graph aggregation is the process of computing a single output graph that constitutes a good compromise between several input graphs, each provided by a different source. One needs to perform graph aggregation in a wide variety of situations, e.g., when applying a voting rule (graphs as preference

Enabling Graph Appliance for Genome Assembly

Energy Technology Data Exchange (ETDEWEB)

Singh, Rina [ORNL; Graves, Jeffrey A [ORNL; Lee, Sangkeun (Matt) [ORNL; Sukumar, Sreenivas R [ORNL; Shankar, Mallikarjun [ORNL

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.

GoFFish: A Sub-Graph Centric Framework for Large-Scale Graph Analytics1

Energy Technology Data Exchange (ETDEWEB)

Simmhan, Yogesh; Kumbhare, Alok; Wickramaarachchi, Charith; Nagarkar, Soonil; Ravi, Santosh; Raghavendra, Cauligi; Prasanna, Viktor

2014-08-25

Large scale graph processing is a major research area for Big Data exploration. Vertex centric programming models like Pregel are gaining traction due to their simple abstraction that allows for scalable execution on distributed systems naturally. However, there are limitations to this approach which cause vertex centric algorithms to under-perform due to poor compute to communication overhead ratio and slow convergence of iterative superstep. In this paper we introduce GoFFish a scalable sub-graph centric framework co-designed with a distributed persistent graph storage for large scale graph analytics on commodity clusters. We introduce a sub-graph centric programming abstraction that combines the scalability of a vertex centric approach with the flexibility of shared memory sub-graph computation. We map Connected Components, SSSP and PageRank algorithms to this model to illustrate its flexibility. Further, we empirically analyze GoFFish using several real world graphs and demonstrate its significant performance improvement, orders of magnitude in some cases, compared to Apache Giraph, the leading open source vertex centric implementation. We map Connected Components, SSSP and PageRank algorithms to this model to illustrate its flexibility. Further, we empirically analyze GoFFish using several real world graphs and demonstrate its significant performance improvement, orders of magnitude in some cases, compared to Apache Giraph, the leading open source vertex centric implementation.

Structure of liquid Te-based alloys used in rewritable DVDs

Energy Technology Data Exchange (ETDEWEB)

Delheusy, M.; Raty, J.Y.; Detemple, R.; Welnic, W.; Wuttig, M.; Gaspard, J.-P

2004-07-15

We analyze the structure of Te-based chalcogenide compounds that are used as materials for rewritable DVDs by using a combination of neutron diffraction and ab initio computer simulation. We show that in the liquid, the atoms have a low average coordination number, as the result of a Peierls distortion. The partial pair correlation functions are obtained from the computer simulation data.

Chromatic polynomials of random graphs

International Nuclear Information System (INIS)

Van Bussel, Frank; Fliegner, Denny; Timme, Marc; Ehrlich, Christoph; Stolzenberg, Sebastian

2010-01-01

Chromatic polynomials and related graph invariants are central objects in both graph theory and statistical physics. Computational difficulties, however, have so far restricted studies of such polynomials to graphs that were either very small, very sparse or highly structured. Recent algorithmic advances (Timme et al 2009 New J. Phys. 11 023001) now make it possible to compute chromatic polynomials for moderately sized graphs of arbitrary structure and number of edges. Here we present chromatic polynomials of ensembles of random graphs with up to 30 vertices, over the entire range of edge density. We specifically focus on the locations of the zeros of the polynomial in the complex plane. The results indicate that the chromatic zeros of random graphs have a very consistent layout. In particular, the crossing point, the point at which the chromatic zeros with non-zero imaginary part approach the real axis, scales linearly with the average degree over most of the density range. While the scaling laws obtained are purely empirical, if they continue to hold in general there are significant implications: the crossing points of chromatic zeros in the thermodynamic limit separate systems with zero ground state entropy from systems with positive ground state entropy, the latter an exception to the third law of thermodynamics.

Local adjacency metric dimension of sun graph and stacked book graph

Science.gov (United States)

Yulisda Badri, Alifiah; Darmaji

2018-03-01

A graph is a mathematical system consisting of a non-empty set of nodes and a set of empty sides. One of the topics to be studied in graph theory is the metric dimension. Application in the metric dimension is the navigation robot system on a path. Robot moves from one vertex to another vertex in the field by minimizing the errors that occur in translating the instructions (code) obtained from the vertices of that location. To move the robot must give different instructions (code). In order for the robot to move efficiently, the robot must be fast to translate the code of the nodes of the location it passes. so that the location vertex has a minimum distance. However, if the robot must move with the vertex location on a very large field, so the robot can not detect because the distance is too far.[6] In this case, the robot can determine its position by utilizing location vertices based on adjacency. The problem is to find the minimum cardinality of the required location vertex, and where to put, so that the robot can determine its location. The solution to this problem is the dimension of adjacency metric and adjacency metric bases. Rodrguez-Velzquez and Fernau combine the adjacency metric dimensions with local metric dimensions, thus becoming the local adjacency metric dimension. In the local adjacency metric dimension each vertex in the graph may have the same adjacency representation as the terms of the vertices. To obtain the local metric dimension of values in the graph of the Sun and the stacked book graph is used the construction method by considering the representation of each adjacent vertex of the graph.

Smooth Bundling of Large Streaming and Sequence Graphs

NARCIS (Netherlands)

Hurter, C.; Ersoy, O.; Telea, A.

2013-01-01

Dynamic graphs are increasingly pervasive in modern information systems. However, understanding how a graph changes in time is difficult. We present here two techniques for simplified visualization of dynamic graphs using edge bundles. The first technique uses a recent image-based graph bundling

A nonlinear merging protocol for consensus in multi-agent systems on signed and weighted graphs

Science.gov (United States)

Feng, Shasha; Wang, Li; Li, Yijia; Sun, Shiwen; Xia, Chengyi

2018-01-01

In this paper, we investigate the multi-agent consensus for networks with undirected graphs which are not connected, especially for the signed graph in which some edge weights are positive and some edges have negative weights, and the negative-weight graph whose edge weights are negative. We propose a novel nonlinear merging consensus protocol to drive the states of all agents to converge to the same state zero which is not dependent upon the initial states of agents. If the undirected graph whose edge weights are positive is connected, then the states of all agents converge to the same state more quickly when compared to most other protocols. While the undirected graph whose edge weights might be positive or negative is unconnected, the states of all agents can still converge to the same state zero under the premise that the undirected graph can be divided into several connected subgraphs with more than one node. Furthermore, we also discuss the impact of parameter r presented in our protocol. Current results can further deepen the understanding of consensus processes for multi-agent systems.

Quantum walks on quotient graphs

International Nuclear Information System (INIS)

Krovi, Hari; Brun, Todd A.

2007-01-01

A discrete-time quantum walk on a graph Γ 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

Designing a Cross-organizational Case Management System using Dynamic Condition Response Graphs

DEFF Research Database (Denmark)

Hildebrandt, Thomas; Mukkamala, Raghava Rao; Slaats, Tijs

2011-01-01

systems. We show how DCR Graphs allow to capture directly both the behavioral constraints identified during meetings with the customer and the operational execution as markings of the graph. In comparison, imperative models such as BPMN, Petri Net, UML Sequence or Activity diagrams are only good...... at describing the operational way to fulfill the constraints, leaving the constraints implicit. In particular, we point out that the BPMN ad-hoc sub process activity, intended to support more loosely structured goal driven ad-hoc processes, is inconsistently described in the final version of the BPMN 2...

Towards a theory of geometric graphs

CERN Document Server

Pach, Janos

2004-01-01

The early development of graph theory was heavily motivated and influenced by topological and geometric themes, such as the Konigsberg Bridge Problem, Euler's Polyhedral Formula, or Kuratowski's characterization of planar graphs. In 1936, when Denes Konig published his classical Theory of Finite and Infinite Graphs, the first book ever written on the subject, he stressed this connection by adding the subtitle Combinatorial Topology of Systems of Segments. He wanted to emphasize that the subject of his investigations was very concrete: planar figures consisting of points connected by straight-line segments. However, in the second half of the twentieth century, graph theoretical research took an interesting turn. In the most popular and most rapidly growing areas (the theory of random graphs, Ramsey theory, extremal graph theory, algebraic graph theory, etc.), graphs were considered as abstract binary relations rather than geometric objects. Many of the powerful techniques developed in these fields have been su...

Classical dynamics on graphs

International Nuclear Information System (INIS)

Barra, F.; Gaspard, P.

2001-01-01

We consider the classical evolution of a particle on a graph by using a time-continuous Frobenius-Perron operator that generalizes previous propositions. In this way, the relaxation rates as well as the chaotic properties can be defined for the time-continuous classical dynamics on graphs. These properties are given as the zeros of some periodic-orbit zeta functions. We consider in detail the case of infinite periodic graphs where the particle undergoes a diffusion process. The infinite spatial extension is taken into account by Fourier transforms that decompose the observables and probability densities into sectors corresponding to different values of the wave number. The hydrodynamic modes of diffusion are studied by an eigenvalue problem of a Frobenius-Perron operator corresponding to a given sector. The diffusion coefficient is obtained from the hydrodynamic modes of diffusion and has the Green-Kubo form. Moreover, we study finite but large open graphs that converge to the infinite periodic graph when their size goes to infinity. The lifetime of the particle on the open graph is shown to correspond to the lifetime of a system that undergoes a diffusion process before it escapes

Quick Mining of Isomorphic Exact Large Patterns from Large Graphs

KAUST Repository

Almasri, Islam

2014-12-01

The applications of the sub graph isomorphism search are growing with the growing number of areas that model their systems using graphs or networks. Specifically, many biological systems, such as protein interaction networks, molecular structures and protein contact maps, are modeled as graphs. The sub graph isomorphism search is concerned with finding all sub graphs that are isomorphic to a relevant query graph, the existence of such sub graphs can reflect on the characteristics of the modeled system. The most computationally expensive step in the search for isomorphic sub graphs is the backtracking algorithm that traverses the nodes of the target graph. In this paper, we propose a pruning approach that is inspired by the minimum remaining value heuristic that achieves greater scalability over large query and target graphs. Our testing on various biological networks shows that performance enhancement of our approach over existing state-of-the-art approaches varies between 6x and 53x. © 2014 IEEE.

Quick Mining of Isomorphic Exact Large Patterns from Large Graphs

KAUST Repository

Almasri, Islam; Gao, Xin; Fedoroff, Nina V.

2014-01-01

The applications of the sub graph isomorphism search are growing with the growing number of areas that model their systems using graphs or networks. Specifically, many biological systems, such as protein interaction networks, molecular structures and protein contact maps, are modeled as graphs. The sub graph isomorphism search is concerned with finding all sub graphs that are isomorphic to a relevant query graph, the existence of such sub graphs can reflect on the characteristics of the modeled system. The most computationally expensive step in the search for isomorphic sub graphs is the backtracking algorithm that traverses the nodes of the target graph. In this paper, we propose a pruning approach that is inspired by the minimum remaining value heuristic that achieves greater scalability over large query and target graphs. Our testing on various biological networks shows that performance enhancement of our approach over existing state-of-the-art approaches varies between 6x and 53x. © 2014 IEEE.

Coexistence of graph-oriented and relational data file organisations in a data bank system

International Nuclear Information System (INIS)

Engel, K.D.

1980-01-01

It is shown that a coexistence of hierarchical and relational data bank structures in computer networks in a common data bank system is possible. This coexistence model, first established by NIJSSEN, regards the graph theory CODASYL approach and CODD's relational model as graph-oriented, or rather table-oriented, data file organisation as presented to the user of a common logical structure of the data bank. (WB) [de

Eigenfunction statistics on quantum graphs

International Nuclear Information System (INIS)

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

2010-01-01

We investigate the spatial statistics of the energy eigenfunctions on large quantum graphs. It has previously been conjectured that these should be described by a Gaussian Random Wave Model, by analogy with quantum chaotic systems, for which such a model was proposed by Berry in 1977. The autocorrelation functions we calculate for an individual quantum graph exhibit a universal component, which completely determines a Gaussian Random Wave Model, and a system-dependent deviation. This deviation depends on the graph only through its underlying classical dynamics. Classical criteria for quantum universality to be met asymptotically in the large graph limit (i.e. for the non-universal deviation to vanish) are then extracted. We use an exact field theoretic expression in terms of a variant of a supersymmetric σ model. A saddle-point analysis of this expression leads to the estimates. In particular, intensity correlations are used to discuss the possible equidistribution of the energy eigenfunctions in the large graph limit. When equidistribution is asymptotically realized, our theory predicts a rate of convergence that is a significant refinement of previous estimates. The universal and system-dependent components of intensity correlation functions are recovered by means of an exact trace formula which we analyse in the diagonal approximation, drawing in this way a parallel between the field theory and semiclassics. Our results provide the first instance where an asymptotic Gaussian Random Wave Model has been established microscopically for eigenfunctions in a system with no disorder.

Chromatic graph theory

CERN Document Server

Chartrand, Gary; Rosen, Kenneth H

2008-01-01

Beginning with the origin of the four color problem in 1852, the field of graph colorings has developed into one of the most popular areas of graph theory. Introducing graph theory with a coloring theme, Chromatic Graph Theory explores connections between major topics in graph theory and graph colorings as well as emerging topics. This self-contained book first presents various fundamentals of graph theory that lie outside of graph colorings, including basic terminology and results, trees and connectivity, Eulerian and Hamiltonian graphs, matchings and factorizations, and graph embeddings. The remainder of the text deals exclusively with graph colorings. It covers vertex colorings and bounds for the chromatic number, vertex colorings of graphs embedded on surfaces, and a variety of restricted vertex colorings. The authors also describe edge colorings, monochromatic and rainbow edge colorings, complete vertex colorings, several distinguishing vertex and edge colorings, and many distance-related vertex coloring...

A survey and comparison of transformation tools based on the transformation tool contest

NARCIS (Netherlands)

Jakumeit, E.; Van Gorp, P.; Buchwald, S.; Rose, L.; Wagelaar, D.; Dan, L.; Hegedüs, Á; Hermannsdörfer, M.; Horn, T.; Kalnina, E.; Krause, C.; Lano, K.; Lepper, M.; Rensink, Arend; Rose, L.M.; Wätzoldt, S.; Mazanek, S.

Model transformation is one of the key tasks in model-driven engineering and relies on the efficient matching and modification of graph-based data structures; its sibling graph rewriting has been used to successfully model problems in a variety of domains. Over the last years, a wide range of graph

A Clustering Graph Generator

Energy Technology Data Exchange (ETDEWEB)

Winlaw, Manda [Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States); De Sterck, Hans [Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States); Sanders, Geoffrey [Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States)

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.

Specific features of the REDUCE system and calculation of QCD Feynman graphs

International Nuclear Information System (INIS)

Dulyan, L.S.

1990-01-01

The ways and methods used in calculation of one class of the QCD Feynman graphs with the help of the REDUCE system are described. It is shown how by introducing new constructions and operations the user could avoid difficulties connected with specific restrictions and features of the REDUCE system

Consensus pursuit of heterogeneous multi-agent systems under a directed acyclic graph

Science.gov (United States)

Yan, Jing; Guan, Xin-Ping; Luo, Xiao-Yuan

2011-04-01

This paper is concerned with the cooperative target pursuit problem by multiple agents based on directed acyclic graph. The target appears at a random location and moves only when sensed by the agents, and agents will pursue the target once they detect its existence. Since the ability of each agent may be different, we consider the heterogeneous multi-agent systems. According to the topology of the multi-agent systems, a novel consensus-based control law is proposed, where the target and agents are modeled as a leader and followers, respectively. Based on Mason's rule and signal flow graph analysis, the convergence conditions are provided to show that the agents can catch the target in a finite time. Finally, simulation studies are provided to verify the effectiveness of the proposed approach.

A Female Interrogative Reader: The Adolescent Jane Austen Reads and Rewrites (His)tory.

Science.gov (United States)

Reid-Walsh, Jacqueline

1992-01-01

Argues that Jane Austen's unpublished juvenile work "The History of England" has considerable relevance to twentieth-century high-school English classrooms. Notes that the work humorously shows the gender bias of traditional history texts because it is a "woman-centered" rewriting. (RS)

Kellogg Foundation Initiative: Rewriting the Way Foundations Do Business in Indian Country.

Science.gov (United States)

Boyer, Paul

2000-01-01

Describes the multi-million dollar initiative announced by W. K. Kellogg Foundation in 1995 to support the Native American Higher Education Initiative, and how the Kellogg initiative deserves attention from the nation as a whole because it is attempting to fundamentally rewrite the way foundations do business with Indian communities. (VWC)

A formal definition of data flow graph models

Science.gov (United States)

Kavi, Krishna M.; Buckles, Bill P.; Bhat, U. Narayan

1986-01-01

In this paper, a new model for parallel computations and parallel computer systems that is based on data flow principles is presented. Uninterpreted data flow graphs can be used to model computer systems including data driven and parallel processors. A data flow graph is defined to be a bipartite graph with actors and links as the two vertex classes. Actors can be considered similar to transitions in Petri nets, and links similar to places. The nondeterministic nature of uninterpreted data flow graphs necessitates the derivation of liveness conditions.

Volatility behavior of visibility graph EMD financial time series from Ising interacting system

Science.gov (United States)

Zhang, Bo; Wang, Jun; Fang, Wen

2015-08-01

A financial market dynamics model is developed and investigated by stochastic Ising system, where the Ising model is the most popular ferromagnetic model in statistical physics systems. Applying two graph based analysis and multiscale entropy method, we investigate and compare the statistical volatility behavior of return time series and the corresponding IMF series derived from the empirical mode decomposition (EMD) method. And the real stock market indices are considered to be comparatively studied with the simulation data of the proposed model. Further, we find that the degree distribution of visibility graph for the simulation series has the power law tails, and the assortative network exhibits the mixing pattern property. All these features are in agreement with the real market data, the research confirms that the financial model established by the Ising system is reasonable.

An Interactive Teaching System for Bond Graph Modeling and Simulation in Bioengineering

Science.gov (United States)

Roman, Monica; Popescu, Dorin; Selisteanu, Dan

2013-01-01

The objective of the present work was to implement a teaching system useful in modeling and simulation of biotechnological processes. The interactive system is based on applications developed using 20-sim modeling and simulation software environment. A procedure for the simulation of bioprocesses modeled by bond graphs is proposed and simulators…

GDSCalc: A Web-Based Application for Evaluating Discrete Graph Dynamical Systems.

Science.gov (United States)

Elmeligy Abdelhamid, Sherif H; Kuhlman, Chris J; Marathe, Madhav V; Mortveit, Henning S; Ravi, S S

2015-01-01

Discrete dynamical systems are used to model various realistic systems in network science, from social unrest in human populations to regulation in biological networks. A common approach is to model the agents of a system as vertices of a graph, and the pairwise interactions between agents as edges. Agents are in one of a finite set of states at each discrete time step and are assigned functions that describe how their states change based on neighborhood relations. Full characterization of state transitions of one system can give insights into fundamental behaviors of other dynamical systems. In this paper, we describe a discrete graph dynamical systems (GDSs) application called GDSCalc for computing and characterizing system dynamics. It is an open access system that is used through a web interface. We provide an overview of GDS theory. This theory is the basis of the web application; i.e., an understanding of GDS provides an understanding of the software features, while abstracting away implementation details. We present a set of illustrative examples to demonstrate its use in education and research. Finally, we compare GDSCalc with other discrete dynamical system software tools. Our perspective is that no single software tool will perform all computations that may be required by all users; tools typically have particular features that are more suitable for some tasks. We situate GDSCalc within this space of software tools.

Tailored Random Graph Ensembles

International Nuclear Information System (INIS)

Roberts, E S; Annibale, A; Coolen, A C C

2013-01-01

Tailored graph ensembles are a developing bridge between biological networks and statistical mechanics. The aim is to use this concept to generate a suite of rigorous tools that can be used to quantify and compare the topology of cellular signalling networks, such as protein-protein interaction networks and gene regulation networks. We calculate exact and explicit formulae for the leading orders in the system size of the Shannon entropies of random graph ensembles constrained with degree distribution and degree-degree correlation. We also construct an ergodic detailed balance Markov chain with non-trivial acceptance probabilities which converges to a strictly uniform measure and is based on edge swaps that conserve all degrees. The acceptance probabilities can be generalized to define Markov chains that target any alternative desired measure on the space of directed or undirected graphs, in order to generate graphs with more sophisticated topological features.

A distributed query execution engine of big attributed graphs.

Science.gov (United States)

Batarfi, Omar; Elshawi, Radwa; Fayoumi, Ayman; Barnawi, Ahmed; Sakr, Sherif

2016-01-01

A graph is a popular data model that has become pervasively used for modeling structural relationships between objects. In practice, in many real-world graphs, the graph vertices and edges need to be associated with descriptive attributes. Such type of graphs are referred to as attributed graphs. G-SPARQL has been proposed as an expressive language, with a centralized execution engine, for querying attributed graphs. G-SPARQL supports various types of graph querying operations including reachability, pattern matching and shortest path where any G-SPARQL query may include value-based predicates on the descriptive information (attributes) of the graph edges/vertices in addition to the structural predicates. In general, a main limitation of centralized systems is that their vertical scalability is always restricted by the physical limits of computer systems. This article describes the design, implementation in addition to the performance evaluation of DG-SPARQL, a distributed, hybrid and adaptive parallel execution engine of G-SPARQL queries. In this engine, the topology of the graph is distributed over the main memory of the underlying nodes while the graph data are maintained in a relational store which is replicated on the disk of each of the underlying nodes. DG-SPARQL evaluates parts of the query plan via SQL queries which are pushed to the underlying relational stores while other parts of the query plan, as necessary, are evaluated via indexless memory-based graph traversal algorithms. Our experimental evaluation shows the efficiency and the scalability of DG-SPARQL on querying massive attributed graph datasets in addition to its ability to outperform the performance of Apache Giraph, a popular distributed graph processing system, by orders of magnitudes.

PRIVATE GRAPHS – ACCESS RIGHTS ON GRAPHS FOR SEAMLESS NAVIGATION

Directory of Open Access Journals (Sweden)

W. Dorner

2016-06-01

Full Text Available After the success of GNSS (Global Navigational Satellite Systems and navigation services for public streets, indoor seems to be the next big development in navigational services, relying on RTLS – Real Time Locating Services (e.g. WIFI and allowing seamless navigation. In contrast to navigation and routing services on public streets, seamless navigation will cause an additional challenge: how to make routing data accessible to defined users or restrict access rights for defined areas or only to parts of the graph to a defined user group? The paper will present case studies and data from literature, where seamless and especially indoor navigation solutions are presented (hospitals, industrial complexes, building sites, but the problem of restricted access rights was only touched from a real world, but not a technical perspective. The analysis of case studies will show, that the objective of navigation and the different target groups for navigation solutions will demand well defined access rights and require solutions, how to make only parts of a graph to a user or application available to solve a navigational task. The paper will therefore introduce the concept of private graphs, which is defined as a graph for navigational purposes covering the street, road or floor network of an area behind a public street and suggest different approaches how to make graph data for navigational purposes available considering access rights and data protection, privacy and security issues as well.

Graph sampling

OpenAIRE

Zhang, L.-C.; Patone, M.

2017-01-01

We synthesise the existing theory of graph sampling. We propose a formal definition of sampling in finite graphs, and provide a classification of potential graph parameters. We develop a general approach of Horvitz–Thompson estimation to T-stage snowball sampling, and present various reformulations of some common network sampling methods in the literature in terms of the outlined graph sampling theory.

Incremental Query Rewriting with Resolution

Science.gov (United States)

Riazanov, Alexandre; Aragão, Marcelo A. T.

We address the problem of semantic querying of relational databases (RDB) modulo knowledge bases using very expressive knowledge representation formalisms, such as full first-order logic or its various fragments. We propose to use a resolution-based first-order logic (FOL) reasoner for computing schematic answers to deductive queries, with the subsequent translation of these schematic answers to SQL queries which are evaluated using a conventional relational DBMS. We call our method incremental query rewriting, because an original semantic query is rewritten into a (potentially infinite) series of SQL queries. In this chapter, we outline the main idea of our technique - using abstractions of databases and constrained clauses for deriving schematic answers, and provide completeness and soundness proofs to justify the applicability of this technique to the case of resolution for FOL without equality. The proposed method can be directly used with regular RDBs, including legacy databases. Moreover, we propose it as a potential basis for an efficient Web-scale semantic search technology.

A kilobyte rewritable atomic memory

Science.gov (United States)

Kalff, Floris; Rebergen, Marnix; Fahrenfort, Nora; Girovsky, Jan; Toskovic, Ranko; Lado, Jose; FernáNdez-Rossier, JoaquíN.; Otte, Sander

The ability to manipulate individual atoms by means of scanning tunneling microscopy (STM) opens op opportunities for storage of digital data on the atomic scale. Recent achievements in this direction include data storage based on bits encoded in the charge state, the magnetic state, or the local presence of single atoms or atomic assemblies. However, a key challenge at this stage is the extension of such technologies into large-scale rewritable bit arrays. We demonstrate a digital atomic-scale memory of up to 1 kilobyte (8000 bits) using an array of individual surface vacancies in a chlorine terminated Cu(100) surface. The chlorine vacancies are found to be stable at temperatures up to 77 K. The memory, crafted using scanning tunneling microscopy at low temperature, can be read and re-written automatically by means of atomic-scale markers, and offers an areal density of 502 Terabits per square inch, outperforming state-of-the-art hard disk drives by three orders of magnitude.

Algorithms for Planar Graphs and Graphs in Metric Spaces

DEFF Research Database (Denmark)

Wulff-Nilsen, Christian

structural properties that can be exploited. For instance, a road network or a wire layout on a microchip is typically (near-)planar and distances in the network are often defined w.r.t. the Euclidean or the rectilinear metric. Specialized algorithms that take advantage of such properties are often orders...... of magnitude faster than the corresponding algorithms for general graphs. The first and main part of this thesis focuses on the development of efficient planar graph algorithms. The most important contributions include a faster single-source shortest path algorithm, a distance oracle with subquadratic...... for geometric graphs and graphs embedded in metric spaces. Roughly speaking, the stretch factor is a real value expressing how well a (geo-)metric graph approximates the underlying complete graph w.r.t. distances. We give improved algorithms for computing the stretch factor of a given graph and for augmenting...

Using the graphs models for evaluating in-core monitoring systems reliability by the method of imiting simulaton

International Nuclear Information System (INIS)

Golovanov, M.N.; Zyuzin, N.N.; Levin, G.L.; Chesnokov, A.N.

1987-01-01

An approach for estimation of reliability factors of complex reserved systems at early stages of development using the method of imitating simulation is considered. Different types of models, their merits and lacks are given. Features of in-core monitoring systems and advosability of graph model and graph theory element application for estimating reliability of such systems are shown. The results of investigation of the reliability factors of the reactor monitoring, control and core local protection subsystem are shown

Infinitary Combinatory Reduction Systems

DEFF Research Database (Denmark)

Ketema, Jeroen; Simonsen, Jakob Grue

2011-01-01

We define infinitary Combinatory Reduction Systems (iCRSs), thus providing the first notion of infinitary higher-order rewriting. The systems defined are sufficiently general that ordinary infinitary term rewriting and infinitary ¿-calculus are special cases. Furthermore,we generalise a number...

The Container Problem in Bubble-Sort Graphs

Science.gov (United States)

Suzuki, Yasuto; Kaneko, Keiichi

Bubble-sort graphs are variants of Cayley graphs. A bubble-sort graph is suitable as a topology for massively parallel systems because of its simple and regular structure. Therefore, in this study, we focus on n-bubble-sort graphs and propose an algorithm to obtain n-1 disjoint paths between two arbitrary nodes in time bounded by a polynomial in n, the degree of the graph plus one. We estimate the time complexity of the algorithm and the sum of the path lengths after proving the correctness of the algorithm. In addition, we report the results of computer experiments evaluating the average performance of the algorithm.

Cellular Automata on Graphs: Topological Properties of ER Graphs Evolved towards Low-Entropy Dynamics

Directory of Open Access Journals (Sweden)

Marc-Thorsten Hütt

2012-06-01

Full Text Available Cellular automata (CA are a remarkably  efficient tool for exploring general properties of complex systems and spatiotemporal patterns arising from local rules. Totalistic cellular automata,  where the update  rules depend  only on the density of neighboring states, are at the same time a versatile  tool for exploring  dynamical  processes on graphs. Here we briefly review our previous results on cellular automata on graphs, emphasizing some systematic relationships between network architecture and dynamics identified in this way. We then extend the investigation  towards graphs obtained in a simulated-evolution procedure, starting from Erdő s–Rényi (ER graphs and selecting for low entropies of the CA dynamics. Our key result is a strong association of low Shannon entropies with a broadening of the graph’s degree distribution.

Chemical Graph Transformation with Stereo-Information

DEFF Research Database (Denmark)

Andersen, Jakob Lykke; Flamm, Christoph; Merkle, Daniel

2017-01-01

Double Pushout graph transformation naturally facilitates the modelling of chemical reactions: labelled undirected graphs model molecules and direct derivations model chemical reactions. However, the most straightforward modelling approach ignores the relative placement of atoms and their neighbo......Double Pushout graph transformation naturally facilitates the modelling of chemical reactions: labelled undirected graphs model molecules and direct derivations model chemical reactions. However, the most straightforward modelling approach ignores the relative placement of atoms...... and their neighbours in space. Stereoisomers of chemical compounds thus cannot be distinguished, even though their chemical activity may differ substantially. In this contribution we propose an extended chemical graph transformation system with attributes that encode information about local geometry. The modelling...... of graph transformation, but we here propose a framework that also allows for partially specified stereoinformation. While there are several stereochemical configurations to be considered, we focus here on the tetrahedral molecular shape, and suggest general principles for how to treat all other chemically...

Degree Associated Edge Reconstruction Number of Graphs with Regular Pruned Graph

Directory of Open Access Journals (Sweden)

P. Anusha Devi

2015-10-01

Full Text Available An ecard of a graph $G$ is a subgraph formed by deleting an edge. A da-ecard specifies the degree of the deleted edge along with the ecard. The degree associated edge reconstruction number of a graph $G,~dern(G,$ is the minimum number of da-ecards that uniquely determines $G.$  The adversary degree associated edge reconstruction number of a graph $G, adern(G,$ is the minimum number $k$ such that every collection of $k$ da-ecards of $G$ uniquely determines $G.$ The maximal subgraph without end vertices of a graph $G$ which is not a tree is the pruned graph of $G.$ It is shown that $dern$ of complete multipartite graphs and some connected graphs with regular pruned graph is $1$ or $2.$ We also determine $dern$ and $adern$ of corona product of standard graphs.

Percolator: Scalable Pattern Discovery in Dynamic Graphs

Energy Technology Data Exchange (ETDEWEB)

Choudhury, Sutanay; Purohit, Sumit; Lin, Peng; Wu, Yinghui; Holder, Lawrence B.; Agarwal, Khushbu

2018-02-06

We demonstrate Percolator, a distributed system for graph pattern discovery in dynamic graphs. In contrast to conventional mining systems, Percolator advocates efficient pattern mining schemes that (1) support pattern detection with keywords; (2) integrate incremental and parallel pattern mining; and (3) support analytical queries such as trend analysis. The core idea of Percolator is to dynamically decide and verify a small fraction of patterns and their in- stances that must be inspected in response to buffered updates in dynamic graphs, with a total mining cost independent of graph size. We demonstrate a) the feasibility of incremental pattern mining by walking through each component of Percolator, b) the efficiency and scalability of Percolator over the sheer size of real-world dynamic graphs, and c) how the user-friendly GUI of Percolator inter- acts with users to support keyword-based queries that detect, browse and inspect trending patterns. We also demonstrate two user cases of Percolator, in social media trend analysis and academic collaboration analysis, respectively.

Graph processing platforms at scale: practices and experiences

Energy Technology Data Exchange (ETDEWEB)

Lim, Seung-Hwan [ORNL; Lee, Sangkeun (Matt) [ORNL; Brown, Tyler C [ORNL; Sukumar, Sreenivas R [ORNL; Ganesh, Gautam [ORNL

2015-01-01

Graph analysis unveils hidden associations of data in many phenomena and artifacts, such as road network, social networks, genomic information, and scientific collaboration. Unfortunately, a wide diversity in the characteristics of graphs and graph operations make it challenging to find a right combination of tools and implementation of algorithms to discover desired knowledge from the target data set. This study presents an extensive empirical study of three representative graph processing platforms: Pegasus, GraphX, and Urika. Each system represents a combination of options in data model, processing paradigm, and infrastructure. We benchmarked each platform using three popular graph operations, degree distribution, connected components, and PageRank over a variety of real-world graphs. Our experiments show that each graph processing platform shows different strength, depending the type of graph operations. While Urika performs the best in non-iterative operations like degree distribution, GraphX outputforms iterative operations like connected components and PageRank. In addition, we discuss challenges to optimize the performance of each platform over large scale real world graphs.

Introduction to graph theory

CERN Document Server

Trudeau, Richard J

1994-01-01

Preface1. Pure Mathematics Introduction; Euclidean Geometry as Pure Mathematics; Games; Why Study Pure Mathematics?; What's Coming; Suggested Reading2. Graphs Introduction; Sets; Paradox; Graphs; Graph diagrams; Cautions; Common Graphs; Discovery; Complements and Subgraphs; Isomorphism; Recognizing Isomorphic Graphs; Semantics The Number of Graphs Having a Given nu; Exercises; Suggested Reading3. Planar Graphs Introduction; UG, K subscript 5, and the Jordan Curve Theorem; Are there More Nonplanar Graphs?; Expansions; Kuratowski's Theorem; Determining Whether a Graph is Planar or

Graph Theory. 2. Vertex Descriptors and Graph Coloring

Directory of Open Access Journals (Sweden)

Lorentz JÄNTSCHI

2002-12-01

Full Text Available This original work presents the construction of a set of ten sequence matrices and their applications for ordering vertices in graphs. For every sequence matrix three ordering criteria are applied: lexicographic ordering, based on strings of numbers, corresponding to every vertex, extracted as rows from sequence matrices; ordering by the sum of path lengths from a given vertex; and ordering by the sum of paths, starting from a given vertex. We also examine a graph that has different orderings for the above criteria. We then proceed to demonstrate that every criterion induced its own partition of graph vertex. We propose the following theoretical result: both LAVS and LVDS criteria generate identical partitioning of vertices in any graph. Finally, a coloring of graph vertices according to introduced ordering criteria was proposed.

On an edge partition and root graphs of some classes of line graphs

Directory of Open Access Journals (Sweden)

K Pravas

2017-04-01

Full Text Available The Gallai and the anti-Gallai graphs of a graph $G$ are complementary pairs of spanning subgraphs of the line graph of $G$. In this paper we find some structural relations between these graph classes by finding a partition of the edge set of the line graph of a graph $G$ into the edge sets of the Gallai and anti-Gallai graphs of $G$. Based on this, an optimal algorithm to find the root graph of a line graph is obtained. Moreover, root graphs of diameter-maximal, distance-hereditary, Ptolemaic and chordal graphs are also discussed.

Graphs and matrices

CERN Document Server

Bapat, Ravindra B

2014-01-01

This new edition illustrates the power of linear algebra in the study of graphs. The emphasis on matrix techniques is greater than in other texts on algebraic graph theory. Important matrices associated with graphs (for example, incidence, adjacency and Laplacian matrices) are treated in detail. Presenting a useful overview of selected topics in algebraic graph theory, early chapters of the text focus on regular graphs, algebraic connectivity, the distance matrix of a tree, and its generalized version for arbitrary graphs, known as the resistance matrix. Coverage of later topics include Laplacian eigenvalues of threshold graphs, the positive definite completion problem and matrix games based on a graph. Such an extensive coverage of the subject area provides a welcome prompt for further exploration. The inclusion of exercises enables practical learning throughout the book. In the new edition, a new chapter is added on the line graph of a tree, while some results in Chapter 6 on Perron-Frobenius theory are reo...

Replica methods for loopy sparse random graphs

International Nuclear Information System (INIS)

Coolen, ACC

2016-01-01

I report on the development of a novel statistical mechanical formalism for the analysis of random graphs with many short loops, and processes on such graphs. The graphs are defined via maximum entropy ensembles, in which both the degrees (via hard constraints) and the adjacency matrix spectrum (via a soft constraint) are prescribed. The sum over graphs can be done analytically, using a replica formalism with complex replica dimensions. All known results for tree-like graphs are recovered in a suitable limit. For loopy graphs, the emerging theory has an appealing and intuitive structure, suggests how message passing algorithms should be adapted, and what is the structure of theories describing spin systems on loopy architectures. However, the formalism is still largely untested, and may require further adjustment and refinement. (paper)

Rule-based programming and strategies for automated generation of detailed kinetic models for gas phase combustion of polycyclic hydrocarbon molecules; Programmation par regles et strategies pour la generation automatique de mecanismes de combustion d'hydrocarbures polycycliques

Energy Technology Data Exchange (ETDEWEB)

Ibanescu, L.

2004-06-15

The primary objective of this thesis is to explore the approach of using rule-based systems and strategies, for a complex problem of chemical kinetic: the automated generation of reaction mechanisms. The chemical reactions are naturally expressed as conditional rewriting rules. The control of the chemical reactions chaining is easy to describe using a strategies language, such as the one of the ELAN system, developed in the Protheo team. The thesis presents the basic concepts of the chemical kinetics, the chemical and computational problems related to the conception and validation of a reaction mechanism, and gives a general structure for the generator of reaction mechanisms called GasEI. Our research focuses on the primary mechanism generator. We give solutions for encoding the chemical species, the reactions and their chaining, and we present the prototype developed in ELAN. The representation of the chemical species uses the notion of molecular graphs, encoded by a term structure called GasEI terms. The chemical reactions are expressed by rewriting rules on molecular graphs, encoded by a set of conditional rewriting rules on GasEI terms. The strategies language of the ELAN system is used to express the reactions chaining in the primary mechanism generator. This approach is illustrated by coding ten generic reactions of the oxidizing pyrolysis. Qualitative chemical validations of the prototype show that our approach gives, for acyclic molecules, the same results as the existing mechanism generators, and for polycyclic molecules produces original results.

Rule-based programming and strategies for automated generation of detailed kinetic models for gas phase combustion of polycyclic hydrocarbon molecules; Programmation par regles et strategies pour la generation automatique de mecanismes de combustion d'hydrocarbures polycycliques

Energy Technology Data Exchange (ETDEWEB)

Ibanescu, L

2004-06-15

The primary objective of this thesis is to explore the approach of using rule-based systems and strategies, for a complex problem of chemical kinetic: the automated generation of reaction mechanisms. The chemical reactions are naturally expressed as conditional rewriting rules. The control of the chemical reactions chaining is easy to describe using a strategies language, such as the one of the ELAN system, developed in the Protheo team. The thesis presents the basic concepts of the chemical kinetics, the chemical and computational problems related to the conception and validation of a reaction mechanism, and gives a general structure for the generator of reaction mechanisms called GasEI. Our research focuses on the primary mechanism generator. We give solutions for encoding the chemical species, the reactions and their chaining, and we present the prototype developed in ELAN. The representation of the chemical species uses the notion of molecular graphs, encoded by a term structure called GasEI terms. The chemical reactions are expressed by rewriting rules on molecular graphs, encoded by a set of conditional rewriting rules on GasEI terms. The strategies language of the ELAN system is used to express the reactions chaining in the primary mechanism generator. This approach is illustrated by coding ten generic reactions of the oxidizing pyrolysis. Qualitative chemical validations of the prototype show that our approach gives, for acyclic molecules, the same results as the existing mechanism generators, and for polycyclic molecules produces original results.

Graphs cospectral with a friendship graph or its complement

Directory of Open Access Journals (Sweden)

Alireza Abdollahi

2013-12-01

Full Text Available Let $n$ be any positive integer and let $F_n$ be the friendship (or Dutch windmill graph with $2n+1$ vertices and $3n$ edges. Here we study graphs with the same adjacency spectrum as the $F_n$. Two graphs are called cospectral if the eigenvalues multiset of their adjacency matrices are the same. Let $G$ be a graph cospectral with $F_n$. Here we prove that if $G$ has no cycle of length $4$ or $5$, then $Gcong F_n$. Moreover if $G$ is connected and planar then $Gcong F_n$.All but one of connected components of $G$ are isomorphic to $K_2$.The complement $overline{F_n}$ of the friendship graph is determined by its adjacency eigenvalues, that is, if $overline{F_n}$ is cospectral with a graph $H$, then $Hcong overline{F_n}$.

The One Universal Graph — a free and open graph database

Science.gov (United States)

Ng, Liang S.; Champion, Corbin

2016-02-01

Recent developments in graph database mostly are huge projects involving big organizations, big operations and big capital, as the name Big Data attests. We proposed the concept of One Universal Graph (OUG) which states that all observable and known objects and concepts (physical, conceptual or digitally represented) can be connected with only one single graph; furthermore the OUG can be implemented with a very simple text file format with free software, capable of being executed on Android or smaller devices. As such the One Universal Graph Data Exchange (GOUDEX) modules can potentially be installed on hundreds of millions of Android devices and Intel compatible computers shipped annually. Coupled with its open nature and ability to connect to existing leading search engines and databases currently in operation, GOUDEX has the potential to become the largest and a better interface for users and programmers to interact with the data on the Internet. With a Web User Interface for users to use and program in native Linux environment, Free Crowdware implemented in GOUDEX can help inexperienced users learn programming with better organized documentation for free software, and is able to manage programmer's contribution down to a single line of code or a single variable in software projects. It can become the first practically realizable “Internet brain” on which a global artificial intelligence system can be implemented. Being practically free and open, One Universal Graph can have significant applications in robotics, artificial intelligence as well as social networks.

On revealing graph cycles via boundary measurements

International Nuclear Information System (INIS)

Belishev, M I; Wada, N

2009-01-01

This paper deals with boundary value inverse problems on a metric graph, the structure of the graph being assumed unknown. The question under consideration is how to detect from the dynamical and/or spectral inverse data whether the graph contains cycles (is not a tree). For any graph Ω, the dynamical as well as spectral boundary inverse data determine the so-called wave diameter d w : H -1 (Ω) → R defined on functionals supported in the graph. The known fact is that if Ω is a tree then d w ≥ 0 holds and, in this case, the inverse data determine Ω up to isometry. A graph Ω is said to be coordinate if the functions {dist Ω (., γ)} γin∂Ω constitute a coordinate system on Ω. For such graphs, we propose a procedure, which reveals the presence/absence of cycles. The hypothesis is that Ω contains cycles if and only if d w takes negative values. We do not justify this hypothesis in the general case but reduce it to a certain special class of graphs (suns)

Graph embedding with rich information through heterogeneous graph

KAUST Repository

Sun, Guolei

2017-11-12

Graph embedding, aiming to learn low-dimensional representations for nodes in graphs, has attracted increasing attention due to its critical application including node classification, link prediction and clustering in social network analysis. Most existing algorithms for graph embedding only rely on the topology information and fail to use the copious information in nodes as well as edges. As a result, their performance for many tasks may not be satisfactory. In this thesis, we proposed a novel and general framework for graph embedding with rich text information (GERI) through constructing a heterogeneous network, in which we integrate node and edge content information with graph topology. Specially, we designed a novel biased random walk to explore the constructed heterogeneous network with the notion of flexible neighborhood. Our sampling strategy can compromise between BFS and DFS local search on heterogeneous graph. To further improve our algorithm, we proposed semi-supervised GERI (SGERI), which learns graph embedding in an discriminative manner through heterogeneous network with label information. The efficacy of our method is demonstrated by extensive comparison experiments with 9 baselines over multi-label and multi-class classification on various datasets including Citeseer, Cora, DBLP and Wiki. It shows that GERI improves the Micro-F1 and Macro-F1 of node classification up to 10%, and SGERI improves GERI by 5% in Wiki.

Topics in graph theory graphs and their Cartesian product

CERN Document Server

Imrich, Wilfried; Rall, Douglas F

2008-01-01

From specialists in the field, you will learn about interesting connections and recent developments in the field of graph theory by looking in particular at Cartesian products-arguably the most important of the four standard graph products. Many new results in this area appear for the first time in print in this book. Written in an accessible way, this book can be used for personal study in advanced applications of graph theory or for an advanced graph theory course.

Algorithm for shortest path search in Geographic Information Systems by using reduced graphs.

Science.gov (United States)

Rodríguez-Puente, Rafael; Lazo-Cortés, Manuel S

2013-01-01

The use of Geographic Information Systems has increased considerably since the eighties and nineties. As one of their most demanding applications we can mention shortest paths search. Several studies about shortest path search show the feasibility of using graphs for this purpose. Dijkstra's algorithm is one of the classic shortest path search algorithms. This algorithm is not well suited for shortest path search in large graphs. This is the reason why various modifications to Dijkstra's algorithm have been proposed by several authors using heuristics to reduce the run time of shortest path search. One of the most used heuristic algorithms is the A* algorithm, the main goal is to reduce the run time by reducing the search space. This article proposes a modification of Dijkstra's shortest path search algorithm in reduced graphs. It shows that the cost of the path found in this work, is equal to the cost of the path found using Dijkstra's algorithm in the original graph. The results of finding the shortest path, applying the proposed algorithm, Dijkstra's algorithm and A* algorithm, are compared. This comparison shows that, by applying the approach proposed, it is possible to obtain the optimal path in a similar or even in less time than when using heuristic algorithms.

Study of Chromatic parameters of Line, Total, Middle graphs and Graph operators of Bipartite graph

Science.gov (United States)

Nagarathinam, R.; Parvathi, N.

2018-04-01

Chromatic parameters have been explored on the basis of graph coloring process in which a couple of adjacent nodes receives different colors. But the Grundy and b-coloring executes maximum colors under certain restrictions. In this paper, Chromatic, b-chromatic and Grundy number of some graph operators of bipartite graph has been investigat

URANOS: User-Guided Rewriting for Plugin-Enabled ANdroid ApplicatiOn Security

OpenAIRE

Schreckling , Daniel; Huber , Stephan; Höhne , Focke; Posegga , Joachim

2013-01-01

Part 2: Mobile Security; International audience; URANOS is an Android application which uses syntactical static analysis to determine in which component of an Android application a permission is required. This work describes how the detection and analysis of widely distributed and security critical ad-ware plugins is achieved. We show, how users can trigger bytecode rewriting to (de)activate selected or redundant permissions in Android applications without sacrificing functionality. The paper...

Particle transport in breathing quantum graph

International Nuclear Information System (INIS)

Matrasulov, D.U.; Yusupov, J.R.; Sabirov, K.K.; Sobirov, Z.A.

2012-01-01

Full text: Particle transport in nanoscale networks and discrete structures is of fundamental and practical importance. Usually such systems are modeled by so-called quantum graphs, the systems attracting much attention in physics and mathematics during past two decades [1-5]. During last two decades quantum graphs found numerous applications in modeling different discrete structures and networks in nanoscale and mesoscopic physics (e.g., see reviews [1-3]). Despite considerable progress made in the study of particle dynamics most of the problems deal with unperturbed case and the case of time-dependent perturbation has not yet be explored. In this work we treat particle dynamics for quantum star graph with time-dependent bonds. In particular, we consider harmonically breathing quantum star graphs, the cases of monotonically contracting and expanding graphs. The latter can be solved exactly analytically. Edge boundaries are considered to be time-dependent, while branching point is assumed to be fixed. Quantum dynamics of a particle in such graphs is studied by solving Schrodinger equation with time-dependent boundary conditions given on a star graph. Time-dependence of the average kinetic energy is analyzed. Space-time evolution of the Gaussian wave packet is treated for harmonically breathing star graph. It is found that for certain frequencies energy is a periodic function of time, while for others it can be non-monotonically growing function of time. Such a feature can be caused by possible synchronization of the particles motion and the motions of the moving edges of graph bonds. (authors) References: [1] Tsampikos Kottos and Uzy Smilansky, Ann. Phys., 76, 274 (1999). [2] Sven Gnutzmann and Uzy Smilansky, Adv. Phys. 55, 527 (2006). [3] S. GnutzmannJ.P. Keating, F. Piotet, Ann. Phys., 325, 2595 (2010). [4] P.Exner, P.Seba, P.Stovicek, J. Phys. A: Math. Gen. 21, 4009 (1988). [5] J. Boman, P. Kurasov, Adv. Appl. Math., 35, 58 (2005)

Concept of rewritable organic ferroelectric random access memory in two lateral transistors-in-one cell architecture

International Nuclear Information System (INIS)

Kim, Min-Hoi; Lee, Gyu Jeong; Keum, Chang-Min; Lee, Sin-Doo

2014-01-01

We propose a concept of rewritable ferroelectric random access memory (RAM) with two lateral organic transistors-in-one cell architecture. Lateral integration of a paraelectric organic field-effect transistor (OFET), being a selection transistor, and a ferroelectric OFET as a memory transistor is realized using a paraelectric depolarizing layer (PDL) which is patterned on a ferroelectric insulator by transfer-printing. For the selection transistor, the key roles of the PDL are to reduce the dipolar strength and the surface roughness of the gate insulator, leading to the low memory on–off ratio and the high switching on–off current ratio. A new driving scheme preventing the crosstalk between adjacent memory cells is also demonstrated for the rewritable operation of the ferroelectric RAM. (paper)

Methodology of system design in electrical engineering with Bond Graph: application on a railway traction system; Methodologie de conception systemique en genie electrique a l'aide de l'outil Bond Graph: application a une chaine de traction ferroviaire

Energy Technology Data Exchange (ETDEWEB)

Gandanegara, G.

2003-11-15

In Electrical Engineering, the global analysis of systems is difficult because of their heterogeneity and their multi-domain nature. Nevertheless, this system approach is essential because it underlines couplings between elements of different physical fields. To facilitate this analysis, the unified formalism Bond Graph is used. This modeling method illustrates the energetic transfers in the system. Moreover, this methodology offers interesting solutions in terms of system analysis. Two simplification methods have been investigated and compared, i.e. the Singular Perturbations Method (SPM), based on the dynamic analysis of elements, and the Model Order Reduction Algorithm (MORA), based on the energetic activity. By these methods, a simplified bond graph model can be obtained for a given frequency range. The stability analysis by the root locus method and the Lyapunov's second method have been examined and applied with the Bond Graph formalism support. An industrial railway traction system is considered as the case study in the application of these different analysis techniques. (author)

Benchmarking Measures of Network Controllability on Canonical Graph Models

Science.gov (United States)

Wu-Yan, Elena; Betzel, Richard F.; Tang, Evelyn; Gu, Shi; Pasqualetti, Fabio; Bassett, Danielle S.

2018-03-01

The control of networked dynamical systems opens the possibility for new discoveries and therapies in systems biology and neuroscience. Recent theoretical advances provide candidate mechanisms by which a system can be driven from one pre-specified state to another, and computational approaches provide tools to test those mechanisms in real-world systems. Despite already having been applied to study network systems in biology and neuroscience, the practical performance of these tools and associated measures on simple networks with pre-specified structure has yet to be assessed. Here, we study the behavior of four control metrics (global, average, modal, and boundary controllability) on eight canonical graphs (including Erdős-Rényi, regular, small-world, random geometric, Barábasi-Albert preferential attachment, and several modular networks) with different edge weighting schemes (Gaussian, power-law, and two nonparametric distributions from brain networks, as examples of real-world systems). We observe that differences in global controllability across graph models are more salient when edge weight distributions are heavy-tailed as opposed to normal. In contrast, differences in average, modal, and boundary controllability across graph models (as well as across nodes in the graph) are more salient when edge weight distributions are less heavy-tailed. Across graph models and edge weighting schemes, average and modal controllability are negatively correlated with one another across nodes; yet, across graph instances, the relation between average and modal controllability can be positive, negative, or nonsignificant. Collectively, these findings demonstrate that controllability statistics (and their relations) differ across graphs with different topologies and that these differences can be muted or accentuated by differences in the edge weight distributions. More generally, our numerical studies motivate future analytical efforts to better understand the mathematical

A heterogeneous graph-based recommendation simulator

Energy Technology Data Exchange (ETDEWEB)

Yeonchan, Ahn [Seoul National University; Sungchan, Park [Seoul National University; Lee, Matt Sangkeun [ORNL; Sang-goo, Lee [Seoul National University

2013-01-01

Heterogeneous graph-based recommendation frameworks have flexibility in that they can incorporate various recommendation algorithms and various kinds of information to produce better results. In this demonstration, we present a heterogeneous graph-based recommendation simulator which enables participants to experience the flexibility of a heterogeneous graph-based recommendation method. With our system, participants can simulate various recommendation semantics by expressing the semantics via meaningful paths like User Movie User Movie. The simulator then returns the recommendation results on the fly based on the user-customized semantics using a fast Monte Carlo algorithm.

The One Universal Graph — a free and open graph database

International Nuclear Information System (INIS)

Ng, Liang S.; Champion, Corbin

2016-01-01

Recent developments in graph database mostly are huge projects involving big organizations, big operations and big capital, as the name Big Data attests. We proposed the concept of One Universal Graph (OUG) which states that all observable and known objects and concepts (physical, conceptual or digitally represented) can be connected with only one single graph; furthermore the OUG can be implemented with a very simple text file format with free software, capable of being executed on Android or smaller devices. As such the One Universal Graph Data Exchange (GOUDEX) modules can potentially be installed on hundreds of millions of Android devices and Intel compatible computers shipped annually. Coupled with its open nature and ability to connect to existing leading search engines and databases currently in operation, GOUDEX has the potential to become the largest and a better interface for users and programmers to interact with the data on the Internet. With a Web User Interface for users to use and program in native Linux environment, Free Crowdware implemented in GOUDEX can help inexperienced users learn programming with better organized documentation for free software, and is able to manage programmer's contribution down to a single line of code or a single variable in software projects. It can become the first practically realizable “Internet brain” on which a global artificial intelligence system can be implemented. Being practically free and open, One Universal Graph can have significant applications in robotics, artificial intelligence as well as social networks. (paper)

Incremental Frequent Subgraph Mining on Large Evolving Graphs

KAUST Repository

Abdelhamid, Ehab

2017-08-22

Frequent subgraph mining is a core graph operation used in many domains, such as graph data management and knowledge exploration, bioinformatics and security. Most existing techniques target static graphs. However, modern applications, such as social networks, utilize large evolving graphs. Mining these graphs using existing techniques is infeasible, due to the high computational cost. In this paper, we propose IncGM+, a fast incremental approach for continuous frequent subgraph mining problem on a single large evolving graph. We adapt the notion of “fringe” to the graph context, that is the set of subgraphs on the border between frequent and infrequent subgraphs. IncGM+ maintains fringe subgraphs and exploits them to prune the search space. To boost the efficiency, we propose an efficient index structure to maintain selected embeddings with minimal memory overhead. These embeddings are utilized to avoid redundant expensive subgraph isomorphism operations. Moreover, the proposed system supports batch updates. Using large real-world graphs, we experimentally verify that IncGM+ outperforms existing methods by up to three orders of magnitude, scales to much larger graphs and consumes less memory.

Decentralized formation of random regular graphs for robust multi-agent networks

KAUST Repository

Yazicioglu, A. Yasin; Egerstedt, Magnus; Shamma, Jeff S.

2014-01-01

systems. One family of robust graphs is the random regular graphs. In this paper, we present a locally applicable reconfiguration scheme to build random regular graphs through self-organization. For any connected initial graph, the proposed scheme

Analysis of the dynamics of the indicators for daily graphs for consumption of electricity of the USSR energy system

Energy Technology Data Exchange (ETDEWEB)

Nekrasov, A M; Lazarenko, T V; Zlatopol' skiy, A N

1982-01-01

The dynamics for the indicators of daily graphs of consumption of electricity in the USSR is the result of interaction of a large number of different-directed factors. Among them in recent years relatively greater influence has come from a change in the structure of consumers of each unified energy system and especially the USSR energy system with the unified energy systems with inclusion in it of large unified energy systems, whose time is shifted on time zones, and intensification of electrical bonds between the unified energy systems. The factor of expansion of the USSR energy system on the territory of the country because of the inclusion of new unified energy systems resulted in condensation of the daily graphs for consumption of electricity of the USSR energy system: increase in the coefficient of filling the daily graphs, their peak and semipeak parts, as well as coefficient of minimum consumption. Taking into consideration the program for further development of the country presented in the main trends for economic and social development of the USSR for 1981-1985 and for the period up to the year 1990, for the current and the near five-year plan, one can expect preservation of the revealed trends for dynamics of the indicators of the daily graphs for electricity consumption of the USSR energy system.

Domain configurations in dislocations embedded hexagonal manganite systems: From the view of graph theory

Science.gov (United States)

Cheng, Shaobo; Zhang, Dong; Deng, Shiqing; Li, Xing; Li, Jun; Tan, Guotai; Zhu, Yimei; Zhu, Jing

2018-04-01

Topological defects and their interactions often arouse multiple types of emerging phenomena from edge states in Skyrmions to disclination pairs in liquid crystals. In hexagonal manganites, partial edge dislocations, a prototype topological defect, are ubiquitous and they significantly alter the topologically protected domains and their behaviors. Herein, combining electron microscopy experiment and graph theory analysis, we report a systematic study of the connections and configurations of domains in this dislocation embedded system. Rules for domain arrangement are established. The dividing line between domains, which can be attributed by the strain field of dislocations, is accurately described by a genus model from a higher dimension in the graph theory. Our results open a door for the understanding of domain patterns in topologically protected multiferroic systems.

Optical generation of matter qubit graph states

International Nuclear Information System (INIS)

Benjamin, S C; Eisert, J; Stace, T M

2005-01-01

We present a scheme for rapidly entangling matter qubits in order to create graph states for one-way quantum computing. The qubits can be simple three-level systems in separate cavities. Coupling involves only local fields and a static (unswitched) linear optics network. Fusion of graph-state sections occurs with, in principle, zero probability of damaging the nascent graph state. We avoid the finite thresholds of other schemes by operating on two entangled pairs, so that each generates exactly one photon. We do not require the relatively slow single qubit local flips to be applied during the growth phase: growth of the graph state can then become a purely optical process. The scheme naturally generates graph states with vertices of high degree and so is easily able to construct minimal graph states, with consequent resource savings. The most efficient approach will be to create new graph-state edges even as qubits elsewhere are measured, in a 'just in time' approach. An error analysis indicates that the scheme is relatively robust against imperfections in the apparatus

Mutual proximity graphs for improved reachability in music recommendation.

Science.gov (United States)

Flexer, Arthur; Stevens, Jeff

2018-01-01

This paper is concerned with the impact of hubness, a general problem of machine learning in high-dimensional spaces, on a real-world music recommendation system based on visualisation of a k-nearest neighbour (knn) graph. Due to a problem of measuring distances in high dimensions, hub objects are recommended over and over again while anti-hubs are nonexistent in recommendation lists, resulting in poor reachability of the music catalogue. We present mutual proximity graphs, which are an alternative to knn and mutual knn graphs, and are able to avoid hub vertices having abnormally high connectivity. We show that mutual proximity graphs yield much better graph connectivity resulting in improved reachability compared to knn graphs, mutual knn graphs and mutual knn graphs enhanced with minimum spanning trees, while simultaneously reducing the negative effects of hubness.

Application of Bipolar Fuzzy Sets in Graph Structures

Directory of Open Access Journals (Sweden)

Muhammad Akram

2016-01-01

Full Text Available A graph structure is a useful tool in solving the combinatorial problems in different areas of computer science and computational intelligence systems. In this paper, we apply the concept of bipolar fuzzy sets to graph structures. We introduce certain notions, including bipolar fuzzy graph structure (BFGS, strong bipolar fuzzy graph structure, bipolar fuzzy Ni-cycle, bipolar fuzzy Ni-tree, bipolar fuzzy Ni-cut vertex, and bipolar fuzzy Ni-bridge, and illustrate these notions by several examples. We study ϕ-complement, self-complement, strong self-complement, and totally strong self-complement in bipolar fuzzy graph structures, and we investigate some of their interesting properties.

Centrosymmetric Graphs And A Lower Bound For Graph Energy Of Fullerenes

Directory of Open Access Journals (Sweden)

Katona Gyula Y.

2014-11-01

Full Text Available The energy of a molecular graph G is defined as the summation of the absolute values of the eigenvalues of adjacency matrix of a graph G. In this paper, an infinite class of fullerene graphs with 10n vertices, n ≥ 2, is considered. By proving centrosymmetricity of the adjacency matrix of these fullerene graphs, a lower bound for its energy is given. Our method is general and can be extended to other class of fullerene graphs.

RNA graph partitioning for the discovery of RNA modularity: a novel application of graph partition algorithm to biology.

Directory of Open Access Journals (Sweden)

Namhee Kim

Full Text Available Graph representations have been widely used to analyze and design various economic, social, military, political, and biological networks. In systems biology, networks of cells and organs are useful for understanding disease and medical treatments and, in structural biology, structures of molecules can be described, including RNA structures. In our RNA-As-Graphs (RAG framework, we represent RNA structures as tree graphs by translating unpaired regions into vertices and helices into edges. Here we explore the modularity of RNA structures by applying graph partitioning known in graph theory to divide an RNA graph into subgraphs. To our knowledge, this is the first application of graph partitioning to biology, and the results suggest a systematic approach for modular design in general. The graph partitioning algorithms utilize mathematical properties of the Laplacian eigenvector (µ2 corresponding to the second eigenvalues (λ2 associated with the topology matrix defining the graph: λ2 describes the overall topology, and the sum of µ2's components is zero. The three types of algorithms, termed median, sign, and gap cuts, divide a graph by determining nodes of cut by median, zero, and largest gap of µ2's components, respectively. We apply these algorithms to 45 graphs corresponding to all solved RNA structures up through 11 vertices (∼ 220 nucleotides. While we observe that the median cut divides a graph into two similar-sized subgraphs, the sign and gap cuts partition a graph into two topologically-distinct subgraphs. We find that the gap cut produces the best biologically-relevant partitioning for RNA because it divides RNAs at less stable connections while maintaining junctions intact. The iterative gap cuts suggest basic modules and assembly protocols to design large RNA structures. Our graph substructuring thus suggests a systematic approach to explore the modularity of biological networks. In our applications to RNA structures, subgraphs

Graphs and Homomorphisms

CERN Document Server

Hell, Pavol

2004-01-01

This is a book about graph homomorphisms. Graph theory is now an established discipline but the study of graph homomorphisms has only recently begun to gain wide acceptance and interest. The subject gives a useful perspective in areas such as graph reconstruction, products, fractional and circular colourings, and has applications in complexity theory, artificial intelligence, telecommunication, and, most recently, statistical physics.Based on the authors' lecture notes for graduate courses, this book can be used as a textbook for a second course in graph theory at 4th year or master's level an

Partitioning a call graph

NARCIS (Netherlands)

Bisseling, R.H.; Byrka, J.; Cerav-Erbas, S.; Gvozdenovic, N.; Lorenz, M.; Pendavingh, R.A.; Reeves, C.; Röger, M.; Verhoeven, A.; Berg, van den J.B.; Bhulai, S.; Hulshof, J.; Koole, G.; Quant, C.; Williams, J.F.

2006-01-01

Splitting a large software system into smaller and more manageable units has become an important problem for many organizations. The basic structure of a software system is given by a directed graph with vertices representing the programs of the system and arcs representing calls from one program to

Optimal perturbations for nonlinear systems using graph-based optimal transport

Science.gov (United States)

Grover, Piyush; Elamvazhuthi, Karthik

2018-06-01

We formulate and solve a class of finite-time transport and mixing problems in the set-oriented framework. The aim is to obtain optimal discrete-time perturbations in nonlinear dynamical systems to transport a specified initial measure on the phase space to a final measure in finite time. The measure is propagated under system dynamics in between the perturbations via the associated transfer operator. Each perturbation is described by a deterministic map in the measure space that implements a version of Monge-Kantorovich optimal transport with quadratic cost. Hence, the optimal solution minimizes a sum of quadratic costs on phase space transport due to the perturbations applied at specified times. The action of the transport map is approximated by a continuous pseudo-time flow on a graph, resulting in a tractable convex optimization problem. This problem is solved via state-of-the-art solvers to global optimality. We apply this algorithm to a problem of transport between measures supported on two disjoint almost-invariant sets in a chaotic fluid system, and to a finite-time optimal mixing problem by choosing the final measure to be uniform. In both cases, the optimal perturbations are found to exploit the phase space structures, such as lobe dynamics, leading to efficient global transport. As the time-horizon of the problem is increased, the optimal perturbations become increasingly localized. Hence, by combining the transfer operator approach with ideas from the theory of optimal mass transportation, we obtain a discrete-time graph-based algorithm for optimal transport and mixing in nonlinear systems.

Decomposing Oriented Graphs into Six Locally Irregular Oriented Graphs

DEFF Research Database (Denmark)

Bensmail, Julien; Renault, Gabriel

2016-01-01

An undirected graph G is locally irregular if every two of its adjacent vertices have distinct degrees. We say that G is decomposable into k locally irregular graphs if there exists a partition E1∪E2∪⋯∪Ek of the edge set E(G) such that each Ei induces a locally irregular graph. It was recently co...

Non-heuristic reduction of the graph in graph-cut optimization

International Nuclear Information System (INIS)

Malgouyres, François; Lermé, Nicolas

2012-01-01

During the last ten years, graph cuts had a growing impact in shape optimization. In particular, they are commonly used in applications of shape optimization such as image processing, computer vision and computer graphics. Their success is due to their ability to efficiently solve (apparently) difficult shape optimization problems which typically involve the perimeter of the shape. Nevertheless, solving problems with a large number of variables remains computationally expensive and requires a high memory usage since underlying graphs sometimes involve billion of nodes and even more edges. Several strategies have been proposed in the literature to improve graph-cuts in this regards. In this paper, we give a formal statement which expresses that a simple and local test performed on every node before its construction permits to avoid the construction of useless nodes for the graphs typically encountered in image processing and vision. A useless node is such that the value of the maximum flow in the graph does not change when removing the node from the graph. Such a test therefore permits to limit the construction of the graph to a band of useful nodes surrounding the final cut.

Graph embedding with rich information through heterogeneous graph

KAUST Repository

Sun, Guolei

2017-01-01

Graph embedding, aiming to learn low-dimensional representations for nodes in graphs, has attracted increasing attention due to its critical application including node classification, link prediction and clustering in social network analysis. Most

Semantic content-based recommendations using semantic graphs.

Science.gov (United States)

Guo, Weisen; Kraines, Steven B

2010-01-01

Recommender systems (RSs) can be useful for suggesting items that might be of interest to specific users. Most existing content-based recommendation (CBR) systems are designed to recommend items based on text content, and the items in these systems are usually described with keywords. However, similarity evaluations based on keywords suffer from the ambiguity of natural languages. We present a semantic CBR method that uses Semantic Web technologies to recommend items that are more similar semantically with the items that the user prefers. We use semantic graphs to represent the items and we calculate the similarity scores for each pair of semantic graphs using an inverse graph frequency algorithm. The items having higher similarity scores to the items that are known to be preferred by the user are recommended.

Two-colorable graph states with maximal Schmidt measure

International Nuclear Information System (INIS)

Severini, Simone

2006-01-01

The Schmidt measure was introduced by Eisert and Briegel for quantifying the degree of entanglement of multipartite quantum systems [J. Eisert, H.-J. Briegel, Phys. Rev. A 64 (2001) 22306]. For two-colorable graph states, the Schmidt measure is related to the spectrum of the associated graph. We observe that almost all two-colorable graph states have maximal Schmidt measure and we construct specific examples. By making appeal to a result of Ehrenfeucht et al. [A. Ehrenfeucht, T. Harju, G. Rozenberg, Discrete Math. 278 (2004) 45], we point out that the graph operations called local complementation and switching form a transitive group acting on the set of all graph states of a given dimension

Solved and unsolved problems of chemical graph theory

International Nuclear Information System (INIS)

Trinajstic, N.; Klein, D.J.; Randic, M.

1986-01-01

The development of several novel graph theoretical concepts and their applications in different branches of chemistry are reviewed. After a few introductory remarks they follow with an outline of selected important graph theoretical invariants, introducing some new results and indicating some open problems. They continue with discussing the problem of graph characterization and construction of graphs of chemical interest, with a particular emphasis on large systems. Finally they consider various problems and difficulties associated with special subgraphs, including subgraphs representing Kekule valence structures. The paper ends with a brief review of structure-property and structure-activity correlations, the topic which is one of prime motivations for application of graph theory to chemistry

AN EFFECTIVE RECOMMENDATIONS BY DIFFUSION ALGORITHM FOR WEB GRAPH MINING

Directory of Open Access Journals (Sweden)

S. Vasukipriya

2013-04-01

Full Text Available The information on the World Wide Web grows in an explosive rate. Societies are relying more on the Web for their miscellaneous needs of information. Recommendation systems are active information filtering systems that attempt to present the information items like movies, music, images, books recommendations, tags recommendations, query suggestions, etc., to the users. Various kinds of data bases are used for the recommendations; fundamentally these data bases can be molded in the form of many types of graphs. Aiming at provided that a general framework on effective DR (Recommendations by Diffusion algorithm for web graphs mining. First introduce a novel graph diffusion model based on heat diffusion. This method can be applied to both undirected graphs and directed graphs. Then it shows how to convert different Web data sources into correct graphs in our models.

"If you thought this story sour, sweeten it with your own telling" - a feminist poetics of rewriting in Susan Price's Ghost dance

Directory of Open Access Journals (Sweden)

Sanna Lehtonen

2010-01-01

Full Text Available The attempts to challenge conventional gendered discourses in children's fantasy have often resulted in feminist rewritings of earlier stories. Ghost dance (1994 by the English author Susan Price is a novel that reflects a specific feminist poetics of rewriting: metafictional passages highlight the constructedness of the narrative and at the end readers are invited to tell their own versions of the story. Moreover, the rewriting freely combines and recontextualises elements from different source texts and reformulates them to create a narrative that challenges conventional discourses of gender. While this poetics has an appeal from a feminist perspective, the play with cross-cultural intertexts and gender becomes more complex when the novel is examined in a postcolonialist framework in relation to ethnicity and the issue of cultural appropriation. Ghost dance is situated in a setting that has a real-world equivalent (Russia, involves characters that are identified with names of real-world ethnic groups (Lapps (Sámi, Russian, and mixes elements from Russian wonder tales, Nordic mythology and an Ojibwe legend. The novel does not aim at historical accuracy in its representations nor is it a direct retelling of any of the pre-texts but combines motifs, themes, names, characters and settings freely from each source. In this textual melting pot, the protagonist Shingebiss is, on one level, a revision of the witch Baba Yaga, but also described as a Lappish shaman with an Ojibwe name. To rewrite gendered discourses, certain elements from the pretexts are chosen and others left out – the question is, then, what effects does this recontextualisation have on the representation of ethnicity? Or, are the feminist rewriting strategies actually a form of cultural appropriation?

Graphing trillions of triangles.

Science.gov (United States)

Burkhardt, Paul

2017-07-01

The increasing size of Big Data is often heralded but how data are transformed and represented is also profoundly important to knowledge discovery, and this is exemplified in Big Graph analytics. Much attention has been placed on the scale of the input graph but the product of a graph algorithm can be many times larger than the input. This is true for many graph problems, such as listing all triangles in a graph. Enabling scalable graph exploration for Big Graphs requires new approaches to algorithms, architectures, and visual analytics. A brief tutorial is given to aid the argument for thoughtful representation of data in the context of graph analysis. Then a new algebraic method to reduce the arithmetic operations in counting and listing triangles in graphs is introduced. Additionally, a scalable triangle listing algorithm in the MapReduce model will be presented followed by a description of the experiments with that algorithm that led to the current largest and fastest triangle listing benchmarks to date. Finally, a method for identifying triangles in new visual graph exploration technologies is proposed.

Distributed Cooperative Optimal Control for Multiagent Systems on Directed Graphs: An Inverse Optimal Approach.

Science.gov (United States)

Zhang, Huaguang; Feng, Tao; Yang, Guang-Hong; Liang, Hongjing

2015-07-01

In this paper, the inverse optimal approach is employed to design distributed consensus protocols that guarantee consensus and global optimality with respect to some quadratic performance indexes for identical linear systems on a directed graph. The inverse optimal theory is developed by introducing the notion of partial stability. As a result, the necessary and sufficient conditions for inverse optimality are proposed. By means of the developed inverse optimal theory, the necessary and sufficient conditions are established for globally optimal cooperative control problems on directed graphs. Basic optimal cooperative design procedures are given based on asymptotic properties of the resulting optimal distributed consensus protocols, and the multiagent systems can reach desired consensus performance (convergence rate and damping rate) asymptotically. Finally, two examples are given to illustrate the effectiveness of the proposed methods.

PERANCANGAN SISTEM PENJADWALAN PEMBELAJARAN MENGGUNAKAN GRAPH COLORING

Directory of Open Access Journals (Sweden)

Taufik Hidayatulloh

2016-03-01

Full Text Available Abstract - In learning scheduling problem often faced by schools in the new academic year. Sometimes collisions on the schedule was not found when the learning process has begun, so it is necessary to re-schedule on the schedule. And this resulted in the teaching and learning first weeks less to run well. Researchers previously have used various methods to solve the scheduling as Tabu search, Simulated Annealing, Network Flow, Graph Coloring. Graph Coloring (coloring of a graph is the simplest method and the experimental results indicate that the development of methods of scheduling Graph Coloring deliver results that meet an average of 93% across the specified constraints. At the time of split schedules that require extra energy at the start of learning did not experience a collision. With this system is expected to facilitate the allocation of space, teachers, lessons to avoid a collision. Keywords: Information Systems, Scheduling, graph coloring Abstraksi - Dalam masalah penjadwalan pembelajaran sering dihadapi sekolah pada tahun ajaran baru. Terkadang tabrakan pada jadwal itu baru ditemukan ketika proses belajar mengajar telah dimulai, sehingga perlu dilakukan penjadwalan ulang pada jadwal tersebut. Dan hal ini mengakibatkan kegiatan belajar mengajar pada minggu-minggu pertama kurang dapat berjalan dengan baik. Para peneliti sebelumnya telah menggunakan berbagai metode untuk memecahkan penjadwalan seperti Tabu search, Simulated Annealing, Network Flow, Graph Coloring. Graph Coloring (pewarnaan graf merupakan metode yang paling sederhana dan hasil percobaan menunjukkan bahwa pengembangan metode Graph Coloring memberikan hasil penjadwalan yang memenuhi rata-rata 93% seluruh constraints yang ditentukan. Pada saat membagi jadwal memerlukan energi ekstra agar pada saat di mulai pembelajaran tidak mengalami tabrakan. Dengan sistem ini diharapkan dapat mempermudah dalam mengalokasikan ruangan, guru, pelajaran agar tidak mengalami tabrakan. Kata

Adaptive Graph Convolutional Neural Networks

OpenAIRE

Li, Ruoyu; Wang, Sheng; Zhu, Feiyun; Huang, Junzhou

2018-01-01

Graph Convolutional Neural Networks (Graph CNNs) are generalizations of classical CNNs to handle graph data such as molecular data, point could and social networks. Current filters in graph CNNs are built for fixed and shared graph structure. However, for most real data, the graph structures varies in both size and connectivity. The paper proposes a generalized and flexible graph CNN taking data of arbitrary graph structure as input. In that way a task-driven adaptive graph is learned for eac...

Asymptote Misconception on Graphing Functions: Does Graphing Software Resolve It?

Directory of Open Access Journals (Sweden)

Mehmet Fatih Öçal

2017-01-01

Full Text Available Graphing function is an important issue in mathematics education due to its use in various areas of mathematics and its potential roles for students to enhance learning mathematics. The use of some graphing software assists students’ learning during graphing functions. However, the display of graphs of functions that students sketched by hand may be relatively different when compared to the correct forms sketched using graphing software. The possible misleading effects of this situation brought a discussion of a misconception (asymptote misconception on graphing functions. The purpose of this study is two- fold. First of all, this study investigated whether using graphing software (GeoGebra in this case helps students to determine and resolve this misconception in calculus classrooms. Second, the reasons for this misconception are sought. The multiple case study was utilized in this study. University students in two calculus classrooms who received instructions with (35 students or without GeoGebra assisted instructions (32 students were compared according to whether they fell into this misconception on graphing basic functions (1/x, lnx, ex. In addition, students were interviewed to reveal the reasons behind this misconception. Data were analyzed by means of descriptive and content analysis methods. The findings indicated that those who received GeoGebra assisted instruction were better in resolving it. In addition, the reasons behind this misconception were found to be teacher-based, exam-based and some other factors.

High Dimensional Spectral Graph Theory and Non-backtracking Random Walks on Graphs

Science.gov (United States)

Kempton, Mark

This thesis has two primary areas of focus. First we study connection graphs, which are weighted graphs in which each edge is associated with a d-dimensional rotation matrix for some fixed dimension d, in addition to a scalar weight. Second, we study non-backtracking random walks on graphs, which are random walks with the additional constraint that they cannot return to the immediately previous state at any given step. Our work in connection graphs is centered on the notion of consistency, that is, the product of rotations moving from one vertex to another is independent of the path taken, and a generalization called epsilon-consistency. We present higher dimensional versions of the combinatorial Laplacian matrix and normalized Laplacian matrix from spectral graph theory, and give results characterizing the consistency of a connection graph in terms of the spectra of these matrices. We generalize several tools from classical spectral graph theory, such as PageRank and effective resistance, to apply to connection graphs. We use these tools to give algorithms for sparsification, clustering, and noise reduction on connection graphs. In non-backtracking random walks, we address the question raised by Alon et. al. concerning how the mixing rate of a non-backtracking random walk to its stationary distribution compares to the mixing rate for an ordinary random walk. Alon et. al. address this question for regular graphs. We take a different approach, and use a generalization of Ihara's Theorem to give a new proof of Alon's result for regular graphs, and to extend the result to biregular graphs. Finally, we give a non-backtracking version of Polya's Random Walk Theorem for 2-dimensional grids.

On the sizes of expander graphs and minimum distances of graph codes

DEFF Research Database (Denmark)

Høholdt, Tom; Justesen, Jørn

2014-01-01

We give lower bounds for the minimum distances of graph codes based on expander graphs. The bounds depend only on the second eigenvalue of the graph and the parameters of the component codes. We also give an upper bound on the size of a degree regular graph with given second eigenvalue....

Similarity Measure of Graphs

Directory of Open Access Journals (Sweden)

Amine Labriji

2017-07-01

Full Text Available The topic of identifying the similarity of graphs was considered as highly recommended research field in the Web semantic, artificial intelligence, the shape recognition and information research. One of the fundamental problems of graph databases is finding similar graphs to a graph query. Existing approaches dealing with this problem are usually based on the nodes and arcs of the two graphs, regardless of parental semantic links. For instance, a common connection is not identified as being part of the similarity of two graphs in cases like two graphs without common concepts, the measure of similarity based on the union of two graphs, or the one based on the notion of maximum common sub-graph (SCM, or the distance of edition of graphs. This leads to an inadequate situation in the context of information research. To overcome this problem, we suggest a new measure of similarity between graphs, based on the similarity measure of Wu and Palmer. We have shown that this new measure satisfies the properties of a measure of similarities and we applied this new measure on examples. The results show that our measure provides a run time with a gain of time compared to existing approaches. In addition, we compared the relevance of the similarity values obtained, it appears that this new graphs measure is advantageous and  offers a contribution to solving the problem mentioned above.

Graph Cellular Automata with Relation-Based Neighbourhoods of Cells for Complex Systems Modelling: A Case of Traffic Simulation

Directory of Open Access Journals (Sweden)

Krzysztof Małecki

2017-12-01

Full Text Available A complex system is a set of mutually interacting elements for which it is possible to construct a mathematical model. This article focuses on the cellular automata theory and the graph theory in order to compare various types of cellular automata and to analyse applications of graph structures together with cellular automata. It proposes a graph cellular automaton with a variable configuration of cells and relation-based neighbourhoods (r–GCA. The developed mechanism enables modelling of phenomena found in complex systems (e.g., transport networks, urban logistics, social networks taking into account the interaction between the existing objects. As an implementation example, modelling of moving vehicles has been made and r–GCA was compared to the other cellular automata models simulating the road traffic and used in the computer simulation process.

Hierarchical organisation of causal graphs

International Nuclear Information System (INIS)

Dziopa, P.

1993-01-01

This paper deals with the design of a supervision system using a hierarchy of models formed by graphs, in which the variables are the nodes and the causal relations between the variables of the arcs. To obtain a representation of the variables evolutions which contains only the relevant features of their real evolutions, the causal relations are completed with qualitative transfer functions (QTFs) which produce roughly the behaviour of the classical transfer functions. Major improvements have been made in the building of the hierarchical organization. First, the basic variables of the uppermost level and the causal relations between them are chosen. The next graph is built by adding intermediary variables to the upper graph. When the undermost graph has been built, the transfer functions parameters corresponding to its causal relations are identified. The second task consists in the upwelling of the information from the undermost graph to the uppermost one. A fusion procedure of the causal relations has been designed to compute the QFTs relevant for each level. This procedure aims to reduce the number of parameters needed to represent an evolution at a high level of abstraction. These techniques have been applied to the hierarchical modelling of nuclear process. (authors). 8 refs., 12 figs

Spectra of Graphs

NARCIS (Netherlands)

Brouwer, A.E.; Haemers, W.H.

2012-01-01

This book gives an elementary treatment of the basic material about graph spectra, both for ordinary, and Laplace and Seidel spectra. The text progresses systematically, by covering standard topics before presenting some new material on trees, strongly regular graphs, two-graphs, association

Greenberger-Horne-Zeilinger paradoxes from qudit graph states.

Science.gov (United States)

Tang, Weidong; Yu, Sixia; Oh, C H

2013-03-08

One fascinating way of revealing quantum nonlocality is the all-versus-nothing test due to Greenberger, Horne, and Zeilinger (GHZ) known as the GHZ paradox. So far genuine multipartite and multilevel GHZ paradoxes are known to exist only in systems containing an odd number of particles. Here we shall construct GHZ paradoxes for an arbitrary number (greater than 3) of particles with the help of qudit graph states on a special kind of graphs, called GHZ graphs. Furthermore, based on the GHZ paradox arising from a GHZ graph, we derive a Bell inequality with two d-outcome observables for each observer, whose maximal violation attained by the corresponding graph state, and a Kochen-Specker inequality testing the quantum contextuality in a state-independent fashion.

Topological and Graph-Coloring Conditions on the Parameter-Independent Stability of Second-Order Networked Systems

NARCIS (Netherlands)

Koerts, Filip; Bürger, Mathias; van der Schaft, Abraham; De Persis, Claudio

2017-01-01

In this paper, we study parameter-independent stability in qualitatively heterogeneous passive networked systems containing damped and undamped nodes. Given the graph topology and a set of damped nodes, we ask if output consensus is achieved for all system parameter values. For given parameter

On middle cube graphs

Directory of Open Access Journals (Sweden)

C. Dalfo

2015-10-01

Full Text Available We study a family of graphs related to the $n$-cube. The middle cube graph of parameter k is the subgraph of $Q_{2k-1}$ induced by the set of vertices whose binary representation has either $k-1$ or $k$ number of ones. The middle cube graphs can be obtained from the well-known odd graphs by doubling their vertex set. Here we study some of the properties of the middle cube graphs in the light of the theory of distance-regular graphs. In particular, we completely determine their spectra (eigenvalues and their multiplicities, and associated eigenvectors.

Graph visualization (Invited talk)

NARCIS (Netherlands)

Wijk, van J.J.; Kreveld, van M.J.; Speckmann, B.

2012-01-01

Black and white node link diagrams are the classic method to depict graphs, but these often fall short to give insight in large graphs or when attributes of nodes and edges play an important role. Graph visualization aims obtaining insight in such graphs using interactive graphical representations.

Adventures in graph theory

CERN Document Server

Joyner, W David

2017-01-01

This textbook acts as a pathway to higher mathematics by seeking and illuminating the connections between graph theory and diverse fields of mathematics, such as calculus on manifolds, group theory, algebraic curves, Fourier analysis, cryptography and other areas of combinatorics. An overview of graph theory definitions and polynomial invariants for graphs prepares the reader for the subsequent dive into the applications of graph theory. To pique the reader’s interest in areas of possible exploration, recent results in mathematics appear throughout the book, accompanied with examples of related graphs, how they arise, and what their valuable uses are. The consequences of graph theory covered by the authors are complicated and far-reaching, so topics are always exhibited in a user-friendly manner with copious graphs, exercises, and Sage code for the computation of equations. Samples of the book’s source code can be found at github.com/springer-math/adventures-in-graph-theory. The text is geared towards ad...

Counting the number of Feynman graphs in QCD

Science.gov (United States)

Kaneko, T.

2018-05-01

Information about the number of Feynman graphs for a given physical process in a given field theory is especially useful for confirming the result of a Feynman graph generator used in an automatic system of perturbative calculations. A method of counting the number of Feynman graphs with weight of symmetry factor was established based on zero-dimensional field theory, and was used in scalar theories and QED. In this article this method is generalized to more complicated models by direct calculation of generating functions on a computer algebra system. This method is applied to QCD with and without counter terms, where many higher order are being calculated automatically.

Decentralized formation of random regular graphs for robust multi-agent networks

KAUST Repository

Yazicioglu, A. Yasin

2014-12-15

Multi-agent networks are often modeled via interaction graphs, where the nodes represent the agents and the edges denote direct interactions between the corresponding agents. Interaction graphs have significant impact on the robustness of networked systems. One family of robust graphs is the random regular graphs. In this paper, we present a locally applicable reconfiguration scheme to build random regular graphs through self-organization. For any connected initial graph, the proposed scheme maintains connectivity and the average degree while minimizing the degree differences and randomizing the links. As such, if the average degree of the initial graph is an integer, then connected regular graphs are realized uniformly at random as time goes to infinity.

Distance-regular graphs

NARCIS (Netherlands)

van Dam, Edwin R.; Koolen, Jack H.; Tanaka, Hajime

2016-01-01

This is a survey of distance-regular graphs. We present an introduction to distance-regular graphs for the reader who is unfamiliar with the subject, and then give an overview of some developments in the area of distance-regular graphs since the monograph 'BCN'[Brouwer, A.E., Cohen, A.M., Neumaier,

Graph-based linear scaling electronic structure theory

Energy Technology Data Exchange (ETDEWEB)

Niklasson, Anders M. N., E-mail: amn@lanl.gov; Negre, Christian F. A.; Cawkwell, Marc J.; Swart, Pieter J.; Germann, Timothy C.; Bock, Nicolas [Theoretical Division, Los Alamos National Laboratory, Los Alamos, New Mexico 87545 (United States); Mniszewski, Susan M.; Mohd-Yusof, Jamal; Wall, Michael E.; Djidjev, Hristo [Computer, Computational, and Statistical Sciences Division, Los Alamos National Laboratory, Los Alamos, New Mexico 87545 (United States); Rubensson, Emanuel H. [Division of Scientific Computing, Department of Information Technology, Uppsala University, Box 337, SE-751 05 Uppsala (Sweden)

2016-06-21

We show how graph theory can be combined with quantum theory to calculate the electronic structure of large complex systems. The graph formalism is general and applicable to a broad range of electronic structure methods and materials, including challenging systems such as biomolecules. The methodology combines well-controlled accuracy, low computational cost, and natural low-communication parallelism. This combination addresses substantial shortcomings of linear scaling electronic structure theory, in particular with respect to quantum-based molecular dynamics simulations.

Generating hierarchial scale-free graphs from fractals

Energy Technology Data Exchange (ETDEWEB)

Komjathy, Julia, E-mail: komyju@math.bme.hu [Department of Stochastics, Institute of Mathematics, Technical University of Budapest, H-1529 P.O. Box 91 (Hungary); Simon, Karoly, E-mail: simonk@math.bme.hu [Department of Stochastics, Institute of Mathematics, Technical University of Budapest, H-1529 P.O. Box 91 (Hungary)

2011-08-15

Highlights: > We generate deterministic scale-free networks using graph-directed self similar IFS. > Our model exhibits similar clustering, power law decay properties to real networks. > The average length of shortest path and the diameter of the graph are determined. > Using this model, we generate random graphs with prescribed power law exponent. - Abstract: Motivated by the hierarchial network model of E. Ravasz, A.-L. Barabasi, and T. Vicsek, we introduce deterministic scale-free networks derived from a graph directed self-similar fractal {Lambda}. With rigorous mathematical results we verify that our model captures some of the most important features of many real networks: the scale-free and the high clustering properties. We also prove that the diameter is the logarithm of the size of the system. We point out a connection between the power law exponent of the degree distribution and some intrinsic geometric measure theoretical properties of the underlying fractal. Using our (deterministic) fractal {Lambda} we generate random graph sequence sharing similar properties.

On the strong metric dimension of generalized butterfly graph, starbarbell graph, and {C}_{m}\\odot {P}_{n} graph

Science.gov (United States)

Yunia Mayasari, Ratih; Atmojo Kusmayadi, Tri

2018-04-01

Let G be a connected graph with vertex set V(G) and edge set E(G). For every pair of vertices u,v\\in V(G), the interval I[u, v] between u and v to be the collection of all vertices that belong to some shortest u ‑ v path. A vertex s\\in V(G) strongly resolves two vertices u and v if u belongs to a shortest v ‑ s path or v belongs to a shortest u ‑ s path. A vertex set S of G is a strong resolving set of G if every two distinct vertices of G are strongly resolved by some vertex of S. The strong metric basis of G is a strong resolving set with minimal cardinality. The strong metric dimension sdim(G) of a graph G is defined as the cardinality of strong metric basis. In this paper we determine the strong metric dimension of a generalized butterfly graph, starbarbell graph, and {C}mȯ {P}n graph. We obtain the strong metric dimension of generalized butterfly graph is sdim(BFn ) = 2n ‑ 2. The strong metric dimension of starbarbell graph is sdim(S{B}{m1,{m}2,\\ldots,{m}n})={\\sum }i=1n({m}i-1)-1. The strong metric dimension of {C}mȯ {P}n graph are sdim({C}mȯ {P}n)=2m-1 for m > 3 and n = 2, and sdim({C}mȯ {P}n)=2m-2 for m > 3 and n > 2.

Subgraph detection using graph signals

KAUST Repository

Chepuri, Sundeep Prabhakar

2017-03-06

In this paper we develop statistical detection theory for graph signals. In particular, given two graphs, namely, a background graph that represents an usual activity and an alternative graph that represents some unusual activity, we are interested in answering the following question: To which of the two graphs does the observed graph signal fit the best? To begin with, we assume both the graphs are known, and derive an optimal Neyman-Pearson detector. Next, we derive a suboptimal detector for the case when the alternative graph is not known. The developed theory is illustrated with numerical experiments.

Subgraph detection using graph signals

KAUST Repository

Chepuri, Sundeep Prabhakar; Leus, Geert

2017-01-01

In this paper we develop statistical detection theory for graph signals. In particular, given two graphs, namely, a background graph that represents an usual activity and an alternative graph that represents some unusual activity, we are interested in answering the following question: To which of the two graphs does the observed graph signal fit the best? To begin with, we assume both the graphs are known, and derive an optimal Neyman-Pearson detector. Next, we derive a suboptimal detector for the case when the alternative graph is not known. The developed theory is illustrated with numerical experiments.

Graph spectrum

NARCIS (Netherlands)

Brouwer, A.E.; Haemers, W.H.; Brouwer, A.E.; Haemers, W.H.

2012-01-01

This chapter presents some simple results on graph spectra.We assume the reader is familiar with elementary linear algebra and graph theory. Throughout, J will denote the all-1 matrix, and 1 is the all-1 vector.

GSMNet: A Hierarchical Graph Model for Moving Objects in Networks

Directory of Open Access Journals (Sweden)

Hengcai Zhang

2017-03-01

Full Text Available Existing data models for moving objects in networks are often limited by flexibly controlling the granularity of representing networks and the cost of location updates and do not encompass semantic information, such as traffic states, traffic restrictions and social relationships. In this paper, we aim to fill the gap of traditional network-constrained models and propose a hierarchical graph model called the Geo-Social-Moving model for moving objects in Networks (GSMNet that adopts four graph structures, RouteGraph, SegmentGraph, ObjectGraph and MoveGraph, to represent the underlying networks, trajectories and semantic information in an integrated manner. The bulk of user-defined data types and corresponding operators is proposed to handle moving objects and answer a new class of queries supporting three kinds of conditions: spatial, temporal and semantic information. Then, we develop a prototype system with the native graph database system Neo4Jto implement the proposed GSMNet model. In the experiment, we conduct the performance evaluation using simulated trajectories generated from the BerlinMOD (Berlin Moving Objects Database benchmark and compare with the mature MOD system Secondo. The results of 17 benchmark queries demonstrate that our proposed GSMNet model has strong potential to reduce time-consuming table join operations an d shows remarkable advantages with regard to representing semantic information and controlling the cost of location updates.

Simplicial complexes of graphs

CERN Document Server

Jonsson, Jakob

2008-01-01

A graph complex is a finite family of graphs closed under deletion of edges. Graph complexes show up naturally in many different areas of mathematics, including commutative algebra, geometry, and knot theory. Identifying each graph with its edge set, one may view a graph complex as a simplicial complex and hence interpret it as a geometric object. This volume examines topological properties of graph complexes, focusing on homotopy type and homology. Many of the proofs are based on Robin Forman's discrete version of Morse theory. As a byproduct, this volume also provides a loosely defined toolbox for attacking problems in topological combinatorics via discrete Morse theory. In terms of simplicity and power, arguably the most efficient tool is Forman's divide and conquer approach via decision trees; it is successfully applied to a large number of graph and digraph complexes.

The STAPL Parallel Graph Library

KAUST Repository

Harshvardhan,

2013-01-01

This paper describes the stapl Parallel Graph Library, a high-level framework that abstracts the user from data-distribution and parallelism details and allows them to concentrate on parallel graph algorithm development. It includes a customizable distributed graph container and a collection of commonly used parallel graph algorithms. The library introduces pGraph pViews that separate algorithm design from the container implementation. It supports three graph processing algorithmic paradigms, level-synchronous, asynchronous and coarse-grained, and provides common graph algorithms based on them. Experimental results demonstrate improved scalability in performance and data size over existing graph libraries on more than 16,000 cores and on internet-scale graphs containing over 16 billion vertices and 250 billion edges. © Springer-Verlag Berlin Heidelberg 2013.

Generating a Tolerogenic Cell Therapy Knowledge Graph from Literature

Directory of Open Access Journals (Sweden)

Andre Lamurias

2017-11-01

Full Text Available Tolerogenic cell therapies provide an alternative to conventional immunosuppressive treatments of autoimmune disease and address, among other goals, the rejection of organ or stem cell transplants. Since various methodologies can be followed to develop tolerogenic therapies, it is important to be aware and up to date on all available studies that may be relevant to their improvement. Recently, knowledge graphs have been proposed to link various sources of information, using text mining techniques. Knowledge graphs facilitate the automatic retrieval of information about the topics represented in the graph. The objective of this work was to automatically generate a knowledge graph for tolerogenic cell therapy from biomedical literature. We developed a system, ICRel, based on machine learning to extract relations between cells and cytokines from abstracts. Our system retrieves related documents from PubMed, annotates each abstract with cell and cytokine named entities, generates the possible combinations of cell–cytokine pairs cooccurring in the same sentence, and identifies meaningful relations between cells and cytokines. The extracted relations were used to generate a knowledge graph, where each edge was supported by one or more documents. We obtained a graph containing 647 cell–cytokine relations, based on 3,264 abstracts. The modules of ICRel were evaluated with cross-validation and manual evaluation of the relations extracted. The relation extraction module obtained an F-measure of 0.789 in a reference database, while the manual evaluation obtained an accuracy of 0.615. Even though the knowledge graph is based on information that was already published in other articles about immunology, the system we present is more efficient than the laborious task of manually reading all the literature to find indirect or implicit relations. The ICRel graph will help experts identify implicit relations that may not be evident in published studies.

Topic Model for Graph Mining.

Science.gov (United States)

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.

Modern graph theory

CERN Document Server

Bollobás, Béla

1998-01-01

The time has now come when graph theory should be part of the education of every serious student of mathematics and computer science, both for its own sake and to enhance the appreciation of mathematics as a whole. This book is an in-depth account of graph theory, written with such a student in mind; it reflects the current state of the subject and emphasizes connections with other branches of pure mathematics. The volume grew out of the author's earlier book, Graph Theory -- An Introductory Course, but its length is well over twice that of its predecessor, allowing it to reveal many exciting new developments in the subject. Recognizing that graph theory is one of several courses competing for the attention of a student, the book contains extensive descriptive passages designed to convey the flavor of the subject and to arouse interest. In addition to a modern treatment of the classical areas of graph theory such as coloring, matching, extremal theory, and algebraic graph theory, the book presents a detailed ...

A graph edit dictionary for correcting errors in roof topology graphs reconstructed from point clouds

Science.gov (United States)

Xiong, B.; Oude Elberink, S.; Vosselman, G.

2014-07-01

In the task of 3D building model reconstruction from point clouds we face the problem of recovering a roof topology graph in the presence of noise, small roof faces and low point densities. Errors in roof topology graphs will seriously affect the final modelling results. The aim of this research is to automatically correct these errors. We define the graph correction as a graph-to-graph problem, similar to the spelling correction problem (also called the string-to-string problem). The graph correction is more complex than string correction, as the graphs are 2D while strings are only 1D. We design a strategy based on a dictionary of graph edit operations to automatically identify and correct the errors in the input graph. For each type of error the graph edit dictionary stores a representative erroneous subgraph as well as the corrected version. As an erroneous roof topology graph may contain several errors, a heuristic search is applied to find the optimum sequence of graph edits to correct the errors one by one. The graph edit dictionary can be expanded to include entries needed to cope with errors that were previously not encountered. Experiments show that the dictionary with only fifteen entries already properly corrects one quarter of erroneous graphs in about 4500 buildings, and even half of the erroneous graphs in one test area, achieving as high as a 95% acceptance rate of the reconstructed models.

Building Scalable Knowledge Graphs for Earth Science

Science.gov (United States)

Ramachandran, R.; Maskey, M.; Gatlin, P. N.; Zhang, J.; Duan, X.; Bugbee, K.; Christopher, S. A.; Miller, J. J.

2017-12-01

Estimates indicate that the world's information will grow by 800% in the next five years. In any given field, a single researcher or a team of researchers cannot keep up with this rate of knowledge expansion without the help of cognitive systems. Cognitive computing, defined as the use of information technology to augment human cognition, can help tackle large systemic problems. Knowledge graphs, one of the foundational components of cognitive systems, link key entities in a specific domain with other entities via relationships. Researchers could mine these graphs to make probabilistic recommendations and to infer new knowledge. At this point, however, there is a dearth of tools to generate scalable Knowledge graphs using existing corpus of scientific literature for Earth science research. Our project is currently developing an end-to-end automated methodology for incrementally constructing Knowledge graphs for Earth Science. Semantic Entity Recognition (SER) is one of the key steps in this methodology. SER for Earth Science uses external resources (including metadata catalogs and controlled vocabulary) as references to guide entity extraction and recognition (i.e., labeling) from unstructured text, in order to build a large training set to seed the subsequent auto-learning component in our algorithm. Results from several SER experiments will be presented as well as lessons learned.

Functions and graphs

CERN Document Server

Gelfand, I M; Shnol, E E

1969-01-01

The second in a series of systematic studies by a celebrated mathematician I. M. Gelfand and colleagues, this volume presents students with a well-illustrated sequence of problems and exercises designed to illuminate the properties of functions and graphs. Since readers do not have the benefit of a blackboard on which a teacher constructs a graph, the authors abandoned the customary use of diagrams in which only the final form of the graph appears; instead, the book's margins feature step-by-step diagrams for the complete construction of each graph. The first part of the book employs simple fu

Loose Graph Simulations

DEFF Research Database (Denmark)

Mansutti, Alessio; Miculan, Marino; Peressotti, Marco

2017-01-01

We introduce loose graph simulations (LGS), a new notion about labelled graphs which subsumes in an intuitive and natural way subgraph isomorphism (SGI), regular language pattern matching (RLPM) and graph simulation (GS). Being a unification of all these notions, LGS allows us to express directly...... also problems which are “mixed” instances of previous ones, and hence which would not fit easily in any of them. After the definition and some examples, we show that the problem of finding loose graph simulations is NP-complete, we provide formal translation of SGI, RLPM, and GS into LGSs, and we give...

Partition function expansion on region graphs and message-passing equations

International Nuclear Information System (INIS)

Zhou, Haijun; Wang, Chuang; Xiao, Jing-Qing; Bi, Zedong

2011-01-01

Disordered and frustrated graphical systems are ubiquitous in physics, biology, and information science. For models on complete graphs or random graphs, deep understanding has been achieved through the mean-field replica and cavity methods. But finite-dimensional 'real' systems remain very challenging because of the abundance of short loops and strong local correlations. A statistical mechanics theory is constructed in this paper for finite-dimensional models based on the mathematical framework of the partition function expansion and the concept of region graphs. Rigorous expressions for the free energy and grand free energy are derived. Message-passing equations on the region graph, such as belief propagation and survey propagation, are also derived rigorously. (letter)

A new intrusion prevention model using planning knowledge graph

Science.gov (United States)

Cai, Zengyu; Feng, Yuan; Liu, Shuru; Gan, Yong

2013-03-01

Intelligent plan is a very important research in artificial intelligence, which has applied in network security. This paper proposes a new intrusion prevention model base on planning knowledge graph and discuses the system architecture and characteristics of this model. The Intrusion Prevention based on plan knowledge graph is completed by plan recognition based on planning knowledge graph, and the Intrusion response strategies and actions are completed by the hierarchical task network (HTN) planner in this paper. Intrusion prevention system has the advantages of intelligent planning, which has the advantage of the knowledge-sharing, the response focused, learning autonomy and protective ability.

Autoregressive Moving Average Graph Filtering

OpenAIRE

Isufi, Elvin; Loukas, Andreas; Simonetto, Andrea; Leus, Geert

2016-01-01

One of the cornerstones of the field of signal processing on graphs are graph filters, direct analogues of classical filters, but intended for signals defined on graphs. This work brings forth new insights on the distributed graph filtering problem. We design a family of autoregressive moving average (ARMA) recursions, which (i) are able to approximate any desired graph frequency response, and (ii) give exact solutions for tasks such as graph signal denoising and interpolation. The design phi...

On cyclic orthogonal double covers of circulant graphs by special infinite graphs

Directory of Open Access Journals (Sweden)

R. El-Shanawany

2017-12-01

Full Text Available In this article, a technique to construct cyclic orthogonal double covers (CODCs of regular circulant graphs by certain infinite graph classes such as complete bipartite and tripartite graphs and disjoint union of butterfly and K1,2n−10 is introduced.

Reaction factoring and bipartite update graphs accelerate the Gillespie Algorithm for large-scale biochemical systems.

Science.gov (United States)

Indurkhya, Sagar; Beal, Jacob

2010-01-06

ODE simulations of chemical systems perform poorly when some of the species have extremely low concentrations. Stochastic simulation methods, which can handle this case, have been impractical for large systems due to computational complexity. We observe, however, that when modeling complex biological systems: (1) a small number of reactions tend to occur a disproportionately large percentage of the time, and (2) a small number of species tend to participate in a disproportionately large percentage of reactions. We exploit these properties in LOLCAT Method, a new implementation of the Gillespie Algorithm. First, factoring reaction propensities allows many propensities dependent on a single species to be updated in a single operation. Second, representing dependencies between reactions with a bipartite graph of reactions and species requires only storage for reactions, rather than the required for a graph that includes only reactions. Together, these improvements allow our implementation of LOLCAT Method to execute orders of magnitude faster than currently existing Gillespie Algorithm variants when simulating several yeast MAPK cascade models.

Good grief: Lord of the Flies as a post-war rewriting of salvation history

Directory of Open Access Journals (Sweden)

M. van Vuuren

2004-07-01

Full Text Available Golding’s Lord of the Flies, first published in 1954, reflects a bleak sense of post-war pessimism. But with undue attention focused on its portrayal of original sin and the problem of evil, readings have often remained reductive. In this article it is argued that the novel’s symbolic narrative is polysemic and, when it is read as anagogic myth, may be seen to span Judaeo-Christian Heilsgeschichte or salvation history, rewriting its chapters of creation, Fall, the problem of evil, the failure of law, the hope of salvation, the mission of a messianic figure, and – in the clearest departure from the Biblical narrative – an ambiguous representation of his return. This study examines the novel’s often paradoxical symbolism using Frye’s phases of anagogic myth, with its poles of apocalyptic and demonic imagery. It traces the relation of symbols to their counterparts in Biblical narratives, drawn in particular from the symbolic writings of the origin and end of humanity, to elucidate Golding’s bleak but certainly not hopeless rewriting of the salvation story for a post-faith readership.

Isotropic covariance functions on graphs and their edges

DEFF Research Database (Denmark)

Anderes, E.; Møller, Jesper; Rasmussen, Jakob Gulddahl

We develop parametric classes of covariance functions on linear networks and their extension to graphs with Euclidean edges, i.e., graphs with edges viewed as line segments or more general sets with a coordinate system allowing us to consider points on the graph which are vertices or points...... on an edge. Our covariance functions are defined on the vertices and edge points of these graphs and are isotropic in the sense that they depend only on the geodesic distance or on a new metric called the resistance metric (which extends the classical resistance metric developed in electrical network theory...... functions in the spatial statistics literature (the power exponential, Matérn, generalized Cauchy, and Dagum classes) are shown to be valid with respect to the resistance metric for any graph with Euclidean edges, whilst they are only valid with respect to the geodesic metric in more special cases....

BootGraph: probabilistic fiber tractography using bootstrap algorithms and graph theory.

Science.gov (United States)

Vorburger, Robert S; Reischauer, Carolin; Boesiger, Peter

2013-02-01

Bootstrap methods have recently been introduced to diffusion-weighted magnetic resonance imaging to estimate the measurement uncertainty of ensuing diffusion parameters directly from the acquired data without the necessity to assume a noise model. These methods have been previously combined with deterministic streamline tractography algorithms to allow for the assessment of connection probabilities in the human brain. Thereby, the local noise induced disturbance in the diffusion data is accumulated additively due to the incremental progression of streamline tractography algorithms. Graph based approaches have been proposed to overcome this drawback of streamline techniques. For this reason, the bootstrap method is in the present work incorporated into a graph setup to derive a new probabilistic fiber tractography method, called BootGraph. The acquired data set is thereby converted into a weighted, undirected graph by defining a vertex in each voxel and edges between adjacent vertices. By means of the cone of uncertainty, which is derived using the wild bootstrap, a weight is thereafter assigned to each edge. Two path finding algorithms are subsequently applied to derive connection probabilities. While the first algorithm is based on the shortest path approach, the second algorithm takes all existing paths between two vertices into consideration. Tracking results are compared to an established algorithm based on the bootstrap method in combination with streamline fiber tractography and to another graph based algorithm. The BootGraph shows a very good performance in crossing situations with respect to false negatives and permits incorporating additional constraints, such as a curvature threshold. By inheriting the advantages of the bootstrap method and graph theory, the BootGraph method provides a computationally efficient and flexible probabilistic tractography setup to compute connection probability maps and virtual fiber pathways without the drawbacks of

Computing paths and cycles in biological interaction graphs

Directory of Open Access Journals (Sweden)

von Kamp Axel

2009-06-01

Full Text Available Abstract Background Interaction graphs (signed directed graphs provide an important qualitative modeling approach for Systems Biology. They enable the analysis of causal relationships in cellular networks and can even be useful for predicting qualitative aspects of systems dynamics. Fundamental issues in the analysis of interaction graphs are the enumeration of paths and cycles (feedback loops and the calculation of shortest positive/negative paths. These computational problems have been discussed only to a minor extent in the context of Systems Biology and in particular the shortest signed paths problem requires algorithmic developments. Results We first review algorithms for the enumeration of paths and cycles and show that these algorithms are superior to a recently proposed enumeration approach based on elementary-modes computation. The main part of this work deals with the computation of shortest positive/negative paths, an NP-complete problem for which only very few algorithms are described in the literature. We propose extensions and several new algorithm variants for computing either exact results or approximations. Benchmarks with various concrete biological networks show that exact results can sometimes be obtained in networks with several hundred nodes. A class of even larger graphs can still be treated exactly by a new algorithm combining exhaustive and simple search strategies. For graphs, where the computation of exact solutions becomes time-consuming or infeasible, we devised an approximative algorithm with polynomial complexity. Strikingly, in realistic networks (where a comparison with exact results was possible this algorithm delivered results that are very close or equal to the exact values. This phenomenon can probably be attributed to the particular topology of cellular signaling and regulatory networks which contain a relatively low number of negative feedback loops. Conclusion The calculation of shortest positive

Graph theory and the Virasoro master equation

International Nuclear Information System (INIS)

Obers, N.A.J.

1991-01-01

A brief history of affine Lie algebra, the Virasoro algebra and its culmination in the Virasoro master equation is given. By studying ansaetze of the master equation, the author obtains exact solutions and gains insight in the structure of large slices of affine-Virasoro space. He finds an isomorphism between the constructions in the ansatz SO(n) diag , which is a set of unitary, generically irrational affine-Virasoro constructions on SO(n), and the unlabeled graphs of order n. On the one hand, the conformal constructions, are classified by the graphs, while, conversely, a group-theoretic and conformal field-theoretic identification is obtained for every graph of graph theory. He also defines a class of magic Lie group bases in which the Virasoro master equation admits a simple metric ansatz {g metric }, whose structure is visible in the high-level expansion. When a magic basis is real on compact g, the corresponding g metric is a large system of unitary, generically irrational conformal field theories. Examples in this class include the graph-theory ansatz SO(n) diag in the Cartesian basis of SO(n), and the ansatz SU(n) metric in the Pauli-like basis of SU(n). Finally, he defines the 'sine-area graphs' of SU(n), which label the conformal field theories of SU(n) metric , and he notes that, in similar fashion, each magic basis of g defines a generalized graph theory on g which labels the conformal field theories of g metric

A novel conductivity mechanism of highly disordered carbon systems based on an investigation of graph zeta function

Science.gov (United States)

Matsutani, Shigeki; Sato, Iwao

2017-09-01

In the previous report (Matsutani and Suzuki, 2000 [21]), by proposing the mechanism under which electric conductivity is caused by the activational hopping conduction with the Wigner surmise of the level statistics, the temperature-dependent of electronic conductivity of a highly disordered carbon system was evaluated including apparent metal-insulator transition. Since the system consists of small pieces of graphite, it was assumed that the reason why the level statistics appears is due to the behavior of the quantum chaos in each granular graphite. In this article, we revise the assumption and show another origin of the Wigner surmise, which is more natural for the carbon system based on a recent investigation of graph zeta function in graph theory. Our method can be applied to the statistical treatment of the electronic properties of the randomized molecular system in general.

Motifs in triadic random graphs based on Steiner triple systems

Science.gov (United States)

Winkler, Marco; Reichardt, Jörg

2013-08-01

Conventionally, pairwise relationships between nodes are considered to be the fundamental building blocks of complex networks. However, over the last decade, the overabundance of certain subnetwork patterns, i.e., the so-called motifs, has attracted much attention. It has been hypothesized that these motifs, instead of links, serve as the building blocks of network structures. Although the relation between a network's topology and the general properties of the system, such as its function, its robustness against perturbations, or its efficiency in spreading information, is the central theme of network science, there is still a lack of sound generative models needed for testing the functional role of subgraph motifs. Our work aims to overcome this limitation. We employ the framework of exponential random graph models (ERGMs) to define models based on triadic substructures. The fact that only a small portion of triads can actually be set independently poses a challenge for the formulation of such models. To overcome this obstacle, we use Steiner triple systems (STSs). These are partitions of sets of nodes into pair-disjoint triads, which thus can be specified independently. Combining the concepts of ERGMs and STSs, we suggest generative models capable of generating ensembles of networks with nontrivial triadic Z-score profiles. Further, we discover inevitable correlations between the abundance of triad patterns, which occur solely for statistical reasons and need to be taken into account when discussing the functional implications of motif statistics. Moreover, we calculate the degree distributions of our triadic random graphs analytically.

Algebraic Methods for Counting Euclidean Embeddings of Rigid Graphs

NARCIS (Netherlands)

I.Z. Emiris; E.P. Tsigaridas; A. Varvitsiotis (Antonios); E.R. Gasner

2009-01-01

textabstract The study of (minimally) rigid graphs is motivated by numerous applications, mostly in robotics and bioinformatics. A major open problem concerns the number of embeddings of such graphs, up to rigid motions, in Euclidean space. We capture embeddability by polynomial systems

Equipackable graphs

DEFF Research Database (Denmark)

Vestergaard, Preben Dahl; Hartnell, Bert L.

2006-01-01

There are many results dealing with the problem of decomposing a fixed graph into isomorphic subgraphs. There has also been work on characterizing graphs with the property that one can delete the edges of a number of edge disjoint copies of the subgraph and, regardless of how that is done, the gr...

Khovanov homology of graph-links

Energy Technology Data Exchange (ETDEWEB)

Nikonov, Igor M [M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Moscow (Russian Federation)

2012-08-31

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

A Graph Summarization Algorithm Based on RFID Logistics

Science.gov (United States)

Sun, Yan; Hu, Kongfa; Lu, Zhipeng; Zhao, Li; Chen, Ling

Radio Frequency Identification (RFID) applications are set to play an essential role in object tracking and supply chain management systems. The volume of data generated by a typical RFID application will be enormous as each item will generate a complete history of all the individual locations that it occupied at every point in time. The movement trails of such RFID data form gigantic commodity flowgraph representing the locations and durations of the path stages traversed by each item. In this paper, we use graph to construct a warehouse of RFID commodity flows, and introduce a database-style operation to summarize graphs, which produces a summary graph by grouping nodes based on user-selected node attributes, further allows users to control the hierarchy of summaries. It can cut down the size of graphs, and provide convenience for users to study just on the shrunk graph which they interested. Through extensive experiments, we demonstrate the effectiveness and efficiency of the proposed method.

Visibility graph analysis on heartbeat dynamics of meditation training

Science.gov (United States)

Jiang, Sen; Bian, Chunhua; Ning, Xinbao; Ma, Qianli D. Y.

2013-06-01

We apply the visibility graph analysis to human heartbeat dynamics by constructing the complex networks of heartbeat interval time series and investigating the statistical properties of the network before and during chi and yoga meditation. The experiment results show that visibility graph analysis can reveal the dynamical changes caused by meditation training manifested as regular heartbeat, which is closely related to the adjustment of autonomous neural system, and visibility graph analysis is effective to evaluate the effect of meditation.

GCPSO in cooperation with graph theory to distribution network reconfiguration for energy saving

International Nuclear Information System (INIS)

Assadian, Mehdi; Farsangi, Malihe M.; Nezamabadi-pour, Hossein

2010-01-01

Network reconfiguration for loss reduction in distribution system is an important way to save energy. This paper investigates the ability of guaranteed convergence particle swarm optimization (GCPSO) and particle swarm optimization (PSO) in cooperation with graph theory for network reconfiguration to reduce the power loss and enhancement of voltage profile of distribution systems. Numerical results of three distribution systems are presented which illustrate the feasibility of the proposed method by GCPSO and PSO using the graph theory. To validate the obtained results, genetic algorithm (GA) using graph theory is also applied and is compared with the proposed GCPSO and PSO using graph theory.

Generalized connectivity of graphs

CERN Document Server

Li, Xueliang

2016-01-01

Noteworthy results, proof techniques, open problems and conjectures in generalized (edge-) connectivity are discussed in this book. Both theoretical and practical analyses for generalized (edge-) connectivity of graphs are provided. Topics covered in this book include: generalized (edge-) connectivity of graph classes, algorithms, computational complexity, sharp bounds, Nordhaus-Gaddum-type results, maximum generalized local connectivity, extremal problems, random graphs, multigraphs, relations with the Steiner tree packing problem and generalizations of connectivity. This book enables graduate students to understand and master a segment of graph theory and combinatorial optimization. Researchers in graph theory, combinatorics, combinatorial optimization, probability, computer science, discrete algorithms, complexity analysis, network design, and the information transferring models will find this book useful in their studies.

On two energy-like invariants of line graphs and related graph operations

Directory of Open Access Journals (Sweden)

Xiaodan Chen

2016-02-01

Full Text Available Abstract For a simple graph G of order n, let μ 1 ≥ μ 2 ≥ ⋯ ≥ μ n = 0 $\\mu_{1}\\geq\\mu_{2}\\geq\\cdots\\geq\\mu_{n}=0$ be its Laplacian eigenvalues, and let q 1 ≥ q 2 ≥ ⋯ ≥ q n ≥ 0 $q_{1}\\geq q_{2}\\geq\\cdots\\geq q_{n}\\geq0$ be its signless Laplacian eigenvalues. The Laplacian-energy-like invariant and incidence energy of G are defined as, respectively, LEL ( G = ∑ i = 1 n − 1 μ i and IE ( G = ∑ i = 1 n q i . $$\\mathit{LEL}(G=\\sum_{i=1}^{n-1}\\sqrt{ \\mu_{i}} \\quad\\mbox{and}\\quad \\mathit {IE}(G=\\sum_{i=1}^{n} \\sqrt{q_{i}}. $$ In this paper, we present some new upper and lower bounds on LEL and IE of line graph, subdivision graph, para-line graph and total graph of a regular graph, some of which improve previously known results. The main tools we use here are the Cauchy-Schwarz inequality and the Ozeki inequality.

Rewriting the Metabolic Blueprint: Advances in Pathway Diversification in Microorganisms

Directory of Open Access Journals (Sweden)

Gazi Sakir Hossain

2018-02-01

Full Text Available Living organisms have evolved over millions of years to fine tune their metabolism to create efficient pathways for producing metabolites necessary for their survival. Advancement in the field of synthetic biology has enabled the exploitation of these metabolic pathways for the production of desired compounds by creating microbial cell factories through metabolic engineering, thus providing sustainable routes to obtain value-added chemicals. Following the past success in metabolic engineering, there is increasing interest in diversifying natural metabolic pathways to construct non-natural biosynthesis routes, thereby creating possibilities for producing novel valuable compounds that are non-natural or without elucidated biosynthesis pathways. Thus, the range of chemicals that can be produced by biological systems can be expanded to meet the demands of industries for compounds such as plastic precursors and new antibiotics, most of which can only be obtained through chemical synthesis currently. Herein, we review and discuss novel strategies that have been developed to rewrite natural metabolic blueprints in a bid to broaden the chemical repertoire achievable in microorganisms. This review aims to provide insights on recent approaches taken to open new avenues for achieving biochemical production that are beyond currently available inventions.

Rewriting the Metabolic Blueprint: Advances in Pathway Diversification in Microorganisms.

Science.gov (United States)

Hossain, Gazi Sakir; Nadarajan, Saravanan Prabhu; Zhang, Lei; Ng, Tee-Kheang; Foo, Jee Loon; Ling, Hua; Choi, Won Jae; Chang, Matthew Wook

2018-01-01

Living organisms have evolved over millions of years to fine tune their metabolism to create efficient pathways for producing metabolites necessary for their survival. Advancement in the field of synthetic biology has enabled the exploitation of these metabolic pathways for the production of desired compounds by creating microbial cell factories through metabolic engineering, thus providing sustainable routes to obtain value-added chemicals. Following the past success in metabolic engineering, there is increasing interest in diversifying natural metabolic pathways to construct non-natural biosynthesis routes, thereby creating possibilities for producing novel valuable compounds that are non-natural or without elucidated biosynthesis pathways. Thus, the range of chemicals that can be produced by biological systems can be expanded to meet the demands of industries for compounds such as plastic precursors and new antibiotics, most of which can only be obtained through chemical synthesis currently. Herein, we review and discuss novel strategies that have been developed to rewrite natural metabolic blueprints in a bid to broaden the chemical repertoire achievable in microorganisms. This review aims to provide insights on recent approaches taken to open new avenues for achieving biochemical production that are beyond currently available inventions.

Price Competition on Graphs

OpenAIRE

Adriaan R. Soetevent

2010-01-01

This paper extends Hotelling's model of price competition with quadratic transportation costs from a line to graphs. I propose an algorithm to calculate firm-level demand for any given graph, conditional on prices and firm locations. One feature of graph models of price competition is that spatial discontinuities in firm-level demand may occur. I show that the existence result of D'Aspremont et al. (1979) does not extend to simple star graphs. I conjecture that this non-existence result holds...

Price Competition on Graphs

OpenAIRE

Pim Heijnen; Adriaan Soetevent

2014-01-01

This paper extends Hotelling's model of price competition with quadratic transportation costs from a line to graphs. We derive an algorithm to calculate firm-level demand for any given graph, conditional on prices and firm locations. These graph models of price competition may lead to spatial discontinuities in firm-level demand. We show that the existence result of D'Aspremont et al. (1979) does not extend to simple star graphs and conjecture that this non-existence result holds more general...

Skew-adjacency matrices of graphs

NARCIS (Netherlands)

Cavers, M.; Cioaba, S.M.; Fallat, S.; Gregory, D.A.; Haemers, W.H.; Kirkland, S.J.; McDonald, J.J.; Tsatsomeros, M.

2012-01-01

The spectra of the skew-adjacency matrices of a graph are considered as a possible way to distinguish adjacency cospectral graphs. This leads to the following topics: graphs whose skew-adjacency matrices are all cospectral; relations between the matchings polynomial of a graph and the characteristic

Graph theory

CERN Document Server

Diestel, Reinhard

2017-01-01

This standard textbook of modern graph theory, now in its fifth edition, combines the authority of a classic with the engaging freshness of style that is the hallmark of active mathematics. It covers the core material of the subject with concise yet reliably complete proofs, while offering glimpses of more advanced methods in each field by one or two deeper results, again with proofs given in full detail. The book can be used as a reliable text for an introductory course, as a graduate text, and for self-study. From the reviews: “This outstanding book cannot be substituted with any other book on the present textbook market. It has every chance of becoming the standard textbook for graph theory.”Acta Scientiarum Mathematiciarum “Deep, clear, wonderful. This is a serious book about the heart of graph theory. It has depth and integrity. ”Persi Diaconis & Ron Graham, SIAM Review “The book has received a very enthusiastic reception, which it amply deserves. A masterly elucidation of modern graph theo...

Acyclicity in edge-colored graphs

DEFF Research Database (Denmark)

Gutin, Gregory; Jones, Mark; Sheng, Bin

2017-01-01

A walk W in edge-colored graphs is called properly colored (PC) if every pair of consecutive edges in W is of different color. We introduce and study five types of PC acyclicity in edge-colored graphs such that graphs of PC acyclicity of type i is a proper superset of graphs of acyclicity of type i......+1, i=1,2,3,4. The first three types are equivalent to the absence of PC cycles, PC closed trails, and PC closed walks, respectively. While graphs of types 1, 2 and 3 can be recognized in polynomial time, the problem of recognizing graphs of type 4 is, somewhat surprisingly, NP-hard even for 2-edge-colored...... graphs (i.e., when only two colors are used). The same problem with respect to type 5 is polynomial-time solvable for all edge-colored graphs. Using the five types, we investigate the border between intractability and tractability for the problems of finding the maximum number of internally vertex...

Graph Sampling for Covariance Estimation

KAUST Repository

Chepuri, Sundeep Prabhakar

2017-04-25

In this paper the focus is on subsampling as well as reconstructing the second-order statistics of signals residing on nodes of arbitrary undirected graphs. Second-order stationary graph signals may be obtained by graph filtering zero-mean white noise and they admit a well-defined power spectrum whose shape is determined by the frequency response of the graph filter. Estimating the graph power spectrum forms an important component of stationary graph signal processing and related inference tasks such as Wiener prediction or inpainting on graphs. The central result of this paper is that by sampling a significantly smaller subset of vertices and using simple least squares, we can reconstruct the second-order statistics of the graph signal from the subsampled observations, and more importantly, without any spectral priors. To this end, both a nonparametric approach as well as parametric approaches including moving average and autoregressive models for the graph power spectrum are considered. The results specialize for undirected circulant graphs in that the graph nodes leading to the best compression rates are given by the so-called minimal sparse rulers. A near-optimal greedy algorithm is developed to design the subsampling scheme for the non-parametric and the moving average models, whereas a particular subsampling scheme that allows linear estimation for the autoregressive model is proposed. Numerical experiments on synthetic as well as real datasets related to climatology and processing handwritten digits are provided to demonstrate the developed theory.

Price competition on graphs

NARCIS (Netherlands)

Soetevent, A.R.

2010-01-01

This paper extends Hotelling's model of price competition with quadratic transportation costs from a line to graphs. I propose an algorithm to calculate firm-level demand for any given graph, conditional on prices and firm locations. One feature of graph models of price competition is that spatial

MSGD: Scalable back-end for indoor magnetic field-based GraphSLAM

OpenAIRE

Gao, C; Harle, Robert Keith

2017-01-01

Simultaneous Localisation and Mapping (SLAM) systems that recover the trajectory of a robot or mobile device are characterised by a front-end and back-end. The front-end uses sensor observations to identify loop closures; the back-end optimises the estimated trajectory to be consistent with these closures. The GraphSLAM framework formulates the back-end problem as a graph-based optimisation on a pose graph. This paper describes a back-end system optimised for very dense sequence-based lo...

Graphing the order of the sexes: constructing, recalling, interpreting, and putting the self in gender difference graphs.

Science.gov (United States)

Hegarty, Peter; Lemieux, Anthony F; McQueen, Grant

2010-03-01

Graphs seem to connote facts more than words or tables do. Consequently, they seem unlikely places to spot implicit sexism at work. Yet, in 6 studies (N = 741), women and men constructed (Study 1) and recalled (Study 2) gender difference graphs with men's data first, and graphed powerful groups (Study 3) and individuals (Study 4) ahead of weaker ones. Participants who interpreted graph order as evidence of author "bias" inferred that the author graphed his or her own gender group first (Study 5). Women's, but not men's, preferences to graph men first were mitigated when participants graphed a difference between themselves and an opposite-sex friend prior to graphing gender differences (Study 6). Graph production and comprehension are affected by beliefs and suppositions about the groups represented in graphs to a greater degree than cognitive models of graph comprehension or realist models of scientific thinking have yet acknowledged.

Collective Rationality in Graph Aggregation

NARCIS (Netherlands)

Endriss, U.; Grandi, U.; Schaub, T.; Friedrich, G.; O'Sullivan, B.

2014-01-01

Suppose a number of agents each provide us with a directed graph over a common set of vertices. Graph aggregation is the problem of computing a single “collective” graph that best represents the information inherent in this profile of individual graphs. We consider this aggregation problem from the

Dist-Orc: A Rewriting-based Distributed Implementation of Orc with Formal Analysis

Directory of Open Access Journals (Sweden)

José Meseguer

2010-09-01

Full Text Available Orc is a theory of orchestration of services that allows structured programming of distributed and timed computations. Several formal semantics have been proposed for Orc, including a rewriting logic semantics developed by the authors. Orc also has a fully fledged implementation in Java with functional programming features. However, as with descriptions of most distributed languages, there exists a fairly substantial gap between Orc's formal semantics and its implementation, in that: (i programs in Orc are not easily deployable in a distributed implementation just by using Orc's formal semantics, and (ii they are not readily formally analyzable at the level of a distributed Orc implementation. In this work, we overcome problems (i and (ii for Orc. Specifically, we describe an implementation technique based on rewriting logic and Maude that narrows this gap considerably. The enabling feature of this technique is Maude's support for external objects through TCP sockets. We describe how sockets are used to implement Orc site calls and returns, and to provide real-time timing information to Orc expressions and sites. We then show how Orc programs in the resulting distributed implementation can be formally analyzed at a reasonable level of abstraction by defining an abstract model of time and the socket communication infrastructure, and discuss the assumptions under which the analysis can be deemed correct. Finally, the distributed implementation and the formal analysis methodology are illustrated with a case study.

Towards Scalable Graph Computation on Mobile Devices.

Science.gov (United States)

Chen, Yiqi; Lin, Zhiyuan; Pienta, Robert; Kahng, Minsuk; Chau, Duen Horng

2014-10-01

Mobile devices have become increasingly central to our everyday activities, due to their portability, multi-touch capabilities, and ever-improving computational power. Such attractive features have spurred research interest in leveraging mobile devices for computation. We explore a novel approach that aims to use a single mobile device to perform scalable graph computation on large graphs that do not fit in the device's limited main memory, opening up the possibility of performing on-device analysis of large datasets, without relying on the cloud. Based on the familiar memory mapping capability provided by today's mobile operating systems, our approach to scale up computation is powerful and intentionally kept simple to maximize its applicability across the iOS and Android platforms. Our experiments demonstrate that an iPad mini can perform fast computation on large real graphs with as many as 272 million edges (Google+ social graph), at a speed that is only a few times slower than a 13″ Macbook Pro. Through creating a real world iOS app with this technique, we demonstrate the strong potential application for scalable graph computation on a single mobile device using our approach.

Towards Scalable Graph Computation on Mobile Devices

Science.gov (United States)

Chen, Yiqi; Lin, Zhiyuan; Pienta, Robert; Kahng, Minsuk; Chau, Duen Horng

2015-01-01

Mobile devices have become increasingly central to our everyday activities, due to their portability, multi-touch capabilities, and ever-improving computational power. Such attractive features have spurred research interest in leveraging mobile devices for computation. We explore a novel approach that aims to use a single mobile device to perform scalable graph computation on large graphs that do not fit in the device's limited main memory, opening up the possibility of performing on-device analysis of large datasets, without relying on the cloud. Based on the familiar memory mapping capability provided by today's mobile operating systems, our approach to scale up computation is powerful and intentionally kept simple to maximize its applicability across the iOS and Android platforms. Our experiments demonstrate that an iPad mini can perform fast computation on large real graphs with as many as 272 million edges (Google+ social graph), at a speed that is only a few times slower than a 13″ Macbook Pro. Through creating a real world iOS app with this technique, we demonstrate the strong potential application for scalable graph computation on a single mobile device using our approach. PMID:25859564

Graph Theory. 1. Fragmentation of Structural Graphs

Directory of Open Access Journals (Sweden)

Lorentz JÄNTSCHI

2002-12-01

Full Text Available The investigation of structural graphs has many fields of applications in engineering, especially in applied sciences like as applied chemistry and physics, computer sciences and automation, electronics and telecommunication. The main subject of the paper is to express fragmentation criteria in graph using a new method of investigation: terminal paths. Using terminal paths are defined most of the fragmentation criteria that are in use in molecular topology, but the fields of applications are more generally than that, as I mentioned before. Graphical examples of fragmentation are given for every fragmentation criteria. Note that all fragmentation is made with a computer program that implements a routine for every criterion.[1] A web routine for tracing all terminal paths in graph can be found at the address: http://vl.academicdirect.ro/molecular_topology/tpaths/ [1] M. V. Diudea, I. Gutman, L. Jäntschi, Molecular Topology, Nova Science, Commack, New York, 2001, 2002.

On the classification of plane graphs representing structurally stable rational Newton flows

NARCIS (Netherlands)

Jongen, H.Th.; Jonker, P.; Twilt, F.

1991-01-01

We study certain plane graphs, called Newton graphs, representing a special class of dynamical systems which are closely related to Newton's iteration method for finding zeros of (rational) functions defined on the complex plane. These Newton graphs are defined in terms of nonvanishing angles

Dynamic MLD analysis with flow graphs

International Nuclear Information System (INIS)

Jenab, K.; Sarfaraz, A.; Dhillon, B.S.; Seyed Hosseini, S.M.

2012-01-01

Master Logic Diagram (MLD) depicts the interrelationships among the independent functions and dependent support functions. Using MLD, the manner in which all functions, sub-functions interact to achieve the overall system objective can be investigated. This paper reports a probabilistic model to analyze an MLD by translating the interrelationships to a graph model. The proposed model uses the flow-graph concept and Moment Generating Function (MGF) to analyze the dependency matrix representing the MLD with embedded self-healing function/sub-functions. The functions/sub-functions are featured by failure detection and recovery mechanisms. The newly developed model provides the probability of the system failure, and system mean and standard deviation time to failure in the MLD. An illustrative example is demonstrated to present the application of the model.

Introductory graph theory

CERN Document Server

Chartrand, Gary

1984-01-01

Graph theory is used today in the physical sciences, social sciences, computer science, and other areas. Introductory Graph Theory presents a nontechnical introduction to this exciting field in a clear, lively, and informative style. Author Gary Chartrand covers the important elementary topics of graph theory and its applications. In addition, he presents a large variety of proofs designed to strengthen mathematical techniques and offers challenging opportunities to have fun with mathematics. Ten major topics - profusely illustrated - include: Mathematical Models, Elementary Concepts of Grap

Exploiting graph kernels for high performance biomedical relation extraction.

Science.gov (United States)

Panyam, Nagesh C; Verspoor, Karin; Cohn, Trevor; Ramamohanarao, Kotagiri

2018-01-30

Relation extraction from biomedical publications is an important task in the area of semantic mining of text. Kernel methods for supervised relation extraction are often preferred over manual feature engineering methods, when classifying highly ordered structures such as trees and graphs obtained from syntactic parsing of a sentence. Tree kernels such as the Subset Tree Kernel and Partial Tree Kernel have been shown to be effective for classifying constituency parse trees and basic dependency parse graphs of a sentence. Graph kernels such as the All Path Graph kernel (APG) and Approximate Subgraph Matching (ASM) kernel have been shown to be suitable for classifying general graphs with cycles, such as the enhanced dependency parse graph of a sentence. In this work, we present a high performance Chemical-Induced Disease (CID) relation extraction system. We present a comparative study of kernel methods for the CID task and also extend our study to the Protein-Protein Interaction (PPI) extraction task, an important biomedical relation extraction task. We discuss novel modifications to the ASM kernel to boost its performance and a method to apply graph kernels for extracting relations expressed in multiple sentences. Our system for CID relation extraction attains an F-score of 60%, without using external knowledge sources or task specific heuristic or rules. In comparison, the state of the art Chemical-Disease Relation Extraction system achieves an F-score of 56% using an ensemble of multiple machine learning methods, which is then boosted to 61% with a rule based system employing task specific post processing rules. For the CID task, graph kernels outperform tree kernels substantially, and the best performance is obtained with APG kernel that attains an F-score of 60%, followed by the ASM kernel at 57%. The performance difference between the ASM and APG kernels for CID sentence level relation extraction is not significant. In our evaluation of ASM for the PPI task, ASM

Creating more effective graphs

CERN Document Server

Robbins, Naomi B

2012-01-01

A succinct and highly readable guide to creating effective graphs The right graph can be a powerful tool for communicating information, improving a presentation, or conveying your point in print. If your professional endeavors call for you to present data graphically, here's a book that can help you do it more effectively. Creating More Effective Graphs gives you the basic knowledge and techniques required to choose and create appropriate graphs for a broad range of applications. Using real-world examples everyone can relate to, the author draws on her years of experience in gr

Graph Compression by BFS

Directory of Open Access Journals (Sweden)

Alberto Apostolico

2009-08-01

Full Text Available The Web Graph is a large-scale graph that does not fit in main memory, so that lossless compression methods have been proposed for it. This paper introduces a compression scheme that combines efficient storage with fast retrieval for the information in a node. The scheme exploits the properties of the Web Graph without assuming an ordering of the URLs, so that it may be applied to more general graphs. Tests on some datasets of use achieve space savings of about 10% over existing methods.

Nonvolatile rewritable memory device based on solution-processable graphene/poly(3-hexylthiophene) nanocomposite

Energy Technology Data Exchange (ETDEWEB)

Zhang, Li, E-mail: lizhang9@zzu.edu.cn [School of Materials Science and Engineering, Zhengzhou University, Zhengzhou 450052 (China); Li, Ye; Shi, Jun [School of Materials Science and Engineering, Zhengzhou University, Zhengzhou 450052 (China); Shi, Gaoquan [Department of Chemistry, Tsinghua University, Beijing 100084 (China); Cao, Shaokui, E-mail: Caoshaokui@zzu.edu.cn [School of Materials Science and Engineering, Zhengzhou University, Zhengzhou 450052 (China)

2013-11-01

An electrically bistable device utilizing a nanocomposite of hexadecylamine-functionalized graphene oxide (HDAGO) with poly(3-hexylthiophene) (P3HT) is demonstrated. The device has an ITO/P3HT-HDAGO/Al sandwich structure, in which the composite film of P3HT-HDAGO was prepared by simple solution phase mixing of the exfoliated HDAGO monolayers with P3HT matrix and a spin-coating method. The memory device exhibits typical bistable electrical switching behavior and a nonvolatile rewritable memory effect, with a turn-on voltage of about 1.5 V and an ON/OFF-state current ratio of 10{sup 5}. Under ambient conditions, both the ON and OFF states are stable under a constant voltage stress or a continuous pulse voltage stress at a read voltage of 1 V. The conduction mechanism is deduced from the modeling of the nature of currents in both states, and the electrical switching behavior can be attributed to the electric-field-induced charge transfer between P3HT and HDAGO nanosheets. - Highlights: • Nonvolatile rewritable memory effect in P3HT–graphene composite is demonstrated. • The memory device was fabricated through a simple solution processing technique. • The device shows a remarkable electrical bistable behavior and excellent stability. • Memory mechanism is deduced from the modeling of the currents in both states.

Nonvolatile rewritable memory device based on solution-processable graphene/poly(3-hexylthiophene) nanocomposite

International Nuclear Information System (INIS)

Zhang, Li; Li, Ye; Shi, Jun; Shi, Gaoquan; Cao, Shaokui

2013-01-01

An electrically bistable device utilizing a nanocomposite of hexadecylamine-functionalized graphene oxide (HDAGO) with poly(3-hexylthiophene) (P3HT) is demonstrated. The device has an ITO/P3HT-HDAGO/Al sandwich structure, in which the composite film of P3HT-HDAGO was prepared by simple solution phase mixing of the exfoliated HDAGO monolayers with P3HT matrix and a spin-coating method. The memory device exhibits typical bistable electrical switching behavior and a nonvolatile rewritable memory effect, with a turn-on voltage of about 1.5 V and an ON/OFF-state current ratio of 10 5 . Under ambient conditions, both the ON and OFF states are stable under a constant voltage stress or a continuous pulse voltage stress at a read voltage of 1 V. The conduction mechanism is deduced from the modeling of the nature of currents in both states, and the electrical switching behavior can be attributed to the electric-field-induced charge transfer between P3HT and HDAGO nanosheets. - Highlights: • Nonvolatile rewritable memory effect in P3HT–graphene composite is demonstrated. • The memory device was fabricated through a simple solution processing technique. • The device shows a remarkable electrical bistable behavior and excellent stability. • Memory mechanism is deduced from the modeling of the currents in both states

Reaction factoring and bipartite update graphs accelerate the Gillespie Algorithm for large-scale biochemical systems.

Directory of Open Access Journals (Sweden)

Sagar Indurkhya

Full Text Available ODE simulations of chemical systems perform poorly when some of the species have extremely low concentrations. Stochastic simulation methods, which can handle this case, have been impractical for large systems due to computational complexity. We observe, however, that when modeling complex biological systems: (1 a small number of reactions tend to occur a disproportionately large percentage of the time, and (2 a small number of species tend to participate in a disproportionately large percentage of reactions. We exploit these properties in LOLCAT Method, a new implementation of the Gillespie Algorithm. First, factoring reaction propensities allows many propensities dependent on a single species to be updated in a single operation. Second, representing dependencies between reactions with a bipartite graph of reactions and species requires only storage for reactions, rather than the required for a graph that includes only reactions. Together, these improvements allow our implementation of LOLCAT Method to execute orders of magnitude faster than currently existing Gillespie Algorithm variants when simulating several yeast MAPK cascade models.

Reaction Factoring and Bipartite Update Graphs Accelerate the Gillespie Algorithm for Large-Scale Biochemical Systems

Science.gov (United States)

Indurkhya, Sagar; Beal, Jacob

2010-01-01

ODE simulations of chemical systems perform poorly when some of the species have extremely low concentrations. Stochastic simulation methods, which can handle this case, have been impractical for large systems due to computational complexity. We observe, however, that when modeling complex biological systems: (1) a small number of reactions tend to occur a disproportionately large percentage of the time, and (2) a small number of species tend to participate in a disproportionately large percentage of reactions. We exploit these properties in LOLCAT Method, a new implementation of the Gillespie Algorithm. First, factoring reaction propensities allows many propensities dependent on a single species to be updated in a single operation. Second, representing dependencies between reactions with a bipartite graph of reactions and species requires only storage for reactions, rather than the required for a graph that includes only reactions. Together, these improvements allow our implementation of LOLCAT Method to execute orders of magnitude faster than currently existing Gillespie Algorithm variants when simulating several yeast MAPK cascade models. PMID:20066048

Modeling flow and transport in fracture networks using graphs

Science.gov (United States)

Karra, S.; O'Malley, D.; Hyman, J. D.; Viswanathan, H. S.; Srinivasan, G.

2018-03-01

Fractures form the main pathways for flow in the subsurface within low-permeability rock. For this reason, accurately predicting flow and transport in fractured systems is vital for improving the performance of subsurface applications. Fracture sizes in these systems can range from millimeters to kilometers. Although modeling flow and transport using the discrete fracture network (DFN) approach is known to be more accurate due to incorporation of the detailed fracture network structure over continuum-based methods, capturing the flow and transport in such a wide range of scales is still computationally intractable. Furthermore, if one has to quantify uncertainty, hundreds of realizations of these DFN models have to be run. To reduce the computational burden, we solve flow and transport on a graph representation of a DFN. We study the accuracy of the graph approach by comparing breakthrough times and tracer particle statistical data between the graph-based and the high-fidelity DFN approaches, for fracture networks with varying number of fractures and degree of heterogeneity. Due to our recent developments in capabilities to perform DFN high-fidelity simulations on fracture networks with large number of fractures, we are in a unique position to perform such a comparison. We show that the graph approach shows a consistent bias with up to an order of magnitude slower breakthrough when compared to the DFN approach. We show that this is due to graph algorithm's underprediction of the pressure gradients across intersections on a given fracture, leading to slower tracer particle speeds between intersections and longer travel times. We present a bias correction methodology to the graph algorithm that reduces the discrepancy between the DFN and graph predictions. We show that with this bias correction, the graph algorithm predictions significantly improve and the results are very accurate. The good accuracy and the low computational cost, with O (104) times lower times than

Graphing Inequalities, Connecting Meaning

Science.gov (United States)

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…

Fuzzy Graph Language Recognizability

OpenAIRE

Kalampakas , Antonios; Spartalis , Stefanos; Iliadis , Lazaros

2012-01-01

Part 5: Fuzzy Logic; International audience; Fuzzy graph language recognizability is introduced along the lines of the established theory of syntactic graph language recognizability by virtue of the algebraic structure of magmoids. The main closure properties of the corresponding class are investigated and several interesting examples of fuzzy graph languages are examined.

Bell inequalities for graph states

International Nuclear Information System (INIS)

Toth, G.; Hyllus, P.; Briegel, H.J.; Guehne, O.

2005-01-01

Full text: In the last years graph states have attracted an increasing interest in the field of quantum information theory. Graph states form a family of multi-qubit states which comprises many popular states such as the GHZ states and the cluster states. They also play an important role in applications. For instance, measurement based quantum computation uses graph states as resources. From a theoretical point of view, it is remarkable that graph states allow for a simple description in terms of stabilizing operators. In this contribution, we investigate the non-local properties of graph states. We derive a family of Bell inequalities which require three measurement settings for each party and are maximally violated by graph states. In turn, any graph state violates at least one of the inequalities. We show that for certain types of graph states the violation of these inequalities increases exponentially with the number of qubits. We also discuss connections to other entanglement properties such as the positively of the partial transpose or the geometric measure of entanglement. (author)

[A retrieval method of drug molecules based on graph collapsing].

Science.gov (United States)

Qu, J W; Lv, X Q; Liu, Z M; Liao, Y; Sun, P H; Wang, B; Tang, Z

2018-04-18

To establish a compact and efficient hypergraph representation and a graph-similarity-based retrieval method of molecules to achieve effective and efficient medicine information retrieval. Chemical structural formula (CSF) was a primary search target as a unique and precise identifier for each compound at the molecular level in the research field of medicine information retrieval. To retrieve medicine information effectively and efficiently, a complete workflow of the graph-based CSF retrieval system was introduced. This system accepted the photos taken from smartphones and the sketches drawn on tablet personal computers as CSF inputs, and formalized the CSFs with the corresponding graphs. Then this paper proposed a compact and efficient hypergraph representation for molecules on the basis of analyzing factors that directly affected the efficiency of graph matching. According to the characteristics of CSFs, a hierarchical collapsing method combining graph isomorphism and frequent subgraph mining was adopted. There was yet a fundamental challenge, subgraph overlapping during the collapsing procedure, which hindered the method from establishing the correct compact hypergraph of an original CSF graph. Therefore, a graph-isomorphism-based algorithm was proposed to select dominant acyclic subgraphs on the basis of overlapping analysis. Finally, the spatial similarity among graphical CSFs was evaluated by multi-dimensional measures of similarity. To evaluate the performance of the proposed method, the proposed system was firstly compared with Wikipedia Chemical Structure Explorer (WCSE), the state-of-the-art system that allowed CSF similarity searching within Wikipedia molecules dataset, on retrieval accuracy. The system achieved higher values on mean average precision, discounted cumulative gain, rank-biased precision, and expected reciprocal rank than WCSE from the top-2 to the top-10 retrieved results. Specifically, the system achieved 10%, 1.41, 6.42%, and 1

Quantitative graph theory mathematical foundations and applications

CERN Document Server

Dehmer, Matthias

2014-01-01

The first book devoted exclusively to quantitative graph theory, Quantitative Graph Theory: Mathematical Foundations and Applications presents and demonstrates existing and novel methods for analyzing graphs quantitatively. Incorporating interdisciplinary knowledge from graph theory, information theory, measurement theory, and statistical techniques, this book covers a wide range of quantitative-graph theoretical concepts and methods, including those pertaining to real and random graphs such as:Comparative approaches (graph similarity or distance)Graph measures to characterize graphs quantitat

Dynamic Representations of Sparse Graphs

DEFF Research Database (Denmark)

Brodal, Gerth Stølting; Fagerberg, Rolf

1999-01-01

We present a linear space data structure for maintaining graphs with bounded arboricity—a large class of sparse graphs containing e.g. planar graphs and graphs of bounded treewidth—under edge insertions, edge deletions, and adjacency queries. The data structure supports adjacency queries in worst...... case O(c) time, and edge insertions and edge deletions in amortized O(1) and O(c+log n) time, respectively, where n is the number of nodes in the graph, and c is the bound on the arboricity....

Spectral fluctuations of quantum graphs

International Nuclear Information System (INIS)

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

2014-01-01

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

PERSEUS-HUB: Interactive and Collective Exploration of Large-Scale Graphs

Directory of Open Access Journals (Sweden)

Di Jin

2017-07-01

Full Text Available Graphs emerge naturally in many domains, such as social science, neuroscience, transportation engineering, and more. In many cases, such graphs have millions or billions of nodes and edges, and their sizes increase daily at a fast pace. How can researchers from various domains explore large graphs interactively and efficiently to find out what is ‘important’? How can multiple researchers explore a new graph dataset collectively and “help” each other with their findings? In this article, we present Perseus-Hub, a large-scale graph mining tool that computes a set of graph properties in a distributed manner, performs ensemble, multi-view anomaly detection to highlight regions that are worth investigating, and provides users with uncluttered visualization and easy interaction with complex graph statistics. Perseus-Hub uses a Spark cluster to calculate various statistics of large-scale graphs efficiently, and aggregates the results in a summary on the master node to support interactive user exploration. In Perseus-Hub, the visualized distributions of graph statistics provide preliminary analysis to understand a graph. To perform a deeper analysis, users with little prior knowledge can leverage patterns (e.g., spikes in the power-law degree distribution marked by other users or experts. Moreover, Perseus-Hub guides users to regions of interest by highlighting anomalous nodes and helps users establish a more comprehensive understanding about the graph at hand. We demonstrate our system through the case study on real, large-scale networks.

Multiple graph regularized protein domain ranking.

Science.gov (United States)

Wang, Jim Jing-Yan; Bensmail, Halima; Gao, Xin

2012-11-19

Protein domain ranking is a fundamental task in structural biology. Most protein domain ranking methods rely on the pairwise comparison of protein domains while neglecting the global manifold structure of the protein domain database. Recently, graph regularized ranking that exploits the global structure of the graph defined by the pairwise similarities has been proposed. However, the existing graph regularized ranking methods are very sensitive to the choice of the graph model and parameters, and this remains a difficult problem for most of the protein domain ranking methods. To tackle this problem, we have developed the Multiple Graph regularized Ranking algorithm, MultiG-Rank. Instead of using a single graph to regularize the ranking scores, MultiG-Rank approximates the intrinsic manifold of protein domain distribution by combining multiple initial graphs for the regularization. Graph weights are learned with ranking scores jointly and automatically, by alternately minimizing an objective function in an iterative algorithm. Experimental results on a subset of the ASTRAL SCOP protein domain database demonstrate that MultiG-Rank achieves a better ranking performance than single graph regularized ranking methods and pairwise similarity based ranking methods. The problem of graph model and parameter selection in graph regularized protein domain ranking can be solved effectively by combining multiple graphs. This aspect of generalization introduces a new frontier in applying multiple graphs to solving protein domain ranking applications.

Acyclicity in edge-colored graphs

DEFF Research Database (Denmark)

Gutin, Gregory; Jones, Mark; Sheng, Bin

2017-01-01

A walk W in edge-colored graphs is called properly colored (PC) if every pair of consecutive edges in W is of different color. We introduce and study five types of PC acyclicity in edge-colored graphs such that graphs of PC acyclicity of type i is a proper superset of graphs of acyclicity of type...

ON BIPOLAR SINGLE VALUED NEUTROSOPHIC GRAPHS

OpenAIRE

Said Broumi; Mohamed Talea; Assia Bakali; Florentin Smarandache

2016-01-01

In this article, we combine the concept of bipolar neutrosophic set and graph theory. We introduce the notions of bipolar single valued neutrosophic graphs, strong bipolar single valued neutrosophic graphs, complete bipolar single valued neutrosophic graphs, regular bipolar single valued neutrosophic graphs and investigate some of their related properties.

Practical graph mining with R

CERN Document Server

Hendrix, William; Jenkins, John; Padmanabhan, Kanchana; Chakraborty, Arpan

2014-01-01

Practical Graph Mining with R presents a "do-it-yourself" approach to extracting interesting patterns from graph data. It covers many basic and advanced techniques for the identification of anomalous or frequently recurring patterns in a graph, the discovery of groups or clusters of nodes that share common patterns of attributes and relationships, the extraction of patterns that distinguish one category of graphs from another, and the use of those patterns to predict the category of new graphs. Hands-On Application of Graph Data Mining Each chapter in the book focuses on a graph mining task, such as link analysis, cluster analysis, and classification. Through applications using real data sets, the book demonstrates how computational techniques can help solve real-world problems. The applications covered include network intrusion detection, tumor cell diagnostics, face recognition, predictive toxicology, mining metabolic and protein-protein interaction networks, and community detection in social networks. De...

A seminar on graph theory

CERN Document Server

Harary, Frank

2015-01-01

Presented in 1962-63 by experts at University College, London, these lectures offer a variety of perspectives on graph theory. Although the opening chapters form a coherent body of graph theoretic concepts, this volume is not a text on the subject but rather an introduction to the extensive literature of graph theory. The seminar's topics are geared toward advanced undergraduate students of mathematics.Lectures by this volume's editor, Frank Harary, include ""Some Theorems and Concepts of Graph Theory,"" ""Topological Concepts in Graph Theory,"" ""Graphical Reconstruction,"" and other introduc

Uniform Single Valued Neutrosophic Graphs

Directory of Open Access Journals (Sweden)

S. Broumi

2017-09-01

Full Text Available In this paper, we propose a new concept named the uniform single valued neutrosophic graph. An illustrative example and some properties are examined. Next, we develop an algorithmic approach for computing the complement of the single valued neutrosophic graph. A numerical example is demonstrated for computing the complement of single valued neutrosophic graphs and uniform single valued neutrosophic graph.

Graph-Based Methods for Discovery Browsing with Semantic Predications

DEFF Research Database (Denmark)

Wilkowski, Bartlomiej; Fiszman, Marcelo; Miller, Christopher M

2011-01-01

. Poorly understood relationships may be explored through novel points of view, and potentially interesting relationships need not be known ahead of time. In a process of "cooperative reciprocity" the user iteratively focuses system output, thus controlling the large number of relationships often generated...... in literature-based discovery systems. The underlying technology exploits SemRep semantic predications represented as a graph of interconnected nodes (predication arguments) and edges (predicates). The system suggests paths in this graph, which represent chains of relationships. The methodology is illustrated...

Construction and application research of knowledge graph in aviation risk field

Directory of Open Access Journals (Sweden)

Zhao Qian

2018-01-01

Full Text Available Since the causes of aviation accidents and risks are complicated, concealed, unpredictable and difficult to be investigated, in order to achieve the efficient organization and knowledge sharing of the historical cases of aviation risk events, this paper put forward the method of constructing vertical knowledge graph for aviation risk field. Firstly, the data-driven incremental construction technology is used to build aviation risk event ontology model. Secondly, the pattern-based knowledge mapping mechanism, which transform structured data into RDF (Resource Description Framework data for storage, is proposed. And then the application, update and maintenance of the knowledge graph are described. Finally, knowledge graph construction system in aviation risk field is developed; and the data from American Aviation Safety Reporting System (ASRS is used as an example to verify the rationality and validity of the knowledge graph construction method. Practice has proved that the construction of knowledge graph has a guiding significance for the case information organization and sharing on the field of aviation risk.

Extremal graph theory

CERN Document Server

Bollobas, Bela

2004-01-01

The ever-expanding field of extremal graph theory encompasses a diverse array of problem-solving methods, including applications to economics, computer science, and optimization theory. This volume, based on a series of lectures delivered to graduate students at the University of Cambridge, presents a concise yet comprehensive treatment of extremal graph theory.Unlike most graph theory treatises, this text features complete proofs for almost all of its results. Further insights into theory are provided by the numerous exercises of varying degrees of difficulty that accompany each chapter. A

Multiple graph regularized protein domain ranking

KAUST Repository

Wang, Jim Jing-Yan

2012-11-19

Background: Protein domain ranking is a fundamental task in structural biology. Most protein domain ranking methods rely on the pairwise comparison of protein domains while neglecting the global manifold structure of the protein domain database. Recently, graph regularized ranking that exploits the global structure of the graph defined by the pairwise similarities has been proposed. However, the existing graph regularized ranking methods are very sensitive to the choice of the graph model and parameters, and this remains a difficult problem for most of the protein domain ranking methods.Results: To tackle this problem, we have developed the Multiple Graph regularized Ranking algorithm, MultiG-Rank. Instead of using a single graph to regularize the ranking scores, MultiG-Rank approximates the intrinsic manifold of protein domain distribution by combining multiple initial graphs for the regularization. Graph weights are learned with ranking scores jointly and automatically, by alternately minimizing an objective function in an iterative algorithm. Experimental results on a subset of the ASTRAL SCOP protein domain database demonstrate that MultiG-Rank achieves a better ranking performance than single graph regularized ranking methods and pairwise similarity based ranking methods.Conclusion: The problem of graph model and parameter selection in graph regularized protein domain ranking can be solved effectively by combining multiple graphs. This aspect of generalization introduces a new frontier in applying multiple graphs to solving protein domain ranking applications. 2012 Wang et al; licensee BioMed Central Ltd.

Multiple graph regularized protein domain ranking

KAUST Repository

Wang, Jim Jing-Yan; Bensmail, Halima; Gao, Xin

2012-01-01

Background: Protein domain ranking is a fundamental task in structural biology. Most protein domain ranking methods rely on the pairwise comparison of protein domains while neglecting the global manifold structure of the protein domain database. Recently, graph regularized ranking that exploits the global structure of the graph defined by the pairwise similarities has been proposed. However, the existing graph regularized ranking methods are very sensitive to the choice of the graph model and parameters, and this remains a difficult problem for most of the protein domain ranking methods.Results: To tackle this problem, we have developed the Multiple Graph regularized Ranking algorithm, MultiG-Rank. Instead of using a single graph to regularize the ranking scores, MultiG-Rank approximates the intrinsic manifold of protein domain distribution by combining multiple initial graphs for the regularization. Graph weights are learned with ranking scores jointly and automatically, by alternately minimizing an objective function in an iterative algorithm. Experimental results on a subset of the ASTRAL SCOP protein domain database demonstrate that MultiG-Rank achieves a better ranking performance than single graph regularized ranking methods and pairwise similarity based ranking methods.Conclusion: The problem of graph model and parameter selection in graph regularized protein domain ranking can be solved effectively by combining multiple graphs. This aspect of generalization introduces a new frontier in applying multiple graphs to solving protein domain ranking applications. 2012 Wang et al; licensee BioMed Central Ltd.

Multiple graph regularized protein domain ranking

Directory of Open Access Journals (Sweden)

Wang Jim

2012-11-01

Full Text Available Abstract Background Protein domain ranking is a fundamental task in structural biology. Most protein domain ranking methods rely on the pairwise comparison of protein domains while neglecting the global manifold structure of the protein domain database. Recently, graph regularized ranking that exploits the global structure of the graph defined by the pairwise similarities has been proposed. However, the existing graph regularized ranking methods are very sensitive to the choice of the graph model and parameters, and this remains a difficult problem for most of the protein domain ranking methods. Results To tackle this problem, we have developed the Multiple Graph regularized Ranking algorithm, MultiG-Rank. Instead of using a single graph to regularize the ranking scores, MultiG-Rank approximates the intrinsic manifold of protein domain distribution by combining multiple initial graphs for the regularization. Graph weights are learned with ranking scores jointly and automatically, by alternately minimizing an objective function in an iterative algorithm. Experimental results on a subset of the ASTRAL SCOP protein domain database demonstrate that MultiG-Rank achieves a better ranking performance than single graph regularized ranking methods and pairwise similarity based ranking methods. Conclusion The problem of graph model and parameter selection in graph regularized protein domain ranking can be solved effectively by combining multiple graphs. This aspect of generalization introduces a new frontier in applying multiple graphs to solving protein domain ranking applications.

Canonical Labelling of Site Graphs

Directory of Open Access Journals (Sweden)

Nicolas Oury

2013-06-01

Full Text Available We investigate algorithms for canonical labelling of site graphs, i.e. graphs in which edges bind vertices on sites with locally unique names. We first show that the problem of canonical labelling of site graphs reduces to the problem of canonical labelling of graphs with edge colourings. We then present two canonical labelling algorithms based on edge enumeration, and a third based on an extension of Hopcroft's partition refinement algorithm. All run in quadratic worst case time individually. However, one of the edge enumeration algorithms runs in sub-quadratic time for graphs with "many" automorphisms, and the partition refinement algorithm runs in sub-quadratic time for graphs with "few" bisimulation equivalences. This suite of algorithms was chosen based on the expectation that graphs fall in one of those two categories. If that is the case, a combined algorithm runs in sub-quadratic worst case time. Whether this expectation is reasonable remains an interesting open problem.

ESIP's Earth Science Knowledge Graph (ESKG) Testbed Project: An Automatic Approach to Building Interdisciplinary Earth Science Knowledge Graphs to Improve Data Discovery

Science.gov (United States)

McGibbney, L. J.; Jiang, Y.; Burgess, A. B.

2017-12-01

Big Earth observation data have been produced, archived and made available online, but discovering the right data in a manner that precisely and efficiently satisfies user needs presents a significant challenge to the Earth Science (ES) community. An emerging trend in information retrieval community is to utilize knowledge graphs to assist users in quickly finding desired information from across knowledge sources. This is particularly prevalent within the fields of social media and complex multimodal information processing to name but a few, however building a domain-specific knowledge graph is labour-intensive and hard to keep up-to-date. In this work, we update our progress on the Earth Science Knowledge Graph (ESKG) project; an ESIP-funded testbed project which provides an automatic approach to building a dynamic knowledge graph for ES to improve interdisciplinary data discovery by leveraging implicit, latent existing knowledge present within across several U.S Federal Agencies e.g. NASA, NOAA and USGS. ESKG strengthens ties between observations and user communities by: 1) developing a knowledge graph derived from various sources e.g. Web pages, Web Services, etc. via natural language processing and knowledge extraction techniques; 2) allowing users to traverse, explore, query, reason and navigate ES data via knowledge graph interaction. ESKG has the potential to revolutionize the way in which ES communities interact with ES data in the open world through the entity, spatial and temporal linkages and characteristics that make it up. This project enables the advancement of ESIP collaboration areas including both Discovery and Semantic Technologies by putting graph information right at our fingertips in an interactive, modern manner and reducing the efforts to constructing ontology. To demonstrate the ESKG concept, we will demonstrate use of our framework across NASA JPL's PO.DAAC, NOAA's Earth Observation Requirements Evaluation System (EORES) and various USGS

Domination criticality in product graphs

Directory of Open Access Journals (Sweden)

M.R. Chithra

2015-07-01

Full Text Available A connected dominating set is an important notion and has many applications in routing and management of networks. Graph products have turned out to be a good model of interconnection networks. This motivated us to study the Cartesian product of graphs G with connected domination number, γc(G=2,3 and characterize such graphs. Also, we characterize the k−γ-vertex (edge critical graphs and k−γc-vertex (edge critical graphs for k=2,3 where γ denotes the domination number of G. We also discuss the vertex criticality in grids.

Graph Colouring Algorithms

DEFF Research Database (Denmark)

Husfeldt, Thore

2015-01-01

This chapter presents an introduction to graph colouring algorithms. The focus is on vertex-colouring algorithms that work for general classes of graphs with worst-case performance guarantees in a sequential model of computation. The presentation aims to demonstrate the breadth of available...

A Bond Graph Approach for the Modeling and Simulation of a Buck Converter

Directory of Open Access Journals (Sweden)

Rached Zrafi

2018-01-01

Full Text Available This paper deals with the modeling of bond graph buck converter systems. The bond graph formalism, which represents a heterogeneous formalism for physical modeling, is used to design a sub-model of a power MOSFET and PiN diode switchers. These bond graph models are based on the device’s electrical elements. The application of these models to a bond graph buck converter permit us to obtain an invariant causal structure when the switch devices change state. This paper shows the usefulness of the bond graph device’s modeling to simulate an implicit bond graph buck converter.

The fascinating world of graph theory

CERN Document Server

Benjamin, Arthur; Zhang, Ping

2015-01-01

Graph theory goes back several centuries and revolves around the study of graphs-mathematical structures showing relations between objects. With applications in biology, computer science, transportation science, and other areas, graph theory encompasses some of the most beautiful formulas in mathematics-and some of its most famous problems. The Fascinating World of Graph Theory explores the questions and puzzles that have been studied, and often solved, through graph theory. This book looks at graph theory's development and the vibrant individuals responsible for the field's growth. Introducin

Interactive exploration of large-scale time-varying data using dynamic tracking graphs

KAUST Repository

Widanagamaachchi, W.

2012-10-01

Exploring and analyzing the temporal evolution of features in large-scale time-varying datasets is a common problem in many areas of science and engineering. One natural representation of such data is tracking graphs, i.e., constrained graph layouts that use one spatial dimension to indicate time and show the "tracks" of each feature as it evolves, merges or disappears. However, for practical data sets creating the corresponding optimal graph layouts that minimize the number of intersections can take hours to compute with existing techniques. Furthermore, the resulting graphs are often unmanageably large and complex even with an ideal layout. Finally, due to the cost of the layout, changing the feature definition, e.g. by changing an iso-value, or analyzing properly adjusted sub-graphs is infeasible. To address these challenges, this paper presents a new framework that couples hierarchical feature definitions with progressive graph layout algorithms to provide an interactive exploration of dynamically constructed tracking graphs. Our system enables users to change feature definitions on-the-fly and filter features using arbitrary attributes while providing an interactive view of the resulting tracking graphs. Furthermore, the graph display is integrated into a linked view system that provides a traditional 3D view of the current set of features and allows a cross-linked selection to enable a fully flexible spatio-temporal exploration of data. We demonstrate the utility of our approach with several large-scale scientific simulations from combustion science. © 2012 IEEE.

Groupies in multitype random graphs

OpenAIRE

Shang, Yilun

2016-01-01

A groupie in a graph is a vertex whose degree is not less than the average degree of its neighbors. Under some mild conditions, we show that the proportion of groupies is very close to 1/2 in multitype random graphs (such as stochastic block models), which include Erd?s-R?nyi random graphs, random bipartite, and multipartite graphs as special examples. Numerical examples are provided to illustrate the theoretical results.

Markov chain aggregation and its applications to combinatorial reaction networks.

Science.gov (United States)

Ganguly, Arnab; Petrov, Tatjana; Koeppl, Heinz

2014-09-01

We consider a continuous-time Markov chain (CTMC) whose state space is partitioned into aggregates, and each aggregate is assigned a probability measure. A sufficient condition for defining a CTMC over the aggregates is presented as a variant of weak lumpability, which also characterizes that the measure over the original process can be recovered from that of the aggregated one. We show how the applicability of de-aggregation depends on the initial distribution. The application section is devoted to illustrate how the developed theory aids in reducing CTMC models of biochemical systems particularly in connection to protein-protein interactions. We assume that the model is written by a biologist in form of site-graph-rewrite rules. Site-graph-rewrite rules compactly express that, often, only a local context of a protein (instead of a full molecular species) needs to be in a certain configuration in order to trigger a reaction event. This observation leads to suitable aggregate Markov chains with smaller state spaces, thereby providing sufficient reduction in computational complexity. This is further exemplified in two case studies: simple unbounded polymerization and early EGFR/insulin crosstalk.

Coupling graph perturbation theory with scalable parallel algorithms for large-scale enumeration of maximal cliques in biological graphs

International Nuclear Information System (INIS)

Samatova, N F; Schmidt, M C; Hendrix, W; Breimyer, P; Thomas, K; Park, B-H

2008-01-01

Data-driven construction of predictive models for biological systems faces challenges from data intensity, uncertainty, and computational complexity. Data-driven model inference is often considered a combinatorial graph problem where an enumeration of all feasible models is sought. The data-intensive and the NP-hard nature of such problems, however, challenges existing methods to meet the required scale of data size and uncertainty, even on modern supercomputers. Maximal clique enumeration (MCE) in a graph derived from such biological data is often a rate-limiting step in detecting protein complexes in protein interaction data, finding clusters of co-expressed genes in microarray data, or identifying clusters of orthologous genes in protein sequence data. We report two key advances that address this challenge. We designed and implemented the first (to the best of our knowledge) parallel MCE algorithm that scales linearly on thousands of processors running MCE on real-world biological networks with thousands and hundreds of thousands of vertices. In addition, we proposed and developed the Graph Perturbation Theory (GPT) that establishes a foundation for efficiently solving the MCE problem in perturbed graphs, which model the uncertainty in the data. GPT formulates necessary and sufficient conditions for detecting the differences between the sets of maximal cliques in the original and perturbed graphs and reduces the enumeration time by more than 80% compared to complete recomputation

Fibonacci number of the tadpole graph

Directory of Open Access Journals (Sweden)

Joe DeMaio

2014-10-01

Full Text Available In 1982, Prodinger and Tichy defined the Fibonacci number of a graph G to be the number of independent sets of the graph G. They did so since the Fibonacci number of the path graph Pn is the Fibonacci number F(n+2 and the Fibonacci number of the cycle graph Cn is the Lucas number Ln. The tadpole graph Tn,k is the graph created by concatenating Cn and Pk with an edge from any vertex of Cn to a pendant of Pk for integers n=3 and k=0. This paper establishes formulae and identities for the Fibonacci number of the tadpole graph via algebraic and combinatorial methods.

On characterizing terrain visibility graphs

Directory of Open Access Journals (Sweden)

William Evans

2015-06-01

Full Text Available A terrain is an $x$-monotone polygonal line in the $xy$-plane. Two vertices of a terrain are mutually visible if and only if there is no terrain vertex on or above the open line segment connecting them. A graph whose vertices represent terrain vertices and whose edges represent mutually visible pairs of terrain vertices is called a terrain visibility graph. We would like to find properties that are both necessary and sufficient for a graph to be a terrain visibility graph; that is, we would like to characterize terrain visibility graphs.Abello et al. [Discrete and Computational Geometry, 14(3:331--358, 1995] showed that all terrain visibility graphs are “persistent”. They showed that the visibility information of a terrain point set implies some ordering requirements on the slopes of the lines connecting pairs of points in any realization, and as a step towards showing sufficiency, they proved that for any persistent graph $M$ there is a total order on the slopes of the (pseudo lines in a generalized configuration of points whose visibility graph is $M$.We give a much simpler proof of this result by establishing an orientation to every triple of vertices, reflecting some slope ordering requirements that are consistent with $M$ being the visibility graph, and prove that these requirements form a partial order. We give a faster algorithm to construct a total order on the slopes. Our approach attempts to clarify the implications of the graph theoretic properties on the ordering of the slopes, and may be interpreted as defining properties on an underlying oriented matroid that we show is a restricted type of $3$-signotope.

A graph-search framework for associating gene identifiers with documents

Directory of Open Access Journals (Sweden)

Cohen William W

2006-10-01

Full Text Available Abstract Background One step in the model organism database curation process is to find, for each article, the identifier of every gene discussed in the article. We consider a relaxation of this problem suitable for semi-automated systems, in which each article is associated with a ranked list of possible gene identifiers, and experimentally compare methods for solving this geneId ranking problem. In addition to baseline approaches based on combining named entity recognition (NER systems with a "soft dictionary" of gene synonyms, we evaluate a graph-based method which combines the outputs of multiple NER systems, as well as other sources of information, and a learning method for reranking the output of the graph-based method. Results We show that named entity recognition (NER systems with similar F-measure performance can have significantly different performance when used with a soft dictionary for geneId-ranking. The graph-based approach can outperform any of its component NER systems, even without learning, and learning can further improve the performance of the graph-based ranking approach. Conclusion The utility of a named entity recognition (NER system for geneId-finding may not be accurately predicted by its entity-level F1 performance, the most common performance measure. GeneId-ranking systems are best implemented by combining several NER systems. With appropriate combination methods, usefully accurate geneId-ranking systems can be constructed based on easily-available resources, without resorting to problem-specific, engineered components.

Network reconstruction via graph blending

Science.gov (United States)

Estrada, Rolando

2016-05-01

Graphs estimated from empirical data are often noisy and incomplete due to the difficulty of faithfully observing all the components (nodes and edges) of the true graph. This problem is particularly acute for large networks where the number of components may far exceed available surveillance capabilities. Errors in the observed graph can render subsequent analyses invalid, so it is vital to develop robust methods that can minimize these observational errors. Errors in the observed graph may include missing and spurious components, as well fused (multiple nodes are merged into one) and split (a single node is misinterpreted as many) nodes. Traditional graph reconstruction methods are only able to identify missing or spurious components (primarily edges, and to a lesser degree nodes), so we developed a novel graph blending framework that allows us to cast the full estimation problem as a simple edge addition/deletion problem. Armed with this framework, we systematically investigate the viability of various topological graph features, such as the degree distribution or the clustering coefficients, and existing graph reconstruction methods for tackling the full estimation problem. Our experimental results suggest that incorporating any topological feature as a source of information actually hinders reconstruction accuracy. We provide a theoretical analysis of this phenomenon and suggest several avenues for improving this estimation problem.

Groupies in multitype random graphs.

Science.gov (United States)

Shang, Yilun

2016-01-01

A groupie in a graph is a vertex whose degree is not less than the average degree of its neighbors. Under some mild conditions, we show that the proportion of groupies is very close to 1/2 in multitype random graphs (such as stochastic block models), which include Erdős-Rényi random graphs, random bipartite, and multipartite graphs as special examples. Numerical examples are provided to illustrate the theoretical results.

Learning a Health Knowledge Graph from Electronic Medical Records.

Science.gov (United States)

Rotmensch, Maya; Halpern, Yoni; Tlimat, Abdulhakim; Horng, Steven; Sontag, David

2017-07-20

Demand for clinical decision support systems in medicine and self-diagnostic symptom checkers has substantially increased in recent years. Existing platforms rely on knowledge bases manually compiled through a labor-intensive process or automatically derived using simple pairwise statistics. This study explored an automated process to learn high quality knowledge bases linking diseases and symptoms directly from electronic medical records. Medical concepts were extracted from 273,174 de-identified patient records and maximum likelihood estimation of three probabilistic models was used to automatically construct knowledge graphs: logistic regression, naive Bayes classifier and a Bayesian network using noisy OR gates. A graph of disease-symptom relationships was elicited from the learned parameters and the constructed knowledge graphs were evaluated and validated, with permission, against Google's manually-constructed knowledge graph and against expert physician opinions. Our study shows that direct and automated construction of high quality health knowledge graphs from medical records using rudimentary concept extraction is feasible. The noisy OR model produces a high quality knowledge graph reaching precision of 0.85 for a recall of 0.6 in the clinical evaluation. Noisy OR significantly outperforms all tested models across evaluation frameworks (p < 0.01).

The Harary index of a graph

CERN Document Server

Xu, Kexiang; Trinajstić, Nenad

2015-01-01

This is the first book to focus on the topological index, the Harary index, of a graph, including its mathematical properties, chemical applications and some related and attractive open problems. This book is dedicated to Professor Frank Harary (1921—2005), the grandmaster of graph theory and its applications. It has be written by experts in the field of graph theory and its applications. For a connected graph G, as an important distance-based topological index, the Harary index H(G) is defined as the sum of the reciprocals of the distance between any two unordered vertices of the graph G. In this book, the authors report on the newest results on the Harary index of a graph. These results mainly concern external graphs with respect to the Harary index; the relations to other topological indices; its properties and applications to pure graph theory and chemical graph theory; and two significant variants, i.e., additively and multiplicatively weighted Harary indices. In the last chapter, we present a number o...

A Qualitative Approach to Sketch the Graph of a Function.

Science.gov (United States)

Alson, Pedro

1992-01-01

Presents a qualitative and global method of graphing functions that involves transformations of the graph of a known function in the cartesian coordinate system referred to as graphic operators. Explains how the method has been taught to students and some comments about the results obtained. (MDH)

Generic Graph Grammar: A Simple Grammar for Generic Procedural Modelling

DEFF Research Database (Denmark)

Christiansen, Asger Nyman; Bærentzen, Jakob Andreas

2012-01-01

in a directed cyclic graph. Furthermore, the basic productions are chosen such that Generic Graph Grammar seamlessly combines the capabilities of L-systems to imitate biological growth (to model trees, animals, etc.) and those of split grammars to design structured objects (chairs, houses, etc.). This results...

Graph mining for next generation sequencing: leveraging the assembly graph for biological insights.

Science.gov (United States)

Warnke-Sommer, Julia; Ali, Hesham

2016-05-06

The assembly of Next Generation Sequencing (NGS) reads remains a challenging task. This is especially true for the assembly of metagenomics data that originate from environmental samples potentially containing hundreds to thousands of unique species. The principle objective of current assembly tools is to assemble NGS reads into contiguous stretches of sequence called contigs while maximizing for both accuracy and contig length. The end goal of this process is to produce longer contigs with the major focus being on assembly only. Sequence read assembly is an aggregative process, during which read overlap relationship information is lost as reads are merged into longer sequences or contigs. The assembly graph is information rich and capable of capturing the genomic architecture of an input read data set. We have developed a novel hybrid graph in which nodes represent sequence regions at different levels of granularity. This model, utilized in the assembly and analysis pipeline Focus, presents a concise yet feature rich view of a given input data set, allowing for the extraction of biologically relevant graph structures for graph mining purposes. Focus was used to create hybrid graphs to model metagenomics data sets obtained from the gut microbiomes of five individuals with Crohn's disease and eight healthy individuals. Repetitive and mobile genetic elements are found to be associated with hybrid graph structure. Using graph mining techniques, a comparative study of the Crohn's disease and healthy data sets was conducted with focus on antibiotics resistance genes associated with transposase genes. Results demonstrated significant differences in the phylogenetic distribution of categories of antibiotics resistance genes in the healthy and diseased patients. Focus was also evaluated as a pure assembly tool and produced excellent results when compared against the Meta-velvet, Omega, and UD-IDBA assemblers. Mining the hybrid graph can reveal biological phenomena captured

Distance-transitive graphs

NARCIS (Netherlands)

Cohen, A.M.; Beineke, L.W.; Wilson, R.J.; Cameron, P.J.

2004-01-01

In this chapter we investigate the classification of distance-transitive graphs: these are graphs whose automorphism groups are transitive on each of the sets of pairs of vertices at distance i, for i = 0, 1,.... We provide an introduction into the field. By use of the classification of finite

TrajGraph: A Graph-Based Visual Analytics Approach to Studying Urban Network Centralities Using Taxi Trajectory Data.

Science.gov (United States)

Huang, Xiaoke; Zhao, Ye; Yang, Jing; Zhang, Chong; Ma, Chao; Ye, Xinyue

2016-01-01

We propose TrajGraph, a new visual analytics method, for studying urban mobility patterns by integrating graph modeling and visual analysis with taxi trajectory data. A special graph is created to store and manifest real traffic information recorded by taxi trajectories over city streets. It conveys urban transportation dynamics which can be discovered by applying graph analysis algorithms. To support interactive, multiscale visual analytics, a graph partitioning algorithm is applied to create region-level graphs which have smaller size than the original street-level graph. Graph centralities, including Pagerank and betweenness, are computed to characterize the time-varying importance of different urban regions. The centralities are visualized by three coordinated views including a node-link graph view, a map view and a temporal information view. Users can interactively examine the importance of streets to discover and assess city traffic patterns. We have implemented a fully working prototype of this approach and evaluated it using massive taxi trajectories of Shenzhen, China. TrajGraph's capability in revealing the importance of city streets was evaluated by comparing the calculated centralities with the subjective evaluations from a group of drivers in Shenzhen. Feedback from a domain expert was collected. The effectiveness of the visual interface was evaluated through a formal user study. We also present several examples and a case study to demonstrate the usefulness of TrajGraph in urban transportation analysis.

Temporal Representation in Semantic Graphs

Energy Technology Data Exchange (ETDEWEB)

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.

The complexity of the matching-cut problem for planar graphs and other graph classes

NARCIS (Netherlands)

Bonsma, P.S.

2009-01-01

The Matching-Cut problem is the problem to decide whether a graph has an edge cut that is also a matching. Previously this problem was studied under the name of the Decomposable Graph Recognition problem, and proved to be -complete when restricted to graphs with maximum degree four. In this paper it

Integer Flows and Circuit Covers of Graphs and Signed Graphs

Science.gov (United States)

Cheng, Jian

The work in Chapter 2 is motivated by Tutte and Jaeger's pioneering work on converting modulo flows into integer-valued flows for ordinary graphs. For a signed graphs (G, sigma), we first prove that for each k ∈ {2, 3}, if (G, sigma) is (k - 1)-edge-connected and contains an even number of negative edges when k = 2, then every modulo k-flow of (G, sigma) can be converted into an integer-valued ( k + 1)-ow with a larger or the same support. We also prove that if (G, sigma) is odd-(2p+1)-edge-connected, then (G, sigma) admits a modulo circular (2 + 1/ p)-flows if and only if it admits an integer-valued circular (2 + 1/p)-flows, which improves all previous result by Xu and Zhang (DM2005), Schubert and Steffen (EJC2015), and Zhu (JCTB2015). Shortest circuit cover conjecture is one of the major open problems in graph theory. It states that every bridgeless graph G contains a set of circuits F such that each edge is contained in at least one member of F and the length of F is at most 7/5∥E(G)∥. This concept was recently generalized to signed graphs by Macajova et al. (JGT2015). In Chapter 3, we improve their upper bound from 11∥E( G)∥ to 14/3 ∥E(G)∥, and if G is 2-edgeconnected and has even negativeness, then it can be further reduced to 11/3 ∥E(G)∥. Tutte's 3-flow conjecture has been studied by many graph theorists in the last several decades. As a new approach to this conjecture, DeVos and Thomassen considered the vectors as ow values and found that there is a close relation between vector S1-flows and integer 3-NZFs. Motivated by their observation, in Chapter 4, we prove that if a graph G admits a vector S1-flow with rank at most two, then G admits an integer 3-NZF. The concept of even factors is highly related to the famous Four Color Theorem. We conclude this dissertation in Chapter 5 with an improvement of a recent result by Chen and Fan (JCTB2016) on the upperbound of even factors. We show that if a graph G contains an even factor, then it

Citation graph based ranking in Invenio

CERN Document Server

Marian, Ludmila; Rajman, Martin; Vesely, Martin

2010-01-01

Invenio is the web-based integrated digital library system developed at CERN. Within this framework, we present four types of ranking models based on the citation graph that complement the simple approach based on citation counts: time-dependent citation counts, a relevancy ranking which extends the PageRank model, a time-dependent ranking which combines the freshness of citations with PageRank and a ranking that takes into consideration the external citations. We present our analysis and results obtained on two main data sets: Inspire and CERN Document Server. Our main contributions are: (i) a study of the currently available ranking methods based on the citation graph; (ii) the development of new ranking methods that correct some of the identified limitations of the current methods such as treating all citations of equal importance, not taking time into account or considering the citation graph complete; (iii) a detailed study of the key parameters for these ranking methods. (The original publication is ava...

Quantum walk on a chimera graph

Science.gov (United States)

Xu, Shu; Sun, Xiangxiang; Wu, Jizhou; Zhang, Wei-Wei; Arshed, Nigum; Sanders, Barry C.

2018-05-01

We analyse a continuous-time quantum walk on a chimera graph, which is a graph of choice for designing quantum annealers, and we discover beautiful quantum walk features such as localization that starkly distinguishes classical from quantum behaviour. Motivated by technological thrusts, we study continuous-time quantum walk on enhanced variants of the chimera graph and on diminished chimera graph with a random removal of vertices. We explain the quantum walk by constructing a generating set for a suitable subgroup of graph isomorphisms and corresponding symmetry operators that commute with the quantum walk Hamiltonian; the Hamiltonian and these symmetry operators provide a complete set of labels for the spectrum and the stationary states. Our quantum walk characterization of the chimera graph and its variants yields valuable insights into graphs used for designing quantum-annealers.

Software for Graph Analysis and Visualization

Directory of Open Access Journals (Sweden)

M. I. Kolomeychenko

2014-01-01

Full Text Available This paper describes the software for graph storage, analysis and visualization. The article presents a comparative analysis of existing software for analysis and visualization of graphs, describes the overall architecture of application and basic principles of construction and operation of the main modules. Furthermore, a description of the developed graph storage oriented to storage and processing of large-scale graphs is presented. The developed algorithm for finding communities and implemented algorithms of autolayouts of graphs are the main functionality of the product. The main advantage of the developed software is high speed processing of large size networks (up to millions of nodes and links. Moreover, the proposed graph storage architecture is unique and has no analogues. The developed approaches and algorithms are optimized for operating with big graphs and have high productivity.

What Would a Graph Look Like in this Layout? A Machine Learning Approach to Large Graph Visualization.

Science.gov (United States)

Kwon, Oh-Hyun; Crnovrsanin, Tarik; Ma, Kwan-Liu

2018-01-01

Using different methods for laying out a graph can lead to very different visual appearances, with which the viewer perceives different information. Selecting a "good" layout method is thus important for visualizing a graph. The selection can be highly subjective and dependent on the given task. A common approach to selecting a good layout is to use aesthetic criteria and visual inspection. However, fully calculating various layouts and their associated aesthetic metrics is computationally expensive. In this paper, we present a machine learning approach to large graph visualization based on computing the topological similarity of graphs using graph kernels. For a given graph, our approach can show what the graph would look like in different layouts and estimate their corresponding aesthetic metrics. An important contribution of our work is the development of a new framework to design graph kernels. Our experimental study shows that our estimation calculation is considerably faster than computing the actual layouts and their aesthetic metrics. Also, our graph kernels outperform the state-of-the-art ones in both time and accuracy. In addition, we conducted a user study to demonstrate that the topological similarity computed with our graph kernel matches perceptual similarity assessed by human users.

Text-Filled Stacked Area Graphs

DEFF Research Database (Denmark)

Kraus, Martin

2011-01-01

-filled stacked area graphs; i.e., graphs that feature stacked areas that are filled with small-typed text. Since these graphs allow for computing the text layout automatically, it is possible to include large amounts of textual detail with very little effort. We discuss the most important challenges and some...... solutions for the design of text-filled stacked area graphs with the help of an exemplary visualization of the genres, publication years, and titles of a database of several thousand PC games....

Graph Design via Convex Optimization: Online and Distributed Perspectives

Science.gov (United States)

Meng, De

Network and graph have long been natural abstraction of relations in a variety of applications, e.g. transportation, power system, social network, communication, electrical circuit, etc. As a large number of computation and optimization problems are naturally defined on graphs, graph structures not only enable important properties of these problems, but also leads to highly efficient distributed and online algorithms. For example, graph separability enables the parallelism for computation and operation as well as limits the size of local problems. More interestingly, graphs can be defined and constructed in order to take best advantage of those problem properties. This dissertation focuses on graph structure and design in newly proposed optimization problems, which establish a bridge between graph properties and optimization problem properties. We first study a new optimization problem called Geodesic Distance Maximization Problem (GDMP). Given a graph with fixed edge weights, finding the shortest path, also known as the geodesic, between two nodes is a well-studied network flow problem. We introduce the Geodesic Distance Maximization Problem (GDMP): the problem of finding the edge weights that maximize the length of the geodesic subject to convex constraints on the weights. We show that GDMP is a convex optimization problem for a wide class of flow costs, and provide a physical interpretation using the dual. We present applications of the GDMP in various fields, including optical lens design, network interdiction, and resource allocation in the control of forest fires. We develop an Alternating Direction Method of Multipliers (ADMM) by exploiting specific problem structures to solve large-scale GDMP, and demonstrate its effectiveness in numerical examples. We then turn our attention to distributed optimization on graph with only local communication. Distributed optimization arises in a variety of applications, e.g. distributed tracking and localization, estimation

VIGOR: Interactive Visual Exploration of Graph Query Results.

Science.gov (United States)

Pienta, Robert; Hohman, Fred; Endert, Alex; Tamersoy, Acar; Roundy, Kevin; Gates, Chris; Navathe, Shamkant; Chau, Duen Horng

2018-01-01

Finding patterns in graphs has become a vital challenge in many domains from biological systems, network security, to finance (e.g., finding money laundering rings of bankers and business owners). While there is significant interest in graph databases and querying techniques, less research has focused on helping analysts make sense of underlying patterns within a group of subgraph results. Visualizing graph query results is challenging, requiring effective summarization of a large number of subgraphs, each having potentially shared node-values, rich node features, and flexible structure across queries. We present VIGOR, a novel interactive visual analytics system, for exploring and making sense of query results. VIGOR uses multiple coordinated views, leveraging different data representations and organizations to streamline analysts sensemaking process. VIGOR contributes: (1) an exemplar-based interaction technique, where an analyst starts with a specific result and relaxes constraints to find other similar results or starts with only the structure (i.e., without node value constraints), and adds constraints to narrow in on specific results; and (2) a novel feature-aware subgraph result summarization. Through a collaboration with Symantec, we demonstrate how VIGOR helps tackle real-world problems through the discovery of security blindspots in a cybersecurity dataset with over 11,000 incidents. We also evaluate VIGOR with a within-subjects study, demonstrating VIGOR's ease of use over a leading graph database management system, and its ability to help analysts understand their results at higher speed and make fewer errors.

Graph transformation tool contest 2008

NARCIS (Netherlands)

Rensink, Arend; van Gorp, Pieter

This special section is the outcome of the graph transformation tool contest organised during the Graph-Based Tools (GraBaTs) 2008 workshop, which took place as a satellite event of the International Conference on Graph Transformation (ICGT) 2008. The contest involved two parts: three “off-line case

On dominator colorings in graphs

Indian Academy of Sciences (India)

colors required for a dominator coloring of G is called the dominator .... Theorem 1.3 shows that the complete graph Kn is the only connected graph of order n ... Conversely, if a graph G satisfies condition (i) or (ii), it is easy to see that χd(G) =.

Graphs with branchwidth at most three

NARCIS (Netherlands)

Bodlaender, H.L.; Thilikos, D.M.

1997-01-01

In this paper we investigate both the structure of graphs with branchwidth at most three, as well as algorithms to recognise such graphs. We show that a graph has branchwidth at most three, if and only if it has treewidth at most three and does not contain the three-dimensional binary cube graph

On the reachability and observability of path and cycle graphs

OpenAIRE

Parlangeli, Gianfranco; Notarstefano, Giuseppe

2011-01-01

In this paper we investigate the reachability and observability properties of a network system, running a Laplacian based average consensus algorithm, when the communication graph is a path or a cycle. More in detail, we provide necessary and sufficient conditions, based on simple algebraic rules from number theory, to characterize all and only the nodes from which the network system is reachable (respectively observable). Interesting immediate corollaries of our results are: (i) a path graph...

Planar graphs theory and algorithms

CERN Document Server

Nishizeki, T

1988-01-01

Collected in this volume are most of the important theorems and algorithms currently known for planar graphs, together with constructive proofs for the theorems. Many of the algorithms are written in Pidgin PASCAL, and are the best-known ones; the complexities are linear or 0(nlogn). The first two chapters provide the foundations of graph theoretic notions and algorithmic techniques. The remaining chapters discuss the topics of planarity testing, embedding, drawing, vertex- or edge-coloring, maximum independence set, subgraph listing, planar separator theorem, Hamiltonian cycles, and single- or multicommodity flows. Suitable for a course on algorithms, graph theory, or planar graphs, the volume will also be useful for computer scientists and graph theorists at the research level. An extensive reference section is included.

Graph Quasicontinuous Functions and Densely Continuous Forms

Directory of Open Access Journals (Sweden)

Lubica Hola

2017-07-01

Full Text Available Let $X, Y$ be topological spaces. A function $f: X \\to Y$ is said to be graph quasicontinuous if there is a quasicontinuous function $g: X \\to Y$ with the graph of $g$ contained in the closure of the graph of $f$. There is a close relation between the notions of graph quasicontinuous functions and minimal usco maps as well as the notions of graph quasicontinuous functions and densely continuous forms. Every function with values in a compact Hausdorff space is graph quasicontinuous; more generally every locally compact function is graph quasicontinuous.

SNAP: A General Purpose Network Analysis and Graph Mining Library.

Science.gov (United States)

Leskovec, Jure; Sosič, Rok

2016-10-01

Large networks are becoming a widely used abstraction for studying complex systems in a broad set of disciplines, ranging from social network analysis to molecular biology and neuroscience. Despite an increasing need to analyze and manipulate large networks, only a limited number of tools are available for this task. Here, we describe Stanford Network Analysis Platform (SNAP), a general-purpose, high-performance system that provides easy to use, high-level operations for analysis and manipulation of large networks. We present SNAP functionality, describe its implementational details, and give performance benchmarks. SNAP has been developed for single big-memory machines and it balances the trade-off between maximum performance, compact in-memory graph representation, and the ability to handle dynamic graphs where nodes and edges are being added or removed over time. SNAP can process massive networks with hundreds of millions of nodes and billions of edges. SNAP offers over 140 different graph algorithms that can efficiently manipulate large graphs, calculate structural properties, generate regular and random graphs, and handle attributes and meta-data on nodes and edges. Besides being able to handle large graphs, an additional strength of SNAP is that networks and their attributes are fully dynamic, they can be modified during the computation at low cost. SNAP is provided as an open source library in C++ as well as a module in Python. We also describe the Stanford Large Network Dataset, a set of social and information real-world networks and datasets, which we make publicly available. The collection is a complementary resource to our SNAP software and is widely used for development and benchmarking of graph analytics algorithms.

CORECLUSTER: A Degeneracy Based Graph Clustering Framework

OpenAIRE

Giatsidis , Christos; Malliaros , Fragkiskos; Thilikos , Dimitrios M. ,; Vazirgiannis , Michalis

2014-01-01

International audience; Graph clustering or community detection constitutes an important task forinvestigating the internal structure of graphs, with a plethora of applications in several domains. Traditional tools for graph clustering, such asspectral methods, typically suffer from high time and space complexity. In thisarticle, we present \\textsc{CoreCluster}, an efficient graph clusteringframework based on the concept of graph degeneracy, that can be used along withany known graph clusteri...

Coloring sums of extensions of certain graphs

Directory of Open Access Journals (Sweden)

Johan Kok

2017-12-01

Full Text Available We recall that the minimum number of colors that allow a proper coloring of graph $G$ is called the chromatic number of $G$ and denoted $\\chi(G$. Motivated by the introduction of the concept of the $b$-chromatic sum of a graph the concept of $\\chi'$-chromatic sum and $\\chi^+$-chromatic sum are introduced in this paper. The extended graph $G^x$ of a graph $G$ was recently introduced for certain regular graphs. This paper furthers the concepts of $\\chi'$-chromatic sum and $\\chi^+$-chromatic sum to extended paths and cycles. Bipartite graphs also receive some attention. The paper concludes with patterned structured graphs. These last said graphs are typically found in chemical and biological structures.

Co-occurrence graphs for word sense disambiguation in the biomedical domain.

Science.gov (United States)

Duque, Andres; Stevenson, Mark; Martinez-Romo, Juan; Araujo, Lourdes

2018-05-01

Word sense disambiguation is a key step for many natural language processing tasks (e.g. summarization, text classification, relation extraction) and presents a challenge to any system that aims to process documents from the biomedical domain. In this paper, we present a new graph-based unsupervised technique to address this problem. The knowledge base used in this work is a graph built with co-occurrence information from medical concepts found in scientific abstracts, and hence adapted to the specific domain. Unlike other unsupervised approaches based on static graphs such as UMLS, in this work the knowledge base takes the context of the ambiguous terms into account. Abstracts downloaded from PubMed are used for building the graph and disambiguation is performed using the personalized PageRank algorithm. Evaluation is carried out over two test datasets widely explored in the literature. Different parameters of the system are also evaluated to test robustness and scalability. Results show that the system is able to outperform state-of-the-art knowledge-based systems, obtaining more than 10% of accuracy improvement in some cases, while only requiring minimal external resources. Copyright © 2018 Elsevier B.V. All rights reserved.

An introduction to grids, graphs, and networks

CERN Document Server

Pozrikidis, C

2014-01-01

An Introduction to Grids, Graphs, and Networks aims to provide a concise introduction to graphs and networks at a level that is accessible to scientists, engineers, and students. In a practical approach, the book presents only the necessary theoretical concepts from mathematics and considers a variety of physical and conceptual configurations as prototypes or examples. The subject is timely, as the performance of networks is recognized as an important topic in the study of complex systems with applications in energy, material, and information grid transport (epitomized by the internet). The bo

Optimization Problems on Threshold Graphs

Directory of Open Access Journals (Sweden)

Elena Nechita

2010-06-01

Full Text Available During the last three decades, different types of decompositions have been processed in the field of graph theory. Among these we mention: decompositions based on the additivity of some characteristics of the graph, decompositions where the adjacency law between the subsets of the partition is known, decompositions where the subgraph induced by every subset of the partition must have predeterminate properties, as well as combinations of such decompositions. In this paper we characterize threshold graphs using the weakly decomposition, determine: density and stability number, Wiener index and Wiener polynomial for threshold graphs.

Hierarchy of modular graph identities

Energy Technology Data Exchange (ETDEWEB)

D’Hoker, Eric; Kaidi, Justin [Mani L. Bhaumik Institute for Theoretical Physics, Department of Physics and Astronomy,University of California,Los Angeles, CA 90095 (United States)

2016-11-09

The low energy expansion of Type II superstring amplitudes at genus one is organized in terms of modular graph functions associated with Feynman graphs of a conformal scalar field on the torus. In earlier work, surprising identities between two-loop graphs at all weights, and between higher-loop graphs of weights four and five were constructed. In the present paper, these results are generalized in two complementary directions. First, all identities at weight six and all dihedral identities at weight seven are obtained and proven. Whenever the Laurent polynomial at the cusp is available, the form of these identities confirms the pattern by which the vanishing of the Laurent polynomial governs the full modular identity. Second, the family of modular graph functions is extended to include all graphs with derivative couplings and worldsheet fermions. These extended families of modular graph functions are shown to obey a hierarchy of inhomogeneous Laplace eigenvalue equations. The eigenvalues are calculated analytically for the simplest infinite sub-families and obtained by Maple for successively more complicated sub-families. The spectrum is shown to consist solely of eigenvalues s(s−1) for positive integers s bounded by the weight, with multiplicities which exhibit rich representation-theoretic patterns.

Hierarchy of modular graph identities

International Nuclear Information System (INIS)

D’Hoker, Eric; Kaidi, Justin

2016-01-01

The low energy expansion of Type II superstring amplitudes at genus one is organized in terms of modular graph functions associated with Feynman graphs of a conformal scalar field on the torus. In earlier work, surprising identities between two-loop graphs at all weights, and between higher-loop graphs of weights four and five were constructed. In the present paper, these results are generalized in two complementary directions. First, all identities at weight six and all dihedral identities at weight seven are obtained and proven. Whenever the Laurent polynomial at the cusp is available, the form of these identities confirms the pattern by which the vanishing of the Laurent polynomial governs the full modular identity. Second, the family of modular graph functions is extended to include all graphs with derivative couplings and worldsheet fermions. These extended families of modular graph functions are shown to obey a hierarchy of inhomogeneous Laplace eigenvalue equations. The eigenvalues are calculated analytically for the simplest infinite sub-families and obtained by Maple for successively more complicated sub-families. The spectrum is shown to consist solely of eigenvalues s(s−1) for positive integers s bounded by the weight, with multiplicities which exhibit rich representation-theoretic patterns.

Well-covered graphs and factors

DEFF Research Database (Denmark)

Randerath, Bert; Vestergaard, Preben D.

2006-01-01

A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality α. Plummer defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. Every well-covered graph G without isolated vertices has a perf...

On the centrality of some graphs

Directory of Open Access Journals (Sweden)

Vecdi Aytac

2017-10-01

Full Text Available A central issue in the analysis of complex networks is the assessment of their stability and vulnerability. A variety of measures have been proposed in the literature to quantify the stability of networks and a number of graph-theoretic parameters have been used to derive formulas for calculating network reliability. Different measures for graph vulnerability have been introduced so far to study different aspects of the graph behavior after removal of vertices or links such as connectivity, toughness, scattering number, binding number, residual closeness and integrity. In this paper, we consider betweenness centrality of a graph. Betweenness centrality of a vertex of a graph is portion of the shortest paths all pairs of vertices passing through a given vertex. In this paper, we obtain exact values for betweenness centrality for some wheel related graphs namely gear, helm, sunflower and friendship graphs.

Matching of renewable source of energy generation graphs and electrical load in local energy system

Science.gov (United States)

Lezhniuk, Petro; Komar, Vyacheslav; Sobchuk, Dmytro; Kravchuk, Sergiy; Kacejko, Piotr; Zavidsky, Vladislav

2017-08-01

The paper contains the method of matching generation graph of photovoltaic electric stations and consumers. Characteristic feature of this method is the application of morphometric analysis for assessment of non-uniformity of the integrated graph of energy supply, optimal coefficients of current distribution, that enables by mean of refining the powers, transferring in accordance with the graph , to provide the decrease of electric energy losses in the grid and transport task, as the optimization tool.

On 4-critical t-perfect graphs

OpenAIRE

Benchetrit, Yohann

2016-01-01

It is an open question whether the chromatic number of $t$-perfect graphs is bounded by a constant. The largest known value for this parameter is 4, and the only example of a 4-critical $t$-perfect graph, due to Laurent and Seymour, is the complement of the line graph of the prism $\\Pi$ (a graph is 4-critical if it has chromatic number 4 and all its proper induced subgraphs are 3-colorable). In this paper, we show a new example of a 4-critical $t$-perfect graph: the complement of the line gra...

A librarian's guide to graphs, data and the semantic web

CERN Document Server

Powell, James

2015-01-01

Graphs are about connections, and are an important part of our connected and data-driven world. A Librarian's Guide to Graphs, Data and the Semantic Web is geared toward library and information science professionals, including librarians, software developers and information systems architects who want to understand the fundamentals of graph theory, how it is used to represent and explore data, and how it relates to the semantic web. This title provides a firm grounding in the field at a level suitable for a broad audience, with an emphasis on open source solutions and what problems these tools solve at a conceptual level, with minimal emphasis on algorithms or mathematics. The text will also be of special interest to data science librarians and data professionals, since it introduces many graph theory concepts by exploring data-driven networks from various scientific disciplines. The first two chapters consider graphs in theory and the science of networks, before the following chapters cover networks in vario...

Expert interpretation of bar and line graphs: The role of graphicacy in reducing the effect of graph format.

Directory of Open Access Journals (Sweden)

David ePeebles

2015-10-01

Full Text Available The distinction between informational and computational equivalence of representations, first articulated by Larkin and Simon (1987 has been a fundamental principle in the analysis of diagrammatic reasoning which has been supported empirically on numerous occasions. We present an experiment that investigates this principle in relation to the performance of expert graph users of 2 x 2 'interaction' bar and line graphs. The study sought to determine whether expert interpretation is affected by graph format in the same way that novice interpretations are. The findings revealed that, unlike novices - and contrary to the assumptions of several graph comprehension models - experts' performance was the same for both graph formats, with their interpretation of bar graphs being no worse than that for line graphs. We discuss the implications of the study for guidelines for presenting such data and for models of expert graph comprehension.

DIMENSI METRIK GRAPH LOBSTER Ln (q;r

Directory of Open Access Journals (Sweden)

PANDE GDE DONY GUMILAR

2013-05-01

Full Text Available The metric dimension of connected graph G is the cardinality of minimum resolving set in graph G. In this research, we study how to find the metric dimension of lobster graph Ln (q;r. Lobster graph Ln (q;r is a regular lobster graph with vertices backbone on the main path, every backbone vertex is connected to q hand vertices and every hand vertex is connected to r finger vertices, with n, q, r element of N. We obtain the metric dimension of lobster graph L2 (1;1 is 1, the metric dimension of lobster graph L2 (1;1 for n > 2 is 2.

Rapidly Responsive and Flexible Chiral Nematic Cellulose Nanocrystal Composites as Multifunctional Rewritable Photonic Papers with Eco-Friendly Inks.

Science.gov (United States)

Wan, Hao; Li, Xiaofeng; Zhang, Liang; Li, Xiaopeng; Liu, Pengfei; Jiang, Zhiguo; Yu, Zhong-Zhen

2018-02-14

Rapidly responsive and flexible photonic papers are manufactured by coassembly of cellulose nanocrystals (CNCs) and waterborne polyurethane (WPU) latex for fully taking advantage of the chiral nematic structure of CNCs and the flexibility of WPU elastomer. The resulting CNC/WPU composite papers exhibit not only tunable iridescent colors by adjusting the helical pitch size, but also instant optical responses to water and wet gas, ascribed to the easy chain movement of the elastomeric WPU that does not restrict the fast water absorption-induced swelling of CNCs. By choosing water or NaCl aqueous solutions as inks, the colorful patterns on the CNC/WPU photonic paper can be made temporary, durable, or even disguisable. In addition, the photonic paper is simultaneously rewritable for all these three types of patterns, and the disguisable patterns, which are invisible at normal times and show up under stimuli, exhibit a quick reveal conversion just by exhaling on the paper. The rewritability, rapid responsibility, easy fabrication, and the eco-friendly nature of the inks make the flexible photonic paper/ink combination highly promising in sensors, displays, and photonic circuits.

Interactive Graph Layout of a Million Nodes

Directory of Open Access Journals (Sweden)

Peng Mi

2016-12-01

Full Text Available Sensemaking of large graphs, specifically those with millions of nodes, is a crucial task in many fields. Automatic graph layout algorithms, augmented with real-time human-in-the-loop interaction, can potentially support sensemaking of large graphs. However, designing interactive algorithms to achieve this is challenging. In this paper, we tackle the scalability problem of interactive layout of large graphs, and contribute a new GPU-based force-directed layout algorithm that exploits graph topology. This algorithm can interactively layout graphs with millions of nodes, and support real-time interaction to explore alternative graph layouts. Users can directly manipulate the layout of vertices in a force-directed fashion. The complexity of traditional repulsive force computation is reduced by approximating calculations based on the hierarchical structure of multi-level clustered graphs. We evaluate the algorithm performance, and demonstrate human-in-the-loop layout in two sensemaking case studies. Moreover, we summarize lessons learned for designing interactive large graph layout algorithms on the GPU.

Eulerian Graphs and Related Topics

CERN Document Server

Fleischner, Herbert

1990-01-01

The two volumes comprising Part 1 of this work embrace the theme of Eulerian trails and covering walks. They should appeal both to researchers and students, as they contain enough material for an undergraduate or graduate graph theory course which emphasizes Eulerian graphs, and thus can be read by any mathematician not yet familiar with graph theory. But they are also of interest to researchers in graph theory because they contain many recent results, some of which are only partial solutions to more general problems. A number of conjectures have been included as well. Various problems (such a

Degree-based graph construction

International Nuclear Information System (INIS)

Kim, Hyunju; Toroczkai, Zoltan; Erdos, Peter L; Miklos, Istvan; Szekely, Laszlo A

2009-01-01

Degree-based graph construction is a ubiquitous problem in network modelling (Newman et al 2006 The Structure and Dynamics of Networks (Princeton Studies in Complexity) (Princeton, NJ: Princeton University Press), Boccaletti et al 2006 Phys. Rep. 424 175), ranging from social sciences to chemical compounds and biochemical reaction networks in the cell. This problem includes existence, enumeration, exhaustive construction and sampling questions with aspects that are still open today. Here we give necessary and sufficient conditions for a sequence of nonnegative integers to be realized as a simple graph's degree sequence, such that a given (but otherwise arbitrary) set of connections from an arbitrarily given node is avoided. We then use this result to present a swap-free algorithm that builds all simple graphs realizing a given degree sequence. In a wider context, we show that our result provides a greedy construction method to build all the f-factor subgraphs (Tutte 1952 Can. J. Math. 4 314) embedded within K n setmn S k , where K n is the complete graph and S k is a star graph centred on one of the nodes. (fast track communication)

Chaotic Traversal (CHAT): Very Large Graphs Traversal Using Chaotic Dynamics

Science.gov (United States)

Changaival, Boonyarit; Rosalie, Martin; Danoy, Grégoire; Lavangnananda, Kittichai; Bouvry, Pascal

2017-12-01

Graph Traversal algorithms can find their applications in various fields such as routing problems, natural language processing or even database querying. The exploration can be considered as a first stepping stone into knowledge extraction from the graph which is now a popular topic. Classical solutions such as Breadth First Search (BFS) and Depth First Search (DFS) require huge amounts of memory for exploring very large graphs. In this research, we present a novel memoryless graph traversal algorithm, Chaotic Traversal (CHAT) which integrates chaotic dynamics to traverse large unknown graphs via the Lozi map and the Rössler system. To compare various dynamics effects on our algorithm, we present an original way to perform the exploration of a parameter space using a bifurcation diagram with respect to the topological structure of attractors. The resulting algorithm is an efficient and nonresource demanding algorithm, and is therefore very suitable for partial traversal of very large and/or unknown environment graphs. CHAT performance using Lozi map is proven superior than the, commonly known, Random Walk, in terms of number of nodes visited (coverage percentage) and computation time where the environment is unknown and memory usage is restricted.

Downhill Domination in Graphs

Directory of Open Access Journals (Sweden)

Haynes Teresa W.

2014-08-01

Full Text Available A path π = (v1, v2, . . . , vk+1 in a graph G = (V,E is a downhill path if for every i, 1 ≤ i ≤ k, deg(vi ≥ deg(vi+1, where deg(vi denotes the degree of vertex vi ∈ V. The downhill domination number equals the minimum cardinality of a set S ⊆ V having the property that every vertex v ∈ V lies on a downhill path originating from some vertex in S. We investigate downhill domination numbers of graphs and give upper bounds. In particular, we show that the downhill domination number of a graph is at most half its order, and that the downhill domination number of a tree is at most one third its order. We characterize the graphs obtaining each of these bounds

Subsampling for graph power spectrum estimation

KAUST Repository

Chepuri, Sundeep Prabhakar; Leus, Geert

2016-01-01

In this paper we focus on subsampling stationary random signals that reside on the vertices of undirected graphs. Second-order stationary graph signals are obtained by filtering white noise and they admit a well-defined power spectrum. Estimating the graph power spectrum forms a central component of stationary graph signal processing and related inference tasks. We show that by sampling a significantly smaller subset of vertices and using simple least squares, we can reconstruct the power spectrum of the graph signal from the subsampled observations, without any spectral priors. In addition, a near-optimal greedy algorithm is developed to design the subsampling scheme.

Proving relations between modular graph functions

International Nuclear Information System (INIS)

Basu, Anirban

2016-01-01

We consider modular graph functions that arise in the low energy expansion of the four graviton amplitude in type II string theory. The vertices of these graphs are the positions of insertions of vertex operators on the toroidal worldsheet, while the links are the scalar Green functions connecting the vertices. Graphs with four and five links satisfy several non-trivial relations, which have been proved recently. We prove these relations by using elementary properties of Green functions and the details of the graphs. We also prove a relation between modular graph functions with six links. (paper)

Subsampling for graph power spectrum estimation

KAUST Repository

Chepuri, Sundeep Prabhakar

2016-10-06

In this paper we focus on subsampling stationary random signals that reside on the vertices of undirected graphs. Second-order stationary graph signals are obtained by filtering white noise and they admit a well-defined power spectrum. Estimating the graph power spectrum forms a central component of stationary graph signal processing and related inference tasks. We show that by sampling a significantly smaller subset of vertices and using simple least squares, we can reconstruct the power spectrum of the graph signal from the subsampled observations, without any spectral priors. In addition, a near-optimal greedy algorithm is developed to design the subsampling scheme.

Semantic graphs and associative memories

Science.gov (United States)

Pomi, Andrés; Mizraji, Eduardo

2004-12-01

Graphs have been increasingly utilized in the characterization of complex networks from diverse origins, including different kinds of semantic networks. Human memories are associative and are known to support complex semantic nets; these nets are represented by graphs. However, it is not known how the brain can sustain these semantic graphs. The vision of cognitive brain activities, shown by modern functional imaging techniques, assigns renewed value to classical distributed associative memory models. Here we show that these neural network models, also known as correlation matrix memories, naturally support a graph representation of the stored semantic structure. We demonstrate that the adjacency matrix of this graph of associations is just the memory coded with the standard basis of the concept vector space, and that the spectrum of the graph is a code invariant of the memory. As long as the assumptions of the model remain valid this result provides a practical method to predict and modify the evolution of the cognitive dynamics. Also, it could provide us with a way to comprehend how individual brains that map the external reality, almost surely with different particular vector representations, are nevertheless able to communicate and share a common knowledge of the world. We finish presenting adaptive association graphs, an extension of the model that makes use of the tensor product, which provides a solution to the known problem of branching in semantic nets.

A Multi-Addressable Dyad with Switchable CMY Colors for Full-Color Rewritable Papers.

Science.gov (United States)

Qin, Tianyou; Han, Jiaqi; Geng, Yue; Ju, Le; Sheng, Lan; Zhang, Sean Xiao-An

2018-06-23

Reversible multicolor displays on solid media using single molecule pigments have been a long-awaited goal. Herein, a new and simple molecular dyad, which can undergo switchable CMY color changes both in solution and solid substrate upon exposure to light, water/acid, and nucleophiles, is designed and synthesized. The stimuli used in this work can be applied independent of each other, which is beneficial for color changes without mutual interference. As a comparison, the mixtures of the two molecular switching motifs forming the basis of the dyad were also studied. The dyad greatly outperforms the corresponding mixed system with respect to reversible color-switching on the paper substrate. Its potential for full-color rewritable paper with excellent reversibility has been demonstrated. Legible multicolor prints, that is, high color contrast and resolution, good dispersion, excellent reversibility, were achieved using common water-jet and light-based printers. This work provides a very promising approach for further development of full-color switchable molecules, materials and displays. © 2018 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.

A generalization of total graphs

Indian Academy of Sciences (India)

M Afkhami

2018-04-12

Apr 12, 2018 ... product of any lower triangular matrix with the transpose of any element of U belongs to U. The ... total graph of R, which is denoted by T( (R)), is a simple graph with all elements of R as vertices, and ...... [9] Badawi A, On dot-product graph of a commutative ring, Communications in Algebra 43 (2015). 43–50.

The Politics of Rewriting History: New History Textbooks and Curriculum Materials in Russia

Science.gov (United States)

Zajda, Joseph; Zajda, Rea

2003-07-01

The collapse of communism in Russia in 1991 necessitated, among other things, the rewriting of school history textbooks, which had been dominated by Marxist-Leninist interpretations of historical events. The aim of this article is to evaluate the new postcommunist history taught in upper secondary schools, giving particular attention to how the models for Russian identity presented in the new textbooks redefine legitimate culture for students. Attention will also be given to the multiple perspectives on history that textbooks and other curriculum materials emphasize; these new methods contrast with the grand narrative that dominated the study of history before 1991.

Decomposing a planar graph into an independent set and a 3-degenerate graph

DEFF Research Database (Denmark)

Thomassen, Carsten

2001-01-01

We prove the conjecture made by O. V. Borodin in 1976 that the vertex set of every planar graph can be decomposed into an independent set and a set inducing a 3-degenerate graph. (C) 2001 Academic Press....

Rewritable three-dimensional holographic data storage via optical forces

Energy Technology Data Exchange (ETDEWEB)

Yetisen, Ali K., E-mail: ayetisen@mgh.harvard.edu [Harvard Medical School and Wellman Center for Photomedicine, Massachusetts General Hospital, 65 Landsdowne Street, Cambridge, Massachusetts 02139 (United States); Harvard-MIT Division of Health Sciences and Technology, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139 (United States); Montelongo, Yunuen [Department of Chemistry, Imperial College London, South Kensington Campus, London SW7 2AZ (United Kingdom); Butt, Haider [Nanotechnology Laboratory, School of Engineering Sciences, University of Birmingham, Birmingham B15 2TT (United Kingdom)

2016-08-08

The development of nanostructures that can be reversibly arranged and assembled into 3D patterns may enable optical tunability. However, current dynamic recording materials such as photorefractive polymers cannot be used to store information permanently while also retaining configurability. Here, we describe the synthesis and optimization of a silver nanoparticle doped poly(2-hydroxyethyl methacrylate-co-methacrylic acid) recording medium for reversibly recording 3D holograms. We theoretically and experimentally demonstrate organizing nanoparticles into 3D assemblies in the recording medium using optical forces produced by the gradients of standing waves. The nanoparticles in the recording medium are organized by multiple nanosecond laser pulses to produce reconfigurable slanted multilayer structures. We demonstrate the capability of producing rewritable optical elements such as multilayer Bragg diffraction gratings, 1D photonic crystals, and 3D multiplexed optical gratings. We also show that 3D virtual holograms can be reversibly recorded. This recording strategy may have applications in reconfigurable optical elements, data storage devices, and dynamic holographic displays.

A searching and reporting system for relational databases using a graph-based metadata representation.

Science.gov (United States)

Hewitt, Robin; Gobbi, Alberto; Lee, Man-Ling

2005-01-01

Relational databases are the current standard for storing and retrieving data in the pharmaceutical and biotech industries. However, retrieving data from a relational database requires specialized knowledge of the database schema and of the SQL query language. At Anadys, we have developed an easy-to-use system for searching and reporting data in a relational database to support our drug discovery project teams. This system is fast and flexible and allows users to access all data without having to write SQL queries. This paper presents the hierarchical, graph-based metadata representation and SQL-construction methods that, together, are the basis of this system's capabilities.

Commuting graphs of matrix algebras

International Nuclear Information System (INIS)

Akbari, S.; Bidkhori, H.; Mohammadian, A.

2006-08-01

The commuting graph of a ring R, denoted by Γ(R), is a graph whose vertices are all non- central elements of R and two distinct vertices x and y are adjacent if and only if xy = yx. The commuting graph of a group G, denoted by Γ(G), is similarly defined. In this paper we investigate some graph theoretic properties of Γ(M n (F)), where F is a field and n ≥ 2. Also we study the commuting graphs of some classical groups such as GL n (F) and SL n (F). We show that Γ(M n (F)) is a connected graph if and only if every field extension of F of degree n contains a proper intermediate field. We prove that apart from finitely many fields, a similar result is true for Γ(GL n (F)) and Γ(SL n (F)). Also we show that for two fields E and F and integers m, n ≥> 2, if Γ(M m (E)) ≅ Γ(M n (F)), then m = n and vertical bar E vertical bar = vertical bar F vertical bar. (author)

Like Water for Chocolate: The Rewriting of the Female Experience and Its Parallels in Philippine History

Directory of Open Access Journals (Sweden)

Marikit Tara Alto Uychoco

2012-06-01

Full Text Available This article focuses on Laura Esquivel’s Like Water for Chocolate and reads the novel using the literary theories of the “new mestiza,” postcolonial theories, feminist theories, and historiographic metafiction. It seeks to find out how this novel rewrites the female experience of the Mexican Revolution, and the various techniques used in the rewriting of history. It reads the novel from a “new mestiza” feminist perspective, which enables the Filipina reader to find commonalities in the Mexican woman’s struggle in Mexican history and society, and finds ways to help her appreciate the Filipina’s struggle in Philippine history and society. The theories of historiographic metafiction are grounded in Linda Hutcheon’s theories about historiography, or the writing of history, and metafiction, or fiction that makes us aware of the craft of fiction. The theories regarding the “new mestiza” consciousness are from Gloria Anzaldua. This is a feminist theory that is contextualized on the historic oppression of women during Spanish colonization and its resulting patriarchal structures in society, and how women can seek to free themselves from such residual structures. Finally, the article touches upon a Filipina feminist perspective on the novel and what it signifies for the Philippine female experience.

Graph-theoretical concepts and physicochemical data

Directory of Open Access Journals (Sweden)

Lionello Pogliani

2003-02-01

Full Text Available Graph theoretical concepts have been used to model the molecular polarizabilities of fifty-four organic derivatives, and the induced dipole moment of a set of fifty-seven organic compounds divided into three subsets. The starting point of these modeling strategies is the hydrogen-suppressed chemical graph and pseudograph of a molecule, which works very well for second row atoms. From these types of graphs a set of graph-theoretical basis indices, the molecular connectivity indices, can be derived and used to model properties and activities of molecules. With the aid of the molecular connectivity basis indices it is then possible to build higher-order descriptors. The problem of 'graph' encoding the contribution of the inner-core electrons of heteroatoms can here be solved with the aid of odd complete graphs, Kp-(p-odd. The use of these graph tools allow to draw an optimal modeling of the molecular polarizabilities and a satisfactory modeling of the induced dipole moment of a wide set of organic derivatives.

Graphs whose complement and square are isomorphic

DEFF Research Database (Denmark)

Pedersen, Anders Sune

2014-01-01

We study square-complementary graphs, that is, graphs whose complement and square are isomorphic. We prove several necessary conditions for a graph to be square-complementary, describe ways of building new square-complementary graphs from existing ones, construct infinite families of square-compl...

Graphs & digraphs

CERN Document Server

Chartrand, Gary; Zhang, Ping

2010-01-01

Gary Chartrand has influenced the world of Graph Theory for almost half a century. He has supervised more than a score of Ph.D. dissertations and written several books on the subject. The most widely known of these texts, Graphs and Digraphs, … has much to recommend it, with clear exposition, and numerous challenging examples [that] make it an ideal textbook for the advanced undergraduate or beginning graduate course. The authors have updated their notation to reflect the current practice in this still-growing area of study. By the authors' estimation, the 5th edition is approximately 50% longer than the 4th edition. … the legendary Frank Harary, author of the second graph theory text ever produced, is one of the figures profiled. His book was the standard in the discipline for several decades. Chartrand, Lesniak and Zhang have produced a worthy successor.-John T. Saccoman, MAA Reviews, June 2012 (This book is in the MAA's basic library list.)As with the earlier editions, the current text emphasizes clear...

Packing Degenerate Graphs Greedily

Czech Academy of Sciences Publication Activity Database

Allen, P.; Böttcher, J.; Hladký, J.; Piguet, Diana

2017-01-01

Roč. 61, August (2017), s. 45-51 ISSN 1571-0653 R&D Projects: GA ČR GJ16-07822Y Institutional support: RVO:67985807 Keywords : tree packing conjecture * graph packing * graph processes Subject RIV: BA - General Mathematics OBOR OECD: Pure mathematics

Continuous-time quantum walks on star graphs

International Nuclear Information System (INIS)

Salimi, S.

2009-01-01

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

The Smallest Valid Extension-Based Efficient, Rare Graph Pattern Mining, Considering Length-Decreasing Support Constraints and Symmetry Characteristics of Graphs

Directory of Open Access Journals (Sweden)

Unil Yun

2016-05-01

Full Text Available Frequent graph mining has been proposed to find interesting patterns (i.e., frequent sub-graphs from databases composed of graph transaction data, which can effectively express complex and large data in the real world. In addition, various applications for graph mining have been suggested. Traditional graph pattern mining methods use a single minimum support threshold factor in order to check whether or not mined patterns are interesting. However, it is not a sufficient factor that can consider valuable characteristics of graphs such as graph sizes and features of graph elements. That is, previous methods cannot consider such important characteristics in their mining operations since they only use a fixed minimum support threshold in the mining process. For this reason, in this paper, we propose a novel graph mining algorithm that can consider various multiple, minimum support constraints according to the types of graph elements and changeable minimum support conditions, depending on lengths of graph patterns. In addition, the proposed algorithm performs in mining operations more efficiently because it can minimize duplicated operations and computational overheads by considering symmetry features of graphs. Experimental results provided in this paper demonstrate that the proposed algorithm outperforms previous mining approaches in terms of pattern generation, runtime and memory usage.

Random graph states, maximal flow and Fuss-Catalan distributions

International Nuclear Information System (INIS)

Collins, BenoIt; Nechita, Ion; Zyczkowski, Karol

2010-01-01

For any graph consisting of k vertices and m edges we construct an ensemble of random pure quantum states which describe a system composed of 2m subsystems. Each edge of the graph represents a bipartite, maximally entangled state. Each vertex represents a random unitary matrix generated according to the Haar measure, which describes the coupling between subsystems. Dividing all subsystems into two parts, one may study entanglement with respect to this partition. A general technique to derive an expression for the average entanglement entropy of random pure states associated with a given graph is presented. Our technique relies on Weingarten calculus and flow problems. We analyze the statistical properties of spectra of such random density matrices and show for which cases they are described by the free Poissonian (Marchenko-Pastur) distribution. We derive a discrete family of generalized, Fuss-Catalan distributions and explicitly construct graphs which lead to ensembles of random states characterized by these novel distributions of eigenvalues.

PDB2Graph: A toolbox for identifying critical amino acids map in proteins based on graph theory.

Science.gov (United States)

Niknam, Niloofar; Khakzad, Hamed; Arab, Seyed Shahriar; Naderi-Manesh, Hossein

2016-05-01

The integrative and cooperative nature of protein structure involves the assessment of topological and global features of constituent parts. Network concept takes complete advantage of both of these properties in the analysis concomitantly. High compatibility to structural concepts or physicochemical properties in addition to exploiting a remarkable simplification in the system has made network an ideal tool to explore biological systems. There are numerous examples in which different protein structural and functional characteristics have been clarified by the network approach. Here, we present an interactive and user-friendly Matlab-based toolbox, PDB2Graph, devoted to protein structure network construction, visualization, and analysis. Moreover, PDB2Graph is an appropriate tool for identifying critical nodes involved in protein structural robustness and function based on centrality indices. It maps critical amino acids in protein networks and can greatly aid structural biologists in selecting proper amino acid candidates for manipulating protein structures in a more reasonable and rational manner. To introduce the capability and efficiency of PDB2Graph in detail, the structural modification of Calmodulin through allosteric binding of Ca(2+) is considered. In addition, a mutational analysis for three well-identified model proteins including Phage T4 lysozyme, Barnase and Ribonuclease HI, was performed to inspect the influence of mutating important central residues on protein activity. Copyright © 2016 Elsevier Ltd. All rights reserved.

Relating zeta functions of discrete and quantum graphs

Science.gov (United States)

Harrison, Jonathan; Weyand, Tracy

2018-02-01

We write the spectral zeta function of the Laplace operator on an equilateral metric graph in terms of the spectral zeta function of the normalized Laplace operator on the corresponding discrete graph. To do this, we apply a relation between the spectrum of the Laplacian on a discrete graph and that of the Laplacian on an equilateral metric graph. As a by-product, we determine how the multiplicity of eigenvalues of the quantum graph, that are also in the spectrum of the graph with Dirichlet conditions at the vertices, depends on the graph geometry. Finally we apply the result to calculate the vacuum energy and spectral determinant of a complete bipartite graph and compare our results with those for a star graph, a graph in which all vertices are connected to a central vertex by a single edge.

Recognition of fractal graphs

NARCIS (Netherlands)

Perepelitsa, VA; Sergienko, [No Value; Kochkarov, AM

1999-01-01

Definitions of prefractal and fractal graphs are introduced, and they are used to formulate mathematical models in different fields of knowledge. The topicality of fractal-graph recognition from the point of view, of fundamental improvement in the efficiency of the solution of algorithmic problems

Interactive Graph Layout of a Million Nodes

OpenAIRE

Peng Mi; Maoyuan Sun; Moeti Masiane; Yong Cao; Chris North

2016-01-01

Sensemaking of large graphs, specifically those with millions of nodes, is a crucial task in many fields. Automatic graph layout algorithms, augmented with real-time human-in-the-loop interaction, can potentially support sensemaking of large graphs. However, designing interactive algorithms to achieve this is challenging. In this paper, we tackle the scalability problem of interactive layout of large graphs, and contribute a new GPU-based force-directed layout algorithm that exploits graph to...

GRAPES: a software for parallel searching on biological graphs targeting multi-core architectures.

Directory of Open Access Journals (Sweden)

Rosalba Giugno

Full Text Available Biological applications, from genomics to ecology, deal with graphs that represents the structure of interactions. Analyzing such data requires searching for subgraphs in collections of graphs. This task is computationally expensive. Even though multicore architectures, from commodity computers to more advanced symmetric multiprocessing (SMP, offer scalable computing power, currently published software implementations for indexing and graph matching are fundamentally sequential. As a consequence, such software implementations (i do not fully exploit available parallel computing power and (ii they do not scale with respect to the size of graphs in the database. We present GRAPES, software for parallel searching on databases of large biological graphs. GRAPES implements a parallel version of well-established graph searching algorithms, and introduces new strategies which naturally lead to a faster parallel searching system especially for large graphs. GRAPES decomposes graphs into subcomponents that can be efficiently searched in parallel. We show the performance of GRAPES on representative biological datasets containing antiviral chemical compounds, DNA, RNA, proteins, protein contact maps and protein interactions networks.

RATGRAPH: Computer Graphing of Rational Functions.

Science.gov (United States)

Minch, Bradley A.

1987-01-01

Presents an easy-to-use Applesoft BASIC program that graphs rational functions and any asymptotes that the functions might have. Discusses the nature of rational functions, graphing them manually, employing a computer to graph rational functions, and describes how the program works. (TW)

Graph algorithms in the titan toolkit.

Energy Technology Data Exchange (ETDEWEB)

McLendon, William Clarence, III; Wylie, Brian Neil

2009-10-01

Graph algorithms are a key component in a wide variety of intelligence analysis activities. The Graph-Based Informatics for Non-Proliferation and Counter-Terrorism project addresses the critical need of making these graph algorithms accessible to Sandia analysts in a manner that is both intuitive and effective. Specifically we describe the design and implementation of an open source toolkit for doing graph analysis, informatics, and visualization that provides Sandia with novel analysis capability for non-proliferation and counter-terrorism.

A Graph Calculus for Predicate Logic

Directory of Open Access Journals (Sweden)

Paulo A. S. Veloso

2013-03-01

Full Text Available We introduce a refutation graph calculus for classical first-order predicate logic, which is an extension of previous ones for binary relations. One reduces logical consequence to establishing that a constructed graph has empty extension, i. e. it represents bottom. Our calculus establishes that a graph has empty extension by converting it to a normal form, which is expanded to other graphs until we can recognize conflicting situations (equivalent to a formula and its negation.

Deep Learning with Dynamic Computation Graphs

OpenAIRE

Looks, Moshe; Herreshoff, Marcello; Hutchins, DeLesley; Norvig, Peter

2017-01-01

Neural networks that compute over graph structures are a natural fit for problems in a variety of domains, including natural language (parse trees) and cheminformatics (molecular graphs). However, since the computation graph has a different shape and size for every input, such networks do not directly support batched training or inference. They are also difficult to implement in popular deep learning libraries, which are based on static data-flow graphs. We introduce a technique called dynami...

Quantum chaos on discrete graphs

International Nuclear Information System (INIS)

Smilansky, Uzy

2007-01-01

Adapting a method developed for the study of quantum chaos on quantum (metric) graphs (Kottos and Smilansky 1997 Phys. Rev. Lett. 79 4794, Kottos and Smilansky 1999 Ann. Phys., NY 274 76), spectral ζ functions and trace formulae for discrete Laplacians on graphs are derived. This is achieved by expressing the spectral secular equation in terms of the periodic orbits of the graph and obtaining functions which belong to the class of ζ functions proposed originally by Ihara (1966 J. Mat. Soc. Japan 18 219) and expanded by subsequent authors (Stark and Terras 1996 Adv. Math. 121 124, Kotani and Sunada 2000 J. Math. Sci. Univ. Tokyo 7 7). Finally, a model of 'classical dynamics' on the discrete graph is proposed. It is analogous to the corresponding classical dynamics derived for quantum graphs (Kottos and Smilansky 1997 Phys. Rev. Lett. 79 4794, Kottos and Smilansky 1999 Ann. Phys., NY 274 76). (fast track communication)

RJSplot: Interactive Graphs with R.

Science.gov (United States)

Barrios, David; Prieto, Carlos

2018-03-01

Data visualization techniques provide new methods for the generation of interactive graphs. These graphs allow a better exploration and interpretation of data but their creation requires advanced knowledge of graphical libraries. Recent packages have enabled the integration of interactive graphs in R. However, R provides limited graphical packages that allow the generation of interactive graphs for computational biology applications. The present project has joined the analytical power of R with the interactive graphical features of JavaScript in a new R package (RJSplot). It enables the easy generation of interactive graphs in R, provides new visualization capabilities, and contributes to the advance of computational biology analytical methods. At present, 16 interactive graphics are available in RJSplot, such as the genome viewer, Manhattan plots, 3D plots, heatmaps, dendrograms, networks, and so on. The RJSplot package is freely available online at http://rjsplot.net. © 2018 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim.

Dynamic Allocation of SPM Based on Time-Slotted Cache Conflict Graph for System Optimization

Science.gov (United States)

Wu, Jianping; Ling, Ming; Zhang, Yang; Mei, Chen; Wang, Huan

This paper proposes a novel dynamic Scratch-pad Memory allocation strategy to optimize the energy consumption of the memory sub-system. Firstly, the whole program execution process is sliced into several time slots according to the temporal dimension; thereafter, a Time-Slotted Cache Conflict Graph (TSCCG) is introduced to model the behavior of Data Cache (D-Cache) conflicts within each time slot. Then, Integer Nonlinear Programming (INP) is implemented, which can avoid time-consuming linearization process, to select the most profitable data pages. Virtual Memory System (VMS) is adopted to remap those data pages, which will cause severe Cache conflicts within a time slot, to SPM. In order to minimize the swapping overhead of dynamic SPM allocation, a novel SPM controller with a tightly coupled DMA is introduced to issue the swapping operations without CPU's intervention. Last but not the least, this paper discusses the fluctuation of system energy profit based on different MMU page size as well as the Time Slot duration quantitatively. According to our design space exploration, the proposed method can optimize all of the data segments, including global data, heap and stack data in general, and reduce the total energy consumption by 27.28% on average, up to 55.22% with a marginal performance promotion. And comparing to the conventional static CCG (Cache Conflicts Graph), our approach can obtain 24.7% energy profit on average, up to 30.5% with a sight boost in performance.

Bipartite separability and nonlocal quantum operations on graphs

Science.gov (United States)

Dutta, Supriyo; Adhikari, Bibhas; Banerjee, Subhashish; Srikanth, R.

2016-07-01

In this paper we consider the separability problem for bipartite quantum states arising from graphs. Earlier it was proved that the degree criterion is the graph-theoretic counterpart of the familiar positive partial transpose criterion for separability, although there are entangled states with positive partial transpose for which the degree criterion fails. Here we introduce the concept of partially symmetric graphs and degree symmetric graphs by using the well-known concept of partial transposition of a graph and degree criteria, respectively. Thus, we provide classes of bipartite separable states of dimension m ×n arising from partially symmetric graphs. We identify partially asymmetric graphs that lack the property of partial symmetry. We develop a combinatorial procedure to create a partially asymmetric graph from a given partially symmetric graph. We show that this combinatorial operation can act as an entanglement generator for mixed states arising from partially symmetric graphs.

Results of a directed graph and fault tree assessment of a MC and A system

International Nuclear Information System (INIS)

Gilman, F.M.; Lambert, H.E.; Lim, J.J.

1978-01-01

An assessment of the effectiveness of the Material Control and Accounting System (MC and A) in a hypothetical nuclear facility, the TEST BED is presented. The key in assessing the TEST BED is the generation of adversary event sets. The adversary event sets are generated and analyzed by a directed graph (digraph) and fault tree procedure. Although the TEST BED is a system hardened against SNM theft, the assessment of the TEST BED finds several major weaknesses, and also indicates possible modifications to correct these weaknesses

Algorithms and Data Structures for Graphs

DEFF Research Database (Denmark)

Rotenberg, Eva

are planar graphs, which are those that can be drawn on a piece of paper without any pair of edges crossing. For planar graphs where each edge can only be traversed in one direction, a fundamental question is whether there is a route from vertex A to vertex B in the graph. We show how such a graph can...... of the form: "Is there an edge such that all paths between A and B go via that edge?" and which can quickly be updated when edges are inserted or deleted. We further show how to represent a planar graph such that we can quickly update our representation when an edge is deleted, and such that questions...

On the nullity number of graphs

Directory of Open Access Journals (Sweden)

Mustapha Aouchiche

2017-10-01

Full Text Available The paper discusses bounds on the nullity number of graphs. It is proved in [B. Cheng and B. Liu, On the nullity of graphs. Electron. J. Linear Algebra 16 (2007 60--67] that $\\eta \\le n - D$, where $\\eta$, n and D denote the nullity number, the order and the diameter of a connected graph, respectively. We first give a necessary condition on the extremal graphs corresponding to that bound, and then we strengthen the bound itself using the maximum clique number. In addition, we prove bounds on the nullity using the number of pendant neighbors in a graph. One of those bounds is an improvement of a known bound involving the domination number.

Graph Transforming Java Data

NARCIS (Netherlands)

de Mol, M.J.; Rensink, Arend; Hunt, James J.

This paper introduces an approach for adding graph transformation-based functionality to existing JAVA programs. The approach relies on a set of annotations to identify the intended graph structure, as well as on user methods to manipulate that structure, within the user’s own JAVA class

Generalized hypercube graph $\\Q_n(S$, graph products and self-orthogonal codes

Directory of Open Access Journals (Sweden)

Pani Seneviratne

2016-01-01

Full Text Available A generalized hypercube graph $\\Q_n(S$ has $\\F_{2}^{n}=\\{0,1\\}^n$ as the vertex set and two vertices being adjacent whenever their mutual Hamming distance belongs to $S$, where $n \\ge 1$ and $S\\subseteq \\{1,2,\\ldots, n\\}$. The graph $\\Q_n(\\{1\\}$ is the $n$-cube, usually denoted by $\\Q_n$.We study graph boolean products $G_1 = \\Q_n(S\\times \\Q_1, G_2 = \\Q_{n}(S\\wedge \\Q_1$, $G_3 = \\Q_{n}(S[\\Q_1]$ and show that binary codes from neighborhood designs of $G_1, G_2$ and $G_3$ are self-orthogonal for all choices of $n$ and $S$. More over, we show that the class of codes $C_1$ are self-dual. Further we find subgroups of the automorphism group of these graphs and use these subgroups to obtain PD-sets for permutation decoding. As an example we find a full error-correcting PD set for the binary $[32, 16, 8]$ extremal self-dual code.

evelopment of a boiling water reactor fault diagnostic system with a signed directed graph method

International Nuclear Information System (INIS)

Chen, M.; Yu, C.C.; Liou, C.T.; Liao, L.Y.

1990-01-01

The fault diagnostic system for a nuclear power reactor is expected to be a useful decision support system for the operators during transients and accident conditions. A considerable research effort has been devoted to the development of automated fault diagnostic systems. One major approach, which has been widely used in chemical engineering, is to identify the possible causes of process disturbance using a logic-oriented method called signed directed graph (SDG). A knowledge based system was developed with the rules derived from the SDG representation. The SDG for the Chinshan nuclear power plant, which is a typical boiling water reactor, is established. The personal consultant system is used as the expert system development tool in this paper