We present a large catalog of optically selected galaxy clusters from the application of a new Gaussian Mixture Brightest Cluster Galaxy (GMBCG) algorithm to SDSS Data Release 7 data. The algorithm detects clusters by identifying the red sequence plus Brightest Cluster Galaxy (BCG) feature, which is unique for galaxy clusters and does not exist among field galaxies. Red sequence clustering in color space is detected using an Error Corrected Gaussian Mixture Model. We run GMBCG on 8240 square degrees of photometric data from SDSS DR7 to assemble the largest ever optical galaxy cluster catalog, consisting of over 55,000 rich clusters across the redshift range from 0.1 < z < 0.55. We present Monte Carlo tests of completeness and purity and perform cross-matching with X-ray clusters and with the maxBCG sample at low redshift. These tests indicate high completeness and purity across the full redshift range for clusters with 15 or more members.

Often we wish to predict a large number of variables that depend on each other as well as on other observed variables. Structured prediction methods are essentially a combination of classification and graphical modeling, combining the ability of graphical models to compactly model multivariate data with the ability of classification methods to perform prediction using large sets of input features. This tutorial describes conditional random fields, a popular probabilistic method for structured prediction. CRFs have seen wide application in natural language processing, computer vision, and bioinformatics. We describe methods for inference and parameter estimation for CRFs, including practical issues for implementing large scale CRFs. We do not assume previous knowledge of graphical modeling, so this tutorial is intended to be useful to practitioners in a wide variety of fields.

Narratives can be defined informally as a “spatio-temporally bounded stream of elementary events”. To make this sort of definition more computationally useful we introduce, firstly, some pragmatic criteria for recognizing highly ambiguous entities like the “elementary events” and for linking these events together into complete narratives. We raise then the problem of how to concretely represent elementary events and narratives in computer-suitable form. We introduce then the main characteristics of a language, NKRL (Narrative Knowledge Representation Language), expressly specified and implemented for dealing with (non-fictional) narratives and temporal information. We conclude by showing briefly how this language can be used for questioning and for particularly complex inference operations.

A peloton is a group of cyclists whose individual and collective energy expenditures are reduced when cyclists ride behind others in zones of reduced air pressure; this effect is known in cycling as ‘drafting’. Through drafting cyclists couple their energy expenditures. Coupling of cyclists’ energy expenditures when drafting is the basic peloton property from which self-organized collective behaviours emerge. Here we examine peloton hysteresis, applying the definition used in the context of vehicle traffic in which a rapid deceleration to a high density state (jam) is followed by a lag in vehicle acceleration. Applying a flow analysis of volume (number of cyclists) over time, peloton hysteresis is examined in three forms: one is similar to vehicle traffic hysteresis in which rapid decelerations and increased flow (or density) are followed by extended acceleration periods and reduced flow. In cycling this is known as the accordion effect. A second kind of hysteresis results from rapid accelerations followed by periods of decreasing speeds and decreasing flow. This form of hysteresis is essentially inverse to traffic hysteresis and the accordion effect. We show this form of hysteresis using data from a mass-start bicycle points-race. A third kind of peloton hysteresis occurs when the drafting benefit is minimized on hills and weaker cyclists lose positions in the peloton, while flow/density is retained. A computer simulation shows this hysteresis among two sets of cyclist agents, each with different output capacity and models hysteresis as a peloton transitions from flat topography to a steep incline on which drafting is negligible.

A large body of research describes the importance of adaptability for systems to be resilient in the face of disruptions. However, adaptive processes can be fallible, either because systems fail to adapt in situations requiring new ways of functioning, or because the adaptations themselves produce undesired consequences. A central question is then: how can systems better manage their capacity to adapt to perturbations, and constitute intelligent adaptive systems? Based on studies conducted in different high-risk domains (healthcare, mission control, military operations, urban firefighting), we have identified three basic patterns of adaptive failures or traps: (1) decompensation – when a system exhausts its capacity to adapt as disturbances and challenges cascade; (2) working at cross-purposes – when sub-systems or roles exhibit behaviors that are locally adaptive but globally maladaptive; (3) getting stuck in outdated behaviors – when a system over-relies on past successes although conditions of operation change. The identification of such basic patterns then suggests ways in which a work organization, as an example of a complex adaptive system, needs to behave in order to see and avoid or recognize and escape the corresponding failures. The paper will present how expert practitioners exhibit such resilient behaviors in high-risk situations, and how adverse events can occur when systems fail to do so. We will also explore how various efforts in research related to complex adaptive systems provide fruitful directions to advance both the necessary theoretical work and the development of concrete solutions for improving systems’ resilience.

