We develop a combinatorial model to study the evolution of graphs underlying proofs during the process of cut elimination. Proofs are two-dimensional objects and differences in the behavior of their cut elimination can often be accounted for by differences in their two-dimensional structure. Our purpose is to determine geometrical conditions on the graphs of proofs to explain the expansion of the size of proofs after cut elimination. We will be concerned with exponential expansion and we give upper and lower bounds (...) which depend on the geometry of the graphs. The lower bound is computed passing through the notion of universal covering for directed graphs. In this paper we present ground material for the study of cut elimination and structure of proofs in purely combinatorial terms. We develop a theory of duplication for directed graphs and derive results on graphs of proofs as corollaries. (shrink)

A rank function for a directed graph G assigns elements of a well ordering to the vertices of G in a fashion that preserves the order induced by the edges. While topological sortings require a one-to-one matching of vertices and elements of the ordering, rank functions frequently must assign several vertices the same value. Theorems stating basic properties of rank functions vary significantly in logical strength. Using the techniques of reverse mathematics, we present results that require the subsystems (...) ${\ensuremath{\vec{RCA}_0}}$ , ${{\vec{ACA}_0}}$ , ${{\vec{ATR}_0}}$ , and ${{\vec{\Pi^1_1 - CA}_0}}$. (shrink)

Given a finite relational language L is there an algorithm that, given two finite sets A and B of structures in the language, determines how many homogeneous L structures there are omitting every structure in B and embedding every structure in A? For directed graphs this question reduces to: Is there an algorithm that, given a finite set of tournaments Γ, determines whether QΓ, the class of finite tournaments omitting every tournament in Γ, is well-quasi-order? First, we give a (...) nonconstructive proof of the existence of an algorithm for the case in which Γ consists of one tournament. Then we determine explicitly the set of tournaments each of which does not have an antichain omitting it. Two antichains are exhibited and a summary is given of two structure theorems which allow the application of Kruskal's Tree Theorem. Detailed proofs of these structure theorems will be given elsewhere. The case in which Γ consists of two tournaments is also discussed. (shrink)

Recursive linear structural equation models can be represented by directed acyclic graphs. When represented in this way, they satisfy the Markov Condition. Hence it is possible to use the graphical d-separation to determine what conditional independence relations are entailed by a given linear structural equation model. I prove in this paper that it is also possible to use the graphical d-separation applied to a cyclic graph to determine what conditional independence relations are entailed to hold by a given (...) non-recursive linear structural equation model. I also give a causal intepretation to the linear coefficients in a non- recursive structural equation models, and explore the relationships between cyclic graphs and undirected graphs, directed acyclic graphs with latent variables, and chain independence graphs. (shrink)

Although it is known that reachability in undirected finite graphs can be expressed by an existential monadic second-order sentence, our main result is that this is not the case for directed finite graphs (even in the presence of certain "built-in" relations, such as the successor relation). The proof makes use of Ehrenfeucht-Fraisse games, along with probabilistic arguments. However, we show that for directed finite graphs with degree at most k, reachability is expressible by an existential monadic second-order sentence.

Christopher Meek. Related Graphical Frameworks: Undircted, Directed Acyclic and Chain Graph Models.

It is well known that there may be many causal explanations that are consistent with a given set of data. Recent work has been done to represent the common aspects of these explanations into one representation. In this paper, we address what is less well known: how do the relationships common to every causal explanation among the observed variables of some DAG process change in the presence of latent variables? Ancestral graphs provide a class of graphs that can encode conditional (...) independence relations that arise in DAG models with latent and selection variables. In this paper we present a set of orientation rules that construct the Markov equivalence class representative for ancestral graphs, given a member of the equivalence class. These rules are sound and complete. We also show that when the equivalence class includes a DAG, the equivalence class representative is the essential graph for the said DAG. (shrink)

Barry Smith recently discussed the diagraphs of book eight of Jacob Lorhard’s Ogdoas scholastica under the heading “birth of ontology” (Smith, 2022; this issue). Here, I highlight the commonalities between the original usage of diagraphs in the tradition of Ramus for didactic purposes and the the usage of their present-day successors–modern ontologies–for computational purposes. The modern ideas of ontology and of the universal computer were born just two generations apart in the breakthrough century of instrumental reason.

