SCHEDULE: NOV 12-18, 2011

When viewing the Technical Program schedule, on the far righthand side is a column labeled "PLANNER." Use this planner to build your own schedule. Once you select an event and want to add it to your personal schedule, just click on the calendar icon of your choice (outlook calendar, ical calendar or google calendar) and that event will be stored there. As you select events in this manner, you will have your own schedule to guide you through the week.

You can also create your personal schedule on the SC11 app (Boopsie) on your smartphone. Simply select a session you want to attend and "add" it to your plan. Continue in this manner until you have created your own personal schedule. All your events will appear under "My Event Planner" on your smartphone.

A Scalable Group Testing Based Algorithm for Finding d-highest Betweenness Centrality Vertices in Large Scale Networks

SESSION: ACM Student Research Competition Poster Session

EVENT TYPE: ACM Student Research Competition Poster

TIME: 5:15PM - 7:00PM

SESSION CHAIR: Bernd Mohr

AUTHOR(S):Vladimir V. Ufimtsev

ROOM:WSCC North Galleria 2nd/3rd Floors

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.

Chair/Author Details:

Bernd Mohr (Chair) - Juelich Supercomputing Centre

Vladimir V. Ufimtsev - University of Nebraska-Omaha

  Click here to download .ics calendar file

  Click here to download .vcs calendar file

  Click here to add event to your Google Calendar