کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
427452 686508 2014 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Heuristical top-k: fast estimation of centralities in complex networks
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Heuristical top-k: fast estimation of centralities in complex networks
چکیده انگلیسی

Centrality metrics have proven to be of a major interest when analyzing the structure of networks. Given modern-day network sizes, fast algorithms for estimating these metrics are needed. This paper proposes a computation framework (named Filter-Compute-Extract) that returns an estimate of the top-k most important nodes in a given network. We show that considerable savings in computation time can be achieved by first filtering the input network based on correlations between cheap and more costly centrality metrics. Running the costly metric on the smaller resulting filtered network yields significant gains in computation time. We examine the complexity improvement due to this heuristic for classic centrality measures, as well as experimental results on well-studied public networks.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 114, Issue 8, August 2014, Pages 432–436
نویسندگان
, , ,