Search

Soft-constraint affinity propagation (SCAP) is a new statistical-physics based clustering technique [M. Leone, Sumedha, M. Weigt, Bioinformatics 23, 2708 (2007)]. First we give the derivation of a simplified version of the algorithm and discuss possibilities of time- and memory-efficient implementations. Later we give a detailed analysis of the performance of SCAP on artificial data, showing that the algorithm efficiently unveils clustered and hierarchical data structures. We generalize the algorithm to the problem of semi-supervised clustering, where data are already partially labeled, and clustering assigns labels to previously unlabeled points. SCAP uses both the geometrical organization of the data and the available labels assigned to few points in a computationally efficient way, as is shown on artificial and biological benchmark data. [ABSTRACT FROM AUTHOR]

We consider the gelation of particles which are permanently connected by random crosslinks, drawn from an ensemble of finite-dimensional continuum percolation. To average over the randomness, we apply the replica trick, and interpret the replicated and crosslink-averaged model as an effective molecular fluid. A Mayer-cluster expansion for moments of the local static density fluctuations is set up. The simplest non-trivial contribution to this series leads back to mean-field theory. The central quantity of mean-field theory is the distribution of localization lengths, which we compute for all connectivities. The highly crosslinked gel is characterized by a one-to-one correspondence of connectivity and localization length. Taking into account higher contributions in the Mayer-cluster expansion, systematic corrections to mean-field can be included. The sol-gel transition shifts to a higher number of crosslinks per particle, as more compact structures are favored. The critical behavior of the model remains unchanged as long as finite truncations of the cluster expansion are considered. To complete the picture, we also discuss various geometrical properties of the crosslink network, e.g. connectivity correlations, and relate the studied crosslink ensemble to a wider class of ensembles, including the Deam-Edwards distribution. [ABSTRACT FROM AUTHOR]

In this paper, the dynamics of heuristic algorithms for constructing small vertex covers (or independent sets) of finite-connectivity random graphs is analysed. In every algorithmic step, a vertex is chosen with respect to its vertex degree. This vertex, and some environment of it, is covered and removed from the graph. This graph reduction process can be described as a Markovian dynamics in the space of random graphs of arbitrary degree distribution. We discuss some solvable cases, including algorithms already analysed using different techniques, and develop approximation schemes for more complicated cases. The approximations are corroborated by numerical simulations. [ABSTRACT FROM AUTHOR]

A variational approach to finite connectivity spin-glass-like models is developed and applied to describe the structure of optimal solutions in random satisfiability problems. Our variational scheme accurately reproduces the known replica symmetric results and also allows for the inclusion of replica symmetry breaking effects. For the 3-SAT problem, we find two transitions as the ratio of logical clauses per Boolean variables increases. At the first one , a non-trivial organization of the solution space in geometrically separated clusters emerges. The multiplicity of these clusters as well as the typical distances between different solutions are calculated. At the second threshold , satisfying assignments disappear and a finite fraction of variables are overconstrained and take the same values in all optimal (though unsatisfying) assignments. These values have to be compared to , obtained from numerical experiments on small instances. Within the present variational approach, the SAT-UNSAT transition naturally appears as a mixture of a first and a second order transition. For the mixed 2+ p-SAT with p<2/5, the behavior is as expected much simpler: a unique smooth transition from SAT to UNSAT takes place at . [ABSTRACT FROM AUTHOR]

We study the small-world networks recently introduced by Watts and Strogatz [Nature 393, 440 (1998)], using analytical as well as numerical tools. We characterize the geometrical properties resulting from the coexistence of a local structure and random long-range connections, and we examine their evolution with size and disorder strength. We show that any finite value of the disorder is able to trigger a “small-world” behaviour as soon as the initial lattice is big enough, and study the crossover between a regular lattice and a “small-world” one. These results are corroborated by the investigation of an Ising model defined on the network, showing for every finite disorder fraction a crossover from a high-temperature region dominated by the underlying one-dimensional structure to a mean-field like low-temperature region. In particular there exists a finite-temperature ferromagnetic phase transition as soon as the disorder strength is finite. [0.5cm] [ABSTRACT FROM AUTHOR]