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 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.
authors.affiliation: Faculty of Physics, Babeş-Bolyai University, Cluj-Napoca, Romania.
authors.forename: Zsolt I
authors.initials: ZI
authors.lastname: Lázár
authors.affiliation: Faculty of Physics, Babeş-Bolyai University, Cluj-Napoca, Romania.
authors.forename: István
authors.initials: I
authors.lastname: Papp
authors.affiliation: Faculty of Physics, Babeş-Bolyai University, Cluj-Napoca, Romania.
authors.forename: Levente
authors.initials: L
authors.lastname: Varga
authors.affiliation: Faculty of Physics, Babeş-Bolyai University, Cluj-Napoca, Romania.
authors.forename: Ferenc
authors.initials: F
authors.lastname: Járai-Szabó
authors.affiliation: Faculty of Physics, Babeş-Bolyai University, Cluj-Napoca, Romania.|Department of Network Science, Central European University, Hungary.
authors.forename: Dávid
authors.initials: D
authors.lastname: Deritei
authors.affiliation: Faculty of Physics, Babeş-Bolyai University, Cluj-Napoca, Romania.|Romanian Institute of Science and Technology, Cluj-Napoca, Romania.
authors.forename: Mária
authors.initials: M
authors.lastname: Ercsey-Ravasz