An Algorithmic Information Calculus for Causal Discovery and Reprogramming Systems

Cell Fate Dynamics Reconstruction Identifies TPT1 and PTPRZ1 Feedback Loops as Master Regulators of Differentiation in Pediatric Glioblastoma-Immune Cell Networks

Pediatric glioblastoma is a complex dynamical disease that is difficult to treat due to its multiple adaptive behaviors driven largely by phenotypic plasticity. Integrated data science and network theory pipelines offer novel approaches to studying glioblastoma cell fate dynamics, particularly phenotypic transitions over time. Here we used various single-cell trajectory inference algorithms to infer signaling dynamics regulating pediatric glioblastoma-immune cell networks. We identified GATA2, PTPRZ1, TPT1, MTRNR2L1/2, OLIG1/2, SOX11, FXYD6, SEZ6L, PDGFRA, EGFR, S100B, WNT, TNF α , and NF-kB as critical transition genes or signals regulating glioblastoma-immune network dynamics, revealing potential clinically relevant targets. Further, we reconstructed glioblastoma cell fate attractors and found complex bifurcation dynamics within glioblastoma phenotypic transitions, suggesting that a causal pattern may be driving glioblastoma evolution and cell fate decision-making. Together, our findings have implications for developing targeted therapies against glioblastoma, and the continued integration of quantitative approaches and artificial intelligence (AI) to understand pediatric glioblastoma tumor-immune interactions.

Approaching the general quantification of functional information

Information is everywhere, especially in the digital, artificial intelligence, and big data worlds we live in. In fact, information has always played a pivotal role; however, that role is, as the years of history accumulate, becoming even more significant. It is, therefore, a pursuit of scientific inquiry to quantify the functionality and semantics of information-this is also the goal of the article one reads. We have constructively and critically reviewed state-of-the-art approaches, presented challenges, and suggested a new approach that deals with the issues of information quantification. The developed approach represents a method for general quantification of functional information, including the total functional information of a system and the semantics revealed by functionality. Such a general method can potentially have significance far beyond the shores of information quantification, especially considering the importance of information in computer and information science, quantum physics, and chemistry. We have also made first steps of placing functional information in a computational complexity framework, which will potentially foster algorithmics around it, especially in terms of optimality or degeneracy, and possibly even in terms of work around classes of computational complexity.

Robust Model-Free Identification of the Causal Networks Underlying Complex Nonlinear Systems

Inferring causal networks from noisy observations is of vital importance in various fields. Due to the complexity of system modeling, the way in which universal and feasible inference algorithms are studied is a key challenge for network reconstruction. In this study, without any assumptions, we develop a novel model-free framework to uncover only the direct relationships in networked systems from observations of their nonlinear dynamics. Our proposed methods are termed multiple-order Polynomial Conditional Granger Causality (PCGC) and sparse PCGC (SPCGC). PCGC mainly adopts polynomial functions to approximate the whole system model, which can be used to judge the interactions among nodes through subsequent nonlinear Granger causality analysis. For SPCGC, Lasso optimization is first used for dimension reduction, and then PCGC is executed to obtain the final network. Specifically, the conditional variables are fused in this general, model-free framework regardless of their formulations in the system model, which could effectively reconcile the inference of direct interactions with an indirect influence. Based on many classical dynamical systems, the performances of PCGC and SPCGC are analyzed and verified. Generally, the proposed framework could be quite promising for the provision of certain guidance for data-driven modeling with an unknown model.

Cascades Towards Noise-Induced Transitions on Networks Revealed Using Information Flows

Complex networks, from neuronal assemblies to social systems, can exhibit abrupt, system-wide transitions without external forcing. These endogenously generated "noise-induced transitions" emerge from the intricate interplay between network structure and local dynamics, yet their underlying mechanisms remain elusive. Our study unveils two critical roles that nodes play in catalyzing these transitions within dynamical networks governed by the Boltzmann-Gibbs distribution. We introduce the concept of "initiator nodes", which absorb and propagate short-lived fluctuations, temporarily destabilizing their neighbors. This process initiates a domino effect, where the stability of a node inversely correlates with the number of destabilized neighbors required to tip it. As the system approaches a tipping point, we identify "stabilizer nodes" that encode the system's long-term memory, ultimately reversing the domino effect and settling the network into a new stable attractor. Through targeted interventions, we demonstrate how these roles can be manipulated to either promote or inhibit systemic transitions. Our findings provide a novel framework for understanding and potentially controlling endogenously generated metastable behavior in complex networks. This approach opens new avenues for predicting and managing critical transitions in diverse fields, from neuroscience to social dynamics and beyond.

