Advances in Network Complexity E-Book
93,99 €
Mehr erfahren.
- Herausgeber: Wiley-VCH
- Kategorie: Wissenschaft und neue Technologien
- Serie: Quantitative and Network Biology
- Sprache: Englisch
A well-balanced overview of mathematical approaches to complex systems ranging from applications in chemistry and ecology to basic research questions on network complexity. Matthias Dehmer, Abbe Mowshowitz, and Frank Emmert-Streib, well-known pioneers in the fi eld, have edited this volume with a view to balancing classical and modern approaches to ensure broad coverage of contemporary research problems. The book is a valuable addition to the literature and a must-have for anyone dealing with network compleaity and complexity issues.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 532
Veröffentlichungsjahr: 2013
Ähnliche
Contents
Cover
Titles of the Series “Quantitative and Network Biology”
Title Page
Copyright
List of Contributors
Preface
Chapter 1: Functional Complexity Based on Topology
1.1 Introduction
1.2 A Measure for the Functional Complexity of Networks
1.3 Applications
1.4 Conclusions
References
Chapter 2: Connections Between Artificial Intelligence and Computational Complexity and the Complexity of Graphs
2.1 Introduction
2.2 Representation Methods
2.3 Searching Methods
2.4 Turing Machines
2.5 Fuzzy Logic and Fuzzy Graphs
2.6 Fuzzy Optimization
2.7 Fuzzy Systems
2.8 Problems Related to AI
2.9 Topology of Complex Networks
2.10 Hierarchies
2.11 Graph Entropy
2.12 Kolmogorov Complexity
2.13 Conclusion
References
Chapter 3: Selection-Based Estimates of Complexity Unravel Some Mechanisms and Selective Pressures Underlying the Evolution of Complexity in Artificial Networks
3.1 Introduction
3.2 Complexity and Evolution
3.3 Macroscopic Quantification of Organismal Complexity
3.4 Selection-Based Methods of Complexity
3.5 Informational Complexity
3.6 Fisher Geometric Model
3.7 The Cost of Complexity
3.8 Quantifying Phenotypic Complexity
3.9 Darwinian Adaptive Neural Networks (DANN)
3.10 The Different Facets of Complexity
3.11 Mechanistic Understanding of Phenotypic Complexity
3.12 Selective Pressures Acting on Phenotypic Complexity
3.13 Conclusion and Perspectives
References
Chapter 4: Three Types of Network Complexity Pyramid
4.1 Introduction
4.2 The First Type: The Life's Complexity Pyramid (LCP)
4.3 The Second Type: Network Model Complexity Pyramid
4.4 The Third Type: Generalized Farey Organized Network Pyramid
4.5 Main Conclusions
Acknowledgment
References
Chapter 5: Computational Complexity of Graphs
5.1 Introduction
5.2 Star Complexity of Graphs
5.3 From Graphs to Boolean Functions
5.4 Formula Complexity of Graphs
5.5 Lower Bounds via Graph Entropy
5.6 Depth-2 Complexity
5.7 Depth-3 Complexity
5.8 Network Complexity of Graphs
5.9 Conclusion and Open Problems
References
Chapter 6: The Linear Complexity of a Graph
6.1 Rationale and Approach
6.2 Background
6.3 An Exploration of Irreducible Graphs
6.4 Bounds on the Linear Complexity of Graphs
6.5 Some Families of Graphs
6.6 Bounds for Graphs in General
6.7 Conclusion
References
Chapter 7: Kirchhoff's Matrix-Tree Theorem Revisited: Counting Spanning Trees with the Quantum Relative Entropy
7.1 Introduction
7.2 Main Result
7.3 Bounds
7.4 Conclusions
Acknowledgments
References
Chapter 8: Dimension Measure for Complex Networks
8.1 Introduction
8.2 Volume Dimension
8.3 Complex Network Zeta Function and Relation to Kolmogorov Complexity
8.4 Comparison with Complexity Classes
8.5 Node-Based Definition
8.6 Linguistic-Analysis Application
8.7 Statistical Mechanics Application
8.8 Function Values
8.9 Other Work on Complexity Measures
8.10 Conclusion
References
Chapter 9: Information-Based Complexity of Networks
9.1 Introduction
9.2 History and Concept of Information-Based Complexity
9.3 Mutual Information
9.4 Graph Theory, and Graph Theoretic Measures: Cyclomatic Number, Spanning Trees
9.5 Erdos–Renyi Random Graphs, Small World Networks, Scale-free Networks
9.6 Graph Entropy
9.7 Information-Based Complexity of Unweighted, Unlabeled, and Undirected Networks
9.8 Motif Expansion
9.9 Labeled Networks
9.10 Weighted Networks
9.11 Empirical Results of Real Network Data, and Artificially Generated Networks
9.12 Extension to Processes on Networks
9.13 Transfer Entropy
9.14 Medium Articulation
9.15 Conclusion
References
Chapter 10: Thermodynamic Depth in Undirected and Directed Networks
10.1 Introduction
10.2 Polytopal vs Heat Flow Complexity
10.3 Characterization of Polytopal and Flow Complexity
10.4 The Laplacian of a Directed Graph
10.5 Directed Heat Kernels and Heat Flow
10.6 Heat Flow–Thermodynamic Depth Complexity
10.7 Experimental Results
10.8 Conclusions and Future Work
Acknowledgments
References
Chapter 11: Circumscribed Complexity in Ecological Networks
11.1 A New Metaphor
11.2 Entropy as a Descriptor of Structure
11.3 Addressing Both Topology and Magnitude
11.4 Amalgamating Topology with Magnitudes
11.5 Effective Network Attributes
11.6 Limits to Complexity
11.7 An Example Ecosystem Network
11.8 A New Window on Complex Dynamics
References
Chapter 12: Metros as Biological Systems: Complexity in Small Real-life Networks
12.1 Introduction
12.2 Methodology
12.3 Interpreting Complexity
12.4 Network Centrality
12.5 Conclusion
References
Index
Titles of the Series“Quantitative and Network Biology”
Advisory Board:
Volume 1
Dehmer, M., Emmert-Streib, F., Graber, A., Salvador, A. (eds.)
Applied Statistics for Network Biology
Methods in Systems Biology
2011
ISBN: 978-3-527-32750-8
Volume 2
Dehmer, M., Varmuza, K., Bonchev, D.(eds.)
Statistical Modelling of Molecular Descriptors in QSAR/QSPR
2012
ISBN: 978-3-527-32434-7
Volume 3
Emmert-Streib, F. Dehmer, M. (eds.)
Statistical Diagnostics for Cancer
Analyzing High-Dimensional Data
2013
ISBN: 978-3-527-32434-7
Related Titles
He, M., Petoukhov, S.
Mathematics of Bioinformatics
Theory, Methods and Applications
2010
ISBN: 978-0-470-40443-0
Schuster, H. G. (ed.)
Reviews of Nonlinear Dynamics and Complexity
Volume 3
2010
ISBN: 978-3-527-40945-7
Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty can be created or extended by sales representatives or written sales materials. The Advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor authors shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.
Library of Congress Card No.: applied for
British Library Cataloguing-in-Publication Data
A catalogue record for this book is available from the British Library.
Bibliographic information published by the Deutsche Nationalbibliothek
The Deutsche Nationalbibliothek lists this publication in the Deutsche Nationalbibliografie; detailed bibliographic data are available on the Internet at http://dnb.d-nb.de.
© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Boschstr. 12, 69469 Weinheim, Germany
Wiley-Blackwell is an imprint of John Wiley & Sons, formed by the merger of Wiley's global Scientific, Technical, and Medical business with Blackwell Publishing.
All rights reserved (including those of translation into other languages). No part of this book may be reproduced in any form – by photoprinting, microfilm, or any other means – nor transmitted or translated into a machine language without written permission from the publishers. Registered names, trademarks, etc. used in this book, even when not specifically marked as such, are not to be considered unprotected by law.
Composition Thomson Digital, Noida, India
Cover Design Schulz Grafik Design, Fußgönheim
Print ISBN: 978-3-527-33291-5
ePDF ISBN: 978-3-527-67047-5
ePub ISBN: 978-3-527-67048-2
mobi ISBN: 978-3-527-67049-9
oBook ISBN: 978-3-527-67046-8
List of Contributors
Sybil Derrible
Future of Urban Mobility Inter-
Disciplinary Research Group
Singapore-MIT Alliance for Research and Technology
1 CREATE Way #09-01/02
CREATE Tower
Singapore 138602
Singapore
Francisco Escolano
University of Alicante
Dpto. de Ciencia de la
Computacione eIA
03080 Alicante
Spain
Ángel Garrido
Faculty of Sciences UNED
Department of Fundamental Mathematics
Paseo Senda del Rey, 9
28040 Madrid
Spain
Vittorio Giovannetti
NEST, Scuola Normale
Superiore and Istituto
Nanoscienze-CNR
Piazza dei Cavalieri 7
56126 Pisa
Italy
Edwin R. Hancock
University of York
Department of Computer Science
Deramore Lane
York YO10 5GH
UK
Fang Jin-Qing
China Institute of Atomic Energy
P.O. Box 275-68
Beijing 102413
China
Stasys Jukna
Vilnius University
Institute of Mathematics and Informatics
Akademijos str. 4
08663 Vilnius
Lithuania
Hervé Le Nagard
University Paris Diderot
INSERM UMR-S 738
75018 Paris
France
Hildegard Meyer-Ortmanns
Jacobs University Bremen
School of Engineering and Science
Campus Ring 8
28759 Bremen
Germany
David L. Neel
Seattle University
Department of Mathematics
901 12th Ave
Seattle, WA 98122-4340
USA
Michael E. Orrison
Harvey Mudd College
Department of Mathematics
301 Platt Boulevard
Claremont, CA 91711
USA
Liu Qiang
China Institute of Atomic Energy
P.O. Box 275-68
Beijing 102413
China
Simone Severini
University College London
Department of Computer Science and Department of Physics & Astronomy
Gower St.
London WC1E 6BT
UK
O. Shanker
Shutterfly Inc.
2800 Bridge Pkwy
Redwood City, CA 94065
USA
Russell K. Standish
University of New South Wales
Mathematics and Statistics
Sydney, NSW, 2052
Australia
Olivier Tenaillon
University Paris Diderot
INSERM UMR-S 722
75018 Paris
France
Robert E. Ulanowicz
University of Florida
Arthur R. Marshall Laboratory, Department of Biology
Gainesville, FL 32611-8525
USA
and
University of Maryland
Chesapeake Biological Laboratory
P.O. Box 38
Solomons, MD 20688-0038
USA
Li Yong
China Institute of Atomic Energy
P.O. Box 275-68
Beijing 102413
China
Preface
Determining network complexity is a challenging problem that emerged in the 1950s. Seminal research on this problem was conducted by Rashevsky and Mowshowitz who investigated information measures designed to quantify the structural information content of a graph. These measures have been proven useful in various disciplines for quantifying the structure of complex systems that can be represented as networks. In the past few decades, a variety of methods using statistical, information-theoretic, and data analysis methods have been employed to meet the challenge of determining the complexity of real-world networks. One problem of ongoing interest is the numerical characterization of chemical graphs (especially QSAR/QSPR) with the aid of graph complexity measures. Such measures have also been used extensively for describing and predicting properties of complex molecular systems. Computer networks, especially the Internet, have occasioned yet further challenges for analysis of complexity using graph representations of real world systems.
The topic of network complexity has been examined from different perspectives in a variety of disciplines including discrete mathematics, computer science, computational biology, structural chemistry and structure-oriented drug design. In discrete mathematics and computer science, the focus has tended to be on the analysis and design of algorithms for solving problems concerning complex networks; in biology and chemistry, the principal aim has been to determine the structural or functional complexity of graphs used to represent complex systems. From a theoretical point of view, exploring network complexity is challenging and depends on the eye of a beholder as numerous methods/measures have been developed and, thus, there is no unique definition of network complexity.
The main goal of the book is to present and explain methods for determining the complexity of networks. Such methods have been developed with the aid of graph-theoretical techniques, information measures such as entropy, methods from complexity theory, and techniques based on boolean functions and statistical concepts. The book is intended for researchers, graduate and advanced undergraduate students in fields such as mathematics, computer science, chemistry, chemometrics and cheminformatics, ecology, physics, bioinformatics and systems biology.
Many colleagues, whether consciously or unconsciously, have provided us with input, help and support before and during the preparation of the present book. In particular we should like to thank Maria and Gheorghe Duca, Andrey A. Dobrynin, Boris Furtula, Ivan Gutman, Armin Graber, D. D. Lozovanu, Alexei Levitchi, Andrei Perjan, Ricardo de Matos Simoes, Fred Sobik, Shailesh Tripathi, Kurt Varmuza, Dongxiao Zhu, and apologize to all whose names have been inadvertently omitted. Also, we would like to thank our editors Andreas Sendtko and Gregor Cicchetti from Wiley-VCH who have been always available and helpful. Last but not least, Matthias Dehmer thanks the Austrian Science Funds (project P22029-N13) and the Standortagentur Tirol for supporting this work. Abbe Mowshowitz was sponsored by the U.S. Army Research Laboratory and the U.K. Ministry of Defence for research accomplished under Agreement Number W911NF-06-3-0001. The views and conclusions contained in this document are those of the author(s) and should not be interpreted as representing the official policies, either expressed or implied, of the U.S. Army Research Laboratory, the U.S. Government, the U.K. Ministry of Defence or the U.K. Government. The U.S. and U.K. Governments are authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation hereon.
To date no book dedicated exclusively to network complexity has been produced. Existing books dealing with related topics such as complexity and complex networks have limited scope, considering only some specialized graph measures that could be used to determine the complexity of networks. Therefore we hope that this book will broaden the scope of scientists who deal with network complexity approaches. Finally, we hope this book conveys the enthusiasm and joy we have for this field and inspires fellow researchers in their own practical or theoretical work.
Hall/Tyrol, New York, and Belfast, April 2013
Matthias Dehmer, Abbe Mowshowitz, and Frank Emmert-Streib
1
Functional Complexity Based on Topology
Hildegard Meyer-Ortmanns
1.1 Introduction
Complexity measures have been proposed as measures for computational, statistical, or structural complex features in various contexts; for review, see [1]. A complexity measure for patterns, for example, arising in chaotic systems, has been proposed in [2]. It is a measure theoretic concept that applies to ensembles of patterns. It is natural in the sense that it reflects the intuitive notion of a complex pattern being neither completely random nor completely regular, but having some structure instead. Complexity of hierarchical systems has been studied in [3]. The complexity measure has the property of isolating the most diverse trees as the ones with maximal complexity. Intuitively one would expect that the complexity of a hierarchy is related to its diversification, that is, to the number of nonisomorphic subtrees found at that level. The proposals given by Ceccatto and Huberman [3] reproduce this expectation. Recently, information storage and transfer was analyzed in [4,5]. A number of complexity measures that are based on various notions of graph entropy have been proposed. Graph entropies are supposed to characterize the structural information content of graphs; what is meant by “information” depends on the context. For review, see [6]. In particular, such measures are used in applications to chemical structures of molecule graphs whose vertices represent atoms and edges represent chemical bonds [7]. Moreover, in connection with molecule graphs, various “distance-related topological indices” are defined [8], for which the connotation of “topology” and spirit of derivation is very different from ours, although the wording may suggest an apparent overlap.
Our complexity measure is based on a proposal presented in [9]. We do not restrict our considerations to graphs that are trees and do not study branching properties of trees. Our graphs can represent a generic network as a dynamical system with n input and m output channels with directed or undirected edges. We restrict the graphs to one type of nodes, one type of edges, and one type of connectivities of nodes via these edges. There may be an arbitrary number of loops. The structural complexity of a graph needs to be considered with an associated dynamics. Hence, the result of our complexity measure will sensitively depend on the dynamics, of which the graph is just a rough abstraction that is supposed to indicate the mutual interactions. In our applications, a whole dynamical system may be assigned to a single node, and a path of regulation or transportation to an edge, where the edge can be equipped with its own dynamics.
Given a graph and the associated dynamics, we determine the complexity measure in two steps. The first one, called the vertex resolution, leads to a proliferation of patterns assigned to this graph, and the second one leads to a selection of only those patterns that are topologically inequivalent. This way we “get rid” off the entropy, generated by symmetries of the initial graph and generated patterns. Therefore, our approach is complementary to measures based on entropies of graphs.
Both steps, the vertex resolution and the restriction to topologically inequivalent contributions, are motivated by dynamical systems. Vertex resolutions “break up” the vertices into parts in all allowed ways leading to rewiring of edges, or a fusion or fission of interaction paths between the vertices; vertices represent nodes which in a broad sense transform an input in kin channels to an output in kout channels, regulating the flux of cargo, traffic, energy, fluid, or information. Their splitting may create or destroy loops, an important basic motif in networks. Not all patterns, resulting from this process of partitioning the edges assigned to a vertex, are dynamically allowed, as we will see later.
The selection of topologically inequivalent graphs is motivated by the fact that whole classes of dynamical systems are known to exist, whose space of attractors and their associated functions are to a large extent determined by their topology, that is, by fixing the mutual interaction. (Attractors are understood as stationary states that can be fixed points, limit cycles, or chaotic attractors of the dynamics. Their relation and interpretation in terms of a “function” is not always obvious, but sometimes possible.) The conjecture then is that changing the topology changes the function or functionality of these systems, so that the complexity measure gives a hint on the functional flexibility of the dynamical systems, natural and artificial ones, represented by the considered graph.
In particular, the concept of functionality applies to networks in life science and in information science. Network motifs have been studied as characteristic building blocks for complex networks [10]. They are local subgraphs or wiring patterns that occur throughout the network significantly more often than in randomized networks. As a result, motifs shared by ecological food webs are specifically different from those in genetic networks. More generally, it has been found in [10] that motifs in networks of information processing are typically distinct from networks of energy transporting. Information processing may refer to nets as diverse as those of gene regulation, neurons, and electric circuits. The overall conclusion is that frequently repeated motifs should represent certain functions.
At a first place, to make these concepts well defined, in particular the topological equivalence of two graphs, we use the framework of LCE-graphs, in which LCE stands for “linked cluster expansions” used in statistical physics. The appropriated definitions are introduced in Section 1.2.1, followed by a definition of the vertex resolution patterns of a graph in Section 1.2.2. Section 1.2.3 contains a short excursion to link invariants and Kauffman states, which are usually used for calculating Jones polynomials as link invariants. The reason for this excursion is a close correspondence between the decomposition of a link into Kauffman states and our scheme of vertex resolutions. We are then ready to define a measure for functional complexity in Section 1.2.4. In Section 1.3, we illustrate with examples from dynamical systems a number of cases, in which the topology determines the function. We start with a very simple system of phase oscillators in Section 1.3.1. Next we indicate applications to transport networks of information (Section 1.3.2) or of cargo (Section 1.3.3), to Boolean networks in Section 1.3.4, and to topological quantum systems in Section 1.3.5. In Section 1.3.6, we sketch a dynamical system, of which the steering dynamics on the highest level of its hierarchical organization is stored in the topology of a knot. In Section 1.4, we draw the conclusions. Throughout this contribution, we will use “lines” and “edges”, and “vertices” and “nodes”, in a synonymous way, respectively.
1.2 A Measure for the Functional Complexity of Networks
1.2.1 Topological Equivalence of LCE-Graphs
As usual in the context of networks, our graphs consist of nodes and edges (or vertices and lines), the edges may be directed or undirected; in principle, we can formulate our notions of topological equivalence for graphs with two type of connectivity: nodes are connected via edges, and edges are connected via a different kind of nodes. Such a type of connectivity was naturally introduced in the context of the graphical representation of a generalized high-temperature expansion in spin glasses, if not only the spins interact via their couplings, but the couplings self-interact with their own dynamics, see [11,12]. For simplicity, we focus here on undirected graphs with only one type of connectivity, represented by graphs with internal and external lines – internal lines to describe internal interactions and external lines for input and output channels in the general context.
Let us now define in detail the notion of an LCE-graph and the topological equivalence of two such graphs. The notions are obtained as special case of those introduced in [11]. An LCE-graph is a structure
(1.1)
Here and are two mutually disjoint sets of internal lines of and vertices of , respectively. are maps that assign the number of external lines to every vertex . are incidence relations that map internal lines to their endpoint vertices. Lines are treated as undirected; the generalization to directed ones is easily done. We consider as the set of unordered pairs of vertices with . Then we have . We say and are the endpoint vertices of if . A line with only one vertex attached is an external line. In a concrete realization, the incidence relations may be realized as a matrix , with
(1.2)
defined in the following way. Given a graph with vertices, internal lines, external lines, and a labeling of vertices and internal lines. is a symmetric matrix with equal to the number of internal lines (i.e., a natural number including 0) connecting and for , . As long as we do not allow self-lines (i.e., lines starting and ending at the same vertex), the diagonal elements may be reserved for storing the number of external lines attached to vertex . The matrix , representing the incidence relations, would be suited for computer implementations of LCE-graphs as it allows computer-aided algorithmic generation of graphs.
Now we can formulate in a purely algebraic way when are two LCE-graphs topologically equivalent. Two LCE-graphs
(1.3)
are called topologically equivalent if there are two invertible maps
(1.4)
between the sets of vertices, and the set of internal lines of these graphs and such that
(1.5)
and
(1.6)
Here is understood as the composition of maps, and
(1.7)
For example, (1.5) means that the following compositions of maps are equivalent: first assign via the endpoint vertices to a given internal line of the first graph and map them to the corresponding vertices in via , or, alternatively, first map the given internal line of the first graph to the corresponding internal line of the second graph via , and then associate the endpoint vertices with this line there via . Both orders are equivalent if graphs are topologically equivalent. Equation (1.6) states the equivalence of assigning the external lines either to the vertex of the first graph or to the corresponding vertex of the second graph. Figure 1.1 shows four graphs, of which three (a), (b), and (c) are topologically inequivalent, but two (c) and (d) are equivalent. Below we will define admissible vertex resolutions. The graphs (c) and (d), “fragmentized” into two pieces, would not be admissible as contribution to a connected two-point correlation function.
Figure 1.1 Topologically (in) equivalent graphs: (c) and (d) are equivalent, whereas (a), (b), and (c) are not.
1.2.2 Vertex Resolution Patterns
Apart from operations like adding or removing vertices, or lines, with or without the attached structures, one operation is of interest in this context that is the resolution of vertices. Let be an LCE-graph, a vertex with lines ending upon it, and let be any partition of the set of lines ending on . is the set of all partitions of lines ending on . (A partition is a disjoint union of subsets of lines ending on such that it gives .). We remove the vertex and draw for every subset of lines a new vertex , so that all lines enter the vertex rather than before its removal. This procedure is called a vertex resolution of . For example, see Figure 1.2 showing three partitions of the original set of four lines, where we left out partitions into vertices with single lines attached. Also we left out permutations from two other possible pairings of lines, which should be taken into account when the lines are labeled. Note that this resolution procedure amounts to a rewiring of lines. It then depends on the dynamical constraints whether the resulting (resolution pattern of a) graph is allowed or not. For example, the graph may become disconnected and fragmentize into several pieces as a result of the resolution procedure. Such a resolution is forbidden if the considered graphs must be connected. More generally, a vertex resolution is called admissible if it satisfies all constraints from the dynamics or from the choice of observables.
Figure 1.2 Three possible resolution patterns (b), (c), and (d) of the graph in (a).
A remark may be in order on what has led us to introduce the concept of vertex resolutions. In the original formal context of so-called dynamical linked cluster expansions [11], the graphs (c) and (d) of Figure 1.1, which now fragmentize into independent parts, could remain connected if one allows self-interactions of spin couplings, represented by lines. These graphs would then contribute to a connected two-point function, for example. But also in connection with linked cluster expansions, one is naturally led to consider resolutions as shown in Figure 1.3 when calculating symmetry factors of an internal symmetry like color or flavor symmetry. For example, assuming an underlying O(N)-symmetry of the system, one of “colors” (“flavors”, “features”, or “bits”) may propagate along each line. In calculating the internal symmetry factor, one looks for all possible paths along which feature 1, say, out of N, can propagate from the input channel through the graph to yield feature 1 in the output channel, while a closed loop may carry any one of the features, and only one feature can propagate along a line at the same time. As shown in Figure 1.3, feature 1 can propagate along the upper line, say , along with possible features for the loop of the remaining lines, and , or it can propagate along , or , or it could choose the intermediate line , or the lower line first, yielding possibilities altogether.
Figure 1.3 Propagation of a “color” labeled as 1 along different paths in three resolution patterns.
Consider the special case of vertices of degree 4 in a closed graph without external lines, and interpret the vertices as crossings of two lines, resulting from a two-dimensional projection of under- or overcrossings in links (for the definition of “link,” see Section 1.2.3) in three dimensions. In this case, our vertex resolutions contain a decomposition of two-dimensional link diagrams into a sum over Kauffman states as we show in the following section.
1.2.3 Kauffman States for Link Invariants
Let us briefly recall some basic facts about knots and links. A “knot” as defined by mathematicians is a submanifold of that is diffeomorphic to , the circle. An example for a two-dimensional projection of a trefoil is shown in Figure 1.4. The over- or undercrossings of the “rope” in three dimensions are indicated with continuous or broken lines, respectively. A “link” is a submanifold of that is diffeomorphic to a disjoint union of circles. The circles are components of the link. A link with two components is the Hopf link, as shown in Figure 1.5. For classifying knots or links, a number of link invariants have been proposed such as the Jones polynomial. Kauffman's approach to Jones polynomials made it a simple construction [13]. The first step is to define the Kauffman bracket of a link L, , which is then used to construct the Jones polynomial. The Kauffman bracket is a function of three variables, , , and . Choosing , , the Kauffman bracket will be invariant under Reidemeister moves. Now, rather than summing over the crossings of the link L, the Kauffman bracket sums over states , which we here will call Kauffman states. Such a state of L assigns to each crossing of L a number that is either A or B, so that a link of N vertices has possible states. Given a state of a link L, we orient each crossing c such that the overcrossing line points upward to the right and the broken line upward to the left as on the left-hand sides of Figures 1.6 and 1.7. Assigning the variable A to this crossing means to avoid it according to Figure 1.6, and assigning the variable B implies an avoiding according to Figure 1.7. This way all crossings are avoided and the resulting diagram consists of a finite set of circles, embedded in the plane, as indicated in Figure 1.8 for the Hopf link. The Kauffman bracket is then defined by a sum over all Kauffman states according to
(1.8)
where denotes the number of circles of the state . (For the Hopf link, the Kauffman bracket is then given by ). Now it should be obvious why we have made this excursion to link invariants in connection with our resolution patterns. For the special case that our graphs have no external lines, and the vertices of the links have all degree 4 corresponding to two crossing lines, our decomposition into patterns contains the decomposition into Kauffman states as a subset of all partitions. The kind of summation reminds to a sum over states of a partition function, and the relation can be made precise in both cases, see [10,14]. In Section 1.3.6, we will indicate a possible application of these link diagrams as generating functions of dynamical processes that arise from different Kauffman states of these links.
Figure 1.4 Trefoil knot.
Figure 1.5 Hopf link.
Figure 1.6 First possibility of avoiding the crossing. In this case, the variable A is assigned to the crossing.
Figure 1.7 Second possibility of avoiding the crossing, here labeled as B.
Figure 1.8 Kauffman states of the Hopf link.
1.2.4 Definition of the Complexity Measure
We are now prepared to define a measure for the functional complexity of networks. It is defined as
(1.9)
that is, it counts the total number of topologically inequivalent admissible resolution patterns of the graph of that network (here defined for an LCE-graph), normalized over all admissible patterns. The prime stands for the restriction to topologically inequivalent and admissible patterns. A resolution pattern is obtained by allowing any resolutions of vertices, denoting the total number of vertices of . It is admissible if it is compatible with the constraints imposed by the dynamics. Two resolution patterns are topologically equivalent if there exist two invertible maps (1.4) between their associated graphs and that satisfy (1.5)–(1.7).
Examples for dynamical constraints are as follows:
After the resolution of vertices, the resulting graph should stay connected.Vertices should have an even number of lines attached. This constraint may reflect an underlying symmetry of the dynamics, which forbids an odd number of attached lines.There are no lines that start and end at the same vertex (i.e., no self-lines or tadpoles).Conservation laws should be respected at each vertex.Rewiring of edges should avoid geometric frustration. It may happen that the vertex resolution leads to the creation of loops such as in the first resolution pattern of Figure 1.3. If the edges are not directed but represent repressing interactions, a loop with an odd number of such edges will lead to geometric frustration [15]. In case of directed edges, representing repressing interactions, an even number of such edges in a loop leads to geometric frustration. If the network shall be designed in a way to avoid geometric frustration, such resolution patterns would be excluded.In our definition of the complexity measure, we count all admissible resolution patterns of graphs with equal weight. In general, it may happen that certain topologically inequivalent patterns are admitted, but dynamically strongly suppressed in some small parameters like a coupling constant. For such cases, the measure should be generalized accordingly.
The scaling of this measure with the number N of (unresolved) vertices is bounded by if denotes the maximal degree of vertices in the network. The actual scaling, however, can be quite different from this exponential proliferation of patterns due to the dynamical constraints.
Our conjecture is that the restriction to topologically inequivalent resolution patterns projects on inequivalent functionalities. We shall give examples in the following sections.
1.3 Applications
The definitions in the previous sections with graphs induced by linked cluster expansions mainly served to illustrate that the notions of topologically inequivalent resolution patterns of graphs (which are themselves graphs) can be well defined and tested in a computer-aided way by analyzing their matrix representations. From now on, we consider any interpretation of such graphs for which the concept of vertex resolution is meaningful.
1.3.1 Creation of a Loop
Let us start with a very simple example in which it is only the topology that determines the attractor of the dynamics, here a synchronized state of a system of interacting phase oscillators. Consider an open chain of coupled phase oscillators, assigned to the nodes of the chain, which are coupled to their nearest neighbors apart from those at the boundaries which have only a neighbor on one side. Depending on the choice of parameters, the oscillators can then oscillate either completely independently of each other or in full synchrony with a fixed phase difference between them. Now let us choose the parameters such that the oscillators are in an incoherent state for open boundary conditions along the chain. As we have shown in [16], the mere closure of the open chain to a closed loop is then sufficient to induce synchronization of the whole set without any other change of parameters. The switch to a synchronized state induced by a change in the topology holds for a whole range of parameters, for which the chain of oscillators is dephased.
More generally, loops, whether undirected, or directed as feedback loops or feedforward loops, play an important role as a basic motif in network dynamics.
1.3.2 Networks of Information
Recently, a discrete-time Gaussian model was analyzed with respect to its capability of storing information on individual nodes, given the network structure and the weights of the edges [4,5]. The authors show that directed feedback or directed cycles and feedforward loop motifs dominantly contribute to the capability of information storage. For example, in this model, feedforward loops let information pass to another node along paths of different lengths, so that the information arrives at different instants of time. This effectively amounts to an intermediate storage of this information at another place within the network. (The active information storage is calculated in terms of certain entropies.) Moreover, the longer such loops, the longer the memory which in principle can be incorporated in such networks.
If our decomposition of nodes in the context of neural networks leads to resolution patterns of graphs that yield a number of loops with a variety of loop lengths, such a network architecture is flexible in its memory capacity and depth. In contrast to loops, a full decomposition of the network graph into trees of different roots would reflect the possibility of a fully parallel transport of information over time.
1.3.3 Transport Networks of Cargo
For transport networks of cargo, the edges correspond to roads or tracks, and the logistics of transport is much determined by the traffic regulations at the crossings. A large value for the complexity measure here would reflect many ways of partitioning the road network for optimizing the speed of transport, the avoidance of traffic jams, the amount of transported cargo, but also a time-ordered supply to have the cargo at the right time at the right place. Different partitions, corresponding to different vertex resolutions, would stand for different strategies to satisfy the logistic requirements. Here we do not only think of macroscopic traffic networks and traffic regulations in cities; one may think of smart energy grids with an efficient design for the transport of power based on renewable energy. On the one hand, one would like to make the network robust against a global electric power outage, so that some redundancy in the number of cables seems to be required. On the other hand, one should avoid Braess' paradox [17] that is well known to occur in traffic systems. It is also known for power networks that the addition of a single route may induce an outage rather than improving the robustness. Such considerations would lead to constraints on the admissible partitions of the road network. In more formal terms, the design should avoid geometric frustration (“frustration” in a similar sense as it is used in spin systems (see [15]), since frustration amounts to conflicting regulations at crossing points of loops. Calculating then our complexity measure for such a traffic network of a given fixed size would not be conclusive on its own, but its scaling with the system size together with a dynamical process of traffic (energy transport) would be conclusive for the network's transport capacity.
Much more fancy transport networks than the artificial ones on the macroscopic scale can be found in natural networks on the mesoscale, realized in the cytoskeleton of eukaryotic cells. The cytoskeleton provides structure and organization of cells, but also drives their change of shape and movement and transforms applied stress, transmitting or resisting it [18]. Within the cytoskeleton, there are three networks: actin filaments together with crosslinkers on the smallest scale, intermediate filaments, and microtubules on the largest scale. Microtubules play a key role in particular for intracellular transport. It is a focus of current research what exactly regulates this traffic, and how traffic jams or malfunctions are avoided in a healthy organism. In contrast to the static networks on the macroscopic scale (often also equipped with static traffic regulations), the networks on the nano- and microscales have a highly dynamic structure. “Roads” and crosslinkers are regularly created and destroyed as in our purely formal vertex “fission” and “fusion” events, in which connections to other edges can be lost or are newly created. Yet we are far off from establishing a direct connection between the functional complexity of this complex viscoelastic material in the cell and our complexity measure that would only indicate the number of inequivalent arrangements of traffic lines. In any case, here the topological aspect is certainly not sufficient to capture the very rich, sophisticated functional behavior of the cytoskeleton, since the very material properties of the involved networks matter as well as metric features related to the range of forces, the very size of the cargo, tracks and crosslinkers, and the very timing of the processes.
Therefore, in regard to an optimal design of a flexible topology of transport networks, one should take into account the nature of the material that is transported, whether it is cargo, energy flux, fluid, single information bits, or signals for regulation. This leads us to the next class of networks for which the topology decides about certain functions which the network can perform.
1.3.4 Boolean Networks of Gene Regulation
Boolean networks provide a prominent example for systems in which it is the topology that determines to a large extent the dynamical attractors, and the attractors can be identified with certain functions. Boolean modeling of gene regulatory networks was very successful for the segment polarity gene network [19], dealing with genes involved in the embryonic pattern formation in the fruit fly Drosophila melanogaster. As it was shown in [19], it is the topology of the regulatory network that essentially determines the dynamics and the overall function, and it is much less the kinetic details of this system which matter. To expose more clearly the connection between function and topology (connectivity), the original graph of the segment polarity network is expanded toward the inclusion of so-called complementary and composite “pseudonodes,” in particular to represent more clearly the logical functions and to account for the two possible signs of interaction ((+) for activating and (−) for repressing interaction). This extension toward further vertices is different from our resolution patterns, but in a similar spirit to reflect further details of the dynamics in the graphical representation.
Another prominent example for a successful description of a genetic system in terms of Boolean functions is provided by the yeast cell cycle [20]. Again it is the topology in which the regulatory functions are arranged that determine the dynamic attractors and their basins of attraction, whose size reflects the robustness against perturbations. In case of the modeling of the yeast cell cycle, one is in the lucky situation, as the intimate relation is obvious not only between Boolean functions and topology but also between biological function and topology, since the attractors can be interpreted in biological terms, such as an attractor corresponding to the G1 state, that is the biological stationary state of the cell cycle, here of yeast. In this system, it is possible to observe how the biologically realized cell-cycle sequence of protein states is an attractive trajectory in the Boolean dynamics with a global range of attraction [20].
It is particularly this kind of systems behind our idea that inequivalent topologies go along with different functionalities.
1.3.5 Topological Quantum Systems
Next we come to an extreme case of a class of systems, in which the functions exclusively depend on the topology. These are quantum systems in which the quantum mechanical amplitude of a particular process depends only on the topology of this process. This means, if the paths, which particles trace out in space-time, are topologically equivalent, they will be equally likely. Theories that describe such topological quantum systems are called topological quantum field theories [21]. In these systems, the amplitude for a particular process is a knot invariant of the space-time paths followed by the particles during this process. Out of a two-particle, two-hole system, one can construct a two-state quantum system or a single quantum bit. This suggests the possibility to use topological quantum systems as quantum computers. Different types of braids (structures formed by intertwining three or more paths) correspond to different quantum computation, so that there is a direct relation between the topology and the function (of performing a calculation). Different realizations of such quantum systems are currently explored. Computations performed in this way would be much more robust against noise of various origin, since they only depend on the topology, but not on other details of the space-time paths.
1.3.6 Steering Dynamics Stored in Knots and Links
Let us finally sketch a toy model for a dynamical system with a hierarchical organization. On the highest level, the steering level, we store the instructions and initializations for dynamical processes taking place on a lower level. These instructions are stored along closed strings which are knotted. To be definite, let us consider the Hopf link of Figure 1.5. Next we let a nanomachine walk along the knotted link, that is along the different pieces of the path, labeled as , , , and in Figure 1.8. During its walk, the machine translates the instructions into operations , , , and , acting upon the dynamics on the underlying level. These operations need not commute. The function of the resulting dynamics on the underlying level will likely reflect the order , , , and of the noncommuting operations, corresponding to the order in which the instructions were read off. Now we offer the nanomachine two options at each crossing to avoid the over- or undercrossing of another string, the two options just corresponding to Figures 1.6 and 1.7. In this case, the instructions along the Hopf link would be read off either in pairings of two pieces to one cycle each, with for the first cycle and with for the second cycle (Figure 1.8a), or, alternatively, with δ for the first and β with γ for the second cycle (Figure 1.8d), or to a single cycle in the order α, δ, γ, and β (Figure 1.8b), or to another single cycle in the order of α, β, γ, and δ (Figure 1.8c), up to cyclic permutations. For noncommuting operations, the versatility of the dynamical performance of the whole system would then be determined by (the Kauffman states of) the Hopf link, associated with the steering level.
A desirable feature of such an organization in general would be that the dynamics on the steering level depends mainly on the topology, since this guarantees a highly robust performance, while less robustness is required for the lower levels in view of the maintenance of the system as a whole. Of course, one may wonder what steers the superimposed dynamics that determines the decisions of the nanomachines at the crossings while they are reading out the instructions along the path. This may be some feedback from the overall performance after the instructions are carried out.
1.4 Conclusions
As we have seen, along with the versatile interpretation of graphs that represent dynamical processes on and of networks, our manipulation of graphs in terms of fusion and fission of nodes and edges has different applications, ranging from transport networks of cargo, energy, or flux to those of transport of information and to regulatory gene networks, described by Boolean functions. After all one may wonder why we distinguish at all between graphs of these networks and their possible resolution patterns if it is mainly the latter which may be directly related to certain functions. The answer is best provided by the answer to an analogous question: Why do we consider links like the Hopf link rather than the associated Kauffman states? The graphs classify the dynamical system, and the resolution patterns correspond to concrete and particular realizations. In the toy model of the last section, it would be the link invariant that would characterize a whole class of dynamical systems by their steering dynamics. In general, we expect a close relation between function (performance) and topology in regulatory systems, which are not sensitive to kinetic details or metric measures such as the size and distance of the involved objects.
Characterizing a complex performance of a dynamical system by a single number such as our complexity measure is certainly not conclusive if we know this number just for a single system size. However, the scaling of this measure with the system size can be revealing. As we have indicated in Section 1.2.4, the scaling need not be exponential in the number of vertices, but can be rather nontrivial due to the presence of dynamical constraints that should be satisfied by the admissible vertex resolutions. Since the measure sensitively depends on the very choice of the dynamics, there are no universal scaling laws; results in concrete applications, however, will be useful for deciding the storage capacity of a network, the robustness of large regulatory systems, or the feasibility of a calculation. In our original application of counting the (topologically inequivalent) resolution patterns of vertices, occurring in a generalized linked cluster expansion for spin glass systems [10,11], this number was a measure for the computational complexity of the problem, so that a computer-aided algorithmic generation of graphs was needed to go to higher orders in the expansion. For a neural network, this number may give a hint on the storage capacity in terms of the abundance of special loop motifs. In nonrandom Boolean networks, it would be interesting to see whether the number reflects a nonexponential scaling with the system size if all dynamic constraints are taken into account that apply to genetic systems, and if the sequential, nonrandom order of regulations is respected in the Boolean modeling. Here it is most interesting to understand why not all in principle allowed combinations (“resolution patterns”) are realized in nature, since the observed number of stable attractors (supposed to represent the stable cell states) is relatively low as compared to the huge number that would be possible without additional constraints.
In summary, it is not all kind of dynamical systems to which we would apply this measure, but those in which the topology of the network has the main influence on the stationary states of the system.
References
1. Wackerbauer, R., Witt, A., Atmanspacher, H., Kurths, J., and Scheingraber, H. (1994) A comparative classification of complexity measures. Chaos, Solitons Fractals, 4, 133.
2. Grassberger, P. (1986) Toward a quantitative theory of self-generated complexity. Int. J. Theor. Phys., 25, 907.
3. Ceccatto, H.A. and Huberman, B.A. (1988) The complexity of hierarchical systems. Phys. Scripta, 37, 145.
4. Lizier, J.T., Prokopenko, M., and Zomaya, A.Y. (2008) Local information transfer as a spatiotemporal filter for complex systems. Phys. Rev. E, 77, 026110.
5. Lizier, J.T., Prokopenko, M., and Zomaya, A.Y. (2010) Information modification and particle collisions in distributed computation. Chaos, 20, 037109.
6. Dehmer, M. and Mowshowitz, A. (2011) A history of graph entropy measures. Inform. Sci., 181, 57.
7. Nikoli, S., Trinajsti, N., and Toli, I.M. (2000) Comlexity of molecules. J. Chem. Inf. Comput. Sci., 40, 920.
8. Randi, M., Balaban, A.T., and Basak, S.C. (2001) On structural interpretation of several distance related topological indices. J. Chem. Inf. Comput. Sci., 41, 593.
12. Meyer-Ortmanns, H. (2004) Functional complexity measure for networks. Physica A, 337, 679.
9. Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., and Alon, U. (2002) Network motifs: simple building blocks of complex networks. Science, 298, 824.
10. Meyer-Ortmanns, H. and Reisz, T. (1999) Dynamical linked cluster expansions: a novel expansion scheme for point-link-point interactions. Int. J. Mod. Phys., A14, 947.
11. Meyer-Ortmanns, H. and Reisz, T. (2002) Dynamical linked cluster expansions with applications to disordered systems. Eur. Phys. J., B27, 549.
13. Kauffman, L.H. (1987) On Knots, Annals of Mathematics Studies, Princeton University Press, Princeton, NJ.
14. Nechaev, S.K. (1996) Statistics of Knots and Entangled Random Polymers, World Scientific Singapore Publishing Co Pte Ltd, Singapore.
15. Kaluza, P. and Meyer-Ortmanns, H. (2010) On the role of frustration in excitable systems. Chaos, 20, 043111.
16. Radicchi, F. and Meyer-Ortmanns, H. (2006) Entrainment of coupled oscillators on regular networks by pacemakers. Phys. Rev. E, 73, 036218.
17. Braess, D. (1968) Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung, 12, 258.
18. Fletcher, D.A. and Dyche Mullins, R. (2010) Cell mechanics and the cytoskeleton. Nature, 43, 485.
19. Albert, R. and Othmer, H.G. (2003) The topology of the regulatory interactions predicts the expression pattern of the segment polarity genes in Drosophila melanogaster. J. Theor. Biol., 223, 1.
20. Li, F., Long, T., Lu, Y., Ouyang, Q., and Tang, C. (2004) The yeast cell-cycle network is robustly designed. Proc. Nat. Sci. Am. USA, 101 (14), 4781.
21. Kitaev, A. (2003) Fault-tolerant quantum computation by anyons. Ann. Phys. NY, 302, 2.
2
Connections Between Artificial Intelligence and Computational Complexity and the Complexity of Graphs
Ángel Garrido
2.1 Introduction
The historical origin of the ideas about thinking machines, the mechanism through working of the human brain, the possibility of mimicking its behavior, if we produce some computational structure similar to neuron, or to neural system, their synapses or connections between neurons, to produce neural networks (NNs) [1–8]... all this can appear with resonances of a Science Fiction history, or a movie, but it is a real subject of study, and it is so from many years ago, and more in the past times.
The basic purpose of the artificial intelligence (denoted by AI) is to create an admissible model for the human knowledge [2,9–11]. Its subject is, therefore, “pure form.” We try to emulate the way of reasoning of a human brain. This must be in successive, approximating steps, but the attempts proceed always in this sense.
Initially, the work in AI was over idealizations of the real world. So, attempting the automatical proof of theorems, or modeling games, and so on. The fields were, therefore, formal worlds. Such search procedures were into the Space of States. This contains the set of all states, or nodes, in the case of representation by graphs, that we can obtain when we apply all the disposable operators [12].
Many early AI programs used the same basic algorithm. To achieve some goal (winning a game or proving a theorem), they proceeded step by step toward it (by making each time a move or a deduction) as if searching through a maze, backtracking whenever they reached a dead end. This paradigm was called reasoning as search.
The techniques for solving problems, on AI, can be of two types, Declarative: it permits the description of the known aspects of the problem; this is the Heuristic Treatment, and Procedural: it itemizes the necessary paths to reach the solution of the problem; this is the Algorithmic Treatment.
To pose problems is equivalent to constructing its solutions [9,10–14]. This requires an agent, the system or program to execute; a set of actions, which allows one to reach such objectives; and a procedure of election, which allows us to decide between distinct paths to reach its solution.
In computational complexity, the measure of complexity of an object is the smallest number of “elementary operations” that is enough to produce a given object starting from some “simplest” objects, the so-called generators. Such a sequence of operations will be called a circuit. The size of the circuit is the number of objects in it. Every circuit for an object can be viewed as a “code.” The larger the circuit must be (i.e., the more operations are required to produce the object), the more “complex” the object is.
The aim of this chapter is to analyze some of the main lines of work in computational complexity related to graphs. Also, graph complexity will be discussed that is a rapidly advancing field and of great interest in AI and related disciplines.
2.2 Representation Methods
We can use a series of resources [2,11,12] approaching problems dealing with AI, such as Logic, Rules, Graphs, Associative Nets, Frames, and Scripts. The election between these methods must be based in the own characteristics of the problem and our expectations about the type of solution.
Many knowledge representation (KR) methods were tried in the 1970s and early 1980s, such as heuristic question-answering, NNs, theorem proving, and expert systems, with varying success. Medical diagnosis (e.g., MYCIN) was a major application area, as were games such as chess. In the 1980s, formal computer knowledge representation languages and systems arose. Major projects attempted to encode wide bodies of general knowledge. In computational linguistics, much larger databases of language information were being built, and these, along with great increases in computer speed and capacity, made deeper KR more feasible. Several programming languages have been developed that are oriented to KR. Prolog developed, in 1972, but popularized much later, represents propositions and basic logic, and can derive conclusions from known premises. In the electronic document world, languages were being developed to represent the structure of documents [1]. These facilitated information retrieval and data mining efforts, which have in recent years begun to relate to KR. Development of the Semantic Web has included development of XML-based knowledge representation languages, and standards, including RDF, Topic Maps, and so on.
In many cases, working on KR, we take at the same time two or more tools [2,9], as in the case of the Frame System, with participation of Inference Rules. About the usual way of appearance of Rules, as Rule-Based Systems (RBS), we need
Interface of Usuary (IU), useful for the interaction with the usuary.Motor of Inference (MI), to control the flow of information among the different modules.Base of Facts (BF), contains the initially known facts and those created during the process.Knowledge Base (KB), containing the Rules used for the Representation of Knowledge, into a certain Domain.There exists a two-way flow. From the MI to IU and from MI to BF, but only in one way between KB and MI, not in the contrary direction, except if we accept in the system the capacity of learning.
The Inference in SBR consists of establishing the certainty of some statement [11,15], from the disposable information into BF and KB. We have two methods, going forward and going backward concatenation.
In the first case, we start off with Rules having verified affirmations in its antecedent, advancing through the affirmations that we find in their consequents.
While in the second case, we depart with Rules verified in certain consequence (all the consequences must be also verified), and we turn back to the antecedent. This converts their affirmations in new sub-objectives for the proof, searching Rules which appear in its consequence, and so on. To hold up this process, we find the required affirmation in the last consequent explored or the last antecedent, according to the selected method.
The Rules show advantages on Classical Logic, where the reasoning was monotonic with inferences without contradicting preexisting facts. While in the RBS we can delete or substitute facts of the Base of Facts, according to the new inferences. All of these may be provisional and modifiable. This made the Reasoning Non-Monotonic.
In the case of some applicable rules at time, what must be executed first? Such a set of Rules constitutes, in each step, the Conflict Set (which will be dynamic, obviously). The subjacent decision problem is called Resolution of Conflicts, or also named Control of Reasoning.
There exist different strategies to make the selection each time for a Rule: Ordering of Rules, Control of Agendas, Criterion of Actuality, and Criterion of Specificity.
The Criterion of Specificity leads to execute, first, the more specific Rules, that is, those with more facts in its antecedent. So, between R1: if a, then b, and R2: if a and d, then c, we must select R2, because it is more specific than R1.
We also have Mechanisms of Control in RBS. So, by
Refractarity's Mechanism, by which we forbid to execute newly a Rule, once utilized, if do not exist more information which allow or recommend such case.Rule Sets. It allows one to activate or neutralize Blocks of Rules.Meta-Rules, or Rules, which treat (or reasoning) about other Rules. Such Meta-Rules can collaborate to Control of Reasoning, with the change or assignation of priorities to different Rules, according to the evolution of circumstances.Now, we describe the Nets: Between them, the more recent studies deal with Bayesian Nets, or Networks. Before this apparition, the purpose was to obtain useful systems for medical diagnosis, by classical statistical techniques, such as the Bayes rule.
A Bayesian Net is represented as a pair (G, D), where G is a directed, acyclic, and connected graph, and D will be a probability distribution, associated with the random variables [14]. Such distribution verifies the Property of Directional Separation, according to which the probability of a variable does not depend on the non-descendant nodes.
The Inference in BN consists in establishing on the Net, for the known variables, their values, and relative to the unknown variables, their respective probabilities.
The objective of BNs in Medicine is to find the probability of success with which we can determine a diagnosis, with known certain symptoms. We need to work with the subsequent Hypotheses: Exclusivity, Exhaustivity, and conditional independence (CI). According to the Exclusivity, two different diagnoses cannot be right at times. With the Exhaustivity, we suppose at our disposition all the possible diagnosis. And by the CI, the discoveries found must be mutually independent, to a certain diagnosis.
The usual problem with such hypotheses will be their inadequacy to the real world [2,11,16]. For this reason, it will be necessary to introduce Bayesian networks.
2.3 Searching Methods
In the searching process [2,15], we have two options: without information of the domain (Blind Search); and with information about of the domain (Heuristic Search). In the first case, we can elect, according to the type of problem, between Search in extent and Search in depth.
There are other methods, obtained from the previous studies, such as Searching in Progressive Depth and Bidirectional Searching
