Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-02T23:21:35.897Z Has data issue: false hasContentIssue false
  • English
  • Français

A distributed clustering process

Published online by Cambridge University Press:  14 July 2016

E. G. Coffman Jr ,
P.-J. Courtois ,
E. N. Gilbert  and
Ph. Piret
E. G. Coffman Jr*
Affiliation:
AT&T Bell Laboratories
P.-J. Courtois*
Affiliation:
Philips Research Laboratory
E. N. Gilbert*
Affiliation:
AT&T Bell Laboratories
Ph. Piret*
Affiliation:
Philips Research Laboratory
*
∗ Postal address: AT&T Bell Laboratories, Murray Hill, NJ 07974, USA.
∗∗ Postal address: Philips Research Laboratory, 4 Avenue Einstein, B-1348 Louvain-la-Neuve, Belgium.
∗ Postal address: AT&T Bell Laboratories, Murray Hill, NJ 07974, USA.
∗∗ Postal address: Philips Research Laboratory, 4 Avenue Einstein, B-1348 Louvain-la-Neuve, Belgium.
Get access Rights & Permissions [Opens in a new window]

Abstract

The points of a graph G will form clusters as a result of a flow process. Initially, points i of G own resources xi which are i.i.d. random real numbers. Afterwards, resources flow between points, but always from a point to a neighbor that has accumulated a larger total resource. Thus points with small resource tend to lose it and points with large resource tend to gain. Eventually the flow stops with only two kinds of points, nulls with no resource left and absorbers with such large resource that no neighbor can take it. The final resource at an absorber is a sum of certain initial resources xi, and the corresponding points i form one cluster. Analytical results are obtainable when G is the chain of integer points on the line. Probability distributions are derived for the distance between consecutive absorbers and the size of a cluster. Indeed these distributions do not involve the given distribution for the xi. The Laplace transform of the distribution of final resources at absorbers is derived but the distribution itself is obtained by a simulation. For general graphs G only partial results are obtained.

Keywords

FLOW OF RESOURCESGAP LENGTHCLUSTER SIZE AND RESOURCES
Type
Research Papers
Information
Journal of Applied Probability , Volume 28 , Issue 4 , December 1991 , pp. 737 - 750
Copyright
Copyright © Applied Probability Trust 1991 

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.)

References

Belic, M. R., Skarka, V., Deneubourg, J. L. and Lax, M. (1986) Mathematical model of honeycomb construction. J. Math. Biol. 24, 437–449.10.1007/BF01236891Google Scholar
Courtois, P.-J. (1985) On time and space decomposition of complex structures. Comm. Assoc. Comp. Mach. 28, 590–603.Google Scholar
Deneubourg, J. L. (1977) Application de l'ordre par fluctuations à la description de certaines étapes de la construction du nid chez les termites. Insectes Sociaux 24, 117–130.10.1007/BF02227166Google Scholar
Kindermann, R. and Snell, J. L. (1980) Markov Random Fields and their Applications, Contemporary Mathematics, Vol. 1 American Mathematical Society, Providence, RI.Google Scholar
Nicolis, G. and Prigogine, I. (1977) Self-Organization in Non-Equilibrium Systems. Wiley-Interscience, New York.Google Scholar
Wolfram, S. (1986) Theory and Applications of Cellular Automata. World Scientific, Singapore (1986).Google Scholar