k-Independent Boolean networks
No Thumbnail Available
Date
2024
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad de Concepción
Abstract
En esta tesis, definimos un nuevo parámetro para estudiar redes Booleanas, denominado “número de independencia”. Establecemos que una red Booleana es k-independiente si, para cualquier conjunto de k variables y cualquier combinación de valores binarios asignados a estas, existe al menos un punto fijo en la red que tome esos valores en dicho conjunto de k índices. En este contexto, definimos el número de independencia de una red como el máximo valor de k tal que la red es k-independiente. Esta definición está estrechamente relacionada con diseños combinatorios ampliamente estudiados, como los “Coveringarrays” de fuerza k, también conocidos como conjuntos Booleanos con todas las k-proyecciones sobreyectivas. Nuestra motivación surge de comprender la relación entre el grafo de interacción de una red y sus puntos fijos, lo que ayuda a profundizar en el paradigma clásico de las investigaciones en esta dirección al incorporar una estructura particular sobre el conjunto de puntos fijos, más allá de simplemente observar su cardinalidad. Específicamente, nos centramos en estudiar grafos de interacción que admiten redes k-independientes, y mostramos que el grafo completo sin bucles con funciones de activación lineales alcanza la máxima fuerza no trivial. Además, presentamos construcciones que demuestran la existencia de re des k-independientes en n variables con grafos de interacción disconexos, conexos y fuertemente conexos. Finalmente, observamos que las simulaciones computacionales no lograron encontrar ejemplos de redes monótonas k-independientes. Esta observación motiva la sección 4.1 de esta tesis, donde utilizamos otro diseño combinatorio clásico, llamado sistema de Steiner, para construir redes monótonas k-independientes con grafo de interacción completo y sin bucles.
In this thesis, we define a new parameter for studying Boolean networks, called the “independence number”. Weestablish that a Boolean network is k-independent if, for any set of k variables and any combination of binary values assigned to them, there exists at least one fixed point in the network that takes those values at the given set of k indices. In this context, we define the independence number of a network as the maximum value of k such that the network is k-independent. This definition is closely related to widely studied combinatorial designs, such as “k-strength cov ering arrays”, also known as Boolean sets with all k-projections surjective. Our motivation arises from understanding the relationship between a network’s interaction graph and its fixed points, which deepens the classical paradigm of research in this direction by incorporating a particular structure on the set of fixed points, beyond merely observing their cardinality. Specifically, we focus on studying interaction graphs that admit k-independent networks and show that the complete graph without loops with linear-type activation functions achieves maximum nontrivial strength. Furthermore, we present constructions that demonstrate the existence of k independent networks on n variables with disconnected, connected and strongly connected interac tion graphs. We also study necessary conditions for a network to be k-independent. Finally, we observe that computational simulations failed to find examples of monotone k-independent networks. This observation motivates Section 4.1 of this thesis, where we use another classical combinatorial design, called a Steiner system, to construct monotone k-independent networks with complete loopless interaction graphs.
In this thesis, we define a new parameter for studying Boolean networks, called the “independence number”. Weestablish that a Boolean network is k-independent if, for any set of k variables and any combination of binary values assigned to them, there exists at least one fixed point in the network that takes those values at the given set of k indices. In this context, we define the independence number of a network as the maximum value of k such that the network is k-independent. This definition is closely related to widely studied combinatorial designs, such as “k-strength cov ering arrays”, also known as Boolean sets with all k-projections surjective. Our motivation arises from understanding the relationship between a network’s interaction graph and its fixed points, which deepens the classical paradigm of research in this direction by incorporating a particular structure on the set of fixed points, beyond merely observing their cardinality. Specifically, we focus on studying interaction graphs that admit k-independent networks and show that the complete graph without loops with linear-type activation functions achieves maximum nontrivial strength. Furthermore, we present constructions that demonstrate the existence of k independent networks on n variables with disconnected, connected and strongly connected interac tion graphs. We also study necessary conditions for a network to be k-independent. Finally, we observe that computational simulations failed to find examples of monotone k-independent networks. This observation motivates Section 4.1 of this thesis, where we use another classical combinatorial design, called a Steiner system, to construct monotone k-independent networks with complete loopless interaction graphs.
Description
Tesis presentada para optar al grado académico de Magíster en Ciencias de la Computación
Keywords
Procesamiento electrónico de datos, Teoría de grafos, Complejidad computacional