Logo des Repositoriums
 

Scaling up network centrality computations – A brief overview

dc.contributor.authorGrinten, Alexander van der
dc.contributor.authorAngriman, Eugenio
dc.contributor.authorMeyerhenke, Henning
dc.date.accessioned2021-06-21T09:38:45Z
dc.date.available2021-06-21T09:38:45Z
dc.date.issued2020
dc.description.abstractNetwork science methodology is increasingly applied to a large variety of real-world phenomena, often leading to big network data sets. Thus, networks (or graphs) with millions or billions of edges are more and more common. To process and analyze these data, we need appropriate graph processing systems and fast algorithms. Yet, many analysis algorithms were pioneered on small networks when speed was not the highest concern. Developing an analysis toolkit for large-scale networks thus often requires faster variants, both from an algorithmic and an implementation perspective. In this paper we focus on computational aspects of vertex centrality measures. Such measures indicate the (relative) importance of a vertex based on the position of the vertex in the network. We describe several common (and some recent and thus less established) measures, optimization problems in their context as well as algorithms for an efficient solution of the raised problems. Our focus is on (not necessarily exact) performance-oriented algorithmic techniques that enable significantly faster processing than the previous state of the art – often allowing to process massive data sets quickly and without resorting to distributed graph processing systems.en
dc.identifier.doi10.1515/itit-2019-0032
dc.identifier.pissn2196-7032
dc.identifier.urihttps://dl.gi.de/handle/20.500.12116/36571
dc.language.isoen
dc.publisherDe Gruyter
dc.relation.ispartofit - Information Technology: Vol. 62, No. 3-4
dc.subjectbig graph data analytics
dc.subjectcentrality measures
dc.subjectscalable graph algorithms
dc.titleScaling up network centrality computations – A brief overviewen
dc.typeText/Journal Article
gi.citation.endPage204
gi.citation.publisherPlaceBerlin
gi.citation.startPage189

Dateien