Key Node Identification Method Based on Multilayer Neighbor Node Gravity and Information Entropy

In the field of complex network analysis, accurately identifying key nodes is crucial for understanding and controlling information propagation. Although several local centrality methods have been proposed, their accuracy may be compromised if interactions between nodes and their neighbors are not fully considered. To address this issue, this paper proposes a key node identification method based on multilayer neighbor node gravity and information entropy (MNNGE). The method works as follows: First, the relative gravity of the nodes is calculated based on their weights. Second, the direct gravity of the nodes is calculated by considering the attributes of neighboring nodes, thus capturing interactions within local triangular structures. Finally, the centrality of the nodes is obtained by aggregating the relative and direct gravity of multilayer neighbor nodes using information entropy. To validate the effectiveness of the MNNGE method, we conducted experiments on various real-world network datasets, using evaluation metrics such as the susceptible-infected-recovered (SIR) model, Kendall τ correlation coefficient, Jaccard similarity coefficient, monotonicity, and complementary cumulative distribution function. Our results demonstrate that MNNGE can identify key nodes more accurately than other methods, without requiring parameter settings, and is suitable for large-scale complex networks.

On the salient limitations of the methods of assembly theory and their classification of molecular biosignatures

We demonstrate that the assembly pathway method underlying assembly theory (AT) is an encoding scheme widely used by popular statistical compression algorithms. We show that in all cases (synthetic or natural) AT performs similarly to other simple coding schemes and underperforms compared to system-related indexes based upon algorithmic probability that take into account statistical repetitions but also the likelihood of other computable patterns. Our results imply that the assembly index does not offer substantial improvements over existing methods, including traditional statistical ones, and imply that the separation between living and non-living compounds following these methods has been reported before.

Exploring Simplicity Bias in 1D Dynamical Systems

Arguments inspired by algorithmic information theory predict an inverse relation between the probability and complexity of output patterns in a wide range of input-output maps. This phenomenon is known as simplicity bias. By viewing the parameters of dynamical systems as inputs, and the resulting (digitised) trajectories as outputs, we study simplicity bias in the logistic map, Gauss map, sine map, Bernoulli map, and tent map. We find that the logistic map, Gauss map, and sine map all exhibit simplicity bias upon sampling of map initial values and parameter values, but the Bernoulli map and tent map do not. The simplicity bias upper bound on the output pattern probability is used to make a priori predictions regarding the probability of output patterns. In some cases, the predictions are surprisingly accurate, given that almost no details of the underlying dynamical systems are assumed. More generally, we argue that studying probability-complexity relationships may be a useful tool when studying patterns in dynamical systems.

Causality Analysis with Information Geometry: A Comparison

The quantification of causality is vital for understanding various important phenomena in nature and laboratories, such as brain networks, environmental dynamics, and pathologies. The two most widely used methods for measuring causality are Granger Causality (GC) and Transfer Entropy (TE), which rely on measuring the improvement in the prediction of one process based on the knowledge of another process at an earlier time. However, they have their own limitations, e.g., in applications to nonlinear, non-stationary data, or non-parametric models. In this study, we propose an alternative approach to quantify causality through information geometry that overcomes such limitations. Specifically, based on the information rate that measures the rate of change of the time-dependent distribution, we develop a model-free approach called information rate causality that captures the occurrence of the causality based on the change in the distribution of one process caused by another. This measurement is suitable for analyzing numerically generated non-stationary, nonlinear data. The latter are generated by simulating different types of discrete autoregressive models which contain linear and nonlinear interactions in unidirectional and bidirectional time-series signals. Our results show that information rate causalitycan capture the coupling of both linear and nonlinear data better than GC and TE in the several examples explored in the paper.

Downward-Growing Neural Networks

