Previous asymptotically correct algorithms for recovering causal structure from sample probabilities have been limited even in sparse graphs to a few variables. We describe an asymptotically correct algorithm whose complexity for fixed graph connectivity increases polynomially in the number of vertices, and may in practice recover sparse graphs with several hundred variables. From..

We present a novel method, called graph sparse nonnegative matrix factorization, for dimensionality reduction. The affinity graph and sparse constraint are further taken into consideration in nonnegative matrix factorization and it is shown that the proposed matrix factorization method can respect the intrinsic graph structure and provide the sparse representation. Different from some existing traditional methods, the inertial neural network was developed, which can be used to optimize our proposed matrix factorization problem. By adopting one parameter in (...) the neural network, the global optimal solution can be searched. Finally, simulations on numerical examples and clustering in real-world data illustrate the effectiveness and performance of the proposed method. (shrink)

Let G = V G, E G be a molecular graph, where V G and E G are the sets of vertices and edges. A topological index of a molecular graph is a numerical quantity which helps to predict the chemical/physical properties of the molecules. The Wiener, Wiener polarity, and the terminal Wiener indices are the distance-based topological indices. In this paper, we described a linear time algorithm that computes the Wiener index for acyclic graphs and extended this (...) algorithm for unicyclic graphs. The same algorithms are modified to compute the terminal Wiener index and the Wiener polarity index. All these algorithms compute the indices in time O n. (shrink)

Graph theory is a specific concept that has numerous applications throughout many industries. Despite the advancement of this technique, graph theory can still yield ambiguous and imprecise results. In order to cut down on these indeterminate factors, neutrosophic logic has emerged as an applicable solution that is gaining significant attention in solving many real-life decision-making problems that involve uncertainty, impreciseness, vagueness, incompleteness, inconsistency, and indeterminacy. However, empirical research on this specific graph set is lacking. Neutrosophic Graph (...) Theory and Algorithms is a collection of innovative research on the methods and applications of neutrosophic sets and logic within various fields including systems analysis, economics, and transportation. While highlighting topics including linear programming, decision-making methods, and homomorphism, this book is ideally designed for programmers, researchers, data scientists, mathematicians, designers, educators, researchers, academicians, and students seeking current research on the various methods and applications of graph theory. (shrink)

In the field of natural language processing, the task of sensitive information detection refers to the procedure of identifying sensitive words for given documents. The majority of existing detection methods are based on the sensitive-word tree, which is usually constructed via the common prefixes of different sensitive words from the given corpus. Yet, these traditional methods suffer from a couple of drawbacks, such as poor generalization and low efficiency. For improvement purposes, this paper proposes a novel self-attention-based detection algorithm using (...) the implementation of graph convolutional network. The main contribution is twofold. Firstly, we consider a weighted GCN to better encode word pairs from the given documents and corpus. Secondly, a simple, yet effective, attention mechanism is introduced to further integrate the interaction among candidate words and corpus. Experimental results from the benchmarking dataset of THUC news demonstrate a promising detection performance, compared to existing work. (shrink)

The study of graph structure has advanced in recent years with great strides: finite graphs can be described algebraically, enabling them to be constructed out of more basic elements. Separately the properties of graphs can be studied in a logical language called monadic second-order logic. In this book, these two features of graph structure are brought together for the first time in a presentation that unifies and synthesizes research over the last 25 years. The author not only provides (...) a thorough description of the theory, but also details its applications, on the one hand to the construction of graph algorithms, and, on the other to the extension of formal language theory to finite graphs. Consequently the book will be of interest to graduate students and researchers in graph theory, finite model theory, formal language theory, and complexity theory. (shrink)

Facebook research has proliferated during recent years. However, since November 2017, Facebook has introduced a new limitation on the maximum amount of page posts retrievable through their Graph application programming interface, while there is limited documentation on how these posts are selected. This paper compares two datasets of the same Facebook page, a full dataset obtained before the introduction of the limitation and a partial dataset obtained after, and employs bootstrapping technique to assess the bias caused by the new (...) limitation. This paper demonstrates that posts with high user engagement, Photo posts and Video posts, are over-represented, while Link posts are under-represented. Top-term analysis reveals that there are significant differences in the most prominent terms between the full and partial dataset. This paper also reverse engineered the new application programming interface’s ranking algorithm to identify the features of a post that would affect its odds of being selected. Sentiment analysis reveals that there are significant differences in the sentiment word usage between the selected and non-selected posts. This paper has significant implications for the representativeness of research that use Facebook page data collected after the introduction of the limitation. (shrink)

