BEGIN:VCALENDAR
PRODID:-//Microsoft Corporation//Outlook MIMEDIR//EN
VERSION:1.0
BEGIN:VEVENT
DTSTART:20111116T011500Z
DTEND:20111116T030000Z
LOCATION:WSCC North Galleria 2nd/3rd Floors
DESCRIPTION;ENCODING=QUOTED-PRINTABLE:ABSTRACT: We present a group testing approach to identify the first d vertices with the highest betweenness centrality. Betweenness centrality (BC) of a vertex is the ratio of shortest paths that pass through it and is an important metric in complex networks. The Brandes algorithm computes the BC cumulatively over all vertices. Approximate BC of a single vertex can be computed by selective vertex sampling. However, applications such as community detection require only the vertices with the first few highest BC values, which are not known a-priori. In our method we sample a set of vertices and compute their combined BC. It can be shown that for small values of d, the number of tests required to find the d-highest BC vertices is logarithmic in the total number of vertices. Our algorithm is highly scalable since the samples are independently selected and therefore each test can be performed in parallel.
SUMMARY:A Scalable Group Testing Based Algorithm for Finding d-highest Betweenness Centrality Vertices in Large Scale Networks
PRIORITY:3
END:VEVENT
END:VCALENDAR