We provide a systematic study of the problem of finding the source of a rumor in a network. We model rumor spreading in a network with a variant of the popular SIR model and then construct an estimator for the rumor source. This estimator is based upon a novel topological quantity which we term \textbf{rumor centrality}. We establish that this is an ML estimator for a class of graphs. We find the following surprising threshold phenomenon: on trees which grow faster than a line, the estimator always has non-trivial detection probability, whereas on trees that grow like a line, the detection probability will go to 0 as the network grows. Simulations performed on synthetic networks such as the popular small-world and scale-free networks, and on real networks such as an internet AS network and the U.S. electric power grid network, show that the estimator either finds the source exactly or within a few hops of the true source across different network topologies. We compare rumor centrality to another common network centrality notion known as distance centrality. We prove that on trees, the rumor center and distance center are equivalent, but on general networks, they may differ. Indeed, simulations show that rumor centrality outperforms distance centrality in finding rumor sources in networks which are not tree-like.

We present an exact method of greatly speeding up belief propagation (BP) for a wide variety of potential functions in pairwise MRFs and other graphical models. Specifically, our technique applies whenever the pairwise potentials have been {\em truncated} to a constant value for most pairs of states, as is commonly done in MRF models with robust potentials (such as stereo) that impose an upper bound on the penalty assigned to discontinuities; for each of the $M$ possible states in one node, only a smaller number $m$ of compatible states in a neighboring node are assigned milder penalties. The computational complexity of our method is $O(mM)$, compared with $O(M^2)$ for standard BP, and we emphasize that the method is {\em exact}, in contrast with related techniques such as pruning; moreover, the method is very simple and easy to implement. Unlike some previous work on speeding up BP, our method applies both to sum-product and max-product BP, which makes it useful in any applications where marginal probabilities are required, such as maximum likelihood estimation. We demonstrate the technique on a stereo MRF example, confirming that the technique speeds up BP without altering the solution.

Lifted inference, handling whole sets of indistinguishable objects together, is critical to the effective application of probabilistic relational models to realistic real world tasks. Recently, lifted belief propagation (LBP) has been proposed as an efficient approximate solution of this inference problem. It runs a modified BP on a lifted network where nodes have been grouped together if they have — roughly speaking — identical computation trees, the tree-structured “unrolling” of the underlying graph rooted at the nodes. In many situations, this purely syntactic criterion is too pessimistic: message errors decay along paths. Intuitively, for a long chain graph with weak edge potentials, distant nodes will send and receive identical messages yet their computation trees are quite different. To overcome this, we propose iLBP, a novel, easy-to-implement, informed LBP approach that interleaves lifting and modified BP iterations. In turn, we can efficiently monitor the true BP messages sent and received in each iteration and group nodes accordingly. As our experiments show, iLBP can yield significantly faster more lifted network while not degrading performance. Above all, we show that iLBP is faster than BP when solving the problem of distributing data to a large network, an important real-world application where BP is faster than uninformed LBP.

Many problems require repeated inference on probabilistic graphical models, with different values for evidence variables or other changes. Examples of such problems include utility maximization, MAP inference, online and interactive inference, parameter and structure learning, and dynamic inference. Since small changes to the evidence typically only affect a small region of the network, repeatedly performing inference from scratch can be massively redundant. In this paper, we propose expanding frontier belief propagation (EFBP), an efficient approximate algorithm for probabilistic inference with incremental changes to the evidence (or model). EFBP is an extension of loopy belief propagation (BP) where each run of inference reuses results from the previous ones, instead of starting from scratch with the new evidence; messages are only propagated in regions of the network affected by the changes. We provide theoretical guarantees bounding the difference in beliefs generated by EFBP and standard BP, and apply EFBP to the problem of expected utility maximization in influence diagrams. Experiments on viral marketing and combinatorial auction problems show that EFBP can converge much faster than BP without significantly affecting the quality of the solutions.

Lifting can greatly reduce the cost of inference on first-order probabilistic graphical models, but constructing the lifted network can itself be quite costly. In online applications (e.g., video segmentation) repeatedly constructing the lifted network for each new inference can be extremely wasteful, because the evidence typically changes little from one inference to the next. The same is true in many other problems that require repeated inference, like utility maximization, MAP inference, interactive inference, parameter and structure learning, etc. In this paper, we propose an efficient algorithm for updating the structure of an existing lifted network with incremental changes to the evidence. This allows us to construct the lifted network once for the initial inference problem, and amortize the cost over the subsequent problems. Experiments on video segmentation and viral marketing problems show that the algorithm greatly reduces the cost of inference without affecting the quality of the solutions.