The graph edit distance (GED) measures the dissimilarity between two graphs as the minimal cost of a sequence of elementary operations transforming one graph into another. This measure is fundamental in many areas such as structural pattern recognition or classification. However, exactly computing GED is NP-hard. Among different classes of heuristic algorithms that were proposed to compute approximate solutions, local search based algorithms provide the tightest upper bounds for GED. In this paper, we present K-REFINE and (...) RANDPOST. K-REFINE generalizes and improves an existing local search algorithm and performs particularly well on small graphs. RANDPOST is a general warm start framework that stochastically generates promising initial solutions to be used by any local search based GED algorithm. It is particularly efficient on large graphs. An extensive empirical evaluation demonstrates that both K-REFINE and RANDPOST perform excellently in practice. (shrink)

Ancient algorithms -- Sorting -- Graph algorithms -- Primality testing -- Solution of linear equations -- Newton's method -- Linear programming -- Eigenvalues and eigenvectors -- MM algorithms -- Data mining -- The fast Fourier transform -- Monte Carlo methods -- Mathematical review.

Multi-Task Learning tries to improve the learning process of different tasks by solving them simultaneously. A popular Multi-Task Learning formulation for SVM is to combine common and task-specific parts. Other approaches rely on using a Graph Laplacian regularizer. Here we propose a combination of these two approaches that can be applied to L1, L2 and LS-SVMs. We also propose an algorithm to iteratively learn the graph adjacency matrix used in the Laplacian regularization. We test our proposal with synthetic (...) and real problems, both in regression and classification settings. When the task structure is present, we show that our model is able to detect it, which leads to better results, and we also show it to be competitive even when this structure is not present. (shrink)

This paper deals primarily with countable, simple, connected graphs and the following two conditions which are trivially satisfied if the graphs are finite: (a) there is an edge-recognition algorithm, i.e., an effective procedure which enables us, given two distinct vertices, to decide whether they are adjacent, (b) there is a shortest path algorithm, i.e., an effective procedure which enables us, given two distinct vertices, to find a minimal path joining them. A graph $G = \langle\eta, \eta\rangle$ with η as (...) set of vertices and η as set of edges is an α-graph if it satisfies (a); it is an ω-graph if it satisfies (b). G is called r.e. (isolic) if the sets ν and η are r.e. (isolated). While every ω-graph is an α-graph, the converse is false, even if G is r.e. or isolic. Several basic properties of finite graphs do not generalize to ω-graphs. For example, an ω-tree with more than one vertex need not have two pendant vertices, but may have only one or none, since it may be a 1-way or 2-way infinite path. Nevertheless, some elementary propositions for finite graphs $G = \langle\nu, \eta\rangle$ with $n = \operatorname{card}(\nu), e = \operatorname{card}(\eta)$ , do generalize to isolic ω-graphs, e.g., n - 1 ≤ e ≤ n(n - 1)/2. Let N and E be the recursive equivalence types of ν and η respectively. Then we have for an isolic α-tree $G = \langle\nu, \eta\rangle: N = E + 1$ iff G is an ω-tree. The theorem that every finite graph has a spanning tree has a natural, effective analogue for ω-graphs. The structural difference between isolic α-graphs and isolic ω-graphs will be illustrated by: (i) every infinite graph is isomorphic to some isolic α-graph; (ii) there is an infinite graph which is not isomorphic to any isolic ω-graph. An isolic α-graph is also called a twilight graph. There are c such graphs, c denoting the cardinality of the continuum. (shrink)

Traditional spatial enabled grammars lack flexibility in specifying the spatial semantics of graphs. This paper describes a new graph grammar formalism called the multigranularity Coordinate Graph Grammar (mgCGG) for spatial graphs. Based on the Coordinate Graph Grammar (CGG), the mgCGG divides coordinates into two categories, physical coordinates and grammatical coordinates, where physical coordinates are the common coordinates in the real world, and grammatical coordinates describe the restrictions on the spatial semantics. In the derivation and reduction of the (...) mgCGG, the spatial matching conditions between nodes are evaluated on the basis of the grammatical coordinates, which can be obtained by the specified granularities. By adjusting the granularities, both qualitative and quantitative analyses for spatial semantics can be obtained, including the transition states between them. In addition, a new redex searching algorithm with polynomial time complexity is designed for the mgCGG. A running example of drawing a flowchart is given to illustrate a practical application of the mgCGG. Through a detailed comparison with related spatial-enabled grammars, it is found that the mgCGG has good performance in four critical aspects—the semantics processing mechanism, fault-tolerance, redex searching algorithm, and practical application—providing a flexible yet uniform way to specify spatial graphs and building a bridge between nonspatial and spatial grammars. (shrink)

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.

