Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-28T20:40:02.206Z Has data issue: false hasContentIssue false
  • English
  • Français

On a distributed clustering process of Coffman, Courtois, Gilbert and Piret

Part of: Special processes Operations research and management science

Published online by Cambridge University Press:  14 July 2016

J. van den Berg  and
A. Ermakov
J. van den Berg*
Affiliation:
CWI
A. Ermakov*
Affiliation:
CWI
*
∗Postal address: CWI, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands.
∗Postal address: CWI, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands.
Get access Rights & Permissions [Opens in a new window]

Abstract

Coffman, Courtois, Gilbert and Piret (1991) have introduced a flow process in graphs, where each vertex gets an initial random resource, and where at each time vertices with large resources tend to attract resources from neighbours. The initial resources are assumed to be i.i.d., with a continuous distribution.

We are mainly interested in the following question: does, with probability 1, the resource of each vertex change only finitely many times?

Coffman et al. concentrate mainly on the case where the graph corresponds with the integer points on the line, in which case it is easily seen that the answer to the above question is positive. For higher-dimensional lattices they make general remarks which suggest that the answer to the above question is still positive. However, no proof seems to be known.

We restrict to the case of the square lattice, and, by a percolation approach, we reduce the question above to the question whether a certain quantity, which can be obtained from a finite computation, is sufficiently small. This computation is, however, still too long to be executed in an acceptable time. We therefore apply Monte Carlo simulation for this finite problem, which gives overwhelming evidence that, for the square lattice, the answer to the main question is positive.

Keywords

Flow of resourcesclusteringpercolation

MSC classification

Primary: 60K35: Interacting random processes; statistical mechanics type models; percolation theory
Secondary: 90B15: Network models, stochastic
Type
Research Papers
Information
Journal of Applied Probability , Volume 35 , Issue 4 , December 1998 , pp. 919 - 924
Copyright
Copyright © Applied Probability Trust 1998 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

Supported by the Netherlands Organization for Scientific Research (NWO).

References

Chayes, J. T., and Chayes, L. (1986). Percolation and random media. Critical Phenomena, Random systems, Gauge theories (Les Houches, Session XLIII, 1984). Elsevier, Amsterdam, pp. 1001–1142.Google Scholar
Coffman, E. G., Courtois, P. J., Gilbert, E. N., and Piret, P. (1991). A distributed clustering process. J. Appl. Prob. 28, 737–750.Google Scholar
Grimmett, G. (1989). Percolation. Springer, Berlin.Google Scholar
Kesten, H. (1981). Analyticity properties and power law estimates of functions in percolation theory. J. Statist. Phys. 25, 717–756.Google Scholar
van den Berg, J., and Meester, R. W. J. (1991). Stability properties of a flow process in graphs. Random Structures and Algorithms 2, 335–341.Google Scholar