BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

R. Zecchina

R. Zecchina contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
cond-mat.stat-mechcond-mat.dis-nnComputer Science and Game Theoryphysics.soc-phData Structures and AlgorithmsQuantitative MethodsArtificial IntelligenceComputational ComplexityComputational Engineering, Finance, and Sciencecond-matcond-mat.str-elInformation Theorymath.ITMolecular NetworksPopulations and EvolutionSocial and Information Networks

Trust snapshot

Quick read

Trust 21 - Emerging
14works
0followers
16topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

14 published item(s)

preprint2013arXiv

Containing epidemic outbreaks by message-passing techniques

The problem of targeted network immunization can be defined as the one of finding a subset of nodes in a network to immunize or vaccinate in order to minimize a tradeoff between the cost of vaccination and the final (stationary) expected infection under a given epidemic model. Although computing the expected infection is a hard computational problem, simple and efficient mean-field approximations have been put forward in the literature in recent years. The optimization problem can be recast into a constrained one in which the constraints enforce local mean-field equations describing the average stationary state of the epidemic process. For a wide class of epidemic models, including the susceptible-infected-removed and the susceptible-infected-susceptible models, we define a message-passing approach to network immunization that allows us to study the statistical properties of epidemic outbreaks in the presence of immunized nodes as well as to find (nearly) optimal immunization sets for a given choice of parameters and costs. The algorithm scales linearly with the size of the graph and it can be made efficient even on large networks. We compare its performance with topologically based heuristics, greedy methods, and simulated annealing.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Large deviations of cascade processes on graphs

Simple models of irreversible dynamical processes such as Bootstrap Percolation have been successfully applied to describe cascade processes in a large variety of different contexts. However, the problem of analyzing non-typical trajectories, which can be crucial for the understanding of the out-of-equilibrium phenomena, is still considered to be intractable in most cases. Here we introduce an efficient method to find and analyze optimized trajectories of cascade processes. We show that for a wide class of irreversible dynamical rules, this problem can be solved efficiently on large-scale systems.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Stochastic Optimization of Service Provision with Selfish Users

We develop a computationally efficient technique to solve a fairly general distributed service provision problem with selfish users and imperfect information. In particular, in a context in which the service capacity of the existing infrastructure can be partially adapted to the user load by activating just some of the service units, we aim at finding the configuration of active service units that achieves the best trade-off between maintenance (e.g.\ energetic) costs for the provider and user satisfaction. The core of our technique resides in the implementation of a belief-propagation (BP) algorithm to evaluate the cost configurations. Numerical results confirm the effectiveness of our approach.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Cavity approach to sphere packing in Hamming space

In this paper we study the hard sphere packing problem in the Hamming space by the cavity method. We show that both the replica symmetric and the replica symmetry breaking approximations give maximum rates of packing that are asymptotically the same as the lower bound of Gilbert and Varshamov. Consistently with known numerical results, the replica symmetric equations also suggest a crystalline solution, where for even diameters the spheres are more likely to be found in one of the subspaces (even or odd) of the Hamming space. These crystalline packings can be generated by a recursive algorithm which finds maximum packings in an ultra-metric space. Finally, we design a message passing algorithm based on the cavity equations to find dense packings of hard spheres. Known maximum packings are reproduced efficiently in non trivial ranges of dimensions and number of spheres.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Sign problem in the Bethe approximation

We propose a message-passing algorithm to compute the Hamiltonian expectation with respect to an appropriate class of trial wave functions for an interacting system of fermions. To this end, we connect the quantum expectations to average quantities in a classical system with both local and global interactions, which are related to the variational parameters and use the Bethe approximation to estimate the average energy within the replica-symmetric approximation. The global interactions, which are needed to obtain a good estimation of the average fermion sign, make the average energy a nonlocal function of the variational parameters. We use some heuristic minimization algorithms to find approximate ground states of the Hubbard model on random regular graphs and observe significant qualitative improvements with respect to the mean-field approximation.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Finding undetected protein associations in cell signaling by belief propagation

External information propagates in the cell mainly through signaling cascades and transcriptional activation, allowing it to react to a wide spectrum of environmental changes. High throughput experiments identify numerous molecular components of such cascades that may, however, interact through unknown partners. Some of them may be detected using data coming from the integration of a protein-protein interaction network and mRNA expression profiles. This inference problem can be mapped onto the problem of finding appropriate optimal connected subgraphs of a network defined by these datasets. The optimization procedure turns out to be computationally intractable in general. Here we present a new distributed algorithm for this task, inspired from statistical physics, and apply this scheme to alpha factor and drug perturbations data in yeast. We identify the role of the COS8 protein, a member of a gene family of previously unknown function, and validate the results by genetic experiments. The algorithm we present is specially suited for very large datasets, can run in parallel, and can be adapted to other problems in systems biology. On renowned benchmarks it outperforms other algorithms in the field.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Inference and learning in sparse systems with multiple states