The emerging area of network biology is seeking to provide insights into organizational principles of life. However, despite significant collaborative efforts, there is still typically a weak link between biological and computational scientists and a lack of understanding of the research issues across the disciplines. This results in the use of simple computational techniques of limited potential that are incapable of explaining these complex data. Hence, the danger is that the community might begin to view the topological properties of network (...) data as mere statistics, rather than rich sources of biological information. A further danger is that such views might result in the imposition of scientific doctrines, such as scale-free-centric (on the modeling side) and genome-centric (on the biological side) opinions onto this area. Here, we take a graph-theoretic perspective on protein-protein interaction networks and present a high-level overview of the area, commenting on possible challenges ahead. (shrink)

In recent years, many face image feature extraction and dimensional reduction algorithms have been proposed for linear and nonlinear data, such as local-based graph embedding algorithms or fuzzy set algorithms. However, the aforementioned algorithms are not very effective for face images because they are always affected by overlaps and sparsity points in the database. To solve the problems, a new and effective dimensional reduction method for face recognition is proposed—sparse graph embedding with the fuzzy (...) set for image classification. The aim of this algorithm is to construct two new fuzzy Laplacian scattering matrices by using the local graph embedding and fuzzy k-nearest neighbor. Finally, the optimal discriminative sparse projection matrix is obtained by adding elastic network regression. Experimental results and analysis indicate that the proposed algorithm is more effective than other algorithms in the UCI wine dataset and ORL, Yale, and AR standard face databases. (shrink)

The classical Feferman–Vaught Theorem for First Order Logic explains how to compute the truth value of a first order sentence in a generalized product of first order structures by reducing this computation to the computation of truth values of other first order sentences in the factors and evaluation of a monadic second order sentence in the index structure. This technique was later extended by Läuchli, Shelah and Gurevich to monadic second order logic. The technique has wide applications in decidability and (...) definability theory. Here we give a unified presentation, including some new results, of how to use the Feferman–Vaught Theorem, and some new variations thereof, algorithmically in the case of Monadic Second Order Logic MSOL . We then extend the technique to graph polynomials where the range of the summation of the monomials is definable in MSOL . Here the Feferman–Vaught Theorem for these polynomials generalizes well known splitting theorems for graph polynomials. Again, these can be used algorithmically. Finally, we discuss extensions of MSOL for which the Feferman–Vaught Theorem holds as well. (shrink)

This book is the result of several decades of teaching experience in data structures and algorithms. It is self-contained but does assume some prior knowledge of data structures, and a grasp of basic programming and mathematics tools. Basic Concepts in Algorithms focuses on more advanced paradigms and methods combining basic programming constructs as building blocks and their usefulness in the derivation of algorithms. Its coverage includes the algorithms' design process and an analysis of their performance. It (...) is primarily intended as a textbook for the teaching of Algorithms for second-year undergraduate students in study fields related to computers and programming. Klein reproduces his oral teaching style in writing, with one topic leading to another, related one. Most of the classical and some more advanced subjects in the theory of algorithms are covered, though not in a comprehensive manner. The topics include Divide and Conquer, Dynamic Programming, Graph algorithms, probabilistic algorithms, data compression, numerical algorithms and intractability. Each chapter comes with its own set of exercises, and solutions to most of them are appended. (shrink)

A function is diagonally non-computable if it diagonalizes against the universal partial computable function. D.n.c. functions play a central role in algorithmic randomness and reverse mathematics. Flood and Towsner asked for which functions h, the principle stating the existence of an h-bounded d.n.c. function implies Ramsey-type weak König’s lemma. In this paper, we prove that for every computable order h, there exists an ω\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\omega}$$\end{document} -model of h-DNR which is not a not (...) model of the Ramsey-type graph coloring principle for two colors and therefore not a model of RWKL. The proof combines bushy tree forcing and a technique introduced by Lerman, Solomon and Towsner to transform a computable non-reducibility into a separation over ω\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\omega}$$\end{document} -models. (shrink)

