Connectivity of Random Geometric Hypergraphs.

We consider a random geometric hypergraph model based on an underlying bipartite graph. Nodes and hyperedges are sampled uniformly in a domain, and a node is assigned to those hyperedges that lie within a certain radius. From a modelling perspective, we explain how the model captures higher-order connections that arise in real data sets. Our main contribution is to study the connectivity properties of the model. In an asymptotic limit where the number of nodes and hyperedges grow in tandem, we give a condition on the radius that guarantees connectivity.

A network model for polarization of political opinion.

We propose and study a simple model for the evolution of political opinion through a population. The model includes a nonlinear term that causes individuals with more extreme views to be less receptive to external influence. Such a term was suggested in 1981 by Cobb in the context of a scalar-valued diffusion equation, and recent empirical studies support this modeling assumption. Here, we use the same philosophy in a network-based model. This allows us to incorporate the pattern of pairwise social interactions present in the population. We show that the model can admit two distinct stable steady states. This bi-stability property is seen to support polarization and can also make the long-term behavior of the system extremely sensitive to the initial conditions and to the precise connectivity structure. Computational results are given to illustrate these effects.

Sustained NMDA receptor hypofunction induces compromised neural systems integration and schizophrenia-like alterations in functional brain networks.

Compromised functional integration between cerebral subsystems and dysfunctional brain network organization may underlie the neurocognitive deficits seen in psychiatric disorders. Applying topological measures from network science to brain imaging data allows the quantification of complex brain network connectivity. While this approach has recently been used to further elucidate the nature of brain dysfunction in schizophrenia, the value of applying this approach in preclinical models of psychiatric disease has not been recognized. For the first time, we apply both established and recently derived algorithms from network science (graph theory) to functional brain imaging data from rats treated subchronically with the N-methyl-D-aspartic acid (NMDA) receptor antagonist phencyclidine (PCP). We show that subchronic PCP treatment induces alterations in the global properties of functional brain networks akin to those reported in schizophrenia. Furthermore, we show that subchronic PCP treatment induces compromised functional integration between distributed neural systems, including between the prefrontal cortex and hippocampus, that have established roles in cognition through, in part, the promotion of thalamic dysconnectivity. We also show that subchronic PCP treatment promotes the functional disintegration of discrete cerebral subsystems and also alters the connectivity of neurotransmitter systems strongly implicated in schizophrenia. Therefore, we propose that sustained NMDA receptor hypofunction contributes to the pathophysiology of dysfunctional brain network organization in schizophrenia.

Generative hypergraph models and spectral embedding.

Many complex systems involve interactions between more than two agents. Hypergraphs capture these higher-order interactions through hyperedges that may link more than two nodes. We consider the problem of embedding a hypergraph into low-dimensional Euclidean space so that most interactions are short-range. This embedding is relevant to many follow-on tasks, such as node reordering, clustering, and visualization. We focus on two spectral embedding algorithms customized to hypergraphs which recover linear and periodic structures respectively. In the periodic case, nodes are positioned on the unit circle. We show that the two spectral hypergraph embedding algorithms are associated with a new class of generative hypergraph models. These models generate hyperedges according to node positions in the embedded space and encourage short-range connections. They allow us to quantify the relative presence of periodic and linear structures in the data through maximum likelihood. They also improve the interpretability of node embedding and provide a metric for hyperedge prediction. We demonstrate the hypergraph embedding and follow-on tasks-including quantifying relative strength of structures, clustering and hyperedge prediction-on synthetic and real-world hypergraphs. We find that the hypergraph approach can outperform clustering algorithms that use only dyadic edges. We also compare several triadic edge prediction methods on high school and primary school contact hypergraphs where our algorithm improves upon benchmark methods when the amount of training data is limited.

Directed network Laplacians and random graph models.