We discuss how inference can be performed when data are sampled from the non-ergodic phase of systems with multiple attractors. We take as model system the finite connectivity Hopfield model in the memory phase and suggest a cavity method approach to reconstruct the couplings when the data are separately sampled from few attractor states. We also show how the inference results can be converted into a learning protocol for neural networks in which patterns are presented through weak external fields. The protocol is simple and fully local, and is able to store patterns with a finite overlap with the input patterns without ever reaching a spin glass phase where all memories are lost.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Statistical physics approach to graphical games: local and global interactions

In a graphical game agents play with their neighbors on a graph to achieve an appropriate state of equilibrium. Here relevant problems are characterizing the equilibrium set and discovering efficient algorithms to find such an equilibrium (solution). We consider a representation of games that extends over graphical games to deal conveniently with both local a global interactions and use the cavity method of statistical physics to study the geometrical structure of the equilibria space. The method also provides a distributive and local algorithm to find an equilibrium. For simplicity we consider only pure Nash equilibria but the methods can as well be extended to deal with (approximated) mixed Nash equilirbia.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Aligning graphs and finding substructures by a cavity approach

We introduce a new distributed algorithm for aligning graphs or finding substructures within a given graph. It is based on the cavity method and is used to study the maximum-clique and the graph-alignment problems in random graphs. The algorithm allows to analyze large graphs and may find applications in fields such as computational biology. As a proof of concept we use our algorithm to align the similarity graphs of two interacting protein families involved in bacterial signal transduction, and to predict actually interacting protein partners between these families.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Clustering with shallow trees

We propose a new method for hierarchical clustering based on the optimisation of a cost function over trees of limited depth, and we derive a message--passing method that allows to solve it efficiently. The method and algorithm can be interpreted as a natural interpolation between two well-known approaches, namely single linkage and the recently presented Affinity Propagation. We analyze with this general scheme three biological/medical structured datasets (human population based on genetic information, proteins based on sequences and verbal autopsies) and show that the interpolation technique provides new insight.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Statistical mechanics of budget-constrained auctions

Finding the optimal assignment in budget-constrained auctions is a combinatorial optimization problem with many important applications, a notable example being the sale of advertisement space by search engines (in this context the problem is often referred to as the off-line AdWords problem). Based on the cavity method of statistical mechanics, we introduce a message passing algorithm that is capable of solving efficiently random instances of the problem extracted from a natural distribution, and we derive from its properties the phase diagram of the problem. As the control parameter (average value of the budgets) is varied, we find two phase transitions delimiting a region in which long-range correlations arise.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Encoding for the Blackwell Channel with Reinforced Belief Propagation

A key idea in coding for the broadcast channel (BC) is binning, in which the transmitter encode information by selecting a codeword from an appropriate bin (the messages are thus the bin indexes). This selection is normally done by solving an appropriate (possibly difficult) combinatorial problem. Recently it has been shown that binning for the Blackwell channel --a particular BC-- can be done by iterative schemes based on Survey Propagation (SP). This method uses decimation for SP and suffers a complexity of O(n^2). In this paper we propose a new variation of the Belief Propagation (BP) algorithm, named Reinforced BP algorithm, that turns BP into a solver. Our simulations show that this new algorithm has complexity O(n log n). Using this new algorithm together with a non-linear coding scheme, we can efficiently achieve rates close to the border of the capacity region of the Blackwell channel.

0 citations0 reviewsNo code linkedOpen access
preprint1995arXiv

Weight Space Structure and Internal Representations: a Direct Approach to Learning and Generalization in Multilayer Neural Network

We analytically derive the geometrical structure of the weight space in multilayer neural networks (MLN), in terms of the volumes of couplings associated to the internal representations of the training set. Focusing on the parity and committee machines, we deduce their learning and generalization capabilities both reinterpreting some known properties and finding new exact results. The relationship between our approach and information theory as well as the Mitchison--Durbin calculation is established. Our results are exact in the limit of a large number of hidden units, showing that MLN are a class of exactly solvable models with a simple interpretation of replica symmetry breaking.

0 citations0 reviewsNo code linkedOpen access