The scale of know­ledge is growing rapidly in the big data environment, and traditional know­ledge organization and services have faced the dilemma of semantic inaccuracy and untimeliness. From a know­ledge fusion perspective-combining the precise semantic superiority of traditional ontology with the large-scale graph processing power and the predicate attribute expression ability of property graph-this paper presents an ontology and property graph fusion framework (OPGFF). The fusion process is divided into content layer fusion and constraint layer fusion. The (...) result of the fusion, that is, the know­ledge representation model is called know­ledge big graph. In addition, this paper applies the know­ledge big graph model to the ownership network in the China’s financial field and builds a financial ownership know­ledge big graph. Furthermore, this paper designs and implements six consistency inference algorithms for finding contradictory data and filling in missing data in the financial ownership know­ledge big graph, five of which are completely domain agnostic. The correctness and validity of the algorithms have been experimentally verified with actual data. The fusion OPGFF framework and the implementation method of the know­ledge big graph could provide technical reference for big data know­ledge organization and services. (shrink)

This paper investigates the Generalized Traveling Salesman Problem (GTSP), which is an extension of the well-known Traveling Salesman Problem (TSP), and it searches for an optimal tour in a clustered graph, such that every cluster is visited exactly once. In this paper, we describe a novel Memetic Algorithm (MA) for solving efficiently the GTSP. Our proposed MA has at its core a genetic algorithm (GA), completed by a Chromosome Enhancement Procedure (CEP), which is based on a TSP solver and (...) the Shortest Path (SP) algorithm and for improving the convergence characteristics of the GA, a Local Search (LS) operation is applied for the best chromosomes in each generation. We tested our algorithm on a set of well-known instances from the literature and the achieved results prove that our novel memetic algorithm is highly competitive against the existing solution approaches from the specialized literature. (shrink)

Design and analysis of algorithms can be a difficult subject for students due to its sometimes-abstract nature and its use of a wide variety of mathematical tools. Here the author, an experienced and successful textbook writer, makes the subject as straightforward as possible in an up-to-date textbook incorporating various new developments appropriate for an introductory course. This text presents the main techniques of algorithm design, namely, divide-and-conquer algorithms, greedy algorithms, dynamic programming algorithms, and backtracking. Graph (...) algorithms are studied in detail, and a careful treatment of the theory of NP-completeness is presented. In addition, the text includes useful introductory material on mathematical background including order notation, algorithm analysis and reductions, and basic data structures. This will serve as a useful review and reference for students who have covered this material in a previous course. Features The first three chapters provide a mathematical review, basic algorithm analysis, and data structures. Detailed pseudocode descriptions of the algorithms along with illustrative algorithms are included. Proofs of correctness of algorithms are included when appropriate. The book presents a suitable amount of mathematical rigor. After reading and understanding the material in this book, students will be able to apply the basic design principles to various real-world problems that they may encounter in their future professional careers. (shrink)

Community detection is a major issue in network analysis. This paper combines a socio-historical approach with an experimental reconstruction of programs to investigate the early automation of clique detection algorithms, which remains one of the unsolved NP-complete problems today. The research led by the archaeologist Jean-Claude Gardin from the 1950s on non-numerical information and graph analysis is retraced to demonstrate the early contributions of social sciences and humanities. The limited recognition and reception of Gardin's innovative computer application to (...) the humanities are addressed through two factors, in addition to the effects of historiography and bibliographies on the recording, discoverability, and reuse of scientific productions: (1) funding policies, evidenced by the transfer of research effort on graph applications from temporary interdisciplinary spaces to disciplinary organizations related to the then-emerging field of computer science; and (2) the erratic careers of algorithms, in which efficiency, flaws, corrections, and authors’ status, were determining factors. (shrink)

In computer science, an algorithm is an unambiguous specification of how to solve a class of problems. Algorithms can perform calculation, data processing and automated reasoning tasks. As an effective method, an algorithm can be expressed within a finite amount of space and time and in a well-defined formal language for calculating a function. Starting from an initial state and initial input (perhaps empty), the instructions describe a computation that, when executed, proceeds through a finite number of well-defined successive (...) states, eventually producing "output" and terminating at a final ending state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as randomized algorithms, incorporate random input. This book introduces a set of concepts in solving problems computationally such as Growth of Functions; Backtracking; Divide and Conquer; Greedy Algorithms; Dynamic Programming; Elementary Graph Algorithms; Minimal Spanning Tree; Single-Source Shortest Paths; All Pairs Shortest Paths; Flow Networks; Polynomial Multiplication, to ways of solving NP-Complete Problems, supported with comprehensive, and detailed problems and solutions, making it an ideal resource to those studying computer science, computer engineering and information technology. (shrink)

