Clustering coefficients for networks with higher order interactions.

We introduce a clustering coefficient for nondirected and directed hypergraphs, which we call the quad clustering coefficient. We determine the average quad clustering coefficient and its distribution in real-world hypergraphs and compare its value with those of random hypergraphs drawn from the configuration model. We find that real-world hypergraphs exhibit a nonnegligible fraction of nodes with a maximal value of the quad clustering coefficient, while we do not find such nodes in random hypergraphs. Interestingly, these highly clustered nodes can have large degrees and can be incident to hyperedges of large cardinality. Moreover, highly clustered nodes are not observed in an analysis based on the pairwise clustering coefficient of the associated projected graph that has binary interactions, and hence higher order interactions are required to identify nodes with a large quad clustering coefficient.

Variational kinetic clustering of complex networks.

Efficiently identifying the most important communities and key transition nodes in weighted and unweighted networks is a prevalent problem in a wide range of disciplines. Here, we focus on the optimal clustering using variational kinetic parameters, linked to Markov processes defined on the underlying networks, namely, the slowest relaxation time and the Kemeny constant. We derive novel relations in terms of mean first passage times for optimizing clustering via the Kemeny constant and show that the optimal clustering boundaries have equal round-trip times to the clusters they separate. We also propose an efficient method that first projects the network nodes onto a 1D reaction coordinate and subsequently performs a variational boundary search using a parallel tempering algorithm, where the variational kinetic parameters act as an energy function to be extremized. We find that maximization of the Kemeny constant is effective in detecting communities, while the slowest relaxation time allows for detection of transition nodes. We demonstrate the validity of our method on several test systems, including synthetic networks generated from the stochastic block model and real world networks (Santa Fe Institute collaboration network, a network of co-purchased political books, and a street network of multiple cities in Luxembourg). Our approach is compared with existing clustering algorithms based on modularity and the robust Perron cluster analysis, and the identified transition nodes are compared with different notions of node centrality.

Modelling the interplay between the CD4[Formula: see text]/CD8[Formula: see text] T-cell ratio and the expression of MHC-I in tumours.

Describing the anti-tumour immune response as a series of cellular kinetic reactions from known immunological mechanisms, we create a mathematical model that shows the CD4[Formula: see text]/CD8[Formula: see text] T-cell ratio, T-cell infiltration and the expression of MHC-I to be interacting factors in tumour elimination. Methods from dynamical systems theory and non-equilibrium statistical mechanics are used to model the T-cell dependent anti-tumour immune response. Our model predicts a critical level of MHC-I expression which determines whether or not the tumour escapes the immune response. This critical level of MHC-I depends on the helper/cytotoxic T-cell ratio. However, our model also suggests that the immune system is robust against small changes in this ratio. We also find that T-cell infiltration and the specificity of the intra-tumour TCR repertoire will affect the critical MHC-I expression. Our work suggests that the functional form of the time evolution of MHC-I expression may explain the qualitative behaviour of tumour growth seen in patients.

Correlation functions, mean first passage times, and the Kemeny constant.

Markov processes are widely used models for investigating kinetic networks. Here, we collate and present a variety of results pertaining to kinetic network models in a unified framework. The aim is to lay out explicit links between several important quantities commonly studied in the field, including mean first passage times (MFPTs), correlation functions, and the Kemeny constant. We provide new insights into (i) a simple physical interpretation of the Kemeny constant, (ii) a relationship to infer equilibrium distributions and rate matrices from measurements of MFPTs, and (iii) a protocol to reduce the dimensionality of kinetic networks based on specific requirements that the MFPTs in the coarse-grained system should satisfy. We prove that this protocol coincides with the one proposed by Hummer and Szabo [J. Phys. Chem. B 119, 9029 (2014)], and it leads to a variational principle for the Kemeny constant. Finally, we introduce a modification of this protocol, which preserves the Kemeny constant. Our work underpinning the theoretical aspects of kinetic networks will be useful in applications including milestoning and path sampling algorithms in molecular simulations.

Mean first passage times in variational coarse graining using Markov state models.

Markov state models (MSMs) provide some of the simplest mathematical and physical descriptions of dynamical and thermodynamical properties of complex systems. However, typically, the large dimensionality of biological systems studied makes them prohibitively expensive to work in fully Markovian regimes. In this case, coarse graining can be introduced to capture the key dynamical processes-slow degrees of the system-and reduce the dimension of the problem. Here, we introduce several possible options for such Markovian coarse graining, including previously commonly used choices: the local equilibrium and the Hummer Szabo approaches. We prove that the coarse grained lower dimensional MSM satisfies a variational principle with respect to its slowest relaxation time scale. This provides an excellent framework for optimal coarse graining, as previously demonstrated. Here, we show that such optimal coarse graining to two or three states has a simple physical interpretation in terms of mean first passage times and fluxes between the coarse grained states. The results are verified numerically using both analytic test potentials and data from explicit solvent molecular dynamics simulations of pentalanine. This approach of optimizing and interpreting clustering protocols has broad applicability and can be used in time series analysis of large data.

