BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: Network analysis defines a number of centrality measures to id
entify the most central nodes in a network. Fast computation of those measu
res is a major challenge in algorithmic network analysis. Aside from closen
ess and betweenness\, Katz centrality is one of the established centrality
measures. We consider the problem of computing rankings for Katz centrality
. In particular\, we propose upper and lower bounds on the Katz score of a
given node. While previous approaches relied on numerical approximation or
heuristics to compute Katz centrality rankings\, we construct an algorithm
that iteratively improves those upper and lower bounds until a correct Katz
ranking is obtained. For a certain class of inputs\, this yields an optima
l algorithm for Katz ranking computation. Furthermore\, Experiments demonst
rate that our algorithm outperforms both numerical approaches and heuristic
s with speedups between 1.5x and 3.5x\, depending on the desired quality gu
arantees. Specifically\, we provide efficient parallel CPU and GPU implemen
tations of the algorithms that enable near real-time Katz centrality comput
ation for graphs with hundreds of millions of nodes in fractions of seconds
.
DTSTAMP:20181030T181300
DTSTART:20181105T160000
CLASS:PUBLIC
LOCATION:Humboldt-Universität zu Berlin\n Institut für Informatik\n Room 3.
408 (House 3 / 4th Floor [British Reading])\n Johann von Neumann-Haus\n Rud
ower Chaussee 25\n 12489 Berlin
SEQUENCE:0
SUMMARY:Alexander van der Grinten (Universität zu Köln): Scalable Katz Rank
ing Computation
UID:94302231@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20181105-C-Grinten.html
END:VEVENT
END:VCALENDAR