DE STERCK, Hans; HENSON, Van Emden; SANDERS, Geoffrey
April 2011
Computing & Informatics;2011, Vol. 30 Issue 2, p225
Academic Journal
We describe multilevel aggregation in the specific context of using Markov chains to rank the nodes of graphs. More generally, aggregation is a graph coarsening technique that has a wide range of possible uses regarding information retrieval applications. Aggregation successfully generates efficient multilevel methods for solving nonsingular linear systems and various eigenproblems from discretized partial differential equations, which tend to involve mesh-like graphs. Our primary goal is to extend the applicability of aggregation to similar problems on small-world graphs, with a secondary goal of developing these methods for eventual applicability towards many other tasks such as using the information in the hierarchies for node clustering or pattern recognition. The nature of small-world graphs makes it difficult for many coarsening approaches to obtain useful hierarchies that have complexity on the order of the number of edges in the original graph while retaining the relevant properties of the original graph. Here, for a set of synthetic graphs with the small-world property, we show how multilevel hierarchies formed with nonoverlapping strength-based aggregation have optimal or near optimal complexity. We also provide an example of how these hierarchies are employed to accelerate convergence of methods that calculate the stationary probability vector of large, sparse, irreducible, slowly-mixing Markov chains on such small-world graphs. The stationary probability vector of a Markov chain allows one to rank the nodes in a graph based on the likelihood that a long random walk visits each node. These ranking approaches have a wide range of applications including information retrieval and web ranking, performance modeling of computer and communication systems, analysis of social networks, dependability and security analysis, and analysis of biological systems [19].


Related Articles

  • Uncovering and Testing the Fuzzy Clusters Based on Lumped Markov Chain in Complex Network. Jing, Fan; Jianbin, Xie; Jinlong, Wang; Jinshuai, Qu // PLoS ONE;Dec2013, Vol. 8 Issue 12, p1 

    Identifying clusters, namely groups of nodes with comparatively strong internal connectivity, is a fundamental task for deeply understanding the structure and function of a network. By means of a lumped Markov chain model of a random walker, we propose two novel ways of inferring the lumped...

  • Fleming-Viot processes: two explicit examples. Cloez, Bertrand; Thai, Marie-Noémie // ALEA. Latin American Journal of Probability & Mathematical Stati;2016, Vol. 13, p337 

    The purpose of this paper is to extend the investigation of the Fleming- Viot process in discrete space started in a previous work to two specific examples. The first one corresponds to a random walk on the complete graph. Due to its geometry, we establish several explicit and optimal formulas...

  • Weighted Mean of a Pair of Graphs. Bunke, H.; Günter, S. // Computing;2001, Vol. 67 Issue 3, p209 

    Graph matching and graph edit distance are fundamental concepts in structural pattern recognition. In this paper, the weighted mean of a pair of graphs is introduced. Given two graphs, G and G′, with d(G, G′) being the edit distance of G and G′, the weighted mean of G and...

  • Occupation time Markov property for countable Markov chains with respect to several states. Vorotov, A. A. // Vestnik Sankt-Peterburgskogo universiteta, Seriia 7: Geologia, G;2013, Issue 4, p30 

    No abstract available.

  • Occupation time Markov property for countable Markov chains with respect to several states. Vorotov, A. A. // Vestnik Sankt-Peterburgskogo universiteta, Seriia 7: Geologia, G;2013, Issue 4, p160 

    No abstract available.

  • Internal Diffusion Limited Aggregation on Discrete Groups Having Exponential Growth. Blachère, Sébastien; Brofferio, Sara // Probability Theory & Related Fields;Mar2007, Vol. 137 Issue 3/4, p323 

    The internal diffusion limited aggregation (DLA) has been introduced by Diaconis and Fulton [Rend. Sem. Mat. Univ. Pol. Torino 49, 95–119 (1991)]. It is a growth model defined on an infinite set and associated to a Markov chain on this set. We focus here on sets which are finitely...

  • A random environment for linearly edge-reinforced random walks on infinite graphs. Merkl, Franz; Rolles, Silke W. W. // Probability Theory & Related Fields;May2007, Vol. 138 Issue 1/2, p157 

    We consider linearly edge-reinforced random walk on an arbitrary locally finite connected graph. It is shown that the process has the same distribution as a mixture of reversible Markov chains, determined by time-independent strictly positive weights on the edges. Furthermore, we prove bounds...

  • Total progeny in killed branching random walk. Addario-Berry, L.; Broutin, N. // Probability Theory & Related Fields;Jul2011, Vol. 151 Issue 1/2, p265 

    We consider a branching random walk for which the maximum position of a particle in the n'th generation, R, has zero speed on the linear scale: R/ n → 0 as n → ∞. We further remove ('kill') any particle whose displacement is negative, together with its entire descendence. The...

  • Infinite volume limit of the Abelian sandpile model in dimensions d ≥ 3. Járai, Antal A.; Redig, Frank // Probability Theory & Related Fields;May2008, Vol. 141 Issue 1/2, p181 

    We study the Abelian sandpile model on $${\mathbb{Z}}^{d}$$ . In d ≥ 3 we prove existence of the infinite volume addition operator, almost surely with respect to the infinite volume limit μ of the uniform measures on recurrent configurations. We prove the existence of a Markov process...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics