Risk-adjusted benchmarking of long-term overall survival in patients with HER2-positive early-stage Breast cancer: A Swedish retrospective cohort study.

AIM: The main objective of the current study was to explore the value of risk-adjustment when comparing (i.e. benchmarking) long-term overall survival (OS) in breast cancer (BC) between Swedish regions. We performed risk-adjusted benchmarking of 5- and 10-year OS after HER2-positive early BC diagnosis between Sweden's two largest healthcare regions, constituting approximately a third of the total population in Sweden. METHODS: All patients diagnosed with HER2-positive early-stage BC between 01-01-2009 and 31-12-2016 in healthcare regions Stockholm-Gotland and Skane were included in the study. Cox proportional hazards model was used for risk-adjustment. Unadjusted (i.e. crude) and adjusted 5- and 10-year OS was benchmarked between the two regions. RESULTS: The crude 5-year OS was 90.3% in the Stockholm-Gotland region and 87.8% in the Skane region. The crude 10-year OS was 81.7% in the Stockholm-Gotland region and 77.3% in the Skane region. However, when adjusted for age, menopausal status and tumour biology, there was no significant OS disparity between the regions, neither at the 5-year nor 10-year follow-up. CONCLUSION: This study showed that risk-adjustment is relevant when benchmarking OS in BC, even when comparing regions from the same country that share the same national treatment guidelines. This is, to our knowledge, the first published risk-adjusted benchmarking of OS in HER2-positive BC.

Planning for return to work during the first year after breast cancer metastasis: A Swedish cohort study.

BACKGROUND: Planning for return to work (RTW) is relevant among sub-groups of metastatic breast cancer (mBC) survivors. RTW and protective factors for RTW in patients with mBC were determined. METHODS: Patients with mBC, ages 18-63 years, were identified in Swedish registers, and data were collected starting 1 year before their mBC diagnosis. The prevalence of working net days (WNDs) (>90 and >180) during the year after mBC diagnosis (y1) was determined. Factors associated with RTW were assessed using regression analysis. The impact of contemporary oncological treatment of mBC on RTW and 5-year mBC-specific survival was compared between those diagnosed in 1997-2002 and 2003-2011. RESULTS: Of 490 patients, 239 (48.8%) and 189 (36.8%) had >90 and >180 WNDs, respectively, during y1. Adjusted odds ratios (AORs) of WNDs >90 or >180 during y1 were significantly higher for patients with age ≤50 years (AOR180  = 1.54), synchronous metastasis (AOR90  = 1.68, AOR180  = 1.67), metastasis within 24 months (AOR180  = 1.51), soft tissue, visceral, brain as first metastatic site (AOR90  = 1.47) and sickness absence <90 net days in the year before mBC diagnosis, suggesting limited comorbidities (AOR90  = 1.28, AOR180  = 2.00), respectively. Mean (standard deviation) WNDs were 134.9 (140.1) and 161.3 (152.4) for patients diagnosed with mBC in 1997-2002 and 2003-2011, respectively (p = 0.046). Median (standard error) mBC-specific survivals were 41.0 (2.5) and 62.0 (9.6) months for patients diagnosed with mBC in 1997-2002 and 2003-2011, respectively (p < 0.001). CONCLUSIONS: RTW of more than 180 WNDs was associated with younger age, early development of metastases and limited comorbidities during the year before the diagnosis of mBC. Patients diagnosed with mBC in 2003 or later had more WNDs and better survival than those diagnosed earlier.

scAEGAN: Unification of single-cell genomics data by adversarial learning of latent space correspondences.

Recent progress in Single-Cell Genomics has produced different library protocols and techniques for molecular profiling. We formulate a unifying, data-driven, integrative, and predictive methodology for different libraries, samples, and paired-unpaired data modalities. Our design of scAEGAN includes an autoencoder (AE) network integrated with adversarial learning by a cycleGAN (cGAN) network. The AE learns a low-dimensional embedding of each condition, whereas the cGAN learns a non-linear mapping between the AE representations. We evaluate scAEGAN using simulated data and real scRNA-seq datasets, different library preparations (Fluidigm C1, CelSeq, CelSeq2, SmartSeq), and several data modalities as paired scRNA-seq and scATAC-seq. The scAEGAN outperforms Seurat3 in library integration, is more robust against data sparsity, and beats Seurat 4 in integrating paired data from the same cell. Furthermore, in predicting one data modality from another, scAEGAN outperforms Babel. We conclude that scAEGAN surpasses current state-of-the-art methods and unifies integration and prediction challenges.

LSD-induced increase of Ising temperature and algorithmic complexity of brain dynamics.

A topic of growing interest in computational neuroscience is the discovery of fundamental principles underlying global dynamics and the self-organization of the brain. In particular, the notion that the brain operates near criticality has gained considerable support, and recent work has shown that the dynamics of different brain states may be modeled by pairwise maximum entropy Ising models at various distances from a phase transition, i.e., from criticality. Here we aim to characterize two brain states (psychedelics-induced and placebo) as captured by functional magnetic resonance imaging (fMRI), with features derived from the Ising spin model formalism (system temperature, critical point, susceptibility) and from algorithmic complexity. We hypothesized, along the lines of the entropic brain hypothesis, that psychedelics drive brain dynamics into a more disordered state at a higher Ising temperature and increased complexity. We analyze resting state blood-oxygen-level-dependent (BOLD) fMRI data collected in an earlier study from fifteen subjects in a control condition (placebo) and during ingestion of lysergic acid diethylamide (LSD). Working with the automated anatomical labeling (AAL) brain parcellation, we first create "archetype" Ising models representative of the entire dataset (global) and of the data in each condition. Remarkably, we find that such archetypes exhibit a strong correlation with an average structural connectome template obtained from dMRI (r = 0.6). We compare the archetypes from the two conditions and find that the Ising connectivity in the LSD condition is lower than in the placebo one, especially in homotopic links (interhemispheric connectivity), reflecting a significant decrease of homotopic functional connectivity in the LSD condition. The global archetype is then personalized for each individual and condition by adjusting the system temperature. The resulting temperatures are all near but above the critical point of the model in the paramagnetic (disordered) phase. The individualized Ising temperatures are higher in the LSD condition than in the placebo condition (p = 9 × 10-5). Next, we estimate the Lempel-Ziv-Welch (LZW) complexity of the binarized BOLD data and the synthetic data generated with the individualized model using the Metropolis algorithm for each participant and condition. The LZW complexity computed from experimental data reveals a weak statistical relationship with condition (p = 0.04 one-tailed Wilcoxon test) and none with Ising temperature (r(13) = 0.13, p = 0.65), presumably because of the limited length of the BOLD time series. Similarly, we explore complexity using the block decomposition method (BDM), a more advanced method for estimating algorithmic complexity. The BDM complexity of the experimental data displays a significant correlation with Ising temperature (r(13) = 0.56, p = 0.03) and a weak but significant correlation with condition (p = 0.04, one-tailed Wilcoxon test). This study suggests that the effects of LSD increase the complexity of brain dynamics by loosening interhemispheric connectivity-especially homotopic links. In agreement with earlier work using the Ising formalism with BOLD data, we find the brain state in the placebo condition is already above the critical point, with LSD resulting in a shift further away from criticality into a more disordered state.

Use of sickness benefits by patients with metastatic breast cancer-A Swedish cohort study.

OBJECTIVE: The objective of this study is to determine the prevalence and predictors of sickness absence (SA) and disability pension (DP) in women with metastatic breast cancer (mBC). METHODS: Data were obtained from Swedish registers concerning 1,240 adult women diagnosed 1997-2011 with mBC, from 1 year before (y-1) to 2 (y1) and 2 (y2) years after diagnosis. SA and DP prevalence was calculated. Odds ratios (AOR) were determined for factors associated with using long-term (SA > 180 days or DP > 0 days) sickness benefits. RESULTS: Prevalence of SA and DP was 56.0% and 24.8% during y-1, 69.9% and 28.9% during y1, and 64.0% and 34.7% during y2, respectively. Odds of using long-term sickness benefits were higher y1 and y2 in patients using long-term sickness benefits the year before diagnosis (AOR = 3.82, 95% CI 2.91-5.02; AOR = 4.31, 95% CI 2.96-6.29, respectively) and y2 in patients with mBC diagnosis 1997-2000 (AOR = 1.84, 95% CI 1.10-3.08) and using long-term sickness benefits the year after diagnosis (AOR = 22.10, 95% CI 14.33-34.22). CONCLUSIONS: The prevalence of sickness benefit utilisation was high and increased after mBC diagnosis, particularly for patients using long-term sickness benefits prior to diagnosis. Additional study is needed to determine factors that might reduce the need for sickness benefits and enhance work ability in these patients.

