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