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.

14 pages,10 figures

References in corpus (8)

• Fast unfolding of communities in large networks
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• An information-theoretic framework for resolving community structure in complex networks
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Distance distribution in random graphs and application to networks exploration