2015 AnEvaluationofParallelEccentric

• (Shun, 2015) ⇒ Julian Shun. (2015). “An Evaluation of Parallel Eccentricity Estimation Algorithms on Undirected Real-World Graphs.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783333

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222015%22+An+Evaluation+of+Parallel+Eccentricity+Estimation+Algorithms+on+Undirected+Real-World+Graphs
• http://dl.acm.org/citation.cfm?id=2783258.2783333&preflayout=flat#citedby

Quotes

Author Keywords

• Approximation; data mining; estimation; graph diameter; graph eccentricity; graph radius; parallel algorithms; parallel programming; real-world graphs

Abstract

This paper presents efficient shared-memory parallel implementations and the first comprehensive experimental study of graph eccentricity estimation algorithms in the literature. The implementations include (1) a simple algorithm based on executing two-pass breadth-first searches from a sample of vertices, (2) algorithms with sub-quadratic worst-case running time for sparse graphs and non-trivial approximation guarantees that execute breadth-first searches from a carefully chosen set of vertices, (3) algorithms based on probabilistic counters, and (4) a well-known 2-approximation algorithm that executes one breadth-first search per connected component. Our experiments on large undirected real-world graphs show that the algorithm based on two-pass breadth-first searches works surprisingly well, outperforming the other algorithms in terms of running time and/or accuracy by up to orders of magnitude. The high accuracy, efficiency, and parallelism of our best implementation allows the fast generation of eccentricity estimates for large graphs, which are useful in many applications arising in large-scale network analysis.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 AnEvaluationofParallelEccentric	Julian Shun			An Evaluation of Parallel Eccentricity Estimation Algorithms on Undirected Real-World Graphs				10.1145/2783258.2783333		2015