Evidence-based prediction and prevention of cardiovascular morbidity in adults treated for cancer.

BACKGROUND: Cancer treatment-related morbidity relevantly compromises health status in cancer survivors, and efforts to optimise health-related outcomes in this population are vital to maximising healthy survivorship. A pre-treatment assessment - and possibly preventive management strategies - of cancer patients at increased risk for cardiovascular disease (CVD) seems a rational approach in this regard. Definitive evidence for such strategies is largely lacking, thereby impeding the formulation of firm recommendations. RESULTS: The current scoping review aims to summarise and grade the evidence regarding strategies for prediction and prevention of CVD in adults in relation to oncological treatments. We conducted a scoping literature search for different strategies for primary prevention, such as medical and lifestyle interventions, as well as the use of predictive risk scores. We identified studies with moderate to good strength and up to now limited evidence to recommend primary preventive strategies in unselected patients treated with potentially cardiotoxic oncologic therapies. CONCLUSION: Efforts to minimize the CVD burden in cancer survivors are needed to accomplish healthy survivorship. This can be done by means of robust models predictive for CVD events or application of interventions during or after oncological treatments. Up to now there is insufficient evidence to implement preventive strategies in an unselected group of patients treated with potential cardiotoxic oncological treatments. We conclude that randomised controlled trials are needed that evaluate medical and lifestyle interventions in groups at increased risk for complications, in order to be able to influence chronic illness risks, such as cardiovascular complications, for cancer survivors.

MYC as a driver of stochastic chromatin networks: implications for the fitness of cancer cells.

The relationship between stochastic transcriptional bursts and dynamic 3D chromatin states is not well understood. Using an innovated, ultra-sensitive technique, we address here enigmatic features underlying the communications between MYC and its enhancers in relation to the transcriptional process. MYC thus interacts with its flanking enhancers in a mutually exclusive manner documenting that enhancer hubs impinging on MYC detected in large cell populations likely do not exist in single cells. Dynamic encounters with pathologically activated enhancers responsive to a range of environmental cues, involved <10% of active MYC alleles at any given time in colon cancer cells. Being the most central node of the chromatin network, MYC itself likely drives its communications with flanking enhancers, rather than vice versa. We submit that these features underlie an acquired ability of MYC to become dynamically activated in response to a diverse range of environmental cues encountered by the cell during the neoplastic process.

Immunometabolic Network Interactions of the Kynurenine Pathway in Cutaneous Malignant Melanoma.

Dysregulation of the kynurenine pathway has been regarded as a mechanism of tumor immune escape by the enzymatic activity of indoleamine 2, 3 dioxygenase and kynurenine production. However, the immune-modulatory properties of other kynurenine metabolites such as kynurenic acid, 3-hydroxykynurenine, and anthranilic acid are poorly understood. In this study, plasma from patients diagnosed with metastatic cutaneous malignant melanoma (CMM) was obtained before (PRE) and during treatment (TRM) with inhibitors of mitogen-activated protein kinase pathway (MAPKIs). Immuno-oncology related protein profile and kynurenine metabolites were analyzed by proximity extension assay (PEA) and LC/MS-MS, respectively. Correlation network analyses of the data derived from PEA and LC/MS-MS identified a set of proteins that modulate the differentiation of Th1 cells, which is linked to 3-hydroxykynurenine levels. Moreover, MAPKIs treatments are associated with alteration of 3-hydroxykynurenine and 3hydroxyanthranilic acid (3HAA) concentrations and led to higher "CXCL11," and "KLRD1" expression that are involved in T and NK cells activation. These findings imply that the kynurenine pathway is pathologically relevant in patients with CMM.

Algorithmic Probability-Guided Machine Learning on Non-Differentiable Spaces.

We show how complexity theory can be introduced in machine learning to help bring together apparently disparate areas of current research. We show that this model-driven approach may require less training data and can potentially be more generalizable as it shows greater resilience to random attacks. In an algorithmic space the order of its element is given by its algorithmic probability, which arises naturally from computable processes. We investigate the shape of a discrete algorithmic space when performing regression or classification using a loss function parametrized by algorithmic complexity, demonstrating that the property of differentiation is not required to achieve results similar to those obtained using differentiable programming approaches such as deep learning. In doing so we use examples which enable the two approaches to be compared (small, given the computational power required for estimations of algorithmic complexity). We find and report that 1) machine learning can successfully be performed on a non-smooth surface using algorithmic complexity; 2) that solutions can be found using an algorithmic-probability classifier, establishing a bridge between a fundamentally discrete theory of computability and a fundamentally continuous mathematical theory of optimization methods; 3) a formulation of an algorithmically directed search technique in non-smooth manifolds can be defined and conducted; 4) exploitation techniques and numerical methods for algorithmic search to navigate these discrete non-differentiable spaces can be performed; in application of the (a) identification of generative rules from data observations; (b) solutions to image classification problems more resilient against pixel attacks compared to neural networks; (c) identification of equation parameters from a small data-set in the presence of noise in continuous ODE system problem, (d) classification of Boolean NK networks by (1) network topology, (2) underlying Boolean function, and (3) number of incoming edges.

An Algorithmic Information Calculus for Causal Discovery and Reprogramming Systems.

We introduce and develop a method that demonstrates that the algorithmic information content of a system can be used as a steering handle in the dynamical phase space, thus affording an avenue for controlling and reprogramming systems. The method consists of applying a series of controlled interventions to a networked system while estimating how the algorithmic information content is affected. We demonstrate the method by reconstructing the phase space and their generative rules of some discrete dynamical systems (cellular automata) serving as controlled case studies. Next, the model-based interventional or causal calculus is evaluated and validated using (1) a huge large set of small graphs, (2) a number of larger networks with different topologies, and finally (3) biological networks derived from a widely studied and validated genetic network (E. coli) as well as on a significant number of differentiating (Th17) and differentiated human cells from a curated biological network data.

Exhaustion of CD4+ T-cells mediated by the Kynurenine Pathway in Melanoma.

Kynurenine pathway (KP) activation by the enzymatic activity of indoleamine 2,3-dioxygenase1 (IDO1) and kynurenine (KYN) production represents an attractive target for reducing tumour progression and improving anti-tumour immunity in multiple cancers. However, immunomodulatory properties of other KP metabolites such as 3-hydroxy kynurenine (3-HK) and kynurenic acid (KYNA) are poorly understood. The association of the kynurenine metabolic pathway with T-cell status in the tumour microenvironment were characterized, using gene expression data of 368 cutaneous skin melanoma (SKCM) patients from the TCGA cohort. Based on the identified correlations, we characterized the production of KYN, 3-HK, and KYNA in vitro using melanoma-derived cell lines and primary CD4+ CD25- T-cells. Activation of the CD4+ T-cells produced IFNγ, which yielded increased levels of KYN and KYNA. Concurrently, kynurenine 3-monooxygenase (KMO) expression and proliferation of CD4+ T-cells were reduced, whereas exhaustion markers such as PD-L1, AHR, FOXP3, and CTLA4 were increased. Additionally, an analysis of the correlation network reconstructed using TCGA-SKCM emphasized KMO and KYNU with high variability among BRAF wild-type compared with V600E, which underscored their role in distinct CD4+ T-cell behavior in tumour immunity. Our results suggest that, in addition to IDO1, there is an alternative immune regulatory mechanism associated with the lower KMO expression and the higher KYNA production, which contributes to dysfunctional effector CD4+ T-cell response.

MAPK pathway and B cells overactivation in multiple sclerosis revealed by phosphoproteomics and genomic analysis.

Dysregulation of signaling pathways in multiple sclerosis (MS) can be analyzed by phosphoproteomics in peripheral blood mononuclear cells (PBMCs). We performed in vitro kinetic assays on PBMCs in 195 MS patients and 60 matched controls and quantified the phosphorylation of 17 kinases using xMAP assays. Phosphoprotein levels were tested for association with genetic susceptibility by typing 112 single-nucleotide polymorphisms (SNPs) associated with MS susceptibility. We found increased phosphorylation of MP2K1 in MS patients relative to the controls. Moreover, we identified one SNP located in the PHDGH gene and another on IRF8 gene that were associated with MP2K1 phosphorylation levels, providing a first clue on how this MS risk gene may act. The analyses in patients treated with disease-modifying drugs identified the phosphorylation of each receptor's downstream kinases. Finally, using flow cytometry, we detected in MS patients increased STAT1, STAT3, TF65, and HSPB1 phosphorylation in CD19+ cells. These findings indicate the activation of cell survival and proliferation (MAPK), and proinflammatory (STAT) pathways in the immune cells of MS patients, primarily in B cells. The changes in the activation of these kinases suggest that these pathways may represent therapeutic targets for modulation by kinase inhibitors.

