zbMATH — the first resource for mathematics

Analyzing disturbed diffusion on networks. (English) Zbl 1135.68522
Asano, Tetsuo (ed.), Algorithms and computation. 17th international symposium, ISAAC 2006, Kolkata, India, December 18–20, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-49694-6/pbk). Lecture Notes in Computer Science 4288, 429-438 (2006).
Summary: This work provides the first detailed investigation of the disturbed diffusion scheme FOS/C, introduced as a type of diffusion distance measure within a graph partitioning framework related to Lloyd’s \(k\)-means algorithm. 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.
For the entire collection see [Zbl 1133.68002].

68R10 Graph theory (including graph drawing) in computer science
60G50 Sums of independent random variables; random walks
Full Text: DOI