BEGIN:VCALENDAR
VERSION:2.0
PRODID:ECMLPKDD-MB
BEGIN:VEVENT
DTSTAMP;TZID=Europe/Dublin:20180826T200000
UID:_ecmlpkdd_DAMI-D-17-00417
DTSTART;TZID="Europe/Dublin":20180911T140000
DTEND;TZID="Europe/Dublin":20180911T142000
LOCATION:Hogan Mezz 2
TRANSP:TRANSPARENT
SEQUENCE:1
DESCRIPTION:Vertices with high betweenness and closeness centrality represent in-fluential entities in a network. An important problem for time varying networks isto know a-priori, using minimal computation, whether the influential vertices ofthe current time step will retain their high centrality, in the future time steps, asthe network evolves.In this paper, based on empirical evidences from several large real world time varying networks, we discover a certain class of networks where the highly central vertices are part of the innermost core of the network and this property is maintained over time. As a key contribution of this work, we propose novel heuristics toidentify these networks in an optimal fashion and also develop a two-step algorithm for predicting high centrality vertices. Consequently, we show for the first time that for such networks, expensive shortest path computations in each timestep as the network changes can be completely avoided; instead we can use time series models (e.g., ARIMA as used here) to predict the overlap between the high centrality vertices in the current time step to the ones in the future time steps. Moreover,once the new network is available in time, we can find the high centrality verticesin the top core simply based on their high degree.To measure the effectiveness of our framework, we perform prediction task ona large set of diverse time-varying networks. We obtain F1-scores as high as 0.81 and 0.72 in predicting the top k closeness and betweenness centrality vertices respectively for networks where the highly central vertices mostly reside in the innermost core. We validate our results by showing that the practical effects of our predicted vertices match the effects of the actual high centrality vertices. Finally, we also provide a formal sketch demonstrating why our method works.
SUMMARY:Using Core-Periphery Structure to Predict High Centrality Nodes in Time-Varying Networks
CLASS:PUBLIC
END:VEVENT
END:VCALENDAR