UNIGE document Chapitre d'actes
previous document  unige:34069  next document
add to browser collection
Title

Interacting urns processes : for clustering of large-scale networks of tiny artifacts

Authors
Schiller, Elad M.
Published in Proceedings of the 2008 ACM Symposium on Applied Computing (SAC). Fortaleza (Ceara, Brazil) - March 16-20, 2008 - ACM Press. 2008
Abstract We analyze a distributed variation on the P´olya urn process in which a network of tiny artifacts manages the individual urns. Neighboring urns interact by repeatedly adding the same colored ball based on previous random choices. We discover that the process rapidly converges to a definitive random ratio between the colors in every urn and that the rate of convergence of the process at a given node depends on the global topology of the network. In particular, the same ratio appears for the case of complete communication graphs. Surprisingly, this effortless random process supports useful applications, such as clustering and pseudocoordinate computation. We present preliminary numerical studies that validate our theoretical predictions.
Identifiers
ISBN: 978-1-59593-753-7
Full text
Structures
Research group Theoretical Computer Science
Citation
(ISO format)
LEONE, Pierre, SCHILLER, Elad M. Interacting urns processes : for clustering of large-scale networks of tiny artifacts. In: Proceedings of the 2008 ACM Symposium on Applied Computing (SAC). Fortaleza (Ceara, Brazil). [s.l.] : ACM Press, 2008. https://archive-ouverte.unige.ch/unige:34069

214 hits

137 downloads

Update

Deposited on : 2014-02-04

Export document
Format :
Citation style :