@article{bindi_predicting_2017, title = {Predicting epidemic evolution on contact networks from partial observations}, volume = {12}, issn = {1932-6203}, url = {http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0176376}, doi = {10.1371/journal.pone.0176376}, abstract = {The massive employment of computational models in network epidemiology calls for the development of improved inference methods for epidemic forecast. For simple compartment models, such as the Susceptible-Infected-Recovered model, Belief Propagation was proved to be a reliable and efficient method to identify the origin of an observed epidemics. Here we show that the same method can be applied to predict the future evolution of an epidemic outbreak from partial observations at the early stage of the dynamics. The results obtained using Belief Propagation are compared with Monte Carlo direct sampling in the case of SIR model on random (regular and power-law) graphs for different observation methods and on an example of real-world contact network. Belief Propagation gives in general a better prediction that direct sampling, although the quality of the prediction depends on the quantity under study (e.g. marginals of individual states, epidemic size, extinction-time distribution) and on the actual number of observed nodes that are infected before the observation time.}, number = {4}, urldate = {2017-05-11}, journal = {PLOS ONE}, author = {Bindi, Jacopo and Braunstein, Alfredo and Dall{\textquoteright}Asta, Luca}, month = apr, year = {2017}, keywords = {Algorithms, Convergent evolution, Epidemiological methods and statistics, Forecasting, graphs, Infectious disease epidemiology, Probability density, Probability distribution}, pages = {e0176376}, file = {[PDF] da arxiv.org:/home/ab/.mozilla/firefox/3nu0zcxd.default-1419871504027/zotero/storage/E6B8DW5T/Bindi et al. - 2016 - Predicting epidemic evolution on contact networks .pdf:application/pdf;Snapshot:/home/ab/.mozilla/firefox/3nu0zcxd.default-1419871504027/zotero/storage/EH7S5RDR/article.html:text/html} } @article{braunstein_analytic_2017, title = {An analytic approximation of the feasible space of metabolic networks}, volume = {8}, copyright = {{\textcopyright} 2017 Macmillan Publishers Limited, part of Springer Nature. All rights reserved.}, issn = {2041-1723}, url = {http://www.nature.com/ncomms/2017/170406/ncomms14915/full/ncomms14915.html}, doi = {10.1038/ncomms14915}, abstract = {Large-scale metabolic models of organisms from microbes to mammals can provide great insight into cellular function, but their analysis remains challenging.}, language = {en}, urldate = {2017-04-07}, journal = {Nature Communications}, author = {Braunstein, Alfredo and Muntoni, Anna Paola and Pagnani, Andrea}, month = apr, year = {2017}, pages = {14915}, file = {ncomms14915.pdf:/home/ab/.mozilla/firefox/3nu0zcxd.default-1419871504027/zotero/storage/UNPTX4QC/ncomms14915.pdf:application/pdf;Snapshot:/home/ab/.mozilla/firefox/3nu0zcxd.default-1419871504027/zotero/storage/6HM8ZZ48/ncomms14915.html:text/html} } @article{braunstein_network_2016, title = {Network dismantling}, issn = {0027-8424, 1091-6490}, url = {http://www.pnas.org/content/early/2016/10/18/1605083113}, doi = {10.1073/pnas.1605083113}, abstract = {We study the network dismantling problem, which consists of determining a minimal set of vertices in which removal leaves the network broken into connected components of subextensive size. For a large class of random graphs, this problem is tightly connected to the decycling problem (the removal of vertices, leaving the graph acyclic). Exploiting this connection and recent works on epidemic spreading, we present precise predictions for the minimal size of a dismantling set in a large random graph with a prescribed (light-tailed) degree distribution. Building on the statistical mechanics perspective, we propose a three-stage Min-Sum algorithm for efficiently dismantling networks, including heavy-tailed ones for which the dismantling and decycling problems are not equivalent. We also provide additional insights into the dismantling problem, concluding that it is an intrinsically collective problem and that optimal dismantling sets cannot be viewed as a collection of individually well-performing nodes.}, language = {en}, urldate = {2016-10-20}, journal = {Proceedings of the National Academy of Sciences}, author = {Braunstein, Alfredo and Dall’Asta, Luca and Semerjian, Guilhem and Zdeborová, Lenka}, month = oct, year = {2016}, note = {arXiv: 1603.08883}, keywords = {graph fragmentation, Influence maximization, message passing, Percolation, random graphs}, pages = {201605083}, file = {arXiv.org Snapshot:/home/ab/.mozilla/firefox/3nu0zcxd.default-1419871504027/zotero/storage/DWKGE8PQ/1603.html:text/html;Full Text PDF:/home/ab/.mozilla/firefox/3nu0zcxd.default-1419871504027/zotero/storage/BR88I334/Braunstein et al. - 2016 - Network dismantling.pdf:application/pdf;Snapshot:/home/ab/.mozilla/firefox/3nu0zcxd.default-1419871504027/zotero/storage/BRA6PC2A/1605083113.html:text/html} } @article{altarelli_statics_2015, title = {Statics and {Dynamics} of {Selfish} {Interactions} in {Distributed} {Service} {Systems}}, volume = {10}, url = {http://dx.doi.org/10.1371/journal.pone.0119286}, doi = {10.1371/journal.pone.0119286}, abstract = {We study a class of games which models the competition among agents to access some service provided by distributed service units and which exhibits congestion and frustration phenomena when service units have limited capacity. We propose a technique, based on the cavity method of statistical physics, to characterize the full spectrum of Nash equilibria of the game. The analysis reveals a large variety of equilibria, with very different statistical properties. Natural selfish dynamics, such as best-response, usually tend to large-utility equilibria, even though those of smaller utility are exponentially more numerous. Interestingly, the latter actually can be reached by selecting the initial conditions of the best-response dynamics close to the saturation limit of the service unit capacities. We also study a more realistic stochastic variant of the game by means of a simple and effective approximation of the average over the random parameters, showing that the properties of the average-case Nash equilibria are qualitatively similar to the deterministic ones.}, number = {7}, urldate = {2015-10-09}, journal = {PLoS ONE}, author = {Altarelli, Fabrizio and Braunstein, Alfredo and Dall{\textquoteright}Asta, Luca}, month = jul, year = {2015}, pages = {e0119286}, file = {PLoS Full Text PDF:/home/ab/.mozilla/firefox/3nu0zcxd.default-1419871504027/zotero/storage/PEP6TF8G/Altarelli et al. - 2015 - Statics and Dynamics of Selfish Interactions in Di.pdf:application/pdf} } @article{baldassi_max-sum_2015, title = {A {Max}-{Sum} algorithm for training discrete neural networks}, volume = {2015}, issn = {1742-5468}, url = {http://iopscience.iop.org/1742-5468/2015/8/P08008}, doi = {10.1088/1742-5468/2015/08/P08008}, abstract = {We present an efficient learning algorithm for the problem of training neural networks with discrete synapses, a well-known hard (NP-complete) discrete optimization problem. The algorithm is a variant of the so-called Max-Sum (MS) algorithm. In particular, we show how, for bounded integer weights with q distinct states and independent concave a priori distribution (e.g. l1 regularization), the algorithm{\textquoteright}s time complexity can be made to scale as per node update, thus putting it on par with alternative schemes, such as Belief Propagation (BP), without resorting to approximations. Two special cases are of particular interest: binary synapses and ternary synapses with l0 regularization. The algorithm we present performs as well as BP on binary perceptron learning problems, and may be better suited to address the problem on fully-connected two-layer networks, since inherent symmetries in two layer networks are naturally broken using the MS approach.}, language = {en}, number = {8}, urldate = {2015-08-13}, journal = {J. Stat. Mech.}, author = {Baldassi, Carlo and Braunstein, Alfredo}, month = aug, year = {2015}, keywords = {cavity and replica method, computational neuroscience, learning theory, message-passing algorithms}, pages = {P08008}, file = {Full Text PDF:/home/ab/.mozilla/firefox/3nu0zcxd.default-1419871504027/zotero/storage/WZH6P9MM/Baldassi and Braunstein - 2015 - A Max-Sum algorithm for training discrete neural n.pdf:application/pdf;Snapshot:/home/ab/.mozilla/firefox/3nu0zcxd.default-1419871504027/zotero/storage/739GA6C4/P08008.html:text/html} } @incollection{baldassi_statistical_2015, series = {Lecture {Notes} in {Mathematics}}, title = {Statistical {Physics} and {Network} {Optimization} {Problems}}, copyright = {{\textcopyright}2015 Springer International Publishing Switzerland}, isbn = {978-3-319-16966-8 978-3-319-16967-5}, url = {http://link.springer.com/chapter/10.1007/978-3-319-16967-5_2}, language = {en}, number = {2141}, urldate = {2015-09-23}, booktitle = {Mathematical {Foundations} of {Complex} {Networked} {Information} {Systems}}, publisher = {Springer International Publishing}, author = {Baldassi, Carlo and Braunstein, Alfredo and Ramezanpour, Abolfazl and Zecchina, Riccardo}, editor = {Fagnani, Fabio and Fosson, Sophie M. and Ravazzi, Chiara}, year = {2015}, keywords = {Complex networks, Complex Systems, graph theory, Mathematical Applications in the Physical Sciences}, pages = {27--49}, file = {Full Text PDF:/home/ab/.mozilla/firefox/3nu0zcxd.default-1419871504027/zotero/storage/WKDCPKGI/Baldassi et al. - 2015 - Statistical Physics and Network Optimization Probl.pdf:application/pdf;Snapshot:/home/ab/.mozilla/firefox/3nu0zcxd.default-1419871504027/zotero/storage/3DV8MJ9B/978-3-319-16967-5_2.html:text/html} } @article{bradde_aligning_2010, title = {Aligning graphs and finding substructures by a cavity approach}, volume = {89}, issn = {0295-5075}, url = {http://iopscience.iop.org/0295-5075/89/3/37009}, doi = {10.1209/0295-5075/89/37009}, abstract = {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.}, language = {en}, number = {3}, urldate = {2013-08-11}, journal = {{EPL}}, author = {Bradde, S. and Braunstein, A. and Mahmoudi, H. and Tria, F. and Weigt, M. and Zecchina, R.}, month = feb, year = {2010}, pages = {37009}, file = {Full Text PDF:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/GHEMEWPH/Bradde et al. - 2010 - Aligning graphs and finding substructures by a cav.pdf:application/pdf;Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/W63S5FAJ/37009.html:text/html} } @incollection{bailly-bechet_prize-collecting_2009, series = {Lecture Notes in Computer Science}, title = {A Prize-Collecting Steiner Tree Approach for Transduction Network Inference}, copyright = {{\textcopyright}2009 Springer Berlin Heidelberg}, isbn = {978-3-642-03844-0, 978-3-642-03845-7}, url = {http://link.springer.com/chapter/10.1007/978-3-642-03845-7_6}, abstract = {Into the cell, information from the environment is mainly propagated via signaling pathways which form a transduction network. Here we propose a new algorithm to infer transduction networks from heterogeneous data, using both the protein interaction network and expression datasets. We formulate the inference problem as an optimization task, and develop a message-passing, probabilistic and distributed formalism to solve it. We apply our algorithm to the pheromone response in the baker{\textquoteright}s yeast S. cerevisiae. We are able to find the backbone of the known structure of the {MAPK} cascade of pheromone response, validating our algorithm. More importantly, we make biological predictions about some proteins whose role could be at the interface between pheromone response and other cellular functions.}, number = {5688}, urldate = {2013-09-19}, booktitle = {Computational Methods in Systems Biology}, publisher = {Springer Berlin Heidelberg}, author = {Bailly-Bechet, Marc and Braunstein, Alfredo and Zecchina, Riccardo}, editor = {Degano, Pierpaolo and Gorrieri, Roberto}, month = jan, year = {2009}, keywords = {Cell Biology, Computational {Biology/Bioinformatics}, Computation by Abstract Devices, Computer Appl. in Life Sciences, Numeric Computing, Simulation and Modeling}, pages = {83--95}, file = {Bailly-Bechet et al_2009_A Prize-Collecting Steiner Tree Approach for Transduction Network Inference.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/9NSFIHMU/Bailly-Bechet et al_2009_A Prize-Collecting Steiner Tree Approach for Transduction Network Inference.pdf:application/pdf;Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/7DGFFS9R/10.html:text/html} } @article{bayati_rigorous_2008, title = {A rigorous analysis of the cavity equations for the minimum spanning tree}, volume = {49}, url = {http://link.aip.org/link/?JMP/49/125206/1}, doi = {10.1063/1.2982805}, number = {12}, journal = {Journal of Mathematical Physics}, author = {Bayati, Mohsen and Braunstein, A. and Zecchina, Riccardo}, year = {2008}, note = {Cited by 0012}, keywords = {biocomp, networks, statphys, topology}, pages = {125206}, file = {Bayati et al_2008_A rigorous analysis of the cavity equations for the minimum spanning tree.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/F7QH3DBD/Bayati et al_2008_A rigorous analysis of the cavity equations for the minimum spanning tree.pdf:application/pdf} } @article{altarelli_bayesian_2014, title = {Bayesian Inference of Epidemics on Networks via Belief Propagation}, volume = {112}, url = {http://link.aps.org/doi/10.1103/PhysRevLett.112.118701}, doi = {10.1103/PhysRevLett.112.118701}, abstract = {We study several Bayesian inference problems for irreversible stochastic epidemic models on networks from a statistical physics viewpoint. We derive equations which allow us to accurately compute the posterior distribution of the time evolution of the state of each node given some observations. At difference with most existing methods, we allow very general observation models, including unobserved nodes, state observations made at different or unknown times, and observations of infection times, possibly mixed together. Our method, which is based on the belief propagation algorithm, is efficient, naturally distributed, and exact on trees. As a particular case, we consider the problem of finding the {\textquotedblleft}zero patient{\textquotedblright} of a susceptible-infected-recovered or susceptible-infected epidemic given a snapshot of the state of the network at a later unknown time. Numerical simulations show that our method outperforms previous ones on both synthetic and real networks, often by a very large margin.}, number = {11}, urldate = {2014-05-06}, journal = {Phys. Rev. Lett.}, author = {Altarelli, Fabrizio and Braunstein, Alfredo and {Dall{\textquoteright}Asta}, Luca and Lage-Castellanos, Alejandro and Zecchina, Riccardo}, month = mar, year = {2014}, pages = {118701}, file = {Altarelli et al_2014_Bayesian Inference of Epidemics on Networks via Belief Propagation.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/BX3T92EM/Altarelli et al_2014_Bayesian Inference of Epidemics on Networks via Belief Propagation.pdf:application/pdf;APS Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/ADTEJTC2/PhysRevLett.112.html:text/html} } @article{bailly-bechet_clustering_2009, title = {Clustering with shallow trees}, url = {http://www.iop.org/EJ/abstract/1742-5468/2009/12/P12010}, doi = {10.1088/1742-5468/2009/12/P12010}, abstract = {We propose a new method for obtaining hierarchical clustering based on the optimization of a cost function over trees of limited depth, and we derive a message-passing method that allows one to use it efficiently. The method and the associated algorithm can be interpreted as a natural interpolation between two well-known approaches, namely that of single linkage and the recently presented affinity propagation. We analyse using this general scheme three biological/medical structured data sets (human population based on genetic information, proteins based on sequences and verbal autopsies) and show that the interpolation technique provides new insight.}, journal = {Journal of Statistical Mechanics: Theory and Experiment}, author = {Bailly-Bechet, Marc and Bradde, Serena and Braunstein, Alfredo and Flaxman, Abraham and Foini, Laura and Zecchina, Riccardo}, month = dec, year = {2009}, note = {Cited by 0006}, keywords = {biocomp, optimization}, pages = {17pp}, file = {Bailly-Bechet et al_2009_Clustering with shallow trees.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/6IFQCM2I/Bailly-Bechet et al_2009_Clustering with shallow trees.pdf:application/pdf;Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/X5RDFSWC/P12010.html:text/html} } @article{braunstein_complexity_2002, title = {Complexity transitions in global algorithms for sparse linear systems over finite fields}, volume = {35}, issn = {0305-4470}, url = {http://iopscience.iop.org/0305-4470/35/35/301}, doi = {10.1088/0305-4470/35/35/301}, abstract = {We study the computational complexity of a very basic problem, namely that of finding solutions to a very large set of random linear equations in a finite Galois field modulo q. Using tools from statistical mechanics we are able to identify phase transitions in the structure of the solution space and to connect them to the changes in the performance of a global algorithm, namely Gaussian elimination. Crossing phase boundaries produces a dramatic increase in memory and {CPU} requirements necessary for the algorithms. In turn, this causes the saturation of the upper bounds for the running time. We illustrate the results on the specific problem of integer factorization, which is of central interest for deciphering messages encrypted with the {RSA} cryptosystem.}, language = {en}, number = {35}, urldate = {2013-09-19}, journal = {J. Phys. A: Math. Gen.}, author = {Braunstein, A. and Leone, M. and Ricci-Tersenghi, F. and Zecchina, R.}, month = sep, year = {2002}, pages = {7559}, file = {Braunstein et al_2002_Complexity transitions in global algorithms for sparse linear systems over.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/NKXVFGHI/Braunstein et al_2002_Complexity transitions in global algorithms for sparse linear systems over.pdf:application/pdf;Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/8Z3I26WQ/301.html:text/html} } @incollection{braunstein_constraint_2005, series = {Computational Complexity and Statistical Physics}, title = {Constraint satisfaction by survey propagation}, volume = {9}, url = {http://arxiv.org/abs/cond-mat/0212451}, booktitle = {Advances in Neural Information Processing Systems}, publisher = {Oxford University Press}, author = {Braunstein, Alfredo and M{\'e}zard, Marc and Weigt, Martin and Zecchina, Riccardo}, editor = {Percus, A. and Istrate, G. and Moore, C.}, year = {2005}, note = {Cited by 0031}, keywords = {biocomp, optimization, statphys}, pages = {424}, file = {Braunstein et al_2005_Constraint satisfaction by survey propagation.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/QHQM6Q2X/Braunstein et al_2005_Constraint satisfaction by survey propagation.pdf:application/pdf} } @article{altarelli_containing_2014, title = {Containing Epidemic Outbreaks by Message-Passing Techniques}, volume = {4}, url = {http://link.aps.org/doi/10.1103/PhysRevX.4.021024}, doi = {10.1103/PhysRevX.4.021024}, abstract = {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 on both random graphs and real-world networks.}, number = {2}, urldate = {2014-05-15}, journal = {Phys. Rev. X}, author = {Altarelli, F. and Braunstein, A. and {Dall{\textquoteright}Asta}, L. and Wakeling, J. R. and Zecchina, R.}, month = may, year = {2014}, pages = {021024}, file = {Altarelli et al_2014_Containing Epidemic Outbreaks by Message-Passing Techniques.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/JTVJD8Q5/Altarelli et al_2014_Containing Epidemic Outbreaks by Message-Passing Techniques.pdf:application/pdf;APS Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/AAA44FAZ/PhysRevX.4.html:text/html} } @article{braunstein_efficient_2011, title = {Efficient data compression from statistical physics of codes over finite fields}, volume = {84}, url = {http://link.aps.org/doi/10.1103/PhysRevE.84.051111}, doi = {10.1103/PhysRevE.84.051111}, abstract = {In this paper we discuss a novel data compression technique for binary symmetric sources based on the cavity method over {GF(q)}, the Galois Field of order q. We present a scheme of low complexity and near-optimal empirical performance. The compression step is based on a reduction of a sparse low-density parity-check code over {GF(q)} and is done through the so-called reinforced belief-propagation equations. These reduced codes appear to have a nontrivial geometrical modification of the space of codewords, which makes such compression computationally feasible. The computational complexity is O(dnqlog2q) per iteration, where d is the average degree of the check nodes and n is the number of bits. For our code ensemble, decompression can be done in a time linear in the code's length by a simple leaf-removal algorithm.}, number = {5}, urldate = {2013-09-19}, journal = {Phys. Rev. E}, author = {Braunstein, A. and Kayhan, F. and Zecchina, R.}, month = nov, year = {2011}, pages = {051111}, file = {APS Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/HIJ6Z7WK/e051111.html:text/html;Braunstein et al_2011_Efficient data compression from statistical physics of codes over finite fields.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/NQT9P4WZ/Braunstein et al_2011_Efficient data compression from statistical physics of codes over finite fields.pdf:application/pdf} } @inproceedings{braunstein_efficient_2009, address = {Seul, Korea}, title = {Efficient {LDPC} Codes over {GF(q)} for Lossy Data Compression}, url = {http://arxiv.org/abs/0901.4467}, abstract = {In this paper we consider the lossy compression of a binary symmetric source. We present a scheme that provides a low complexity lossy compressor with near optimal empirical performance. The proposed scheme is based on b-reduced ultra-sparse {LDPC} codes over {GF(q).} Encoding is performed by the Reinforced Belief Propagation algorithm, a variant of Belief Propagation. The computational complexity at the encoder is O(d.n.q.log q), where d is the average degree of the check nodes. For our code ensemble, decoding can be performed iteratively following the inverse steps of the leaf removal algorithm. For a sparse parity-check matrix the number of needed operations is O(n).}, booktitle = {{IEEE} International Symposium on Information Theory, 2009. {ISIT} 2009}, author = {Braunstein, Alfredo and Kayhan, Farbod and Zecchina, Riccardo}, year = {2009}, note = {Cited by 0008}, keywords = {biocomp, coding, optimization, statphys} } @article{baldassi_efficient_2007, title = {Efficient supervised learning in networks with binary synapses}, volume = {8}, issn = {1471-2202}, doi = {10.1186/1471-2202-8-S2-S13}, number = {Suppl 2}, journal = {{BMC} Neuroscience}, author = {Baldassi, Carlo and Braunstein, Alfredo and Brunel, Nicolas and Zecchina, Riccardo}, year = {2007}, keywords = {biocomp, networks, neuroscience, optimization, statphys}, pages = {S13}, file = {Baldassi et al_2007_Efficient supervised learning in networks with binary synapses.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/UI7F5SX4/Baldassi et al_2007_Efficient supervised learning in networks with binary synapses.pdf:application/pdf} } @article{baldassi_efficient_2007-1, title = {Efficient supervised learning in networks with binary synapses}, volume = {104}, issn = {0027-8424, 1091-6490}, url = {http://www.pnas.org/content/104/26/11079}, doi = {10.1073/pnas.0700324104}, abstract = {Recent experimental studies indicate that synaptic changes induced by neuronal activity are discrete jumps between a small number of stable states. Learning in systems with discrete synapses is known to be a computationally hard problem. Here, we study a neurobiologically plausible on-line learning algorithm that derives from belief propagation algorithms. We show that it performs remarkably well in a model neuron with binary synapses, and a finite number of {\textquotedblleft}hidden{\textquotedblright} states per synapse, that has to learn a random classification task. Such a system is able to learn a number of associations close to the theoretical limit in time that is sublinear in system size. This is to our knowledge the first on-line algorithm that is able to achieve efficiently a finite number of patterns learned per binary synapse. Furthermore, we show that performance is optimal for a finite number of hidden states that becomes very small for sparse coding. The algorithm is similar to the standard {\textquotedblleft}perceptron{\textquotedblright} learning algorithm, with an additional rule for synaptic transitions that occur only if a currently presented pattern is {\textquotedblleft}barely correct.{\textquotedblright} In this case, the synaptic changes are metaplastic only (change in hidden states and not in actual synaptic state), stabilizing the synapse in its current state. Finally, we show that a system with two visible states and K hidden states is much more robust to noise than a system with K visible states. We suggest that this rule is sufficiently simple to be easily implemented by neurobiological systems or in hardware.}, language = {en}, number = {26}, urldate = {2013-08-08}, journal = {{PNAS}}, author = {Baldassi, Carlo and Braunstein, Alfredo and Brunel, Nicolas and Zecchina, Riccardo}, month = jun, year = {2007}, note = {{PMID:} 17581884}, keywords = {belief propagation, computational neuroscience, perceptron, synaptic plasticity}, pages = {11079--11084}, file = {Full Text PDF:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/RV88P9T5/Baldassi et al. - 2007 - Efficient supervised learning in networks with bin.pdf:application/pdf;Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/NXKU6254/11079.html:text/html} } @article{braunstein_estimating_2008, title = {Estimating the size of the solution space of metabolic networks}, volume = {9}, copyright = {2008 Braunstein et al; licensee {BioMed} Central Ltd.}, issn = {1471-2105}, url = {http://www.biomedcentral.com/1471-2105/9/240/abstract}, doi = {10.1186/1471-2105-9-240}, abstract = {Cellular metabolism is one of the most investigated system of biological interactions. While the topological nature of individual reactions and pathways in the network is quite well understood there is still a lack of comprehension regarding the global functional behavior of the system. In the last few years flux-balance analysis ({FBA)} has been the most successful and widely used technique for studying metabolism at system level. This method strongly relies on the hypothesis that the organism maximizes an objective function. However only under very specific biological conditions (e.g. maximization of biomass for E. coli in reach nutrient medium) the cell seems to obey such optimization law. A more refined analysis not assuming extremization remains an elusive task for large metabolic systems due to algorithmic limitations.}, language = {en}, number = {1}, urldate = {2013-09-19}, journal = {{BMC} Bioinformatics}, author = {Braunstein, Alfredo and Mulet, Roberto and Pagnani, Andrea}, month = may, year = {2008}, note = {{PMID:} 18489757}, pages = {240}, file = {Braunstein et al_2008_Estimating the size of the solution space of metabolic networks.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/T2VJDWW7/Braunstein et al_2008_Estimating the size of the solution space of metabolic networks.pdf:application/pdf;Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/EWPJN3E7/240.html:text/html} } @inproceedings{battaglia_exact_2005, title = {Exact Probing of Glassy States by Survey Propagation}, volume = {157}, booktitle = {Prog. Theor. Phys. Suppl.}, author = {Battaglia, Demian and Braunstein, Alfredo and Chavas, Jo{\"e}l and Zecchina, Riccardo}, year = {2005}, note = {Cited by 0003}, keywords = {biocomp, optimization, statphys}, pages = {330{\textendash}337}, file = {Battaglia et al_2005_Exact Probing of Glassy States by Survey Propagation.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/EZN85RXW/Battaglia et al_2005_Exact Probing of Glassy States by Survey Propagation.pdf:application/pdf} } @article{bailly-bechet_finding_2011, title = {Finding undetected protein associations in cell signaling by belief propagation}, volume = {108}, issn = {0027-8424, 1091-6490}, url = {http://www.pnas.org/content/108/2/882}, doi = {10.1073/pnas.1004751108}, abstract = {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{\textendash}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.}, number = {2}, urldate = {2013-09-10}, journal = {{PNAS}}, author = {Bailly-Bechet, M. and Borgs, C. and Braunstein, A. and Chayes, J. and Dagkessamanskaia, A. and Fran{\c c}ois, J.-M. and Zecchina, R.}, month = jan, year = {2011}, note = {{PMID:} 21187432}, keywords = {biocomp, computational biology, minimum Steiner tree, prize-collecting Steiner tree}, pages = {882--887}, file = {Bailly-Bechet et al_2011_Finding undetected protein associations in cell signaling by belief propagation.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/BQ4IZI72/Bailly-Bechet et al_2011_Finding undetected protein associations in cell signaling by belief propagation.pdf:application/pdf;Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/AKEEIUSE/882.html:text/html} } @article{braunstein_gene-network_2008, title = {Gene-network inference by message passing}, volume = {95}, issn = {1742-6596}, url = {http://iopscience.iop.org/1742-6596/95/1/012016}, doi = {10.1088/1742-6596/95/1/012016}, abstract = {The inference of gene-regulatory processes from gene-expression data belongs to the major challenges of computational systems biology. Here we address the problem from a statistical-physics perspective and develop a message-passing algorithm which is able to infer sparse, directed and combinatorial regulatory mechanisms. Using the replica technique, the algorithmic performance can be characterized analytically for artificially generated data. The algorithm is applied to genome-wide expression data of baker's yeast under various environmental conditions. We find clear cases of combinatorial control, and enrichment in common functional annotations of regulated genes and their regulators.}, language = {en}, number = {1}, urldate = {2014-05-06}, journal = {J. Phys.: Conf. Ser.}, author = {Braunstein, A. and Pagnani, A. and Weigt, M. and Zecchina, R.}, month = jan, year = {2008}, pages = {012016}, file = {Braunstein et al_2008_Gene-network inference by message passing.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/8UB4IIWW/Braunstein et al_2008_Gene-network inference by message passing.pdf:application/pdf;Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/7TURG7UI/012016.html:text/html} } @article{braunstein_inference_2008, title = {Inference algorithms for gene networks: a statistical mechanics analysis}, volume = {2008}, issn = {1742-5468}, shorttitle = {Inference algorithms for gene networks}, url = {http://iopscience.iop.org/1742-5468/2008/12/P12001}, doi = {10.1088/1742-5468/2008/12/P12001}, abstract = {The inference of gene regulatory networks from high throughput gene expression data is one of the major challenges in systems biology. This paper aims at analysing and comparing two different algorithmic approaches. The first approach uses pairwise correlations between regulated and regulating genes; the second one uses message-passing techniques for inferring activating and inhibiting regulatory interactions. The performance of these two algorithms can be analysed theoretically on well-defined test sets, using tools from the statistical physics of disordered systems like the replica method. We find that the second algorithm outperforms the first one since it takes into account collective effects of multiple regulators.}, language = {en}, number = {12}, urldate = {2013-09-19}, journal = {J. Stat. Mech.}, author = {Braunstein, A. and Pagnani, A. and Weigt, M. and Zecchina, R.}, month = dec, year = {2008}, keywords = {cavity and replica method, genomic and proteomic networks, message-passing algorithms, regulatory networks (theory)}, pages = {P12001}, file = {Braunstein et al_2008_Inference algorithms for gene networks.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/NQZUJFJV/Braunstein et al_2008_Inference algorithms for gene networks.pdf:application/pdf;Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/Z2V39SEM/P12001.html:text/html} } @article{braunstein_inference_2011, title = {Inference and learning in sparse systems with multiple states}, volume = {83}, url = {http://link.aps.org/doi/10.1103/PhysRevE.83.056114}, doi = {10.1103/PhysRevE.83.056114}, abstract = {We discuss how inference can be performed when data are sampled from the nonergodic phase of systems with multiple attractors. We take as a 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.}, number = {5}, urldate = {2013-09-19}, journal = {Phys. Rev. E}, author = {Braunstein, A. and Ramezanpour, A. and Zecchina, R. and Zhang, P.}, month = may, year = {2011}, pages = {056114}, file = {APS Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/CBIGN4ZP/e056114.html:text/html;Braunstein et al_2011_Inference and learning in sparse systems with multiple states.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/NXNWX6NK/Braunstein et al_2011_Inference and learning in sparse systems with multiple states.pdf:application/pdf} } @article{bailly-bechet_inference_2010, title = {Inference of sparse combinatorial-control networks from gene-expression data: a message passing approach}, volume = {11}, copyright = {2010 Bailly-Bechet et al; licensee {BioMed} Central Ltd.}, issn = {1471-2105}, shorttitle = {Inference of sparse combinatorial-control networks from gene-expression data}, url = {http://www.biomedcentral.com/1471-2105/11/355/abstract}, doi = {10.1186/1471-2105-11-355}, abstract = {Transcriptional gene regulation is one of the most important mechanisms in controlling many essential cellular processes, including cell development, cell-cycle control, and the cellular response to variations in environmental conditions. Genes are regulated by transcription factors and other genes/proteins via a complex interconnection network. Such regulatory links may be predicted using microarray expression data, but most regulation models suppose transcription factor independence, which leads to spurious links when many genes have highly correlated expression levels.}, language = {en}, number = {1}, urldate = {2013-09-19}, journal = {{BMC} Bioinformatics}, author = {Bailly-Bechet, Marc and Braunstein, Alfredo and Pagnani, Andrea and Weigt, Martin and Zecchina, Riccardo}, month = jun, year = {2010}, note = {{PMID:} 20587029}, pages = {355}, file = {Bailly-Bechet et al_2010_Inference of sparse combinatorial-control networks from gene-expression data.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/8CXPRUDP/Bailly-Bechet et al_2010_Inference of sparse combinatorial-control networks from gene-expression data.pdf:application/pdf;Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/DEDNI77Z/355.html:text/html} } @article{alemi-neissi_information_2012, title = {Information theoretic and machine learning approaches to quantify non-linear visual feature interaction underlying visual object recognition}, volume = {13}, url = {http://dx.doi.org/10.1186/1471-2202-13-S1-P2}, doi = {10.1186/1471-2202-13-S1-P2}, journal = {{BMC} Neuroscience}, author = {Alemi-Neissi, Alireza and Baldassi, Carlo and Braunstein, Alfredo and Pagnani, Andrea and Zecchina, Riccardo and Zoccolan, Davide}, year = {2012}, note = {Cited by 0000}, keywords = {Animal Models, biocomp, Neurobiology, neuroscience, Neurosciences}, pages = {1--2}, file = {Alemi-Neissi et al_2012_Information theoretic and machine learning approaches to quantify non-linear.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/A2F4CZ3F/Alemi-Neissi et al_2012_Information theoretic and machine learning approaches to quantify non-linear.pdf:application/pdf;Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/DXJCECNR/10.html:text/html} } @article{altarelli_large_2013, title = {Large deviations of cascade processes on graphs}, volume = {87}, url = {http://link.aps.org/doi/10.1103/PhysRevE.87.062115}, doi = {10.1103/PhysRevE.87.062115}, abstract = {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 nontypical trajectories, which can be crucial for the understanding of 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.}, number = {6}, urldate = {2013-06-15}, journal = {Phys. Rev. E}, author = {Altarelli, Fabrizio and Braunstein, Alfredo and {Dall'Asta}, Luca and Zecchina, Riccardo}, month = jun, year = {2013}, keywords = {Condensed Matter - Disordered Systems and Neural Networks, Condensed Matter - Statistical Mechanics}, pages = {062115}, file = {1305.5745 PDF:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/TFXIKV7U/Altarelli et al. - 2013 - Large deviations of cascade processes on graphs.pdf:application/pdf;APS Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/XNJDX2P6/e062115.html:text/html;APS Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/PGGHTSDH/e062115.html:text/html;arXiv.org Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/5U4X7264/1305.html:text/html;e062115.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/NJGSGUMP/e062115.pdf:application/pdf} } @article{braunstein_learning_2006, title = {Learning by Message Passing in Networks of Discrete Synapses}, volume = {96}, url = {http://link.aps.org/doi/10.1103/PhysRevLett.96.030201}, doi = {10.1103/PhysRevLett.96.030201}, abstract = {We show that a message-passing process allows us to store in binary {\textquotedblleft}material{\textquotedblright} synapses a number of random patterns which almost saturate the information theoretic bounds. We apply the learning algorithm to networks characterized by a wide range of different connection topologies and of size comparable with that of biological systems (e.g., n?105{\textendash}106). The algorithm can be turned into an online{\textemdash}fault tolerant{\textemdash}learning protocol of potential interest in modeling aspects of synaptic plasticity and in building neuromorphic devices.}, number = {3}, urldate = {2013-09-19}, journal = {Phys. Rev. Lett.}, author = {Braunstein, Alfredo and Zecchina, Riccardo}, month = jan, year = {2006}, pages = {030201}, file = {APS Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/BVRA9I5Q/e030201.html:text/html;Braunstein_Zecchina_2006_Learning by Message Passing in Networks of Discrete Synapses.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/DTQ6ZMTB/Braunstein_Zecchina_2006_Learning by Message Passing in Networks of Discrete Synapses.pdf:application/pdf} } @article{altarelli_optimizing_2013, title = {Optimizing spread dynamics on graphs by message passing}, volume = {2013}, issn = {1742-5468}, url = {http://iopscience.iop.org/1742-5468/2013/09/P09011}, doi = {10.1088/1742-5468/2013/09/P09011}, abstract = {Cascade processes are responsible for many important phenomena in natural and social sciences. Simple models of irreversible dynamics on graphs, in which nodes activate depending on the state of their neighbors, have been successfully applied to describe cascades in a large variety of contexts. Over the past decades, much effort has been devoted to understanding the typical behavior of the cascades arising from initial conditions extracted at random from some given ensemble. However, the problem of optimizing the trajectory of the system, i.e. of identifying appropriate initial conditions to maximize (or minimize) the final number of active nodes, is still considered to be practically intractable, with the only exception being models that satisfy a sort of diminishing returns property called submodularity. Submodular models can be approximately solved by means of greedy strategies, but by definition they lack cooperative characteristics which are fundamental in many real systems. Here we introduce an efficient algorithm based on statistical physics for the optimization of trajectories in cascade processes on graphs. We show that for a wide class of irreversible dynamics, even in the absence of submodularity, the spread optimization problem can be solved efficiently on large networks. Analytic and algorithmic results on random graphs are complemented by the solution of the spread maximization problem on a real-world network (the Epinions consumer reviews network).}, number = {09}, urldate = {2013-09-13}, journal = {J. Stat. Mech.}, author = {Altarelli, F. and Braunstein, A. and {Dall{\textquoteright}Asta}, L. and Zecchina, R.}, month = sep, year = {2013}, keywords = {message-passing algorithms, network dynamics, optimization over networks}, pages = {P09011}, file = {Altarelli et al_2013_Optimizing spread dynamics on graphs by message passing.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/HASQ8PQZ/Altarelli et al_2013_Optimizing spread dynamics on graphs by message passing.pdf:application/pdf;arXiv.org Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/7G4TWSCX/1203.html:text/html;Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/5R9HW7R3/P09011.html:text/html} } @article{biazzo_performance_2012, title = {Performance of a cavity-method-based algorithm for the prize-collecting Steiner tree problem on graphs}, volume = {86}, url = {http://link.aps.org/doi/10.1103/PhysRevE.86.026706}, doi = {10.1103/PhysRevE.86.026706}, journal = {Phys. Rev. E}, author = {Biazzo, Indaco and Braunstein, Alfredo and Zecchina, Riccardo}, month = aug, year = {2012}, pages = {026706}, file = {Biazzo et al_2012_Performance of a cavity-method-based algorithm for the prize-collecting Steiner.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/MCJ8488R/Biazzo et al_2012_Performance of a cavity-method-based algorithm for the prize-collecting Steiner.pdf:application/pdf} } @article{braunstein_polynomial_2003, title = {Polynomial iterative algorithms for coloring and analyzing random graphs}, volume = {68}, url = {http://link.aps.org/doi/10.1103/PhysRevE.68.036702}, doi = {10.1103/PhysRevE.68.036702}, abstract = {We study the graph coloring problem over random graphs of finite average connectivity c. Given a number q of available colors, we find that graphs with low connectivity admit almost always a proper coloring whereas graphs with high connectivity are uncolorable. Depending on q, we find with a one-step replica-symmetry breaking approximation the precise value of the critical average connectivity cq. Moreover, we show that below cq there exists a clustering phase c?[cd,cq] in which ground states spontaneously divide into an exponential number of clusters. Furthermore, we extended our considerations to the case of single instances showing consistent results. This leads us to propose a different algorithm that is able to color in polynomial time random graphs in the hard but colorable region, i.e., when c?[cd,cq].}, number = {3}, urldate = {2013-09-19}, journal = {Phys. Rev. E}, author = {Braunstein, A. and Mulet, R. and Pagnani, A. and Weigt, M. and Zecchina, R.}, month = sep, year = {2003}, pages = {036702}, file = {APS Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/7BBPRAWN/e036702.html:text/html;Braunstein et al_2003_Polynomial iterative algorithms for coloring and analyzing random graphs.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/8NFXDDCZ/Braunstein et al_2003_Polynomial iterative algorithms for coloring and analyzing random graphs.pdf:application/pdf} } @incollection{tuncbag_simultaneous_2012, series = {Lecture Notes in Computer Science}, title = {Simultaneous Reconstruction of Multiple Signaling Pathways via the Prize-Collecting Steiner Forest Problem}, volume = {7262}, isbn = {978-3-642-29626-0}, url = {http://dx.doi.org/10.1007/978-3-642-29627-7_31}, booktitle = {Research in Computational Molecular Biology}, publisher = {Springer Berlin Heidelberg}, author = {Tuncbag, Nurcan and Braunstein, Alfredo and Pagnani, Andrea and Huang, Shao-{ShanCarol} and Chayes, Jennifer and Borgs, Christian and Zecchina, Riccardo and Fraenkel, Ernest}, editor = {Chor, Benny}, year = {2012}, note = {Cited by 0002}, keywords = {multiple network reconstruction, Prize-collecting Steiner forest, signaling pathways}, pages = {287--301}, file = {Tuncbag et al_2012_Simultaneous Reconstruction of Multiple Signaling Pathways via the.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/PTDEC3EE/Tuncbag et al_2012_Simultaneous Reconstruction of Multiple Signaling Pathways via the.pdf:application/pdf} } @article{battaglia_source_2005, title = {Source coding by efficient selection of ground-state clusters}, volume = {72}, url = {http://link.aps.org/doi/10.1103/PhysRevE.72.015103}, doi = {10.1103/PhysRevE.72.015103}, abstract = {We analyze the geometrical structure of clusters of ground states which appear in many frustrated systems over random graphs. Focusing on the regime of connectivities where the number of clusters is exponential in the size of the problems, we identify an appropriate generalization of the survey propagation equations efficiently exploring the geometry. The possibility of selecting different clusters has also computational consequences. As a proof of concept here we show how a well-known physical system can be used to perform nontrivial data compression, for which we introduce a unique compression scheme. Performances are optimized when the number of well-separated clusters is maximal in the underlying physical model.}, number = {1}, urldate = {2014-05-06}, journal = {Phys. Rev. E}, author = {Battaglia, Demian and Braunstein, Alfredo and Chavas, Jo{\"e}l and Zecchina, Riccardo}, month = jul, year = {2005}, pages = {015103}, file = {APS Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/AIKVIUW7/PhysRevE.72.html:text/html;Battaglia et al_2005_Source coding by efficient selection of ground-state clusters.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/ZEX67UTU/Battaglia et al_2005_Source coding by efficient selection of ground-state clusters.pdf:application/pdf} } @article{altarelli_statistical_2009, title = {Statistical mechanics of budget-constrained auctions}, volume = {2009}, issn = {1742-5468}, url = {http://iopscience.iop.org/1742-5468/2009/07/P07002}, doi = {10.1088/1742-5468/2009/07/P07002}, abstract = {Finding the optimal assignment in budget-constrained auctions is a combinatorial optimization problem with many important applications, a notable example being in the sale of advertisement space by search engines (in this context the problem is often referred to as the off-line {AdWords} problem). On the basis of 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.}, language = {en}, number = {07}, urldate = {2013-09-19}, journal = {J. Stat. Mech.}, author = {Altarelli, F. and Braunstein, A. and Realpe-Gomez, J. and Zecchina, R.}, month = jul, year = {2009}, keywords = {applications to game theory and mathematical economics, cavity and replica method, message-passing algorithms}, pages = {P07002}, file = {Altarelli et al_2009_Statistical mechanics of budget-constrained auctions.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/TRNCZICV/Altarelli et al_2009_Statistical mechanics of budget-constrained auctions.pdf:application/pdf;Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/5XMM3K52/P07002.html:text/html} } @article{bayati_statistical_2008, title = {Statistical Mechanics of Steiner Trees}, volume = {101}, url = {http://link.aps.org/doi/10.1103/PhysRevLett.101.037208}, doi = {10.1103/PhysRevLett.101.037208}, abstract = {The minimum weight Steiner tree ({MST)} is an important combinatorial optimization problem over networks that has applications in a wide range of fields. Here we discuss a general technique to translate the imposed global connectivity constrain into many local ones that can be analyzed with cavity equation techniques. This approach leads to a new optimization algorithm for {MST} and allows us to analyze the statistical mechanics properties of {MST} on random graphs of various types.}, number = {3}, urldate = {2013-09-10}, journal = {Phys. Rev. Lett.}, author = {Bayati, M. and Borgs, C. and Braunstein, A. and Chayes, J. and Ramezanpour, A. and Zecchina, R.}, month = jul, year = {2008}, keywords = {biocomp, networks, optimization, statphys}, pages = {037208}, file = {APS Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/CGAM93RC/e037208.html:text/html;APS Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/SUPWGRB9/e037208.html:text/html;Bayati et al_2008_Statistical Mechanics of Steiner Trees.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/FEXIQMEE/Bayati et al_2008_Statistical Mechanics of Steiner Trees.pdf:application/pdf} } @article{altarelli_stochastic_2011, title = {Stochastic Matching Problem}, volume = {106}, url = {http://link.aps.org/doi/10.1103/PhysRevLett.106.190601}, doi = {10.1103/PhysRevLett.106.190601}, abstract = {The matching problem plays a basic role in combinatorial optimization and in statistical mechanics. In its stochastic variants, optimization decisions have to be taken given only some probabilistic information about the instance. While the deterministic case can be solved in polynomial time, stochastic variants are worst-case intractable. We propose an efficient method to solve stochastic matching problems which combines some features of the survey propagation equations and of the cavity method. We test it on random bipartite graphs, for which we analyze the phase diagram and compare the results with exact bounds. Our approach is shown numerically to be effective on the full range of parameters, and to outperform state-of-the-art methods. Finally we discuss how the method can be generalized to other problems of optimization under uncertainty.}, number = {19}, urldate = {2014-05-06}, journal = {Phys. Rev. Lett.}, author = {Altarelli, F. and Braunstein, A. and Ramezanpour, A. and Zecchina, R.}, month = may, year = {2011}, pages = {190601}, file = {Altarelli et al_2011_Stochastic Matching Problem.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/NKUWPNUN/Altarelli et al_2011_Stochastic Matching Problem.pdf:application/pdf;APS Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/JC4V67CR/PhysRevLett.106.html:text/html} } @article{altarelli_stochastic_2011-1, title = {Stochastic optimization by message passing}, volume = {2011}, issn = {1742-5468}, url = {http://iopscience.iop.org/1742-5468/2011/11/P11009}, doi = {10.1088/1742-5468/2011/11/P11009}, abstract = {Most optimization problems in applied sciences realistically involve uncertainty in the parameters defining the cost function, of which only statistical information is known beforehand. Here we provide an in-depth discussion of how message passing algorithms for stochastic optimization based on the cavity method of statistical physics can be constructed. We focus on two basic problems, namely the independent set problem and the matching problem, for which we display the general method and caveats for the case of the so called two-stage problem with independently distributed stochastic parameters. We compare the results with some greedy algorithms and briefly discuss the extension to more complicated stochastic multi-stage problems.}, number = {11}, urldate = {2013-09-10}, journal = {J. Stat. Mech.}, author = {Altarelli, F. and Braunstein, A. and Ramezanpour, A. and Zecchina, R.}, month = nov, year = {2011}, keywords = {error correcting codes, message-passing algorithms, networks, random graphs, source and channel coding}, pages = {P11009}, file = {Altarelli et al_2011_Stochastic optimization by message passing.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/T59PSAM7/Altarelli et al_2011_Stochastic optimization by message passing.pdf:application/pdf;Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/78755NPW/P11009.html:text/html} } @inproceedings{leonardi_stochastic_2013, address = {Budapest (Hungary)}, title = {Stochastic Optimization of Service Provision with Selfish Users}, url = {http://porto.polito.it/2506220/}, urldate = {2013-09-12}, publisher = {{IEEE} / Institute of Electrical and Electronics Engineers Incorporated:445 Hoes {Lane:Piscataway}, {NJ} 08854}, author = {Leonardi, Emilio and {Dall'Asta}, Luca and Chiasserini, Carla Fabiana and Giaccone, Paolo and Braunstein, Alfredo and Zecchina, Riccardo and Altarelli, Fabrizio}, month = feb, year = {2013}, file = {Leonardi et al_2013_Stochastic Optimization of Service Provision with Selfish Users.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/Z58USIP8/Leonardi et al_2013_Stochastic Optimization of Service Provision with Selfish Users.pdf:application/pdf;Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/HF4AU3WH/2506220.html:text/html} } @incollection{braunstein_survey_2004, series = {Lecture Notes in Computer Science}, title = {Survey and Belief Propagation on Random K-{SAT}}, copyright = {{\textcopyright}2004 Springer-Verlag Berlin Heidelberg}, isbn = {978-3-540-20851-8, 978-3-540-24605-3}, url = {http://link.springer.com/chapter/10.1007/978-3-540-24605-3_38}, abstract = {Survey Propagation ({SP)} is a message passing algorithm that can be viewed as a generalization of the so called Belief Propagation ({BP)} algorithm used in statistical inference and error correcting codes. In this work we discuss the connections between {BP} and {SP.}}, number = {2919}, urldate = {2014-05-06}, booktitle = {Theory and Applications of Satisfiability Testing}, publisher = {Springer Berlin Heidelberg}, author = {Braunstein, Alfredo and Zecchina, Riccardo}, editor = {Giunchiglia, Enrico and Tacchella, Armando}, month = jan, year = {2004}, keywords = {Algorithm Analysis and Problem Complexity, Artificial Intelligence (incl. Robotics), Mathematical Logic and Formal Languages, Mathematical Logic and Foundations, Numeric Computing}, pages = {519--528}, file = {Braunstein_Zecchina_2004_Survey and Belief Propagation on Random K-SAT.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/TUSB7NC9/Braunstein_Zecchina_2004_Survey and Belief Propagation on Random K-SAT.pdf:application/pdf;Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/J2T666VD/10.html:text/html} } @article{braunstein_survey_2005, title = {Survey Propagation: an algorithm for satisfiability}, volume = {27}, url = {http://arxiv.org/abs/cs/0212002}, abstract = {We study the satisfiability of randomly generated formulas formed by {\$M\$} clauses of exactly {\$K\$} literals over {\$N\$} Boolean variables. For a given value of {\$N\$} the problem is known to be most difficult with \${\textbackslash}{alpha=M/N\$} close to the experimental threshold \${\textbackslash}alpha\_c\$ separating the region where almost all formulas are {SAT} from the region where all formulas are {UNSAT.} Recent results from a statistical physics analysis suggest that the difficulty is related to the existence of a clustering phenomenon of the solutions when \${\textbackslash}alpha\$ is close to (but smaller than) \${\textbackslash}alpha\_c\$. We introduce a new type of message passing algorithm which allows to find efficiently a satisfiable assignment of the variables in the difficult region. This algorithm is iterative and composed of two main parts. The first is a message-passing procedure which generalizes the usual methods like Sum-Product or Belief Propagation: it passes messages that are surveys over clusters of the ordinary messages. The second part uses the detailed probabilistic information obtained from the surveys in order to fix variables and simplify the problem. Eventually, the simplified problem that remains is solved by a conventional heuristic.}, journal = {Random Structures Algorithms}, author = {Braunstein, Alfredo and M{\'e}zard, Marc and Zecchina, Riccardo}, year = {2005}, keywords = {Computer Science - Computational Complexity, Condensed Matter - Statistical Mechanics, G.3, optimization, statphys}, pages = {201--226}, file = {arXiv.org Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/2DWXREU7/0212002.html:text/html;Braunstein et al_2002_Survey propagation.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/TGP57INU/Braunstein et al_2002_Survey propagation.pdf:application/pdf;Braunstein et al. - 2005 - Survey Propagation an algorithm for satisfiabilit.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/72524ZN3/Braunstein et al. - 2005 - Survey Propagation an algorithm for satisfiabilit.pdf:application/pdf} } @article{braunstein_survey_2004-1, title = {Survey propagation as local equilibrium equations}, volume = {2004}, issn = {1742-5468}, url = {http://iopscience.iop.org/1742-5468/2004/06/P06007}, doi = {10.1088/1742-5468/2004/06/P06007}, abstract = {It has been shown experimentally that a decimation algorithm based on survey propagation ({SP)} equations allows one to solve efficiently some combinatorial problems over random graphs. We show that these equations can be derived as sum{\textendash}product equations for the computation of marginals in an extended space where the variables are allowed to take an additional value{\textemdash}*{\textemdash}when they are not forced by the combinatorial constraints. An appropriate 'local equilibrium condition' cost/energy function is introduced and its entropy is shown to coincide with the expected logarithm of the number of clusters of solutions as computed by {SP.} These results may help to clarify the geometrical notion of clusters assumed by {SP} for random K-{SAT} or random graph colouring (where it is conjectured to be exact) and help to explain which kind of clustering operation or approximation is enforced in general/small sized models in which it is known to be inexact.}, language = {en}, number = {06}, urldate = {2013-09-19}, journal = {J. Stat. Mech.}, author = {Braunstein, Alfredo and Zecchina, Riccardo}, month = jun, year = {2004}, keywords = {cavity and replica method, message-passing algorithms, source and channel coding}, pages = {P06007}, file = {Braunstein_Zecchina_2004_Survey propagation as local equilibrium equations.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/S3ZX886C/Braunstein_Zecchina_2004_Survey propagation as local equilibrium equations.pdf:application/pdf;Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/MGWWAD8N/P06007.html:text/html} } @article{baldassi_theory_2013, title = {Theory and learning protocols for the material tempotron model}, volume = {2013}, issn = {1742-5468}, url = {http://iopscience.iop.org/1742-5468/2013/12/P12013}, doi = {10.1088/1742-5468/2013/12/P12013}, abstract = {Neural networks are able to extract information from the timing of spikes. Here we provide new results on the behavior of the simplest neuronal model which is able to decode information embedded in temporal spike patterns, the so-called tempotron. Using statistical physics techniques we compute the capacity for the case of sparse, time-discretized input, and {\textquoteleft}material{\textquoteright} discrete synapses, showing that the device saturates the information theoretic bounds with a statistics of output spikes that is consistent with the statistics of the inputs. We also derive two simple and highly efficient learning algorithms which are able to learn a number of associations which are close to the theoretical limit. The simplest versions of these algorithms correspond to distributed online protocols of interest for neuromorphic devices, and can be adapted to address the more biologically relevant continuous-time version of the classification problem, hopefully allowing the understanding of some aspects of synaptic plasticity.}, language = {en}, number = {12}, urldate = {2014-01-13}, journal = {J. Stat. Mech.}, author = {Baldassi, Carlo and Braunstein, Alfredo and Zecchina, Riccardo}, month = dec, year = {2013}, keywords = {computational neuroscience, learning theory, message-passing algorithms, neural code}, pages = {P12013}, file = {Baldassi et al_2013_Theory and learning protocols for the material tempotron model.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/T7KNAG9G/Baldassi et al_2013_Theory and learning protocols for the material tempotron model.pdf:application/pdf;Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/G4MSSC2C/P12013.html:text/html} } @article{braunstein_space_2008, title = {The space of feasible solutions in metabolic networks}, volume = {95}, issn = {1742-6596}, url = {http://iopscience.iop.org/1742-6596/95/1/012017}, doi = {10.1088/1742-6596/95/1/012017}, abstract = {In this work we propose a novel algorithmic strategy that allows for an efficient characterization of the whole set of stable fluxes compatible with the metabolic constraints. The algorithm, based on the well-known Bethe approximation, allows the computation in polynomial time of the volume of a non full-dimensional convex polytope in high dimensions. The result of our algorithm match closely the prediction of Monte Carlo based estimations of the flux distributions of the Red Blood Cell metabolic network but in incomparably shorter time. We also analyze the statistical properties of the average fluxes of the reactions in the E-Coli metabolic network and finally to test the effect of flux knock-outs on the size of the solution space of the E-Coli central metabolism.}, language = {en}, number = {1}, urldate = {2014-05-06}, journal = {J. Phys.: Conf. Ser.}, author = {Braunstein, A. and Mulet, R. and Pagnani, A.}, month = jan, year = {2008}, pages = {012017}, file = {Braunstein et al_2008_The space of feasible solutions in metabolic networks.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/JMN4EM3W/Braunstein et al_2008_The space of feasible solutions in metabolic networks.pdf:application/pdf;Snapshot:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/RV8WMKAD/012017.html:text/html} } @article{molinelli_perturbation_2013, title = {Perturbation Biology: Inferring Signaling Networks in Cellular Systems}, volume = {9}, shorttitle = {Perturbation Biology}, url = {http://dx.doi.org/10.1371/journal.pcbi.1003290}, doi = {10.1371/journal.pcbi.1003290}, abstract = {Author {SummaryDrugs} that target specific effects of signaling proteins are promising agents for treating cancer. One of the many obstacles facing optimal drug design is inadequate quantitative understanding of the coordinated interactions between signaling proteins. De novo model inference of network or pathway models refers to the algorithmic construction of mathematical predictive models from experimental data without dependence on prior knowledge. De novo inference is difficult because of the prohibitively large number of possible sets of interactions that may or may not be consistent with observations. Our new method overcomes this difficulty by adapting a method from statistical physics, called Belief Propagation, which first calculates probabilistically the most likely interactions in the vast space of all possible solutions, then derives a set of individual, highly probable solutions in the form of executable models. In this paper, we test this method on artificial data and then apply it to model signaling pathways in a {BRAF}-mutant melanoma cancer cell line based on a large set of rich output measurements from a systematic set of perturbation experiments using drug combinations. Our results are in agreement with established biological knowledge, predict novel interactions, and predict efficacious drug targets that are specific to the experimental cell line and potentially to related tumors. The method has the potential, with sufficient systematic perturbation data, to model, de novo and quantitatively, the effects of hundreds of proteins on cellular responses, on a scale that is currently unreachable in diverse areas of cell biology. In a disease context, the method is applicable to the computational design of novel combination drug treatments.}, number = {12}, urldate = {2014-10-01}, journal = {{PLoS} Comput Biol}, author = {Molinelli, Evan J. and Korkut, Anil and Wang, Weiqing and Miller, Martin L. and Gauthier, Nicholas P. and Jing, Xiaohong and Kaushik, Poorvi and He, Qin and Mills, Gordon and Solit, David B. and Pratilas, Christine A. and Weigt, Martin and Braunstein, Alfredo and Pagnani, Andrea and Zecchina, Riccardo and Sander, Chris}, month = dec, year = {2013}, pages = {e1003290}, file = {PLoS Snapshot:/home/ab/.mozilla/firefox/6bl4zn6g.default/zotero/storage/39EX26D5/infodoi10.1371journal.pcbi.html:text/html} } @article{altarelli_patient-zero_2014, title = {The patient-zero problem with noisy observations}, volume = {2014}, issn = {1742-5468}, url = {http://iopscience.iop.org/1742-5468/2014/10/P10016}, doi = {10.1088/1742-5468/2014/10/P10016}, abstract = {A belief propagation approach has been recently proposed for the patient-zero problem in {SIR} epidemics. The patient-zero problem consists of finding the initial source of an epidemic outbreak given observations at a later time. In this work, we study a more difficult but related inference problem, in which observations are noisy and there is confusion between observed states. In addition to studying the patient-zero problem, we also tackle the problem of completing and correcting the observations to possibly find undiscovered infected individuals and false test results.Moreover, we devise a set of equations, based on the variational expression of the Bethe free energy, to find the patient-zero along with maximum-likelihood epidemic parameters. We show, by means of simulated epidemics, that this method is able to infer details on the past history of an epidemic outbreak based solely on the topology of the contact network and a single snapshot of partial and noisy observations.}, language = {en}, number = {10}, urldate = {2014-10-13}, journal = {Journal of Statistical Mechanics: Theory and Experiment}, author = {Altarelli, Fabrizio and Braunstein, Alfredo and Dall{\textquoteright}Asta, Luca and Ingrosso, Alessandro and Zecchina, Riccardo}, month = oct, year = {2014}, keywords = {message-passing algorithms, network dynamics, statistical inference}, pages = {P10016}, file = {Full Text PDF:/home/ab/.mozilla/firefox/6bl4zn6g.default/zotero/storage/TUEIC65I/Altarelli et al. - 2014 - The patient-zero problem with noisy observations.pdf:application/pdf;Snapshot:/home/ab/.mozilla/firefox/6bl4zn6g.default/zotero/storage/RIHAMI8M/P10016.html:text/html} } @article{altarelli_edge-disjoint_2015, title = {The {Edge}-{Disjoint} {Path} {Problem} on {Random} {Graphs} by {Message}-{Passing}}, volume = {10}, url = {http://dx.doi.org/10.1371/journal.pone.0145222}, doi = {10.1371/journal.pone.0145222}, abstract = {We present a message-passing algorithm to solve a series of edge-disjoint path problems on graphs based on the zero-temperature cavity equations. Edge-disjoint paths problems are important in the general context of routing, that can be defined by incorporating under a unique framework both traffic optimization and total path length minimization. The computation of the cavity equations can be performed efficiently by exploiting a mapping of a generalized edge-disjoint path problem on a star graph onto a weighted maximum matching problem. We perform extensive numerical simulations on random graphs of various types to test the performance both in terms of path length minimization and maximization of the number of accommodated paths. In addition, we test the performance on benchmark instances on various graphs by comparison with state-of-the-art algorithms and results found in the literature. Our message-passing algorithm always outperforms the others in terms of the number of accommodated paths when considering non trivial instances (otherwise it gives the same trivial results). Remarkably, the largest improvement in performance with respect to the other methods employed is found in the case of benchmarks with meshes, where the validity hypothesis behind message-passing is expected to worsen. In these cases, even though the exact message-passing equations do not converge, by introducing a reinforcement parameter to force convergence towards a sub optimal solution, we were able to always outperform the other algorithms with a peak of 27\% performance improvement in terms of accommodated paths. On random graphs, we numerically observe two separated regimes: one in which all paths can be accommodated and one in which this is not possible. We also investigate the behavior of both the number of paths to be accommodated and their minimum total length.}, number = {12}, urldate = {2016-01-21}, journal = {PLoS ONE}, author = {Altarelli, Fabrizio and Braunstein, Alfredo and Dall{\textquoteright}Asta, Luca and De Bacco, Caterina and Franz, Silvio}, month = dec, year = {2015}, pages = {e0145222}, file = {PLoS Full Text PDF:/home/ab/.mozilla/firefox/3nu0zcxd.default-1419871504027/zotero/storage/Z7H257VP/Altarelli et al. - 2015 - The Edge-Disjoint Path Problem on Random Graphs by.pdf:application/pdf} } @article{braunstein_large_2016, title = {The large deviations of the whitening process in random constraint satisfaction problems}, volume = {2016}, issn = {1742-5468}, url = {http://stacks.iop.org/1742-5468/2016/i=5/a=053401}, doi = {10.1088/1742-5468/2016/05/053401}, abstract = {Random constraint satisfaction problems undergo several phase transitions as the ratio between the number of constraints and the number of variables is varied. When this ratio exceeds the satisfiability threshold no more solutions exist; the satisfiable phase, for less constrained problems, is itself divided in an unclustered regime and a clustered one. In the latter solutions are grouped in clusters of nearby solutions separated in configuration space from solutions of other clusters. In addition the rigidity transition signals the appearance of so-called frozen variables in typical solutions: beyond this threshold most solutions belong to clusters with an extensive number of variables taking the same values in all solutions of the cluster. In this paper we refine the description of this phenomenon by estimating the location of the freezing transition, corresponding to the disappearance of all unfrozen solutions (not only typical ones). We also unveil phase transitions for the existence and uniqueness of locked solutions, in which all variables are frozen. From a technical point of view we characterize atypical solutions with a number of frozen variables different from the typical value via a large deviation study of the dynamics of a stripping process (whitening) that unveils the frozen variables of a solution, building upon recent works on atypical trajectories of the bootstrap percolation dynamics. Our results also bear some relevance from an algorithmic perspective, previous numerical studies having shown that heuristic algorithms of various kinds usually output unfrozen solutions.}, language = {en}, number = {5}, urldate = {2016-05-20}, journal = {Journal of Statistical Mechanics: Theory and Experiment}, author = {Braunstein, Alfredo and Dall’Asta, Luca and Semerjian, Guilhem and Zdeborová, Lenka}, year = {2016}, pages = {053401}, note = {arXiv: 1602.01700}, file = {IOP Full Text PDF:/home/ab/.mozilla/firefox/3nu0zcxd.default-1419871504027/zotero/storage/8V29I2D8/Braunstein et al. - 2016 - The large deviations of the whitening process in r.pdf:application/pdf} } @inproceedings{braunstein_encoding_2007, title = {Encoding for the Blackwell Channel with Reinforced Belief Propagation}, booktitle = {{IEEE} International Symposium on Information Theory ({ISIT07)}}, author = {Braunstein, Alfredo and Kayhan, Farbod and Montorsi, Guido and Zecchina, Riccardo}, year = {2007}, keywords = {coding}, pages = {1891--1895}, file = {Braunstein et al_2007_Encoding for the Blackwell Channel with Reinforced Belief Propagation.pdf:/home/ab/.mozilla/firefox/kzbv3j9l.default-1369812946519/zotero/storage/CC7K6I5V/Braunstein et al_2007_Encoding for the Blackwell Channel with Reinforced Belief Propagation.pdf:application/pdf} } @article{braunstein_inference_2016, title = {Inference of causality in epidemics on temporal contact networks}, volume = {6}, issn = {2045-2322}, doi = {10.1038/srep27538}, abstract = {Investigating into the past history of an epidemic outbreak is a paramount problem in epidemiology. Based on observations about the state of individuals, on the knowledge of the network of contacts and on a mathematical model for the epidemic process, the problem consists in describing some features of the posterior distribution of unobserved past events, such as the source, potential transmissions, and undetected positive cases. Several methods have been proposed for the study of these inference problems on discrete-time, synchronous epidemic models on networks, including naive Bayes, centrality measures, accelerated Monte-Carlo approaches and Belief Propagation. However, most traced real networks consist of short-time contacts on continuous time. A possibility that has been adopted is to discretize time line into identical intervals, a method that becomes more and more precise as the length of the intervals vanishes. Unfortunately, the computational time of the inference methods increase with the number of intervals, turning a sufficiently precise inference procedure often impractical. We show here an extension of the Belief Propagation method that is able to deal with a model of continuous-time events, without resorting to time discretization. We also investigate the effect of time discretization on the quality of the inference.}, language = {ENG}, journal = {Scientific Reports}, author = {Braunstein, Alfredo and Ingrosso, Alessandro}, month = jun, year = {2016}, doi = {10.1038/srep27538}, url = {http://www.nature.com/articles/srep27538}, pages = {27538} } @article{braunstein_practical_2016, title = {Practical optimization of {Steiner} trees via the cavity method}, volume = {2016}, issn = {1742-5468}, url = {http://stacks.iop.org/1742-5468/2016/i=7/a=073302}, doi = {10.1088/1742-5468/2016/07/073302}, abstract = {The optimization version of the cavity method for single instances, called Max-Sum, has been applied in the past to the minimum Steiner tree problem on graphs and variants. Max-Sum has been shown experimentally to give asymptotically optimal results on certain types of weighted random graphs, and to give good solutions in short computation times for some types of real networks. However, the hypotheses behind the formulation and the cavity method itself limit substantially the class of instances on which the approach gives good results (or even converges). Moreover, in the standard model formulation, the diameter of the tree solution is limited by a predefined bound, that affects both computation time and convergence properties. In this work we describe two main enhancements to the Max-Sum equations to be able to cope with optimization of real-world instances. First, we develop an alternative ‘ flat ’ model formulation that allows the relevant configuration space to be reduced substantially, making the approach feasible on instances with large solution diameter, in particular when the number of terminal nodes is small. Second, we propose an integration between Max-Sum and three greedy heuristics. This integration allows Max-Sum to be transformed into a highly competitive self-contained algorithm, in which a feasible solution is given at each step of the iterative procedure. Part of this development participated in the 2014 DIMACS Challenge on Steiner problems, and we report the results here. The performance on the challenge of the proposed approach was highly satisfactory: it maintained a small gap to the best bound in most cases, and obtained the best results on several instances in two different categories. We also present several improvements with respect to the version of the algorithm that participated in the competition, including new best solutions for some of the instances of the challenge.}, language = {en}, number = {7}, urldate = {2016-11-04}, journal = {Journal of Statistical Mechanics: Theory and Experiment}, author = {Braunstein, Alfredo and Muntoni, Anna}, year = {2016}, pages = {073302}, file = {IOP Full Text PDF:/home/ab/.mozilla/firefox/3nu0zcxd.default-1419871504027/zotero/storage/Q5FTNF2F/Braunstein and Muntoni - 2016 - Practical optimization of Steiner trees via the ca.pdf:application/pdf} } @article{braunstein_contamination_2017, title = {Contamination source inference in water distribution networks}, url = {http://arxiv.org/abs/1712.00486}, abstract = {We study the inference of the origin and the pattern of contamination in water distribution networks after the observation of contaminants in few nodes of the network}, journal = {arXiv:1712.00486 [physics]}, author = {Braunstein, Alfredo and Lage-Castellanos, Alejandro and Ortega, Ernesto}, month = dec, year = {2017}, note = {arXiv: 1712.00486}, keywords = {Physics - Applied Physics, Physics - Physics and Society}, file = {arXiv\:1712.00486 PDF:/home/ab/.mozilla/firefox/3nu0zcxd.default-1419871504027/zotero/storage/4TINTHC7/Braunstein et al. - 2017 - Contamination source inference in water distributi.pdf:application/pdf;arXiv.org Snapshot:/home/ab/.mozilla/firefox/3nu0zcxd.default-1419871504027/zotero/storage/C4S4FNZ7/1712.html:text/html} } @article{braunstein_inferencia_2017, title = {{INFERENCIA} {DEL} {ORIGEN} {DE} {CONTAMINACION} {EN} {REDES} {HIDRICAS}}, volume = {34}, issn = {02539268}, url = {https://go.gale.com/ps/i.do?p=IFME&sw=w&issn=02539268&v=2.1&it=r&id=GALE%7CA599660082&sid=googleScholar&linkaccess=abs}, language = {Spanish}, number = {2}, urldate = {2020-11-02}, journal = {Revista Cubana de F\ísica}, author = {Braunstein, A. and Lage-Castellanos, A. and Ortega, E.}, month = dec, year = {2017}, pages = {100--108}, file = {Snapshot:/home/ab/Zotero/storage/KCULP97W/anonymous.html:text/html} } @article{braunstein_cavity_2018, title = {The cavity approach for {Steiner} trees packing problems}, volume = {2018}, issn = {1742-5468}, url = {https://doi.org/10.1088%2F1742-5468%2Faaeb3f}, doi = {10.1088/1742-5468/aaeb3f}, abstract = {The belief propagation approximation, or cavity method, has been recently applied to several combinatorial optimization problems in its zero-temperature implementation, the max-sum algorithm. In particular, recent developments to solve the edge-disjoint paths problem and the prize-collecting Steiner tree problem on graphs have shown remarkable results for several classes of graphs and for benchmark instances. Here we propose a generalization of these techniques for two variants of the Steiner trees packing problem where multiple {\textquoteleft}interacting{\textquoteright} trees have to be sought within a given graph. Depending on the interaction among trees we distinguish the vertex-disjoint Steiner trees problem, where trees cannot share nodes, from the edge-disjoint Steiner trees problem, where edges cannot be shared by trees but nodes can be members of multiple trees. Several practical problems of huge interest in network design can be mapped into these two variants, for instance, the physical design of very large scale integration (VLSI) chips. The formalism described here relies on two components edge-variables that allows us to formulate a massage-passing algorithm for the V-DStP and two algorithms for the E-DStP differing in the scaling of the computational time with respect to some relevant parameters. We will show that through one of the two formalisms used for the edge-disjoint variant it is possible to map the max-sum update equations into a weighted maximum matching problem over proper bipartite graphs. We developed a heuristic procedure based on the max-sum equations that shows excellent performance in synthetic networks (in particular outperforming standard multi-step greedy procedures by large margins) and on large benchmark instances of VLSI for which the optimal solution is known, on which the algorithm found the optimum in two cases and the gap to optimality was never larger than 4\%.}, language = {en}, number = {12}, urldate = {2020-11-02}, journal = {Journal of Statistical Mechanics: Theory and Experiment}, author = {Braunstein, Alfredo and Muntoni, Anna Paola}, month = dec, year = {2018}, pages = {123401}, file = {Submitted Version:/home/ab/Zotero/storage/4SJAW3WR/Braunstein and Muntoni - 2018 - The cavity approach for Steiner trees packing prob.pdf:application/pdf} } @article{braunstein_network_2019, title = {Network reconstruction from infection cascades}, volume = {16}, url = {https://royalsocietypublishing.org/doi/full/10.1098/rsif.2018.0844}, doi = {10.1098/rsif.2018.0844}, abstract = {Accessing the network through which a propagation dynamics diffuses is essential for understanding and controlling it. In a few cases, such information is available through direct experiments or thanks to the very nature of propagation data. In a majority of cases however, available information about the network is indirect and comes from partial observations of the dynamics, rendering the network reconstruction a fundamental inverse problem. Here we show that it is possible to reconstruct the whole structure of an interaction network and to simultaneously infer the complete time course of activation spreading, relying just on single epoch (i.e. snapshot) or time-scattered observations of a small number of activity cascades. The method that we present is built on a belief propagation approximation, that has shown impressive accuracy in a wide variety of relevant cases, and is able to infer interactions in the presence of incomplete time-series data by providing a detailed modelling of the posterior distribution of trajectories conditioned to the observations. Furthermore, we show by experiments that the information content of full cascades is relatively smaller than that of sparse observations or single snapshots.}, number = {151}, urldate = {2020-11-02}, journal = {Journal of The Royal Society Interface}, author = {Braunstein, Alfredo and Ingrosso, Alessandro and Muntoni, Anna Paola}, month = feb, year = {2019}, pages = {20180844}, file = {Full Text PDF:/home/ab/Zotero/storage/XVUAGKHF/Braunstein et al. - 2019 - Network reconstruction from infection cascades.pdf:application/pdf;Snapshot:/home/ab/Zotero/storage/5D2SR4K2/rsif.2018.html:text/html} } @article{braunstein_loop_2019, title = {Loop {Corrections} in {Spin} {Models} through {Density} {Consistency}}, volume = {123}, url = {https://link.aps.org/doi/10.1103/PhysRevLett.123.020604}, doi = {10.1103/PhysRevLett.123.020604}, abstract = {Computing marginal distributions of discrete or semidiscrete Markov random fields (MRFs) is a fundamental, generally intractable problem with a vast number of applications in virtually all fields of science. We present a new family of computational schemes to approximately calculate the marginals of discrete MRFs. This method shares some desirable properties with belief propagation, in particular, providing exact marginals on acyclic graphs, but it differs with the latter in that it includes some loop corrections; i.e., it takes into account correlations coming from all cycles in the factor graph. It is also similar to the adaptive Thouless-Anderson-Palmer method, but it differs with the latter in that the consistency is not on the first two moments of the distribution but rather on the value of its density on a subset of values. The results on finite-dimensional Isinglike models show a significant improvement with respect to the Bethe-Peierls (tree) approximation in all cases and with respect to the plaquette cluster variational method approximation in many cases. In particular, for the critical inverse temperature $\beta$c of the homogeneous hypercubic lattice, the expansion of (d$\beta$c)-1 around d=$\infty$ of the proposed scheme is exact up to d-4 order, whereas the latter two are exact only up to d-2 order.}, number = {2}, urldate = {2020-11-02}, journal = {Physical Review Letters}, author = {Braunstein, Alfredo and Catania, Giovanni and Dall{\textquoteright}Asta, Luca}, month = jul, year = {2019}, pages = {020604}, file = {APS Snapshot:/home/ab/Zotero/storage/JNI9I7Q2/PhysRevLett.123.html:text/html;Submitted Version:/home/ab/Zotero/storage/G8R33MYT/Braunstein et al. - 2019 - Loop Corrections in Spin Models through Density Co.pdf:application/pdf} } @article{muntoni_nonconvex_2019, title = {Nonconvex image reconstruction via expectation propagation}, volume = {100}, url = {https://link.aps.org/doi/10.1103/PhysRevE.100.032134}, doi = {10.1103/PhysRevE.100.032134}, abstract = {The problem of efficiently reconstructing tomographic images can be mapped into a Bayesian inference problem over the space of pixels densities. Solutions to this problem are given by pixels assignments that are compatible with tomographic measurements and maximize a posterior probability density. This maximization can be performed with standard local optimization tools when the log-posterior is a convex function, but it is generally intractable when introducing realistic nonconcave priors that reflect typical images features such as smoothness or sharpness. We introduce a new method to reconstruct images obtained from Radon projections by using expectation propagation, which allows us to approximate the intractable posterior. We show, by means of extensive simulations, that, compared to state-of-the-art algorithms for this task, expectation propagation paired with very simple but non-log-concave priors is often able to reconstruct images up to a smaller error while using a lower amount of information per pixel. We provide estimates for the critical rate of information per pixel above which recovery is error-free by means of simulations on ensembles of phantom and real images.}, number = {3}, urldate = {2020-11-02}, journal = {Physical Review E}, author = {Muntoni, Anna Paola and Rojas, Rafael D{\'i}az Hern{\'a}ndez and Braunstein, Alfredo and Pagnani, Andrea and P{\'e}rez Castillo, Isaac}, month = sep, year = {2019}, pages = {032134}, file = {APS Snapshot:/home/ab/Zotero/storage/V5XR2ZJP/PhysRevE.100.html:text/html} } @article{saldida_unbiased_2020, title = {Unbiased metabolic flux inference through combined thermodynamic and {13C} flux analysis}, copyright = {{\textcopyright} 2020, Posted by Cold Spring Harbor Laboratory. This pre-print is available under a Creative Commons License (Attribution-NonCommercial-NoDerivs 4.0 International), CC BY-NC-ND 4.0, as described at http://creativecommons.org/licenses/by-nc-nd/4.0/}, url = {https://www.biorxiv.org/content/10.1101/2020.06.29.177063v1}, doi = {10.1101/2020.06.29.177063}, abstract = {{\textless}h3{\textgreater}ABSTRACT{\textless}/h3{\textgreater} {\textless}p{\textgreater}Quantification of cellular metabolic fluxes, for instance with $^{\textrm{13}}$C-metabolic flux analysis, is highly important for applied and fundamental metabolic research. A current challenge in $^{\textrm{13}}$C-flux analysis is that the available experimental data are usually insufficient to resolve metabolic fluxes in large metabolic networks without making assumptions on flux directions and reversibility. To infer metabolic fluxes in a more unbiased manner, we devised an approach that does not require such assumptions. The developed three-step approach integrates thermodynamics, metabolome, physiological data, and $^{\textrm{13}}$C labelling data, and involves a novel method to comprehensively sample the complex thermodynamically-constrained metabolic flux space. Applying our approach to budding yeast with its compartmentalised metabolism and parallel pathways, we could resolve metabolic fluxes in an unbiased manner, we obtained an uncertainty estimate for each flux, and we found novel flux patterns that until now had remained unknown, likely due to assumptions made in previous $^{\textrm{13}}$C flux analysis studies. We expect that our approach will be an important step forward to determine metabolic fluxes with improved accuracy in microorganisms and possibly also in more complex organisms.{\textless}/p{\textgreater}}, language = {en}, urldate = {2020-11-02}, journal = {bioRxiv}, author = {Saldida, Joana and Muntoni, Anna Paola and Martino, Daniele de and Hubmann, Georg and Niebel, Bastian and Schmidt, A. Mareike and Braunstein, Alfredo and Milias-Argeitis, Andreas and Heinemann, Matthias}, month = jun, year = {2020}, pages = {2020.06.29.177063}, file = {Full Text PDF:/home/ab/Zotero/storage/P57VRESK/Saldida et al. - 2020 - Unbiased metabolic flux inference through combined.pdf:application/pdf;Snapshot:/home/ab/Zotero/storage/KUDFNCWI/2020.06.29.177063v1.html:text/html} } @article{ortega_contamination_2020, title = {Contamination source detection in water distribution networks using belief propagation}, volume = {34}, issn = {1436-3259}, url = {https://doi.org/10.1007/s00477-020-01788-y}, doi = {10.1007/s00477-020-01788-y}, abstract = {We present a Bayesian approach for the Contamination Source Detection problem in water distribution networks. Assuming that contamination is a rare event (in space and time), we try to locate the most probable source of such events after reading contamination patterns in few sensed nodes. The method relies on strong simplifications considering binary clean/contaminated states for nodes in discrete time, and therefore focuses on the time structure of the sensed patterns rather than on the concentration levels. As a result, a posterior probability over discrete variables is written, and posterior marginals are computed using belief propagation algorithm. The resulting algorithm runs once on a given observation and reports probabilities for each node being the source and for the contamination patterns altogether. We test it on Anytown model, proving its efficacy even when only a single sensed node is known.}, language = {en}, number = {3}, urldate = {2020-11-02}, journal = {Stochastic Environmental Research and Risk Assessment}, author = {Ortega, Ernesto and Braunstein, Alfredo and Lage-Castellanos, Alejandro}, month = apr, year = {2020}, pages = {493--511}, file = {Submitted Version:/home/ab/Zotero/storage/6DIBFNNX/Ortega et al. - 2020 - Contamination source detection in water distributi.pdf:application/pdf} } @article{braunstein_compressed_2020, title = {Compressed sensing reconstruction using expectation propagation}, volume = {53}, issn = {1751-8121}, url = {https://doi.org/10.1088%2F1751-8121%2Fab3065}, doi = {10.1088/1751-8121/ab3065}, abstract = {Many interesting problems in fields ranging from telecommunications to computational biology can be formalized in terms of large underdetermined systems of linear equations with additional constraints or regularizers. One of the most studied, the compressed sensing problem, consists in finding the solution with the smallest number of non-zero components of a given system of linear equations for known measurement vector and sensing matrix . Here, we will address the compressed sensing problem within a Bayesian inference framework where the sparsity constraint is remapped into a singular prior distribution (called Spike-and-Slab or Bernoulli{\textendash}Gauss). A solution to the problem is attempted through the computation of marginal distributions via expectation propagation, an iterative computational scheme originally developed in statistical physics. We will show that this strategy is more accurate for statistically correlated measurement matrices. For computational strategies based on the Bayesian framework such as variants of belief propagation, this is to be expected, as they implicitly rely on the hypothesis of statistical independence among the entries of the sensing matrix. Perhaps surprisingly, the method outperforms uniformly all the other state-of-the-art methods in our tests.}, language = {en}, number = {18}, urldate = {2020-11-02}, journal = {Journal of Physics A: Mathematical and Theoretical}, author = {Braunstein, Alfredo and Muntoni, Anna Paola and Pagnani, Andrea and Pieropan, Mirko}, month = apr, year = {2020}, pages = {184001}, file = {Submitted Version:/home/ab/Zotero/storage/2NUSYGBN/Braunstein et al. - 2020 - Compressed sensing reconstruction using expectatio.pdf:application/pdf} } @article{braunstein_casualita_2020, title = {Casualit{\`a}, causalit{\`a} e {Machine} {Learning} nel contenimento epidemico}, language = {it}, journal = {Ithaca: viaggio nella scienza XVI}, url = {http://ithaca.unisalento.it/nr-16_2020/articolo_IIp_13.pdf}, author = {Alfredo Braunstein and Luca Dall'Asta and Alessandro Ingrosso}, pages = {12}, year = {2020}, file = {Casualit{\`a}, causalit{\`a} e Machine Learning nel conten.pdf:/home/ab/Zotero/storage/TGXLAKKC/Adams - Casualit{\`a}, causalit{\`a} e Machine Learning nel conten.pdf:application/pdf} } @article{braunstein_density_2020, title = {A {Density} {Consistency} approach to the inverse {Ising} problem}, url = {http://arxiv.org/abs/2010.13746}, abstract = {We propose a novel approach to the inverse Ising problem which employs the recently introduced Density Consistency approximation (DC) to determine the model parameters (couplings and external fields) maximizing the likelihood of given empirical data. This method allows for closed-form expressions of the inferred parameters as a function of the first and second experimental moments. Such expressions have a similar structure to the small-correlation expansion derived by Sessak and Monasson, of which they provide an improvement in the case of non-zero magnetization at low temperatures, as well as in presence of random external fields. The present work provides an extensive comparison with most common inference methods used to reconstruct the model parameters in several regimes, i.e. by varying both the network topology and the distribution of fields and couplings. The comparison shows that no method is uniformly better than every other one, but DC appears nevertheless as one of the most accurate and reliable approaches to infer couplings and fields from first and second moments in a significant range of parameters.}, urldate = {2020-11-02}, journal = {arXiv:2010.13746 [cond-mat]}, author = {Braunstein, Alfredo and Catania, Giovanni and Dall'Asta, Luca and Muntoni, Anna Paola}, month = oct, year = {2020}, note = {arXiv: 2010.13746}, keywords = {Condensed Matter - Statistical Mechanics, G.3, I.2.6}, annote = {Comment: 15 pages, 4 figures}, file = {arXiv Fulltext PDF:/home/ab/Zotero/storage/4V6ZUCR5/Braunstein et al. - 2020 - A Density Consistency approach to the inverse Isin.pdf:application/pdf;arXiv.org Snapshot:/home/ab/Zotero/storage/B6WV9KUW/2010.html:text/html} } @article{baker_epidemic_2020, title = {Epidemic mitigation by statistical inference from contact tracing data}, url = {http://arxiv.org/abs/2009.09422}, abstract = {Contact-tracing is an essential tool in order to mitigate the impact of pandemic such as the COVID-19. In order to achieve efficient and scalable contact-tracing in real time, digital devices can play an important role. While a lot of attention has been paid to analyzing the privacy and ethical risks of the associated mobile applications, so far much less research has been devoted to optimizing their performance and assessing their impact on the mitigation of the epidemic. We develop Bayesian inference methods to estimate the risk that an individual is infected. This inference is based on the list of his recent contacts and their own risk levels, as well as personal information such as results of tests or presence of syndromes. We propose to use probabilistic risk estimation in order to optimize testing and quarantining strategies for the control of an epidemic. Our results show that in some range of epidemic spreading (typically when the manual tracing of all contacts of infected people becomes practically impossible, but before the fraction of infected people reaches the scale where a lock-down becomes unavoidable), this inference of individuals at risk could be an efficient way to mitigate the epidemic. Our approaches translate into fully distributed algorithms that only require communication between individuals who have recently been in contact. Such communication may be encrypted and anonymized and thus compatible with privacy preserving standards. We conclude that probabilistic risk estimation is capable to enhance performance of digital contact tracing and should be considered in the currently developed mobile applications.}, urldate = {2020-11-02}, journal = {arXiv:2009.09422 [cond-mat, q-bio]}, author = {Baker, Antoine and Biazzo, Indaco and Braunstein, Alfredo and Catania, Giovanni and Dall'Asta, Luca and Ingrosso, Alessandro and Krzakala, Florent and Mazza, Fabio and M{\'e}zard, Marc and Muntoni, Anna Paola and Refinetti, Maria and Mannelli, Stefano Sarao and Zdeborov{\'a}, Lenka}, month = sep, year = {2020}, note = {arXiv: 2009.09422}, keywords = {Computer Science - Artificial Intelligence, Computer Science - Machine Learning, Condensed Matter - Statistical Mechanics, G.3, G.4, I.2.11, J.3, Quantitative Biology - Populations and Evolution}, annote = {Comment: 21 pages, 7 figures}, file = {arXiv Fulltext PDF:/home/ab/Zotero/storage/ERVZGX4F/Baker et al. - 2020 - Epidemic mitigation by statistical inference from .pdf:application/pdf;arXiv.org Snapshot:/home/ab/Zotero/storage/SZQXETKN/2009.html:text/html} }