A major issue in the application of deep learning is the definition of a proper architecture for the learning machine at hand, in such a way that the model is neither excessively large (which results in overfitting the training data) nor too small (which limits the learning and modeling capabilities of the automatic learner). Facing this issue boosted the development of algorithms for automatically growing and pruning the architectures as part of the learning process. The paper introduces a novel approach to growing the architecture of deep neural networks, called downward-growing neural network (DGNN). The approach can be applied to arbitrary feed-forward deep neural networks. Groups of neurons that negatively affect the performance of the network are selected and grown with the aim of improving the learning and generalization capabilities of the resulting machine. The growing process is realized via replacement of these groups of neurons with sub-networks that are trained relying on ad hoc target propagation techniques. In so doing, the growth process takes place simultaneously in both the depth and width of the DGNN architecture. We assess empirically the effectiveness of the DGNN on several UCI datasets, where the DGNN significantly improves the average accuracy over a range of established deep neural network approaches and over two popular growing algorithms, namely, the AdaNet and the cascade correlation neural network.

Auxiliary Graph for Attribute Graph Clustering

Attribute graph clustering algorithms that include topological structural information into node characteristics for building robust representations have proven to have promising efficacy in a variety of applications. However, the presented topological structure emphasizes local links between linked nodes but fails to convey relationships between nodes that are not directly linked, limiting the potential for future clustering performance improvement. To solve this issue, we offer the Auxiliary Graph for Attribute Graph Clustering technique (AGAGC). Specifically, we construct an additional graph as a supervisor based on the node attribute. The additional graph can serve as an auxiliary supervisor that aids the present one. To generate a trustworthy auxiliary graph, we offer a noise-filtering approach. Under the supervision of both the pre-defined graph and an auxiliary graph, a more effective clustering model is trained. Additionally, the embeddings of multiple layers are merged to improve the discriminative power of representations. We offer a clustering module for a self-supervisor to make the learned representation more clustering-aware. Finally, our model is trained using a triplet loss. Experiments are done on four available benchmark datasets, and the findings demonstrate that the proposed model outperforms or is comparable to state-of-the-art graph clustering models.

Relative Entropy of Distance Distribution Based Similarity Measure of Nodes in Weighted Graph Data

Many similarity measure algorithms of nodes in weighted graph data have been proposed by employing the degree of nodes in recent years. Despite these algorithms obtaining great results, there may be still some limitations. For instance, the strength of nodes is ignored. Aiming at this issue, the relative entropy of the distance distribution based similarity measure of nodes is proposed in this paper. At first, the structural weights of nodes are given by integrating their degree and strength. Next, the distance between any two nodes is calculated with the help of their structural weights and the Euclidean distance formula to further obtain the distance distribution of each node. After that, the probability distribution of nodes is constructed by normalizing their distance distributions. Thus, the relative entropy can be applied to measure the difference between the probability distributions of the top d important nodes and all nodes in graph data. Finally, the similarity of two nodes can be measured in terms of this above-mentioned difference calculated by relative entropy. Experimental results demonstrate that the algorithm proposed by considering the strength of node in the relative entropy has great advantages in the most similar node mining and link prediction.

Dissecting cell fate dynamics in pediatric glioblastoma through the lens of complex systems and cellular cybernetics

Cancers are complex dynamic ecosystems. Reductionist approaches to science are inadequate in characterizing their self-organized patterns and collective emergent behaviors. Since current approaches to single-cell analysis in cancer systems rely primarily on single time-point multiomics, many of the temporal features and causal adaptive behaviors in cancer dynamics are vastly ignored. As such, tools and concepts from the interdisciplinary paradigm of complex systems theory are introduced herein to decode the cellular cybernetics of cancer differentiation dynamics and behavioral patterns. An intuition for the attractors and complex networks underlying cancer processes such as cell fate decision-making, multiscale pattern formation systems, and epigenetic state-transitions is developed. The applications of complex systems physics in paving targeted therapies and causal pattern discovery in precision oncology are discussed. Pediatric high-grade gliomas are discussed as a model-system to demonstrate that cancers are complex adaptive systems, in which the emergence and selection of heterogeneous cellular states and phenotypic plasticity are driven by complex multiscale network dynamics. In specific, pediatric glioblastoma (GBM) is used as a proof-of-concept model to illustrate the applications of the complex systems framework in understanding GBM cell fate decisions and decoding their adaptive cellular dynamics. The scope of these tools in forecasting cancer cell fate dynamics in the emerging field of computational oncology and patient-centered systems medicine is highlighted.