The semantic paradoxes are often associated with self-reference or referential circularity. Yablo (Analysis 53(4):251–252, 1993), however, has shown that there are infinitary versions of the paradoxes that do not involve this form of circularity. It remains an open question what relations of reference between collections of sentences afford the structure necessary for paradoxicality. In this essay, we lay the groundwork for a general investigation into the nature of reference structures that support the semantic paradoxes and the semantic hypodoxes. We develop (...) a functionally complete infinitary propositional language endowed with a denotation assignment and extract the reference structural information in terms of graph-theoretic properties. We introduce the new concepts of dangerous and precarious reference graphs, which allows us to rigorously define the task: classify the dangerous and precarious directed graphs purely in terms of their graph-theoretic properties. Ungroundedness will be shown to fully characterize the precarious reference graphs and fully characterize the dangerous finite graphs. We prove that an undirected graph has a dangerous orientation if and only if it contains a cycle, providing some support for the traditional idea that cyclic structure is required for paradoxicality. This leaves the task of classifying danger for infinite acyclic reference graphs. We provide some compactness results, which give further necessary conditions on danger in infinite graphs, which in conjunction with a notion of self-containment allows us to prove that dangerous acyclic graphs must have infinitely many vertices with infinite out-degree. But a full characterization of danger remains an open question. In the appendices we relate our results to the results given in Cook (J Symb Log 69(3):767–774, 2004) and Yablo (2006) with respect to more restricted sentences systems, which we call $\mathcal{F}$ -systems. (shrink)

The conditional independence relations present in a data set usually admit multiple causal explanations — typically represented by directed graphs — which are Markov equivalent in that they entail the same conditional independence relations among the observed variables. Markov equivalence between directed acyclic graphs (DAGs) has been characterized in various ways, each of which has been found useful for certain purposes. In particular, Chickering’s transformational characterization is useful in deriving properties shared by Markov equivalent DAGs, and, with certain (...) generalization, is needed to justify a search procedure over Markov equivalence classes, known as the GES algorithm. Markov equivalence between DAGs with latent variables has also been characterized, in the spirit of Verma and Pearl (1990), via maximal ancestral graphs (MAGs). The latter can represent the observable conditional independence relations as well as some causal features of DAG models with latent variables. However, no characterization of Markov equivalent MAGs is yet available that is analogous to the transformational characterization for Markov equivalent DAGs. The main contribution of the current paper is to establish such a characterization for directed MAGs, which we expect will have similar uses as Chickering’s characterization does for DAGs. (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)

In this book, the authors systematically define the new notion of linguistic graphs associated with a linguistic set of a linguistic variable. We can also define the notion of directed linguistic graphs and linguistic-weighted graphs. Chapter two discusses all types of linguistic graphs, linguistic dyads, linguistic triads, linguistic wheels, complete linguistic graphs, linguistic connected graphs, disconnected linguistic graphs, linguistic components of the graphs and so on. Further, we define the notion of linguistic subgraphs of a linguistic graph. However, (...) like usual graphs, we will not be able to arbitrarily connect any two linguistic words of a linguistic set associated with a linguistic variable. They can be related or adjacent depending on the linguistic variable associated with the linguistic set. This is an exceptional feature of a linguistic graph. (shrink)

Recently developed theory using directed graphs permits simple and precise statements about the validity of causal inferences in most cases. Applying this while reading econometric papers can make it easy to understand assumptions that are vague in prose, and to isolate those assumptions that are crucial to support the main causal claims. The method is illustrated here alongside a close reading of the paper that introduced the use of settler mortality to instrument the impact of institutions on economic development. (...) Two causal pathways that invalidate the instrument are found not to be blocked by satisfactory strategies. The estimates in the original paper, and in many that have used the instrument since, should be considered highly suspect. (shrink)

Different directed acyclic graphs may be Markov equivalent in the sense that they entail the same conditional indepen- dence relations among the observed variables. Meek characterizes Markov equiva- lence classes for DAGs by presenting a set of orientation rules that can correctly identify all arrow orienta- tions shared by all DAGs in a Markov equiv- alence class, given a member of that class. For DAG models with latent variables, maxi- mal ancestral graphs provide a neat representation that facilitates model (...) search. Earlier work has identified a set of orientation rules sufficient to con- struct all arrowheads common to a Markov equivalence class of MAGs. In this paper, we provide extra rules sufficient to construct all common tails as well. We end up with a set of orientation rules sound and complete for identifying commonalities across a Markov equivalence class of MAGs, which is partic- ularly useful for causal inference. (shrink)

