Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс: http://elar.urfu.ru/handle/10995/75633
Название: Heuristic Algorithm for Approximation Betweenness Centrality Using Graph Coarsening
Авторы: Chernoskutov, M.
Ineichen, Y.
Bekas, C.
Дата публикации: 2015
Издатель: Elsevier B.V.
Библиографическое описание: Chernoskutov M. Heuristic Algorithm for Approximation Betweenness Centrality Using Graph Coarsening / M. Chernoskutov, Y. Ineichen, C. Bekas // Procedia Computer Science. — 2015. — Vol. 66. — P. 83-92.
Аннотация: Nowadays, graph analytics are widely used in many research fields and applications. One important analytic that measures the influence of each vertex on flows through the network, is the betweenness centrality. It is used to analyze real-world networks like for example social networks and networks in computational biology. Unfortunately this centrality metric is rather expensive to compute and there is a number of studies devoted to approximate it. Here we focus on approximating the computation of betweenness centrality for dynamically changing graphs. We present a novel approach based on graph coarsening for approximating values of betweenness centrality, when new edges are inserted. Unlike other approaches, we reduce the cost (but not complexity) of the betweenness centrality computation step by working on a coarser graph. Our approach demonstrates more than 60% speedup compared to the exact recalculation of the betweenness centrality for dynamically changing graphs. © 2015 The Authors.
Ключевые слова: APPROXIMATE COMPUTATION
BETWEENNESS CENTRALITY
GRAPH ALGORITHMS
ALGORITHMS
BIOINFORMATICS
COMPLEX NETWORKS
HEURISTIC ALGORITHMS
APPROXIMATE COMPUTATION
BETWEENNESS CENTRALITY
COMPUTATION STEPS
COMPUTATIONAL BIOLOGY
GRAPH ALGORITHMS
GRAPH COARSENING
REAL-WORLD NETWORKS
RESEARCH FIELDS
APPROXIMATION ALGORITHMS
URI: http://elar.urfu.ru/handle/10995/75633
Условия доступа: info:eu-repo/semantics/openAccess
cc-by-nc-nd
gold
Конференция/семинар: 4th International Young Scientist Conference on Computational Science, 2015
Дата конференции/семинара: 25 June 2015 through 25 June 2015
Идентификатор SCOPUS: 84962648734
Идентификатор WOS: 000373782500010
Идентификатор PURE: 785056
ISSN: 1877-0509
DOI: 10.1016/j.procs.2015.11.011
Располагается в коллекциях:Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC

Файлы этого ресурса:
Файл Описание РазмерФормат 
2-s2.0-84962648734.pdf323,42 kBAdobe PDFПросмотреть/Открыть


Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.