HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Computing the Probability Vectors for Random Walks on Graphs with Bounded Arboricity

Gaurav Goel 1, 2
1 ALGORILLE - Algorithms for the Grid
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : The problem of detecting dense subgraphs (\emph{communities}) in large sparse graphs is inherent to many real world domains like social networking. A popular approach of detecting these communities involves first computing the \emph{probability~vectors} for \emph{random~walks} on the graph for a fixed number of steps, and then using these probability vectors to detect the communities. Such an approach has been discussed by Latapy and Pons in \cite{latapypons}. They compute the probability vectors using simple matrix multiplication and define a measure of the structural similarity between vertices which they call \emph{distance}. Based on the probability vectors, they compute the distances between vertices and then based on these distances group the vertices into communities. Their algorithm takes $O(n^2\log n)$ time where $n$ is the number of vertices in the graph. We focus on the first part of the approach i.e. computation of the probability vectors for the random walks, and propose a more efficient algorithm (than matrix multiplication) for computing these vectors in time complexity that is linear in the size of the output.
Complete list of metadata

Cited literature [5 references]  Display  Hide  Download

Contributor : Jens Gustedt Connect in order to contact the contributor
Submitted on : Friday, November 4, 2005 - 9:58:31 AM
Last modification on : Friday, February 26, 2021 - 3:28:02 PM
Long-term archiving on: : Tuesday, September 11, 2012 - 12:41:18 PM


  • HAL Id : inria-00000578, version 1



Gaurav Goel. Computing the Probability Vectors for Random Walks on Graphs with Bounded Arboricity. [Internship report] 2005. ⟨inria-00000578⟩



Record views


Files downloads