Limiting relaxation times from Markov state models.

Markov state models (MSMs) are more and more widely used in the analysis of molecular simulations to incorporate multiple trajectories together and obtain more accurate time scale information of the slowest processes in the system. Typically, however, multiple lagtimes are used and analyzed as input parameters, yet convergence with respect to the choice of lagtime is not always possible. Here, we present a simple method for calculating the slowest relaxation time (RT) of the system in the limit of very long lagtimes. Our approach relies on the fact that the second eigenvector's autocorrelation function of the propagator will be approximately single exponential at long lagtimes. This allows us to obtain a simple equation for the behavior of the MSM's relaxation time as a function of the lagtime with only two free parameters, one of these being the RT of the system. We demonstrate that the second parameter is a useful indicator of how Markovian a selected variable is for building the MSM. Fitting this function to data gives a limiting value for the optimal variational RT. Testing this on analytic and molecular dynamics data for Ala5 and umbrella sampling-biased ion channel simulations shows that the function accurately describes the behavior of the RT and furthermore that this RT can improve noticeably the value calculated at the longest accessible lagtime. We compare our RT limit to the hidden Markov model (HMM) approach that typically finds RTs of comparable values. However, HMMs cannot be used in conjunction with biased simulation data, requiring more complex algorithms to construct than MSMs, and the derived RTs are not variational, leading to ambiguity in the choice of lagtime at which to build the HMM.

Extensive parallel processing on scale-free networks.

We adapt belief-propagation techniques to study the equilibrium behavior of a bipartite spin glass, with interactions between two sets of N and P=αN spins each having an arbitrary degree, i.e., number of interaction partners in the opposite set. An equivalent view is then of a system of N neurons storing P diluted patterns via Hebbian learning, in the high storage regime. Our method allows analysis of parallel pattern processing on a broad class of graphs, including those with pattern asymmetry and heterogeneous dilution; previous replica approaches assumed homogeneity. We show that in a large part of the parameter space of noise, dilution, and storage load, delimited by a critical surface, the network behaves as an extensive parallel processor, retrieving all P patterns in parallel without falling into spurious states due to pattern cross talk, as would be typical of the structural glassiness built into the network. Parallel extensive retrieval is more robust for homogeneous degree distributions, and is not disrupted by asymmetric pattern distributions. For scale-free pattern degree distributions, Hebbian learning induces modularity in the neural network; thus, our Letter gives the first theoretical description for extensive information processing on modular and scale-free networks.

Graphie: A network-based visual interface for the UK's primary legislation.

Background: legislation.gov.uk is a platform that enables users to explore and navigate the many sections of the UK's legal corpus through its well-designed searching and browsing features. However, there is room for improvement as it lacks the ability to easily move between related sections or Acts and only presents a text-only rendering of provisions. With Graphie, our novel navigational tool (graphie.quantlaw.co.uk), we aim to address this limitation by presenting alternative visualizations of legal documents using both text and graphs. Methods: The building block of Graphie is Sofia, an offline data pipeline designed to support different data visualizations by parsing and modelling data provided by legislation.gov.uk in open access form. Results: Graphie provides a network representation of the hierarchical structure of an Act of Parliament, which is typically organized in a tree-like fashion according to the content and information contained in each sub-branch. Nodes in Graphie represent sections of an Act (or individual provisions), while links embody the hierarchical connections between them. The legal map provided by Graphie is easily navigable by hovering on nodes, which are also color-coded and numbered to provide easily accessible information about the underlying content. The full textual content of each node is also available on a dedicated hyperlinked canvas. Conclusions: While we focus on the Housing Act 2004 for illustrative purposes, our platform is scalable, versatile, and provides users with a unified toolbox to visualize and explore the UK legal corpus in a fast and user-friendly way.

Overcoming the complexity barrier of the dynamic message-passing method in networks with fat-tailed degree distributions.

The dynamic cavity method provides the most efficient way to evaluate probabilities of dynamic trajectories in systems of stochastic units with unidirectional sparse interactions. It is closely related to sum-product algorithms widely used to compute marginal functions from complicated global functions of many variables, with applications in disordered systems, combinatorial optimization, and computer science. However, the complexity of the cavity approach grows exponentially with the in-degrees of the interacting units, which creates a defacto barrier for the successful analysis of systems with fat-tailed in-degree distributions. In this paper, we present a dynamic programming algorithm that overcomes this barrier by reducing the computational complexity in the in-degrees from exponential to quadratic, whenever couplings are chosen randomly from (or can be approximated in terms of) discrete, possibly unit-dependent, sets of equidistant values. As a case study, we analyze the dynamics of a random Boolean network with a fat-tailed degree distribution and fully asymmetric binary ±J couplings, and we use the power of the algorithm to unlock the noise-dependent heterogeneity of stationary node activation patterns in such a system.