Once upon a time, coherentism was the dominant response to the regress problem in epistemology, but in recent decades the view has fallen into disrepute: now almost everyone is a foundationalist (with a few infinitists sprinkled here and there). In this paper, I sketch a new way of thinking about coherentism, and show how it avoids many of the problems often thought fatal for the view, including the isolation objection, worries over circularity, and concerns that the concept of coherence is (...) too vague or metaphorical for serious theoretical use. The key to my approach is to take a familiar tool from discussions of the regress problem -- namely, directed graphs depicting the support relations between beliefs -- and to use that tool in a more sophisticated manner than it is standardly employed. (shrink)

Peter Spirtes. Calculating TETRAD Constraints Implied by Directed Acyclic Graphs.

We examine possible causal structures of experiments with entangled quantum objects. Previously, these structures have been obscured by assuming a misleading probabilistic analysis of quantum non locality as 'Outcome Dependence or Parameter Dependence' and by directly associating these correlations with influences. Here we try to overcome these shortcomings: we proceed from a recent stronger Bell argument, which provides an appropriate probabilistic description, and apply the rigorous methods of causal graph theory. Against the standard view that there is only an (...) influence between the measurement outcomes, we show that there must be an influence from one setting to its distant outcome: EPR correlations can only come about if one of the outcomes is a common effect of both settings. Our discussion makes explicit under which assumptions similar conclusions from information theoretic considerations can be interpreted causally. (shrink)

Any set x is uniquely specified by the graph of the membership relation on the set obtained by adjoining x to the transitive closure of x. Thus any operation on sets can be looked at as an operation on these graphs. We look at the operations of ordinal arithmetic of sets in this light. This turns out to be simplest for a modified ordinal arithmetic based on the Zermelo ordinals, instead of the usual von Neumann ordinals. In this arithmetic, (...) addition of sets corresponds to concatenating graphs, and multiplication corresponds to replacing each edge of a graph by a copy of another graph. Characterizations for the von Neumann case are also given. (shrink)

We present a system for deciding whether a given sentence can be inferred from text. Each sentence is represented as a directed graph (extracted from a dependency parser) in which the nodes represent words or phrases, and the links represent syntactic and semantic relationships. We develop a learned graph matching model to approximate entailment by the amount of the sentence’s semantic content which is contained in the text. We present results on the Recognizing Textual Entailment dataset (Dagan (...) et al., 2005), and show that our approach outperforms Bag- Of-Words and TF-IDF models. (shrink)

Given a quantum system with a very large number of degrees of freedom and a preferred tensor product factorization of the Hilbert space 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 with vertices representing subsystems and edges representing mutual information between subsystems. The second step is to deform the adjacency matrices of the information graphs (...) to that of a low-dimensional lattice using the graph flow equations introduced in the paper. 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 two information graph flows with geometric attractors and metric perturbations obeying a geometric flow equation. Our analysis also suggests a possible approach to quantum gravity in which the geometry emerges directly from a quantum state due to the flow of the information graphs. (shrink)

Topics covered in Discrete Mathematics have become essential tools in many areas of studies in recent years. This is primarily due to the revolution in technology, communications, and cyber security. The book treats major themes in a typical introductory modern Discrete Mathematics course: Propositional and predicate logic, proof techniques, set theory (including Boolean algebra, functions and relations), introduction to number theory, combinatorics and graph theory. An accessible, precise, and comprehensive approach is adopted in the treatment of each topic. The (...) ability of abstract thinking and the art of writing valid arguments are emphasized through detailed proof of (almost) every result. Developing the ability to think abstractly and roguishly is key in any areas of science, information technology and engineering. Every result presented in the book is followed by examples and applications to consolidate its comprehension. The hope is that the reader ends up developing both the abstract reasoning as well as acquiring practical skills. All efforts are made to write the book at a level accessible to first-year students and to present each topic in a way that facilitates self-directed learning. Each chapter starts with basic concepts of the subject at hand and progresses gradually to cover more ground on the subject. Chapters are divided into sections and subsections to facilitate readings. Each section ends with its own carefully chosen set of practice exercises to reenforce comprehension and to challenge and stimulate readers. As an introduction to Discrete Mathematics, the book is written with the smallest set of prerequisites possible. Familiarity with basic mathematical concepts (usually acquired in high school) is sufficient for most chapters. However, some mathematical maturity comes in handy to grasp some harder concepts presented in the book. (shrink)