Independence of Conditionals (IC) has recently been proposed as a basic rule for causal structure learning. If a Bayesian network represents the causal structure, its Conditional Probability Distributions (CPDs) should be algorithmically independent. In this paper we compare IC with causal faithfulness (FF), stating that only those conditional independences that are implied by the causal Markov condition hold true. The latter is a basic postulate in common approaches to causal structure learning. The common spirit of FF and IC is to (...) reject causal graphs for which the joint distribution looks ‘non-generic’. The difference lies in the notion of genericity: FF sometimes rejects models just because one of the CPDs is simple, for instance if the CPD describes a deterministic relation. IC does not behave in this undesirable way. It only rejects a model when there is a non-generic relation between different CPDs although each CPD looks generic when considered separately. Moreover, it detects relations between CPDs that cannot be captured by conditional independences. IC therefore helps in distinguishing causal graphs that induce the same conditional independences (i.e., they belong to the same Markov equivalence class). The usual justification for FF implicitly assumes a prior that is a probability density on the parameter space. IC can be justified by Solomonoff’s universal prior, assigning non-zero probability to those points in parameter space that have a finite description. In this way, it favours simple CPDs, and therefore respects Occam’s razor. Since Kolmogorov complexity is uncomputable, IC is not directly applicable in practice. We argue that it is nevertheless helpful, since it has already served as inspiration and justification for novel causal inference algorithms. (shrink)

The Fast Casual Inference (FCI) algorithm searches for features common to observationally equivalent sets of causal directed acyclic graphs. It is correct in the large sample limit with probability one even if there is a possibility of hidden variables and selection bias. In the worst case, the number of conditional independence tests performed by the algorithm grows exponentially with the number of variables in the data set. This affects both the speed of the algorithm and the accuracy of the algorithm (...) on small samples, because tests of independence conditional on large numbers of variables have very low power. In this paper, I prove that the FCI algorithm can be interrupted at any stage and asked for output. The output from the interrupted algorithm is still correct with probability one in the large sample limit, although possibly less informative (in the sense that it answers “Can’t tell” for a larger number of questions) than if the FCI algorithm had been allowed to continue uninterrupted. (shrink)

if and only if for every W in V, W is independent of the set of all its non-descendants conditional on the set of its parents. One natural question that arises with respect to DAGs is when two DAGs are “statistically equivalent”. One interesting sense of “statistical equivalence” is “d-separation equivalence” (explained in more detail below.) In the case of DAGs, d-separation equivalence is also corresponds to a variety of other natural senses of statistical equivalence (such as representing the same (...) set of distributions). Theorems characterizing d-separation equivalence for directed acyclic graphs and that can be used as the basis for polynomial time algorithms for checking d-separation equivalence were provided by Verma and Pearl (1990), and Frydenberg (1990). The question we will examine is how to extend these results to cases where a DAG may have latent (unmeasured) variables or selection bias (i.e. some of the variables in the DAG have been conditioned on.) D-separation equivalence is of interest in part because there are algorithms for constructing DAGs with latent variables and selection bias that are based on observed conditional independence relations. For this class of algorithms, it is impossible to determine which of two d-separation equivalent causal structures generated a given probability distribution, given only the set of conditional independence and dependence relations true of the observed distribution. We will describe a polynomial (in the number of vertices) time algorithm for determining when two DAGs which may have latent variables or selection bias are d-separation equivalent. (shrink)

