Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Modellierung und Analyse komplexer Systeme

This work provides the first detailed investigation of the disturbed
diffusion scheme FOS/C introduced in [17] as a type of diffusion
distance measure within a graph partitioning framework related to
Lloyd's k-means algorithm [14]. After outlining connections to distance
measures proposed in machine learning, we show that FOS/C can be
related to random walks despite its disturbance. Its convergence
properties regarding load distribution and edge flow characterization
are examined on two different graph classes, namely torus graphs and
distance-transitive graphs (including hypercubes), representatives of
which are frequently used as interconnection networks.

Keywords: Disturbed diffusion, Diffusion distance, Random walks.