Position-Dependent Diffusion from Biased Simulations and Markov State Model Analysis.

A variety of enhanced statistical and numerical methods are now routinely used to extract important thermodynamic and kinetic information from the vast amount of complex, high-dimensional data obtained from molecular simulations. For the characterization of kinetic properties, Markov state models, in which the long-time statistical dynamics of a system is approximated by a Markov chain on a discrete partition of configuration space, have seen widespread use in recent years. However, obtaining kinetic properties for molecular systems with high energy barriers remains challenging as often enhanced sampling techniques are required with biased simulations to observe the relevant rare events. Particularly, the calculation of diffusion coefficients remains elusive from biased molecular simulation data. Here, we propose a novel method that can calculate multidimensional position-dependent diffusion coefficients equally from either biased or unbiased simulations using the same formalism. Our method builds on Markov state model analysis and the Kramers-Moyal expansion. We demonstrate the validity of our formalism using one- and two-dimensional analytic potentials and also apply it to data from explicit solvent molecular dynamics simulations, including the water-mediated conformations of alanine dipeptide and umbrella sampling simulations of drug transport across a lipid bilayer. Importantly, the developed algorithm presents significant improvement compared to standard methods when the transport of solute across three-dimensional heterogeneous porous media is studied, for example, the prediction of membrane permeation of drug molecules.

Maximal modularity and the optimal size of parliaments.

An important question in representative democracies is how to determine the optimal parliament size of a given country. According to an old conjecture, known as the cubic root law, there is a fairly universal power-law relation, with an exponent equal to 1/3, between the size of an elected parliament and the country's population. Empirical data in modern European countries support such universality but are consistent with a larger exponent. In this work, we analyse this intriguing regularity using tools from complex networks theory. We model the population of a democratic country as a random network, drawn from a growth model, where each node is assigned a constituency membership sampled from an available set of size D. We calculate analytically the modularity of the population and find that its functional relation with the number of constituencies is strongly non-monotonic, exhibiting a maximum that depends on the population size. The criterion of maximal modularity allows us to predict that the number of representatives should scale as a power-law in the size of the population, a finding that is qualitatively confirmed by the empirical analysis of real-world data.

Bridging topological and functional information in protein interaction networks by short loops profiling.

Protein-protein interaction networks (PPINs) have been employed to identify potential novel interconnections between proteins as well as crucial cellular functions. In this study we identify fundamental principles of PPIN topologies by analysing network motifs of short loops, which are small cyclic interactions of between 3 and 6 proteins. We compared 30 PPINs with corresponding randomised null models and examined the occurrence of common biological functions in loops extracted from a cross-validated high-confidence dataset of 622 human protein complexes. We demonstrate that loops are an intrinsic feature of PPINs and that specific cell functions are predominantly performed by loops of different lengths. Topologically, we find that loops are strongly related to the accuracy of PPINs and define a core of interactions with high resilience. The identification of this core and the analysis of loop composition are promising tools to assess PPIN quality and to uncover possible biases from experimental detection methods. More than 96% of loops share at least one biological function, with enrichment of cellular functions related to mRNA metabolic processing and the cell cycle. Our analyses suggest that these motifs can be used in the design of targeted experiments for functional phenotype detection.

Supersymmetric complexity in the Sherrington-Kirkpatrick model.

By using a supersymmetric approach we compute the complexity of the metastable states in the Sherrington-Kirkpatrick spin-glass model. We prove that the supersymmetric complexity is exactly equal to the Legendre transform of the thermodynamic free energy, thus providing a recipe to find the complexity once the free energy is known. Our results suggest that the supersymmetry may be a useful tool for the calculation of the entropy of metastable states in generic glassy systems.

Protein networks reveal detection bias and species consistency when analysed by information-theoretic methods.

We apply our recently developed information-theoretic measures for the characterisation and comparison of protein-protein interaction networks. These measures are used to quantify topological network features via macroscopic statistical properties. Network differences are assessed based on these macroscopic properties as opposed to microscopic overlap, homology information or motif occurrences. We present the results of a large-scale analysis of protein-protein interaction networks. Precise null models are used in our analyses, allowing for reliable interpretation of the results. By quantifying the methodological biases of the experimental data, we can define an information threshold above which networks may be deemed to comprise consistent macroscopic topological properties, despite their small microscopic overlaps. Based on this rationale, data from yeast-two-hybrid methods are sufficiently consistent to allow for intra-species comparisons (between different experiments) and inter-species comparisons, while data from affinity-purification mass-spectrometry methods show large differences even within intra-species comparisons.