A Review of Mathematical and Computational Methods in Cancer Dynamics

Cancers are complex adaptive diseases regulated by the nonlinear feedback systems between genetic instabilities, environmental signals, cellular protein flows, and gene regulatory networks. Understanding the cybernetics of cancer requires the integration of information dynamics across multidimensional spatiotemporal scales, including genetic, transcriptional, metabolic, proteomic, epigenetic, and multi-cellular networks. However, the time-series analysis of these complex networks remains vastly absent in cancer research. With longitudinal screening and time-series analysis of cellular dynamics, universally observed causal patterns pertaining to dynamical systems, may self-organize in the signaling or gene expression state-space of cancer triggering processes. A class of these patterns, strange attractors, may be mathematical biomarkers of cancer progression. The emergence of intracellular chaos and chaotic cell population dynamics remains a new paradigm in systems medicine. As such, chaotic and complex dynamics are discussed as mathematical hallmarks of cancer cell fate dynamics herein. Given the assumption that time-resolved single-cell datasets are made available, a survey of interdisciplinary tools and algorithms from complexity theory, are hereby reviewed to investigate critical phenomena and chaotic dynamics in cancer ecosystems. To conclude, the perspective cultivates an intuition for computational systems oncology in terms of nonlinear dynamics, information theory, inverse problems, and complexity. We highlight the limitations we see in the area of statistical machine learning but the opportunity at combining it with the symbolic computational power offered by the mathematical tools explored.

Emergence and algorithmic information dynamics of systems and observers

One of the challenges of defining emergence is that one observer's prior knowledge may cause a phenomenon to present itself as emergent that to another observer appears reducible. By formalizing the act of observing as mutual perturbations between dynamical systems, we demonstrate that the emergence of algorithmic information does depend on the observer's formal knowledge, while being robust vis-a-vis other subjective factors, particularly: the choice of programming language and method of measurement; errors or distortions during the observation; and the informational cost of processing. This is called observer-dependent emergence (ODE). In addition, we demonstrate that the unbounded and rapid increase of emergent algorithmic information implies asymptotically observer-independent emergence (AOIE). Unlike ODE, AOIE is a type of emergence for which emergent phenomena will be considered emergent no matter what formal theory an observer might bring to bear. We demonstrate the existence of an evolutionary model that displays the diachronic variant of AOIE and a network model that displays the holistic variant of AOIE. Our results show that, restricted to the context of finite discrete deterministic dynamical systems, computable systems and irreducible information content measures, AOIE is the strongest form of emergence that formal theories can attain. This article is part of the theme issue 'Emergent phenomena in complex physical and socio-technical systems: from cells to societies'.

Emergence and algorithmic information dynamics of systems and observers

One of the challenges of defining emergence is that one observer's prior knowledge may cause a phenomenon to present itself as emergent that to another observer appears reducible. By formalizing the act of observing as mutual perturbations between dynamical systems, we demonstrate that the emergence of algorithmic information does depend on the observer's formal knowledge, while being robust vis-a-vis other subjective factors, particularly: the choice of programming language and method of measurement; errors or distortions during the observation; and the informational cost of processing. This is called observer-dependent emergence (ODE). In addition, we demonstrate that the unbounded and rapid increase of emergent algorithmic information implies asymptotically observer-independent emergence (AOIE). Unlike ODE, AOIE is a type of emergence for which emergent phenomena will be considered emergent no matter what formal theory an observer might bring to bear. We demonstrate the existence of an evolutionary model that displays the diachronic variant of AOIE and a network model that displays the holistic variant of AOIE. Our results show that, restricted to the context of finite discrete deterministic dynamical systems, computable systems and irreducible information content measures, AOIE is the strongest form of emergence that formal theories can attain. This article is part of the theme issue 'Emergent phenomena in complex physical and socio-technical systems: from cells to societies'.

Algorithmic reconstruction of glioblastoma network complexity