Phosphatase inhibitor PPP1R11 modulates resistance of human T cells toward Treg-mediated suppression of cytokine expression.

Regulatory T cells (Tregs) act as indispensable unit for maintaining peripheral immune tolerance mainly by regulating effector T cells. T cells resistant to suppression by Tregs pose therapeutic challenges in the treatment of autoimmune diseases, while augmenting susceptibility to suppression may be desirable for cancer therapy. To understand the cell intrinsic signals in T cells during suppression by Tregs, we have previously performed a global phosphoproteomic characterization. We revealed altered phosphorylation of protein phosphatase 1 regulatory subunit 11 (PPP1R11; Inhibitor-3) in conventional T cells upon suppression by Tregs. Here, we show that silencing of PPP1R11 renders T cells resistant toward Treg-mediated suppression of TCR-induced cytokine expression. Furthermore, whole-transcriptome sequencing revealed that PPP1R11 differentially regulates not only the expression of specific T cell stimulation-induced cytokines but also other molecules and pathways in T cells. We further confirmed the target of PPP1R11, PP1, to augment TCR-induced cytokine expression. In conclusion, we present PPP1R11 as a novel negative regulator of T cell activation-induced cytokine expression. Targeting PPP1R11 may have therapeutic potential to regulate the T cell activation status including modulating the susceptibility of T cells toward Treg-mediated suppression, specifically altering the stimulation-induced T cell cytokine milieu.

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.

Algorithmically probable mutations reproduce aspects of evolution, such as convergence rate, genetic memory and modularity.

Natural selection explains how life has evolved over millions of years from more primitive forms. The speed at which this happens, however, has sometimes defied formal explanations when based on random (uniformly distributed) mutations. Here, we investigate the application of a simplicity bias based on a natural but algorithmic distribution of mutations (no recombination) in various examples, particularly binary matrices, in order to compare evolutionary convergence rates. Results both on synthetic and on small biological examples indicate an accelerated rate when mutations are not statistically uniform but algorithmically uniform. We show that algorithmic distributions can evolve modularity and genetic memory by preservation of structures when they first occur sometimes leading to an accelerated production of diversity but also to population extinctions, possibly explaining naturally occurring phenomena such as diversity explosions (e.g. the Cambrian) and massive extinctions (e.g. the End Triassic) whose causes are currently a cause for debate. The natural approach introduced here appears to be a better approximation to biological evolution than models based exclusively upon random uniform mutations, and it also approaches a formal version of open-ended evolution based on previous formal results. These results validate some suggestions in the direction that computation may be an equally important driver of evolution. We also show that inducing the method on problems of optimization, such as genetic algorithms, has the potential to accelerate convergence of artificial evolutionary algorithms.

Predictive Systems Toxicology.

In this review we address to what extent computational techniques can augment our ability to predict toxicity. The first section provides a brief history of empirical observations on toxicity dating back to the dawn of Sumerian civilization. Interestingly, the concept of dose emerged very early on, leading up to the modern emphasis on kinetic properties, which in turn encodes the insight that toxicity is not solely a property of a compound but instead depends on the interaction with the host organism. The next logical step is the current conception of evaluating drugs from a personalized medicine point of view. We review recent work on integrating what could be referred to as classical pharmacokinetic analysis with emerging systems biology approaches incorporating multiple omics data. These systems approaches employ advanced statistical analytical data processing complemented with machine learning techniques and use both pharmacokinetic and omics data. We find that such integrated approaches not only provide improved predictions of toxicity but also enable mechanistic interpretations of the molecular mechanisms underpinning toxicity and drug resistance. We conclude the chapter by discussing some of the main challenges, such as how to balance the inherent tension between the predicitive capacity of models, which in practice amounts to constraining the number of features in the models versus allowing for rich mechanistic interpretability, i.e., equipping models with numerous molecular features. This challenge also requires patient-specific predictions on toxicity, which in turn requires proper stratification of patients as regards how they respond, with or without adverse toxic effects. In summary, the transformation of the ancient concept of dose is currently successfully operationalized using rich integrative data encoded in patient-specific models.

Time-resolved transcriptome and proteome landscape of human regulatory T cell (Treg) differentiation reveals novel regulators of FOXP3.

BACKGROUND: Regulatory T cells (Tregs) expressing the transcription factor FOXP3 are crucial mediators of self-tolerance, preventing autoimmune diseases but possibly hampering tumor rejection. Clinical manipulation of Tregs is of great interest, and first-in-man trials of Treg transfer have achieved promising outcomes. Yet, the mechanisms governing induced Treg (iTreg) differentiation and the regulation of FOXP3 are incompletely understood. RESULTS: To gain a comprehensive and unbiased molecular understanding of FOXP3 induction, we performed time-series RNA sequencing (RNA-Seq) and proteomics profiling on the same samples during human iTreg differentiation. To enable the broad analysis of universal FOXP3-inducing pathways, we used five differentiation protocols in parallel. Integrative analysis of the transcriptome and proteome confirmed involvement of specific molecular processes, as well as overlap of a novel iTreg subnetwork with known Treg regulators and autoimmunity-associated genes. Importantly, we propose 37 novel molecules putatively involved in iTreg differentiation. Their relevance was validated by a targeted shRNA screen confirming a functional role in FOXP3 induction, discriminant analyses classifying iTregs accordingly, and comparable expression in an independent novel iTreg RNA-Seq dataset. CONCLUSION: The data generated by this novel approach facilitates understanding of the molecular mechanisms underlying iTreg generation as well as of the concomitant changes in the transcriptome and proteome. Our results provide a reference map exploitable for future discovery of markers and drug candidates governing control of Tregs, which has important implications for the treatment of cancer, autoimmune, and inflammatory diseases.

Symmetry and Correspondence of Algorithmic Complexity over Geometric, Spatial and Topological Representations.

We introduce a definition of algorithmic symmetry in the context of geometric and spatial complexity able to capture mathematical aspects of different objects using as a case study polyominoes and polyhedral graphs. We review, study and apply a method for approximating the algorithmic complexity (also known as Kolmogorov-Chaitin complexity) of graphs and networks based on the concept of Algorithmic Probability (AP). AP is a concept (and method) capable of recursively enumerate all properties of computable (causal) nature beyond statistical regularities. We explore the connections of algorithmic complexity-both theoretical and numerical-with geometric properties mainly symmetry and topology from an (algorithmic) information-theoretic perspective. We show that approximations to algorithmic complexity by lossless compression and an Algorithmic Probability-based method can characterize spatial, geometric, symmetric and topological properties of mathematical objects and graphs.

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.

A Decomposition Method for Global Evaluation of Shannon Entropy and Local Estimations of Algorithmic Complexity.

We investigate the properties of a Block Decomposition Method (BDM), which extends the power of a Coding Theorem Method (CTM) that approximates local estimations of algorithmic complexity based on Solomonoff-Levin's theory of algorithmic probability providing a closer connection to algorithmic complexity than previous attempts based on statistical regularities such as popular lossless compression schemes. The strategy behind BDM is to find small computer programs that produce the components of a larger, decomposed object. The set of short computer programs can then be artfully arranged in sequence so as to produce the original object. We show that the method provides efficient estimations of algorithmic complexity but that it performs like Shannon entropy when it loses accuracy. We estimate errors and study the behaviour of BDM for different boundary conditions, all of which are compared and assessed in detail. The measure may be adapted for use with more multi-dimensional objects than strings, objects such as arrays and tensors. To test the measure we demonstrate the power of CTM on low algorithmic-randomness objects that are assigned maximal entropy (e.g., π ) but whose numerical approximations are closer to the theoretical low algorithmic-randomness expectation. We also test the measure on larger objects including dual, isomorphic and cospectral graphs for which we know that algorithmic randomness is low. We also release implementations of the methods in most major programming languages-Wolfram Language (Mathematica), Matlab, R, Perl, Python, Pascal, C++, and Haskell-and an online algorithmic complexity calculator.