Various methods have been employed to investigate different aspects of the brain activity modulation related to the performance of a cycling task. In our study we examined how functional connectivity and brain network efficiency varied during an endurance cycling task. To this purpose, we reconstructed EEG signals at source level: we computed current densities in 28 anatomical regions of interest (ROIs) through the eLORETA algorithm, then we calculated the Lagged Coherence of the 28 current density signals to define the adjacency (...) matrix. To quantify changes of functional network efficiency during an exhaustive cycling task, we computed three graph theoretical indices: local efficiency (LE), global efficiency (GE) and Density (D) in two different frequency bands, Alpha and Beta bands, that indicate alertness processes and motor binding/fatigue respectively. This analysis was conducted for six different task intervals: pre-cycling, initial, intermediate and final stages of cycling, active recovery and passive recovery. Fourteen participants performed an incremental cycling task with simultaneous EEG recording and RPE monitoring to detect participants’ exhaustion. LE remained constant during the endurance cycling task in both bands. Therefore, we speculate that fatigue processes did not affect segregated neural processing. We observed an increase of GE in the Alpha band only during cycling, that could be due to greater alertness processes and preparedness to stimuli during exercise. Conversely, although D did not change significantly over time in the Alpha band, its general reduction in the Beta bands during cycling could be interpreted within the framework of the neural efficiency hypothesis, which posits a reduced neural activity for expert/automated performances. We argue that the use of graph theoretical indices represents a clear methodological advancement in studying endurance performance. (shrink)

A large number of cross-references to various bodies of text are used in legal texts, each serving a different purpose. It is often necessary for authorities and companies to look into certain types of these citations. Yet, there is a lack of automatic tools to aid in this process. Recently, citation graphs have been used to improve the intelligibility of complex rule frameworks. We propose an algorithm that builds the citation graph from a document and automatically labels each edge (...) according to its purpose. Our method uses the citing text only and thus works only on citations who’s purpose can be uniquely identified by their surrounding text. This framework is then applied to the US code. This paper includes defining and evaluating a standard gold set of labels that cover a vast majority of citation types which appear in the “US Code” but are still short enough for practical use. We also proposed a novel linear-chain conditional random field model that extracts the features required for labeling the citations from the surrounding text. We then analyzed the effectiveness of different clustering methods such as K-means and support vector machine to automatically label each citation with the corresponding label. Besides this, we talk about the practical difficulties of this task and give a comparison of human accuracy compared to our end-to-end algorithm. (shrink)

Graph theory is one of those subjects that is a vital part of the digital world. It is used to monitor the movement of robots on a network, to debug computer networks, to develop algorithms, and to analyze the structural properties of chemical structures, among other things. It is also useful in airplane scheduling and the study of diffusion mechanisms. The parameters computed in this article are very useful in pattern recognition and image processing. A number d f, (...) w = min d w, t, d w, s is referred as distance between f = t s an edge and w a vertex. d w, f 1 ≠ d w, f 2 implies that two edges f 1, f 2 ∈ E are resolved by node w ∈ V. A set of nodes A is referred to as an edge metric generator if every two links/edges of Γ are resolved by some nodes of A and least cardinality of such sets is termed as edge metric dimension, e dim Γ for a graph Γ. A set B of some nodes of Γ is a mixed metric generator if any two members of V ∪ E are resolved by some members of B. Such a set B with least cardinality is termed as mixed metric dimension, m dim Γ. In this paper, the metric dimension, edge metric dimension, and mixed metric dimension of dragon graph T n, m, line graph of dragon graph L T n, m, paraline graph of dragon graph L S T n, m, and line graph of line graph of dragon graph L L T n, m have been computed. It is shown that these parameters are constant, and a comparative analysis is also given for the said families of graphs. (shrink)

Counting models for a two conjunctive formula $F$, a problem known as $\sharp $2Sat, is a classic $\sharp $P complete problem. Given a 2-CF $F$ as input, its constraint graph $G$ is built. If $G$ is acyclic, then $\sharp $2Sat can be computed efficiently. In this paper, we address the case when $G$ has cycles. When $G$ is cyclic, we propose a decomposition on the constraint graph $G$ that allows the computation of $\sharp $2Sat in incremental way. Let (...) $T$ be a cactus graph of $G$ containing a maximal number of independent cycles, and let $\overline{T}=-E)$ be a subset of frond edges from $G$. The clauses in $\overline{T}$ are ordered in connected components $\{K_1, \ldots, K_r\}$. Each $, i=1,\ldots,r$ is a knot of the graph. The arrangement of the clauses of $\overline{T}$ allows the decomposition of $G$ in knots and provides a way of computing $\sharp $2Sat in an incremental way. Our procedure has a bottom-up orientation for the computation of $\sharp $2Sat. It begins with $F_0 = T$. In each iteration of the procedure, a new clause $C_i \in \overline{T}$ is considered in order to form $F_i = $ and then to compute $\sharp $2Sat$$ based on the computation of $\sharp $2Sat$$. (shrink)