There is a Turing computable embedding $\Phi $ of directed graphs $\mathcal {A}$ in undirected graphs. Moreover, there is a fixed tuple of formulas that give a uniform effective interpretation; i.e., for all directed graphs $\mathcal {A}$, these formulas interpret $\mathcal {A}$ in $\Phi $. It follows that $\mathcal {A}$ is Medvedev reducible to $\Phi $ uniformly; i.e., $\mathcal {A}\leq _s\Phi $ with a fixed Turing operator that serves for all $\mathcal {A}$. We observe that there is a (...) graph G that is not Medvedev reducible to any linear ordering. Hence, G is not effectively interpreted in any linear ordering. Similarly, there is a graph that is not interpreted in any linear ordering using computable $\Sigma _2$ formulas. Any graph can be interpreted in a linear ordering using computable $\Sigma _3$ formulas. Friedman and Stanley [4] gave a Turing computable embedding L of directed graphs in linear orderings. We show that there is no fixed tuple of $L_{\omega _1\omega }$ -formulas that, for all G, interpret the input graph G in the output linear ordering $L$. Harrison-Trainor and Montalbán [7] have also shown this, by a quite different proof. (shrink)

We show how Peirce's architectonics folds on itself and finds local consequences that correspond to the major global hypotheses of the system. In particular, we study how the pragmaticist maxim can be technically represented in Peirce's existential graphs, well-suited to reveal an underlying continuity in logical operations, and can provide suggestive philosophical analogies. Further, using the existential graphs, we formalize — and prove one direction of — a “local proof of pragmaticism,” trying thus to explain the prominent place that existential (...) graphs can play in the architectonics of pragmaticism, as Peirce persistently advocated. Finally, we present a web of “continuous iterations” of some key Peircean concepts that supports a “lattice of partial proofs” of pragmaticism. (shrink)

This paper raises the question of the prominence and use of statistical graphs in science, and argues that their use in problem solving analysis can best be understood in an ‘interactionist’ frame of analysis, including bio-emotion, culture, social organization, and environment as elements. The frame contrasts both with philosophical realism and with social constructivism, which posit two variables and one way causal flows. We next posit basic differences between visual, verbal, and numerical media of perception and communication. Graphs are thus (...) seen as key interactive sites where different media are transformed into more interpretable forms. Examples are taken from Limnology where numbers are transformed into graphs to find patterns in them, and thus, by implication in the environmental materials from which the numerical measurements were taken. Their revisualization by passes a human cognitive limitation, for the direct analysis — interpretation of lists and tables of numbers, visual imaging being a cognitive strength. Sense of problem, conceptual repertoire, and social relations are seen to direct this pattern search and interpretive process. (shrink)

We recall and improve our 2019 and 2020 concepts of n-SuperHyperGraph, Plithogenic nSuperHyperGraph, n-Power Set of a Set, and we present some application from the real world. The nSuperHyperGraph is the most general form of graph today and it is able to describe the complex reality we live in, by using n-SuperVertices (groups of groups of groups etc.) and nSuperHyperEdges (edges connecting groups of groups of groups etc.).

Every set can been thought of as a directed graph whose edge relation is ∈. We show that many natural examples of directed graphs of this kind are indivisible: for every infinite κ, for every indecomposable λ, and every countable model of set theory. All of the countable digraphs we consider are orientations of the countable random graph. In this way we find indivisible well‐founded orientations of the random graph that are distinct up to isomorphism, (...) and ℵ1 that are distinct up to siblinghood. (shrink)

The seminal book on graph theory by Dénes Kőnig, published in the year 1936, collected notions and results from precursory works from the mid to late nineteenth century by Hamilton, Cayley, Sylvester and others. More importantly, Kőnig himself contributed many of his own results that he had obtained in the more than twenty years that he had been working on this subject matter. What is noteworthy is the fact that the fundamentals of what he calls directed graphs are (...) taken almost exhaustively from Paul Hertz' 1922 article on structural reasoning about sentences of the form a→b. This is not a fact that is well known in logical circles, even though Kőnig fully acknowledges this in his book. In view of the numerous trends in the recent decades to describe and explicate logical matters by means of graphs, the fact that it was Hertz' foundation of structural reasoning that informed basic notions of graph theory in the first place is highly significant. The main goal of this paper is to summarize Hertz' article and demonstrate how Kőnig integrates the notions and results presented therein in his book. This is followed by an exposition of how and when Hertz' results were reinvented in terms of graph theory. A critical discussion of the opinion expressed by both Hertz and Kőnig that the more general sentences of the form (a1,…,an)→b, introduced by Hertz in a companion article in 1923, cannot be interpreted by graphs concludes this paper. (shrink)