Glioblastoma is a complex disease that is difficult to treat. Network and data science offer alternative approaches to classical bioinformatics pipelines to study gene expression patterns from single-cell datasets, helping to distinguish genes associated with the control of differentiation and aggression. To identify the key molecular regulators of the networks driving glioblastoma/GSC and predict their cell fate dynamics, we applied a host of data theoretic techniques to gene expression patterns from pediatric and adult glioblastoma, and adult glioma-derived stem cells (GSCs). We identified eight transcription factors (OLIG1/2, TAZ, GATA2, FOXG1, SOX6, SATB2, and YY1) and four signaling genes (ATL3, MTSS1, EMP1, and TPT1) as coordinators of cell state transitions and, thus, clinically targetable putative factors differentiating pediatric and adult glioblastomas from adult GSCs. Our study provides strong evidence of complex systems approaches for inferring complex dynamics from reverse-engineering gene networks, bolstering the search for new clinically relevant targets in glioblastoma.

•

Complex cell fate attractors capture glioblastoma differentiation dynamics

•

Graph theoretic approaches decode master regulators of GBM glioblastoma cell fate decisions

•

Network dynamics of pediatric glioblastoma resemble adult GSCs

•

Transcriptional networks may help reprogram glioblastoma behavioral patterns

Kolmogorov Basic Graphs and Their Application in Network Complexity Analysis

Throughout the years, measuring the complexity of networks and graphs has been of great interest to scientists. The Kolmogorov complexity is known as one of the most important tools to measure the complexity of an object. We formalized a method to calculate an upper bound for the Kolmogorov complexity of graphs and networks. Firstly, the most simple graphs possible, those with O(1) Kolmogorov complexity, were identified. These graphs were then used to develop a method to estimate the complexity of a given graph. The proposed method utilizes the simple structures within a graph to capture its non-randomness. This method is able to capture features that make a network closer to the more non-random end of the spectrum. The resulting algorithm takes a graph as an input and outputs an upper bound to its Kolmogorov complexity. This could be applicable in, for example evaluating the performances of graph compression methods.

Entropy: From Thermodynamics to Information Processing

Entropy is a concept that emerged in the 19th century. It used to be associated with heat harnessed by a thermal machine to perform work during the Industrial Revolution. However, there was an unprecedented scientific revolution in the 20th century due to one of its most essential innovations, i.e., the information theory, which also encompasses the concept of entropy. Therefore, the following question is naturally raised: “what is the difference, if any, between concepts of entropy in each field of knowledge?” There are misconceptions, as there have been multiple attempts to conciliate the entropy of thermodynamics with that of information theory. Entropy is most commonly defined as “disorder”, although it is not a good analogy since “order” is a subjective human concept, and “disorder” cannot always be obtained from entropy. Therefore, this paper presents a historical background on the evolution of the term “entropy”, and provides mathematical evidence and logical arguments regarding its interconnection in various scientific areas, with the objective of providing a theoretical review and reference material for a broad audience.

A review of dynamical systems approaches for the detection of chaotic attractors in cancer networks

Cancers are complex dynamical systems. They remain the leading cause of disease-related pediatric mortality in North America. To overcome this burden, we must decipher the state-space attractor dynamics of gene expression patterns and protein oscillations orchestrated by cancer stemness networks. The review provides an overview of dynamical systems theory to steer cancer research in pattern science. While most of our current tools in network medicine rely on statistical correlation methods, causality inference remains primitively developed. As such, a survey of attractor reconstruction methods and machine algorithms for the detection of causal structures applicable in experimentally derived time series cancer datasets is presented. A toolbox of complex systems approaches are discussed for reconstructing the signaling state space of cancer networks, interpreting causal relationships in their time series gene expression patterns, and assisting clinical decision making in computational oncology. As a proof of concept, the applicability of some algorithms are demonstrated on pediatric brain cancer datasets and the requirement of their time series analysis is highlighted.

Deep Learning in Mining Biological Data

Recent technological advancements in data acquisition tools allowed life scientists to acquire multimodal data from different biological application domains. Categorized in three broad types (i.e. images, signals, and sequences), these data are huge in amount and complex in nature. Mining such enormous amount of data for pattern recognition is a big challenge and requires sophisticated data-intensive machine learning techniques. Artificial neural network-based learning systems are well known for their pattern recognition capabilities, and lately their deep architectures-known as deep learning (DL)-have been successfully applied to solve many complex pattern recognition problems. To investigate how DL-especially its different architectures-has contributed and been utilized in the mining of biological data pertaining to those three types, a meta-analysis has been performed and the resulting resources have been critically analysed. Focusing on the use of DL to analyse patterns in data from diverse biological domains, this work investigates different DL architectures' applications to these data. This is followed by an exploration of available open access data sources pertaining to the three data types along with popular open-source DL tools applicable to these data. Also, comparative investigations of these tools from qualitative, quantitative, and benchmarking perspectives are provided. Finally, some open research challenges in using DL to mine biological data are outlined and a number of possible future perspectives are put forward.