Regression testing is applied whenever a code changes, ensuring that the modifications fixed the fault and no other faults are introduced. Due to a large number of test cases to be run, test case prioritization is one of the strategies that allows to run the test cases with the highest fault rate first. The aim of the paper is to present an optimized test case prioritization method inspired by ant colony optimization, test case prioritization–ANT. The criteria used by the optimization (...) algorithm are the number of faults not covered yet by the selected test cases and the sum of severity of the faults. The cost, i.e. time execution, for test cases is considered in the computation of the pheromone deposited on the graph’s edges. The average percentage of fault detected metric, as best selection criterion, is used to uncover maximum faults with the highest severity, and reducing the regression testing time. Several experiments are considered, detailed and discussed, comparing various algorithm parameter’s alternatives. A benchmark project is also used to validate the proposed approach. The obtained results are encouraging, being a cornerstone for new perspectives to be considered. (shrink)

Lines of Identity are important elements in Existential Graphs. They can be assembled to whole networks called “ligatures.” They are not straightforwardly understandable: for example, in constrast to LoI, ligatures may stand for more than one object.This article elaborates the handling of ligatures. It is precisely investigated how ligatures are dealt with in the calculus and how they can be modified without changing the meaning of a graph. Finally, a sufficient criterion for reading a ligature similar to a LoI (...) is provided, as well as an algorithm which grasps the correct meaning of an existential graph even if it contains arbitrarily complex ligatures. (shrink)

A Bayesian network consists of two distinct parts: a directed acyclic graph (DAG or belief-network structure) and a set of parameters for the DAG. The DAG in a Bayesian network can be used to represent both causal hypotheses and sets of probability distributions. Under the causal interpretation, a DAG represents the causal relations in a given population with a set of vertices V when there is an edge from A to B if and only if A is a direct (...) cause of B relative to V. (We adopt the convention that sets of variables are capitalized and boldfaced, and individual variables are capitalized and italicized.) Under the statistical interpretation a DAG G can be taken to represent a set of all distributions all of which share a set of conditional independence relations that are entailed by satisfying a local directed Markov property (defined below). (shrink)

A hybrid preference framework is proposed for strategic conflict analysis to integrate preference strength and preference uncertainty into the paradigm of the graph model for conflict resolution (GMCR) under multiple decision makers. This structure offers decision makers a more flexible mechanism for preference expression, which can include strong or mild preference of one state or scenario over another, as well as equal preference. In addition, preference between two states can be uncertain. The result is a preference framework that is (...) more general than existing models which consider preference strength and preference uncertainty separately. Within the hybrid preference structure, four kinds of stability are defined as solution concepts and a post-stability analysis, called status quo analysis, which can be used to track the evolution of a given conflict. Algorithms are provided for implementing the key inputs of stability analysis and status quo analysis within the extended preference structure. The new stability concepts under the hybrid preference structure can be used to model complex strategic conflicts arising in practical applications, and can provide new insights for the conflicts. The method is illustrated using the conflict over proposed bulk water exports from Lake Gisborne in Newfoundland, Canada. (shrink)

Background and objectivesThe study of brain functional connectivity alterations in children with Attention-Deficit/Hyperactivity Disorder has been the subject of considerable investigation, but the biological mechanisms underlying these changes remain poorly understood. Here, we aim to investigate the brain alterations in patients with ADHD and Typical Development children and accurately classify ADHD children from TD controls using the graph-theoretical measures obtained from resting-state fMRI.Materials and methodsWe investigated the performances of rs-fMRI data for classifying drug-naive children with ADHD from TD controls. (...) Fifty six drug-naive ADHD children and 56 age matched TD controls were included in this study. The graph measures extracted from rs-fMRI functional connectivity were used as features. Extracted network-based features were fed to the RFE feature selection algorithm to select the most discriminating subset of features. We trained and tested Support Vector Machine, Random Forest, and Gradient Boosting using Peking center data from ADHD-200 database to classify ADHD and TD children using discriminative features. In addition to the machine learning approach, the statistical analysis was conducted on graph measures to discover the differences in the brain network of patients with ADHD.ResultsAn accuracy of 78.2% was achieved for classifying drug-naive children with ADHD from TD controls employing the optimal features and the GB classifier. We also performed a hub node analysis and found that the number of hubs in TD controls and ADHD children were 8 and 5, respectively, indicating that children with ADHD have disturbance of critical communication regions in their brain network. The findings of this study provide insight into the neurophysiological mechanisms underlying ADHD.ConclusionPattern recognition and graph measures of the brain networks, based on the rs-fMRI data, can efficiently assist in the classification of ADHD children from TD controls. (shrink)