We consider spectral methods that uncover hidden structures in directed networks. We establish and exploit connections between node reordering via (a) minimizing an objective function and (b) maximizing the likelihood of a random graph model. We focus on two existing spectral approaches that build and analyse Laplacian-style matrices via the minimization of frustration and trophic incoherence. These algorithms aim to reveal directed periodic and linear hierarchies, respectively. We show that reordering nodes using the two algorithms, or mapping them onto a specified lattice, is associated with new classes of directed random graph models. Using this random graph setting, we are able to compare the two algorithms on a given network and quantify which structure is more likely to be present. We illustrate the approach on synthetic and real networks, and discuss practical implementation issues.

Epidemics on hypergraphs: spectral thresholds for extinction.

Epidemic spreading is well understood when a disease propagates around a contact graph. In a stochastic susceptible-infected-susceptible setting, spectral conditions characterize whether the disease vanishes. However, modelling human interactions using a graph is a simplification which only considers pairwise relationships. This does not fully represent the more realistic case where people meet in groups. Hyperedges can be used to record higher order interactions, yielding more faithful and flexible models and allowing for the rate of infection of a node to depend on group size and also to vary as a nonlinear function of the number of infectious neighbours. We discuss different types of contagion models in this hypergraph setting and derive spectral conditions that characterize whether the disease vanishes. We study both the exact individual-level stochastic model and a deterministic mean field ODE approximation. Numerical simulations are provided to illustrate the analysis. We also interpret our results and show how the hypergraph model allows us to distinguish between contributions to infectiousness that (i) are inherent in the nature of the pathogen and (ii) arise from behavioural choices (such as social distancing, increased hygiene and use of masks). This raises the possibility of more accurately quantifying the effect of interventions that are designed to contain the spread of a virus.

Geometric de-noising of protein-protein interaction networks.

Understanding complex networks of protein-protein interactions (PPIs) is one of the foremost challenges of the post-genomic era. Due to the recent advances in experimental bio-technology, including yeast-2-hybrid (Y2H), tandem affinity purification (TAP) and other high-throughput methods for protein-protein interaction (PPI) detection, huge amounts of PPI network data are becoming available. Of major concern, however, are the levels of noise and incompleteness. For example, for Y2H screens, it is thought that the false positive rate could be as high as 64%, and the false negative rate may range from 43% to 71%. TAP experiments are believed to have comparable levels of noise.We present a novel technique to assess the confidence levels of interactions in PPI networks obtained from experimental studies. We use it for predicting new interactions and thus for guiding future biological experiments. This technique is the first to utilize currently the best fitting network model for PPI networks, geometric graphs. Our approach achieves specificity of 85% and sensitivity of 90%. We use it to assign confidence scores to physical protein-protein interactions in the human PPI network downloaded from BioGRID. Using our approach, we predict 251 interactions in the human PPI network, a statistically significant fraction of which correspond to protein pairs sharing common GO terms. Moreover, we validate a statistically significant portion of our predicted interactions in the HPRD database and the newer release of BioGRID. The data and Matlab code implementing the methods are freely available from the web site: http://www.kuchaev.com/Denoising.

A framework for second-order eigenvector centralities and clustering coefficients.

We propose and analyse a general tensor-based framework for incorporating second-order features into network measures. This approach allows us to combine traditional pairwise links with information that records whether triples of nodes are involved in wedges or triangles. Our treatment covers classical spectral methods and recently proposed cases from the literature, but we also identify many interesting extensions. In particular, we define a mutually reinforcing (spectral) version of the classical clustering coefficient. The underlying object of study is a constrained nonlinear eigenvalue problem associated with a cubic tensor. Using recent results from nonlinear Perron-Frobenius theory, we establish existence and uniqueness under appropriate conditions, and show that the new spectral measures can be computed efficiently with a nonlinear power method. To illustrate the added value of the new formulation, we analyse the measures on a class of synthetic networks. We also give computational results on centrality and link prediction for real-world networks.

Beyond non-backtracking: non-cycling network centrality measures.