Cancer: A turbulence problem

•

Application of nonlinear dynamics to cancer ecosystems.

•

Chemical turbulence and strange attractor models in tumor growth, invasion and pattern formation are investigated.

•

Computational algorithms for detecting such structures are proposed.

•

Complex systems applications to cancer dynamics.

Cancers are complex, adaptive ecosystems. They remain the leading cause of disease-related death among children in North America. As we approach computational oncology and Deep Learning Healthcare, our mathematical models of cancer dynamics must be revised. Recent findings support the perspective that cancer-microenvironment interactions may consist of chaotic gene expressions and turbulent protein flows during pattern formation. As such, cancer pattern formation, protein-folding and metastatic invasion are discussed herein as processes driven by chemical turbulence within the framework of complex systems theory. To conclude, cancer stem cells are presented as strange attractors of the Waddington landscape.

Non-Uniform Embedding Scheme and Low-Dimensional Approximation Methods for Causality Detection

Information causality measures have proven to be very effective in uncovering the connectivity patterns of multivariate systems. The non-uniform embedding (NUE) scheme has been developed to address the “curse of dimensionality”, since the estimation relies on high-dimensional conditional mutual information (CMI) terms. Although the NUE scheme is a dimension reduction technique, the estimation of high-dimensional CMIs is still required. A possible solution is the utilization of low-dimensional approximation (LA) methods for the computation of CMIs. In this study, we aim to provide useful insights regarding the effectiveness of causality measures that rely on NUE and/or on LA methods. In a comparative study, three causality detection methods are evaluated, namely partial transfer entropy (PTE) defined using uniform embedding, PTE using the NUE scheme (PTENUE), and PTE utilizing both NUE and an LA method (LATE). Results from simulations on well known coupled systems suggest the superiority of PTENUE over the other two measures in identifying the true causal effects, having also the least computational cost. The effectiveness of PTENUE is also demonstrated in a real application, where insights are presented regarding the leading forces in financial data.

A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions

Some established and also novel techniques in the field of applications of algorithmic (Kolmogorov) complexity currently co-exist for the first time and are here reviewed, ranging from dominant ones such as statistical lossless compression to newer approaches that advance, complement and also pose new challenges and may exhibit their own limitations. Evidence suggesting that these different methods complement each other for different regimes is presented and despite their many challenges, some of these methods can be better motivated by and better grounded in the principles of algorithmic information theory. It will be explained how different approaches to algorithmic complexity can explore the relaxation of different necessary and sufficient conditions in their pursuit of numerical applicability, with some of these approaches entailing greater risks than others in exchange for greater relevance. We conclude with a discussion of possible directions that may or should be taken into consideration to advance the field and encourage methodological innovation, but more importantly, to contribute to scientific discovery. This paper also serves as a rebuttal of claims made in a previously published minireview by another author, and offers an alternative account.

Entropy as a Robustness Marker in Genetic Regulatory Networks

Genetic regulatory networks have evolved by complexifying their control systems with numerous effectors (inhibitors and activators). That is, for example, the case for the double inhibition by microRNAs and circular RNAs, which introduce a ubiquitous double brake control reducing in general the number of attractors of the complex genetic networks (e.g., by destroying positive regulation circuits), in which complexity indices are the number of nodes, their connectivity, the number of strong connected components and the size of their interaction graph. The stability and robustness of the networks correspond to their ability to respectively recover from dynamical and structural disturbances the same asymptotic trajectories, and hence the same number and nature of their attractors. The complexity of the dynamics is quantified here using the notion of attractor entropy: it describes the way the invariant measure of the dynamics is spread over the state space. The stability (robustness) is characterized by the rate at which the system returns to its equilibrium trajectories (invariant measure) after a dynamical (structural) perturbation. The mathematical relationships between the indices of complexity, stability and robustness are presented in case of Markov chains related to threshold Boolean random regulatory networks updated with a Hopfield-like rule. The entropy of the invariant measure of a network as well as the Kolmogorov-Sinaï entropy of the Markov transition matrix ruling its random dynamics can be considered complexity, stability and robustness indices; and it is possible to exploit the links between these notions to characterize the resilience of a biological system with respect to endogenous or exogenous perturbations. The example of the genetic network controlling the kinin-kallikrein system involved in a pathology called angioedema shows the practical interest of the present approach of the complexity and robustness in two cases, its physiological normal and pathological, abnormal, dynamical behaviors.