Different directed acyclic graphs may be Markov equivalent in the sense that they entail the same conditional independence relations among the observed variables. Chickering provided a transformational characterization of Markov equivalence for DAGs, which is useful in deriving properties shared by Markov equivalent DAGs, and, with certain generalization, is needed to prove the asymptotic correctness of a search procedure over Markov equivalence classes, known as the GES algorithm. For DAG models with latent variables, maximal ancestral graphs provide a neat representation (...) that facilitates model search. However, no transformational characterization -- analogous to Chickering's -- of Markov equivalent MAGs is yet available. This paper establishes such a characterization for directed MAGs, which we expect will have similar uses as it does for DAGs. (shrink)

The International Workshop on Combinatorial Algorithms was established in 1989 as the Australasian Workshop on Combinatorial Algorithms. As a consequence of the workshop's success in attracting mathematicians and computer scientists from around the world, it was decided at the 2006 meeting to go global, to change the workshop's name, and to hold it in appropriate venues around the world. The workshop supports basic research on the interface between mathematics and computing, specifically * Algorithms & Data Structures * (...) Complexity Theory * Algorithms on Graphs & Strings * Combinatorial Optimization * Cryptography & Information Security * Computational Biology * Communications Networks and many other related areas. This is Volume 1 in the series of IWOCA proceedings. See http: //www.iwoca.org/. (shrink)

Subgraph matching on a large graph has become a popular research topic in the field of graph analysis, which has a wide range of applications including question answering and community detection. However, traditional edge-cutting strategy destroys the structure of indivisible knowledge in a large RDF graph. On the premise of load-balancing on subgraph division, a dominance-partitioned strategy is proposed to divide a large RDF graph without compromising the knowledge structure. Firstly, a dominance-connected pattern graph is (...) extracted from a pattern graph to construct a dominance-partitioned pattern hypergraph, which divides a pattern graph as multiple fish-shaped pattern subgraphs. Secondly, a dominance-driven spectrum clustering strategy is used to gather the pattern subgraphs into multiple clusters. Thirdly, the dominance-partitioned subgraph matching algorithm is designed to conduct all isomorphic subgraphs on a cluster-partitioned RDF graph. Finally, experimental evaluation verifies that our strategy has higher time-efficiency of complex queries, and it has a better scalability on multiple machines and different data scales. (shrink)

An intervention may have an effect on units other than those to which it was administered. This phenomenon is called interference and it usually goes unmodeled. In this paper, we propose to combine Lauritzen-Wermuth-Frydenberg and Andersson-Madigan-Perlman chain graphs to create a new class of causal models that can represent both interference and non-interference relationships for Gaussian distributions. Specifically, we define the new class of models, introduce global and local and pairwise Markov properties for them, and prove their equivalence. We also (...) propose an algorithm for maximum likelihood parameter estimation for the new models, and report experimental results. Finally, we show how to compute the effects of interventions in the new models. (shrink)

Heterogeneous information networks can naturally simulate complex objects, and they can enrich recommendation systems according to the connections between different types of objects. At present, a large number of recommendation algorithms based on heterogeneous information networks have been proposed. However, the existing algorithms cannot extract and combine the structural features in heterogeneous information networks. Therefore, this paper proposes an efficient recommendation algorithm based on heterogeneous information network, which uses the characteristics of graph convolution neural network to automatically (...) learn node information to extract heterogeneous information and avoid errors caused by the manual search for metapaths. Furthermore, by fully considering the scoring relationship between nodes, a calculation strategy combining heterogeneous information and a scoring information fusion strategy is proposed to solve the scoring between nodes, which makes the prediction scoring more accurate. Finally, by updating the nodes, the training scale is reduced, and the calculation efficiency is improved. The study conducted a large number of experiments on three real data sets with millions of edges. The results of the experiments show that compared with PMF, SemRec, and other algorithms, the proposed algorithm improves the recommendation accuracy MAE by approximately 3% and the RMSE by approximately 8% and reduces the time consumption significantly. (shrink)