Abstract
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.
This work is partially supported by German Science Foundation (DFG) Research Training Group GK-693 of the Paderborn Institute for Scientific Computation (PaSCo) and by Integrated Project IST-15964 ”Algorithmic Principles for Building Efficient Overlay Computers” (AEOLUS) of the European Union.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adámek, J.: Foundations of Coding. J. Wiley & Sons, Chichester (1991)
Alon, N., Spencer, J.H.: The Probabilistic Method, 2nd edn. J. Wiley & Sons, Chichester (2000)
Biggs, N.: Algebraic Graph Theory. Cambridge University Press, Cambridge (1993)
Coifman, R.R., Lafon, S., Lee, A.B., Maggioni, M., Nadler, B., Warner, F., Zucker, S.W.: Geometric diffusions as a tool for harmonic analysis and structure definition of data. Parts I and II. Proc. Natl. Academy of Sciences 102(21), 7426–7437 (2005)
Cybenko, G.: Dynamic load balancing for distributed memory multiprocessors. Parallel and Distributed Computing 7, 279–301 (1989)
Diekmann, R., Frommer, A., Monien, B.: Efficient schemes for nearest neighbor load balancing. Parallel Computing 25(7), 789–812 (1999)
Doyle, P.G., Snell, J.L.: Random Walks and Electric Networks. Math. Assoc. of America (1984)
Ellis, R.B.: Discrete green’s functions for products of regular graphs. In: AMS National Conference, invited talk, special session on Graph Theory (2001)
Grimmett, G.R., Stirzaker, D.R.: Probability and Random Processes, 2nd edn. Oxford University Press, Oxford (1992)
Gross, J.L., Yellen, J. (eds.): Handbook of Graph Theory. CRC Press, Boca Raton (2004)
Hu, Y.F., Blake, R.F.: An improved diffusion algorithm for dynamic load balancing. Parallel Computing 25(4), 417–444 (1999)
Kemeny, J.G., Snell, J.L.: Finite Markov Chains. Springer, Heidelberg (1976)
Leighton, F.T.: Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann Publishers, San Francisco (1992)
Lloyd, S.P.: Least squares quantization in PCM. IEEE Transactions on Information Theory 28(2), 129–136 (1982)
Lovász, L.: Random walks on graphs: A survey. Combinatorics, Paul Erdös is Eighty 2, 1–46 (1993)
Meila, M., Shi, J.: A random walks view of spectral segmentation. In: Eighth International Workshop on Artificial Intelligence and Statistics (AISTATS) (2001)
Meyerhenke, H., Monien, B., Schamberger, S.: Accelerating shape optimizing load balancing for parallel FEM simulations by algebraic multigrid. In: Proc. 20th IEEE Intl. Parallel and Distributed Processing Symp (IPDPS 2006), p. 57 (CD). IEEE, Los Alamitos (2006)
Nadler, B., Lafon, S., Coifman, R.R., Kevrekidis, I.G.: Diffusion maps, spectral clustering and eigenfunctions of fokker-planck operators. In: NIPS (2005)
Saerens, M., Dupont, P., Fouss, F., Yen, L.: The principal components analysis of a graph, and its relationships to spectral clustering. In: Boulicaut, J.-F., Esposito, F., Giannotti, F., Pedreschi, D. (eds.) ECML 2004. LNCS (LNAI), vol. 3201, pp. 371–383. Springer, Heidelberg (2004)
Schamberger, S.: A shape optimizing load distribution heuristic for parallel adaptive FEM computations. In: Malyshkin, V.E. (ed.) PaCT 2005. LNCS, vol. 3606, pp. 263–277. Springer, Heidelberg (2005)
Shewchuk, J.R.: An introduction to the conjugate gradient method without the agonizing pain. Technical Report CMU-CS-94-125, Carnegie Mellon University (1994)
The BlueGene/L Team. An overview of the BlueGene/L supercomputer. In: Proc. ACM/IEEE Conf. on Supercomputing, pp. 1–22 (2002)
Tishby, N., Slonim, N.: Data clustering by markovian relaxation and the information bottleneck method. In: NIPS, pp. 640–646 (2000)
Trottenberg, U., Oosterlee, C.W., Schüller, A.: Multigrid. Academic Press, London (2000)
van Dongen, S.: Graph Clustering by Flow Simulation. PhD thesis, Univ. of Utrecht (2000)
Xu, C., Lau, F.C.M.: Load Balancing in Parallel Computers. Kluwer, Dordrecht (1997)
Yen, L., Vanvyve, D., Wouters, F., Fouss, F., Verleysen, M., Saerens, M.: Clustering using a random-walk based distance measure. In: ESANN 2005, European Symposium on Artificial Neural Networks (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Meyerhenke, H., Sauerwald, T. (2006). Analyzing Disturbed Diffusion on Networks. In: Asano, T. (eds) Algorithms and Computation. ISAAC 2006. Lecture Notes in Computer Science, vol 4288. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11940128_44
Download citation
DOI: https://doi.org/10.1007/11940128_44
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49694-6
Online ISBN: 978-3-540-49696-0
eBook Packages: Computer ScienceComputer Science (R0)