Stochastic graph Voronoi tessellation reveals community structure
Published in Physical Review E, 2017
Recommended citation: Lázár, Z. I., Papp, I., Varga, L., Járai-Szabó, F., Deritei, D., & Ercsey-Ravasz, M. (2017). Stochastic graph Voronoi tessellation reveals community structure. Physical Review E, 95(2), 022306. https://journals.aps.org/pre/abstract/10.1103/PhysRevE.95.022306
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 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.
Recommended citation: Lázár, Z. I., Papp, I., Varga, L., Járai-Szabó, F., Deritei, D., & Ercsey-Ravasz, M. (2017). Stochastic graph Voronoi tessellation reveals community structure. Physical Review E, 95(2), 022306.