Understanding the implication of point cloud is still challenging in the aim of classification or segmentation for point cloud due to its irregular and sparse structure. As we have known, PointNet architecture as a ground-breaking work for point cloud process can learn shape features directly on unordered 3D point cloud and has achieved favorable performance, such as 86% mean accuracy and 89.2% overall accuracy for classification task, respectively. However, this model fails to consider the fine-grained semantic information of local structure (...) for point cloud. Then, a multiscale receptive fields graph attention network by means of semantic features of local patch for point cloud is proposed in this paper, and the learned feature map for our network can well capture the abundant features information of point cloud. The proposed MRFGAT architecture is tested on ModelNet datasets, and results show it achieves state-of-the-art performance in shape classification tasks, such as it outperforms GAPNet model by 0.1% in terms of OA and compete with DGCNN model in terms of MA. (shrink)

We propose the solution concept of directional equilibrium for the multidimensional model of voting with general spatial preferences. This concept isolates alternatives that are stable with respect to forces applied by all voters in the directions of their gradients, and it extends a known concept from statistics for Euclidean preferences. We establish connections to the majority core, Pareto optimality, and existence and closed graph, and we provide non-cooperative foundations in terms of a local contest game played by voters.

In order to make scientific results relevant to practical decision making, it is often necessary to transfer a result obtained in one set of circumstances—an animal model, a computer simulation, an economic experiment—to another that may differ in relevant respects—for example, to humans, the global climate, or an auction. Such inferences, which we can call extrapolations, are a type of argument by analogy. This essay sketches a new approach to analogical inference that utilizes chain graphs, which resemble directed acyclic (...) graphs (DAGs) except in allowing that nodes may be connected by lines as well as arrows. This chain graph approach generalizes the account of extrapolation I provided in my (2008) book and leads to new insights that integrate the contributions of the other participants of this symposium. More specifically, this approach explicates the role of “fingerprints,” or distinctive markers, as a strategy for avoiding an underdetermination problem having to do with spurious analogies. Moreover, it shows how the extrapolator’s circle, one of the central challenges for extrapolation highlighted in my book, is closely tied to distinctive markers and the Markov condition as it applies to chain graphs. Finally, the approach suggests additional ways in which investigations of a model can provide information about a target that are illustrated by examples concerning nanomaterials in sunscreens and Wendy Parker’s discussion of fingerprints in climate science. (shrink)

This paper defends the view that the asymmetry of causation can be explained in terms of probabilistic relationships between event types. Papineau first explores three different versions of the "fork asymmetry", namely David Lewis' asymmetry of overdetermination, the screening-off property of common causes, and Spirtes', Glymour's and Scheines' analysis of probabilistic graphs. He then argues that this fork asymmetry is both a genuine phenomenon and a satisfactory metaphysical reduction of causal asymmetry. In his final section he shows how this reduction (...) can account for the relevance of causal direction to human agency, and in particular for the fact that we can manipulate causes to influence their effects, but not vice versa. (shrink)

Continuous subgraph matching problem on dynamic graph has become a popular research topic in the field of graph analysis, which has a wide range of applications including information retrieval and community detection. Specifically, given a query graph q, an initial graph G 0, and a graph update stream △ G i, the problem of continuous subgraph matching is to sequentially conduct all possible isomorphic subgraphs covering △ G i of q on G i. Since knowledge (...) graph is a directed labeled multigraph having multiple edges between a pair of vertices, it brings new challenges for the problem focusing on dynamic knowledge graph. One challenge is that the multigraph characteristic of knowledge graph intensifies the complexity of candidate calculation, which is the combination of complex topological and attributed structures. Another challenge is that the isomorphic subgraphs covering a given region are conducted on a huge search space of seed candidates, which causes a lot of time consumption for searching the unpromising candidates. To address these challenges, a method of subgraph-indexed sequential subdivision is proposed to accelerating the continuous subgraph matching on dynamic knowledge graph. Firstly, a flow graph index is proposed to arrange the search space of seed candidates in topological knowledge graph and an adjacent index is designed to accelerate the identification of candidate activation states in attributed knowledge graph. Secondly, the sequential subdivision of flow graph index and the transition state model are employed to incrementally conduct subgraph matching and maintain the regional influence of changed candidates, respectively. Finally, extensive empirical studies on real and synthetic graphs demonstrate that our techniques outperform the state-of-the-art algorithms. (shrink)