Influential Nodes Identification in Complex Networks via Information Entropy

Identifying a set of influential nodes is an important topic in complex networks which plays a crucial role in many applications, such as market advertising, rumor controlling, and predicting valuable scientific publications. In regard to this, researchers have developed algorithms from simple degree methods to all kinds of sophisticated approaches. However, a more robust and practical algorithm is required for the task. In this paper, we propose the EnRenew algorithm aimed to identify a set of influential nodes via information entropy. Firstly, the information entropy of each node is calculated as initial spreading ability. Then, select the node with the largest information entropy and renovate its l-length reachable nodes’ spreading ability by an attenuation factor, repeat this process until specific number of influential nodes are selected. Compared with the best state-of-the-art benchmark methods, the performance of proposed algorithm improved by 21.1%, 7.0%, 30.0%, 5.0%, 2.5%, and 9.0% in final affected scale on CEnew, Email, Hamster, Router, Condmat, and Amazon network, respectively, under the Susceptible-Infected-Recovered (SIR) simulation model. The proposed algorithm measures the importance of nodes based on information entropy and selects a group of important nodes through dynamic update strategy. The impressive results on the SIR simulation model shed light on new method of node mining in complex networks for information spreading and epidemic prevention.

Approximate and Situated Causality in Deep Learning

Causality is the most important topic in the history of western science, and since the beginning of the statistical paradigm, its meaning has been reconceptualized many times. Causality entered into the realm of multi-causal and statistical scenarios some centuries ago. Despite widespread critics, today deep learning and machine learning advances are not weakening causality but are creating a new way of finding correlations between indirect factors. This process makes it possible for us to talk about approximate causality, as well as about a situated causality.

The Thermodynamics of Network Coding, and an Algorithmic Refinement of the Principle of Maximum Entropy

The principle of maximum entropy (Maxent) is often used to obtain prior probability distributions as a method to obtain a Gibbs measure under some restriction giving the probability that a system will be in a certain state compared to the rest of the elements in the distribution. Because classical entropy-based Maxent collapses cases confounding all distinct degrees of randomness and pseudo-randomness, here we take into consideration the generative mechanism of the systems considered in the ensemble to separate objects that may comply with the principle under some restriction and whose entropy is maximal but may be generated recursively from those that are actually algorithmically random offering a refinement to classical Maxent. We take advantage of a causal algorithmic calculus to derive a thermodynamic-like result based on how difficult it is to reprogram a computer code. Using the distinction between computable and algorithmic randomness, we quantify the cost in information loss associated with reprogramming. To illustrate this, we apply the algorithmic refinement to Maxent on graphs and introduce a Maximal Algorithmic Randomness Preferential Attachment (MARPA) Algorithm, a generalisation over previous approaches. We discuss practical implications of evaluation of network randomness. Our analysis provides insight in that the reprogrammability asymmetry appears to originate from a non-monotonic relationship to algorithmic probability. Our analysis motivates further analysis of the origin and consequences of the aforementioned asymmetries, reprogrammability, and computation.

A Review of Graph and Network Complexity from an Algorithmic Information Perspective

Information-theoretic-based measures have been useful in quantifying network complexity. Here we briefly survey and contrast (algorithmic) information-theoretic methods which have been used to characterize graphs and networks. We illustrate the strengths and limitations of Shannon’s entropy, lossless compressibility and algorithmic complexity when used to identify aspects and properties of complex networks. We review the fragility of computable measures on the one hand and the invariant properties of algorithmic measures on the other demonstrating how current approaches to algorithmic complexity are misguided and suffer of similar limitations than traditional statistical approaches such as Shannon entropy. Finally, we review some current definitions of algorithmic complexity which are used in analyzing labelled and unlabelled graphs. This analysis opens up several new opportunities to advance beyond traditional measures.