Walks around a graph are studied in a wide range of fields, from graph theory and stochastic analysis to theoretical computer science and physics. In many cases it is of interest to focus on non-backtracking walks; those that do not immediately revisit their previous location. In the network science context, imposing a non-backtracking constraint on traditional walk-based node centrality measures is known to offer tangible benefits. Here, we use the Hashimoto matrix construction to characterize, generalize and study such non-backtracking centrality measures. We then devise a recursive extension that systematically removes triangles, squares and, generally, all cycles up to a given length. By characterizing the spectral radius of appropriate matrix power series, we explore how the universality results on the limiting behaviour of classical walk-based centrality measures extend to these non-cycling cases. We also demonstrate that the new recursive construction gives rise to practical centrality measures that can be applied to large-scale networks.

Fitting a geometric graph to a protein-protein interaction network.

MOTIVATION: Finding a good network null model for protein-protein interaction (PPI) networks is a fundamental issue. Such a model would provide insights into the interplay between network structure and biological function as well as into evolution. Also, network (graph) models are used to guide biological experiments and discover new biological features. It has been proposed that geometric random graphs are a good model for PPI networks. In a geometric random graph, nodes correspond to uniformly randomly distributed points in a metric space and edges (links) exist between pairs of nodes for which the corresponding points in the metric space are close enough according to some distance norm. Computational experiments have revealed close matches between key topological properties of PPI networks and geometric random graph models. In this work, we push the comparison further by exploiting the fact that the geometric property can be tested for directly. To this end, we develop an algorithm that takes PPI interaction data and embeds proteins into a low-dimensional Euclidean space, under the premise that connectivity information corresponds to Euclidean proximity, as in geometric-random graphs. We judge the sensitivity and specificity of the fit by computing the area under the Receiver Operator Characteristic (ROC) curve. The network embedding algorithm is based on multi-dimensional scaling, with the square root of the path length in a network playing the role of the Euclidean distance in the Euclidean space. The algorithm exploits sparsity for computational efficiency, and requires only a few sparse matrix multiplications, giving a complexity of O(N(2)) where N is the number of proteins. RESULTS: The algorithm has been verified in the sense that it successfully rediscovers the geometric structure in artificially constructed geometric networks, even when noise is added by re-wiring some links. Applying the algorithm to 19 publicly available PPI networks of various organisms indicated that: (a) geometric effects are present and (b) two-dimensional Euclidean space is generally as effective as higher dimensional Euclidean space for explaining the connectivity. Testing on a high-confidence yeast data set produced a very strong indication of geometric structure (area under the ROC curve of 0.89), with this network being essentially indistinguishable from a noisy geometric network. Overall, the results add support to the hypothesis that PPI networks have a geometric structure. AVAILABILITY: MATLAB code implementing the algorithm is available upon request.

A weighted communicability measure applied to complex brain networks.

Recent advances in experimental neuroscience allow non-invasive studies of the white matter tracts in the human central nervous system, thus making available cutting-edge brain anatomical data describing these global connectivity patterns. Through magnetic resonance imaging, this non-invasive technique is able to infer a snapshot of the cortical network within the living human brain. Here, we report on the initial success of a new weighted network communicability measure in distinguishing local and global differences between diseased patients and controls. This approach builds on recent advances in network science, where an underlying connectivity structure is used as a means to measure the ease with which information can flow between nodes. One advantage of our method is that it deals directly with the real-valued connectivity data, thereby avoiding the need to discretize the corresponding adjacency matrix, i.e. to round weights up to 1 or down to 0, depending upon some threshold value. Experimental results indicate that the new approach is able to extract biologically relevant features that are not immediately apparent from the raw connectivity data.

Communicability and multipartite structures in complex networks at negative absolute temperatures.

We here present a method of clearly identifying multipartite subgraphs in a network. The method is based on a recently introduced concept of the communicability, which very clearly identifies communities in a complex network. We here show that, while the communicability at a positive temperature is useful in identifying communities, the communicability at a negative temperature is useful in identifying multipartite subgraphs; the latter quantity between two nodes is positive when the two nodes belong to the same subgraph and is negative when they do not. The method is able to discover "almost" multipartite structures, where intercommunity connections vastly outweigh intracommunity connections. We illustrate the relevance of this work to real-life food web and protein-protein interaction networks.

High Modularity Creates Scaling Laws.

Scaling laws have been observed in many natural and engineered systems. Their existence can give useful information about the growth or decay of one quantitative feature in terms of another. For example, in the field of city analytics, it is has been fruitful to compare some urban attribute, such as energy usage or wealth creation, with population size. In this work, we use network science and dynamical systems perspectives to explain that the observed scaling laws, and power laws in particular, arise naturally when some feature of a complex system is measured in terms of the system size. Our analysis is based on two key assumptions that may be posed in graph theoretical terms. We assume (a) that the large interconnection network has a well-defined set of communities and (b) that the attribute under study satisfies a natural continuity-type property. We conclude that precise mechanistic laws are not required in order to explain power law effects in complex systems-very generic network-based rules can reproduce the behaviors observed in practice. We illustrate our results using Twitter interaction between accounts geolocated to the city of Bristol, UK.

A lock-and-key model for protein-protein interactions.

MOTIVATION: Protein-protein interaction networks are one of the major post-genomic data sources available to molecular biologists. They provide a comprehensive view of the global interaction structure of an organism's proteome, as well as detailed information on specific interactions. Here we suggest a physical model of protein interactions that can be used to extract additional information at an intermediate level: It enables us to identify proteins which share biological interaction motifs, and also to identify potentially missing or spurious interactions. RESULTS: Our new graph model explains observed interactions between proteins by an underlying interaction of complementary binding domains (lock-and-key model). This leads to a novel graph-theoretical algorithm to identify bipartite subgraphs within protein-protein interaction networks where the underlying data are taken from yeast two-hybrid experimental results. By testing on synthetic data, we demonstrate that under certain modelling assumptions, the algorithm will return correct domain information about each protein in the network. Tests on data from various model organisms show that the local and global patterns predicted by the model are indeed found in experimental data. Using functional and protein structure annotations, we show that bipartite subnetworks can be identified that correspond to biologically relevant interaction motifs. Some of these are novel and we discuss an example involving SH3 domains from the Saccharomyces cerevisiae interactome. AVAILABILITY: The algorithm (in Matlab format) is available (see http://www.maths.strath.ac.uk/~aas96106/lock_key.html).

Spectral analysis of two-signed microarray expression data.

We give a simple and informative derivation of a spectral algorithm for clustering and reordering complementary DNA microarray expression data. Here, expression levels of a set of genes are recorded simultaneously across a number of samples, with a positive weight reflecting up-regulation and a negative weight reflecting down-regulation. We give theoretical support for the algorithm based on a biologically justified hypothesis about the structure of the data, and illustrate its use on public domain data in the context of unsupervised tumour classification. The algorithm is derived by considering a discrete optimization problem and then relaxing to the continuous realm. We prove that in the case where the data have an inherent 'checkerboard' sign pattern, the algorithm will automatically reveal that pattern. Further, our derivation shows that the algorithm may be regarded as imposing a random graph model on the expression levels and then clustering from a maximum likelihood perspective. This indicates that the output will be tolerant to perturbations and will reveal 'near-checkerboard' patterns when these are present in the data. It is interesting to note that the checkerboard structure is revealed by the first (dominant) singular vectors--previous work on spectral methods has focussed on the case of nonnegative edge weights, where only the second and higher singular vectors are relevant. We illustrate the algorithm on real and synthetic data, and then use it in a tumour classification context on three different cancer data sets. Our results show that respecting the two-signed nature of the data (thereby distinguishing between up-regulation and down-regulation) reveals structures that cannot be gleaned from the absolute value data (where up- and down-regulation are both regarded as 'changes').

Sparse matrix computations for dynamic network centrality.

Time sliced networks describing human-human digital interactions are typically large and sparse. This is the case, for example, with pairwise connectivity describing social media, voice call or physical proximity, when measured over seconds, minutes or hours. However, if we wish to quantify and compare the overall time-dependent centrality of the network nodes, then we should account for the global flow of information through time. Because the time-dependent edge structure typically allows information to diffuse widely around the network, a natural summary of sparse but dynamic pairwise interactions will generally take the form of a large dense matrix. For this reason, computing nodal centralities for a time-dependent network can be extremely expensive in terms of both computation and storage; much more so than for a single, static network. In this work, we focus on the case of dynamic communicability, which leads to broadcast and receive centrality measures. We derive a new algorithm for computing time-dependent centrality that works with a sparsified version of the dynamic communicability matrix. In this way, the computation and storage requirements are reduced to those of a sparse, static network at each time point. The new algorithm is justified from first principles and then tested on a large scale data set. We find that even with very stringent sparsity requirements (retaining no more than ten times the number of nonzeros in the individual time slices), the algorithm accurately reproduces the list of highly central nodes given by the underlying full system. This allows us to capture centrality over time with a minimal level of storage and with a cost that scales only linearly with the number of time points. We also describe and test three variants of the proposed algorithm that require fewer parameters and achieve a further reduction in the computational cost.

An overview of city analytics.

We introduce the 14 articles in the Royal Society Open Science themed issue on City Analytics. To provide a high-level, strategic, overview, we summarize the topics addressed and the analytical tools deployed. We then give a more detailed account of the individual contributions. Our overall aims are (i) to highlight exciting advances in this emerging, interdisciplinary field, (ii) to encourage further activity and (iii) to emphasize the variety of new, public-domain, datasets that are available to researchers.

Modelling protein-protein interaction networks via a stickiness index.

What type of connectivity structure are we seeing in protein-protein interaction networks? A number of random graph models have been mooted. After fitting model parameters to real data, the models can be judged by their success in reproducing key network properties. Here, we propose a very simple random graph model that inserts a connection according to the degree, or 'stickiness', of the two proteins involved. This model can be regarded as a testable distillation of more sophisticated versions that attempt to account for the presence of interaction surfaces or binding domains. By computing a range of network similarity measures, including relative graphlet frequency distance, we find that our model outperforms other random graph classes. In particular, we show that given the underlying degree information, fitting a stickiness model produces better results than simply choosing a degree-matching graph uniformly at random. Therefore, the results lend support to the basic modelling methodology.

Comment on "Numerical methods for stochastic differential equations".

Wilkie [Phys. Rev. E 70, 017701 (2004)] used a heuristic approach to derive Runge-Kutta-based numerical methods for stochastic differential equations based on methods used for solving ordinary differential equations. The aim was to follow solution paths with high order. We point out that this approach is invalid in the general case and does not lead to high order methods. We warn readers against the inappropriate use of deterministic calculus in a stochastic setting.

GeneRank: using search engine technology for the analysis of microarray experiments.

BACKGROUND: Interpretation of simple microarray experiments is usually based on the fold-change of gene expression between a reference and a "treated" sample where the treatment can be of many types from drug exposure to genetic variation. Interpretation of the results usually combines lists of differentially expressed genes with previous knowledge about their biological function. Here we evaluate a method--based on the PageRank algorithm employed by the popular search engine Google--that tries to automate some of this procedure to generate prioritized gene lists by exploiting biological background information. RESULTS: GeneRank is an intuitive modification of PageRank that maintains many of its mathematical properties. It combines gene expression information with a network structure derived from gene annotations (gene ontologies) or expression profile correlations. Using both simulated and real data we find that the algorithm offers an improved ranking of genes compared to pure expression change rankings. CONCLUSION: Our modification of the PageRank algorithm provides an alternative method of evaluating microarray experimental results which combines prior knowledge about the underlying network. GeneRank offers an improvement compared to assessing the importance of a gene based on its experimentally observed fold-change alone and may be used as a basis for further analytical developments.