Background: Typically, proteins perform key biological functions by interacting with each other. As a consequence, predicting which protein pairs interact is a fundamental problem. Experimental methods are slow, expensive, and may be error prone. Man
y computational methods have been proposed to identify candidate interacting pairs. When accurate, they can serve as an inexpensive, preliminary filtering stage, to be followed by downstream experimental validation. Among such methods, sequence-based ones are very promising. Results: We present MPS(T&B) (Maximum Protein Similarity Topological and Biological), a new algorithm that leverages both topological and biological information to predict protein-protein interactions. We comprehensively compare MPS(T) and MPS(T&B) with state-of-the-art approaches on reliable PPIs datasets, showing that they have competitive or higher accuracy on biologically validated test sets. Conclusion: MPS(T) and MPS(T&B) are topological only and topological plus sequence-based computational methods that can effectively predict the entire human interactome.
We study epidemic spreading according to a emph{Susceptible-Infectious-Recovered} (for short, emph{SIR}) network model known as the {em Reed-Frost} model, and we establish sharp thresholds for two generative models of {em one-dimensional small-world
graphs}, in which graphs are obtained by adding random edges to a cycle. In $3$-regular graphs obtained as the union of a cycle and a random perfect matching, we show that there is a sharp threshold at $.5$ for the contagion probability along edges. In graphs obtained as the union of a cycle and of a $mathcal{G}_{n,c/n}$ ErdH{o}s-Renyi random graph with edge probability $c/n$, we show that there is a sharp threshold $p_c$ for the contagion probability: the value of $p_c$ turns out to be $sqrt 2 -1approx .41$ for the sparse case $c=1$ yielding an expected node degree similar to the random $3$-regular graphs above. In both models, below the threshold we prove that the infection only affects $mathcal{O}(log n)$ nodes, and that above the threshold it affects $Omega(n)$ nodes. These are the first fully rigorous results establishing a phase transition for SIR models (and equivalent percolation problems) in small-world graphs. Although one-dimensional small-world graphs are an idealized and unrealistic network model, a number of realistic qualitative phenomena emerge from our analysis, including the spread of the disease through a sequence of local outbreaks, the danger posed by random connections, and the effect of super-spreader events.
We investigate opinion dynamics in multi-agent networks when a bias toward one of two possible opinions exists; for example, reflecting a status quo vs a superior alternative. Starting with all agents sharing an initial opinion representing the statu
s quo, the system evolves in steps. In each step, one agent selected uniformly at random adopts the superior opinion with some probability $alpha$, and with probability $1 - alpha$ it follows an underlying update rule to revise its opinion on the basis of those held by its neighbors. We analyze convergence of the resulting process under two well-known update rules, namely majority and voter. The framework we propose exhibits a rich structure, with a non-obvious interplay between topology and underlying update rule. For example, for the voter rule we show that the speed of convergence bears no significant dependence on the underlying topology, whereas the picture changes completely under the majority rule, where network density negatively affects convergence. We believe that the model we propose is at the same time simple, rich, and modular, affording mathematical characterization of the interplay between bias, underlying opinion dynamics, and social structure in a unified setting.
We study expansion and information diffusion in dynamic networks, that is in networks in which nodes and edges are continuously created and destroyed. We consider information diffusion by {em flooding}, the process by which, once a node is informed,
it broadcasts its information to all its neighbors. We study models in which the network is {em sparse}, meaning that it has $mathcal{O}(n)$ edges, where $n$ is the number of nodes, and in which edges are created randomly, rather than according to a carefully designed distributed algorithm. In our models, when a node is born, it connects to $d=mathcal{O}(1)$ random other nodes. An edge remains alive as long as both its endpoints do. If no further edge creation takes place, we show that, although the network will have $Omega_d(n)$ isolated nodes, it is possible, with large constant probability, to inform a $1-exp(-Omega(d))$ fraction of nodes in $mathcal{O}(log n)$ time. Furthermore, the graph exhibits, at any given time, a large-set expansion property. We also consider models with {em edge regeneration}, in which if an edge $(v,w)$ chosen by $v$ at birth goes down because of the death of $w$, the edge is replaced by a fresh random edge $(v,z)$. In models with edge regeneration, we prove that the network is, with high probability, a vertex expander at any given time, and flooding takes $mathcal{O}(log n)$ time. The above results hold both for a simple but artificial streaming model of node churn, in which at each time step one node is born and the oldest node dies, and in a more realistic continuous-time model in which the time between births is Poisson and the lifetime of each node follows an exponential distribution.
Spectral techniques have proved amongst the most effective approaches to graph clustering. However, in general they require explicit computation of the main eigenvectors of a suitable matrix (usually the Laplacian matrix of the graph). Recent work (e
.g., Becchetti et al., SODA 2017) suggests that observing the temporal evolution of the power method applied to an initial random vector may, at least in some cases, provide enough information on the space spanned by the first two eigenvectors, so as to allow recovery of a hidden partition without explicit eigenvector computations. While the results of Becchetti et al. apply to perfectly balanced partitions and/or graphs that exhibit very strong forms of regularity, we extend their approach to graphs containing a hidden $k$ partition and characterized by a milder form of volume-regularity. We show that the class of $k$-volume-regular graphs is the largest class of undirected (possibly weighted) graphs whose transition matrix admits $k$ stepwise eigenvectors (i.e., vectors that are constant over each set of the hidden partition). To obtain this result, we highlight a connection between volume regularity and lumpability of Markov chains. Moreover, we prove that if the stepwise eigenvectors are those associated to the first $k$ eigenvalues and the gap between the $k$-th and the ($k$+1)-th eigenvalues is sufficiently large, the averaging dynamics of Becchetti et al. recovers the underlying community structure of the graph in logarithmic time, with high probability.
Reducing hidden bias in the data and ensuring fairness in algorithmic data analysis has recently received significant attention. We complement several recent papers in this line of research by introducing a general method to reduce bias in the data t
hrough random projections in a fair subspace. We apply this method to densest subgraph problem. For densest subgraph, our approach based on fair projections allows to recover both theoretically and empirically an almost optimal, fair, dense subgraph hidden in the input data. We also show that, under the small set expansion hypothesis, approximating this problem beyond a factor of 2 is NP-hard and we show a polynomial time algorithm with a matching approximation bound.
The computation of electrical flows is a crucial primitive for many recently proposed optimization algorithms on weighted networks. While typically implemented as a centralized subroutine, the ability to perform this task in a fully decentralized way
is implicit in a number of biological systems. Thus, a natural question is whether this task can provably be accomplished in an efficient way by a network of agents executing a simple protocol. We provide a positive answer, proposing two distributed approaches to electrical flow computation on a weighted network: a deterministic process mimicking Jacobis iterative method for solving linear systems, and a randomized token diffusion process, based on revisiting a classical random walk process on a graph with an absorbing node. We show that both processes converge to a solution of Kirchhoffs node potential equations, derive bounds on their convergence rates in terms of the weights of the network, and analyze their time and message complexity.
