A Survey on Graph Centrality Analysis

PhD Qualifying Examination


Title: "A Survey on Graph Centrality Analysis"

by

Mr. Lipeng WANG


Abstract:

A wide range of real-world datasets are stored as graphs. To have a better 
understanding of the structures of these graphs, researchers have proposed 
many algorithms to perform graph analysis. Graph centrality analysis is 
one of these algorithms, which computes the importance of each vertex in a 
graph. For example, people in a social network such as Twitter and 
Facebook can be regarded as vertices and the relations among people can be 
treated as edges. In such a graph, centrality algorithms can identify 
influential people based on various measures. To cope with the dramatic 
growth in graph size, efficient centrality algorithm implementations have 
been developed in recent years. In this survey, we discuss the 
implementations of three of the most popular centrality metrics: degree 
centrality, closeness centrality and betweenness centrality on modern 
hardware, including GPUs and many-core CPUs. We also discuss the single 
source shortest path (SSSP) algorithm, which is the building block of many 
centrality analysis algorithms. Additionally, we review a distributed 
graph processing model called GAS (Gather-Apply-Scatter). Finally, we 
outline potential optimization strategies, such as using wider SIMD 
instructions and enabling multi-source shortest path computation in a 
computer cluster.


Date:			Thursday, 14 December 2017

Time:                  	10:00am - 12:00noon

Venue:                  Room 5501
                         Lifts 25/26

Committee Members:	Dr. Qiong Luo (Supervisor)
 			Dr. Wei Wang (Chairperson)
 			Prof. Lei Chen
 			Dr. Ke Yi


**** ALL are Welcome ****