Title: Stochastic graph Voronoi tessellation reveals community structure,
Abstract: Given a network, the statistical ensemble of its graph-Voronoi diagrams with
randomly chosen cell centers exhibits properties convertible into information
on the network's large scale structures. We define a node-pair level measure
called {\it Voronoi cohesion} which describes the probability for sharing the
same Voronoi cell, when randomly choosing $g$ centers in the network. This
measure provides information based on the global context (the network in its
entirety) a type of information that is not carried by other similarity
measures. We explore the mathematical background of this phenomenon and several
of its potential applications. A special focus is laid on the possibilities and
limitations pertaining to the exploitation of the phenomenon for community
detection purposes.