Conference proceeding
The self-avoiding walk-jump (SAWJ) algorithm for finding maximum degree nodes in large graphs
2016 IEEE International Conference on Big Data (Big Data), pp 142-149
Dec 2016
Abstract
In this paper we present a self-avoiding walk-jump (SAWJ) algorithm for finding a maximum degree node on a large assortative graph. We offer two contributions: i) we use the theory of absorbing Markov chains to effectively approximate the required search time as a function of the number of nodes, the edge density, and the assortativity, and ii) we measure the performance of our algorithm against competing algorithms (including star sampling) from the literature on the class of assortative Erdos-Renyi (AER) random graphs, and on six real-world large graphs from the Stanford SNAP dataset. In most cases SAWJ significantly outperforms the competing algorithms.
Metrics
4 Record Views
2 citations in Scopus
Details
- Title
- The self-avoiding walk-jump (SAWJ) algorithm for finding maximum degree nodes in large graphs
- Creators
- Jonathan Stokes - Drexel UniversitySteven Weber - Drexel University
- Publication Details
- 2016 IEEE International Conference on Big Data (Big Data), pp 142-149
- Publisher
- IEEE
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Electrical and Computer Engineering
- Scopus ID
- 2-s2.0-85015215156
- Other Identifier
- 991019170413904721