One of the main challenges for computational legal research is drawing up innovative heuristics to derive actionable knowledge from legal documents. While a large part of the research has been so far devoted to the extraction of purely legal information, less attention has been paid to seeking out in the texts the clues of more complex entities: legally relevant facts whose detection requires to link and interpret, as a unified whole, legal information and results of empirical analyses. This paper presents (...) an ongoing research that points in this direction, trying to devise new ways to support public prosecutors in assessing the dangerousness of individuals and groups under investigation, an activity that precisely relies on the cross-sectional evaluation of legal and empirical data. A knowledge mining strategy will be outlined that lines up, into a single metaheuristic model, information extraction, network-based inference, machine learning and visual analytics. We will focus, in particular, on the integration of graph-based inference and machine learning methods used both to support classification tasks and to explore new forms of man-machine cooperation. Experiments made involving public prosecutors from the Italian Anti-Mafia Investigation Directorate and using data from real investigations have not only shown the potentialities of our approach but also offered an opportunity to reflect on the role we could assign to AI when thinking about the future of legal science and practice. (shrink)

Recent advances in neuroscience indicate that analysis of bio-signals such as rest state electroencephalogram and eye-tracking data can provide more reliable evaluation of children autism spectrum disorder than traditional methods of behavior measurement relying on scales do. However, the effectiveness of the new approaches still lags behind the increasing requirement in clinical or educational practices as the “bio-marker” information carried by the bio-signal of a single-modality is likely insufficient or distorted. This study proposes an approach to joint analysis of EEG (...) and eye-tracking for children ASD evaluation. The approach focuses on deep fusion of the features in two modalities as no explicit correlations between the original bio-signals are available, which also limits the performance of existing methods along this direction. First, the synchronization measures, information entropy, and time-frequency features of the multi-channel EEG are derived. Then a random forest applies to the eye-tracking recordings of the same subjects to single out the most significant features. A graph convolutional network model then naturally fuses the two group of features to differentiate the children with ASD from the typically developed subjects. Experiments have been carried out on the two types of the bio-signals collected from 42 children. The results indicate that the proposed approach can achieve an accuracy of 95% in ASD detection, and strong correlations exist between the two bio-signals collected even asynchronously, in particular the EEG synchronization against the face related/joint attentions in terms of covariance. (shrink)

It is shown that complex adaptations are best modelled as discrete processes represented on directed weighted graphs. Such a representation captures the idea that problems of adaptation in evolutionary biology are problems in a discrete space, something that the conventional representations using continuous adaptive landscapes does not. Further, this representation allows the utilization of well-known algorithms for the computation of several biologically interesting results such as the accessibility of one allele from another by a specified number of point mutations, (...) the accessibility of alleles at a local maximum of fitness, the accessibility of the allele with the globally maximum fitness, etc. A reduction of a model due to Kauffman and Levin to such a representation is explicitly carried out and it is shown how this reduction clarifies the biological questions that are of interest. (shrink)

Background and PurposeTranscranial direct current stimulation is an emerging non-invasive neuromodulation technique for focal epilepsy. Because epilepsy is a disease affecting the brain network, our study was aimed to evaluate and predict the treatment outcome of cathodal tDCS by analyzing the ctDCS-induced functional network alterations.MethodsEither the active 5-day, −1.0 mA, 20-min ctDCS or sham ctDCS targeting at the most active interictal epileptiform discharge regions was applied to 27 subjects suffering from focal epilepsy. The functional networks before and after ctDCS were (...) compared employing graph theoretical analysis based on the functional magnetic resonance imaging data. A support vector machine prediction model was built to predict the treatment outcome of ctDCS using the graph theoretical measures as markers.ResultsOur results revealed that the mean clustering coefficient and the global efficiency decreased significantly, as well as the characteristic path length and the mean shortest path length at the stimulation sites in the fMRI functional networks increased significantly after ctDCS only for the patients with response to the active ctDCS. Our prediction model achieved the mean prediction accuracy of 68.3% after the nested cross validation. The mean area under the receiver operating curve was 0.75, which showed good prediction performance.ConclusionThe study demonstrated that the response to ctDCS was related to the topological alterations in the functional networks of epilepsy patients detected by fMRI. The graph theoretical measures were promising for clinical prediction of ctDCS treatment outcome. (shrink)