2018/06/20 by Soumya Sarkar, Sarkar, Soumya, Sandipan Sikdar +5
Biochemistry, Genetics and Molecular Biology · Mathematics · Physics and Astronomy · #Bioinformatics and Genomic Networks #Complex Network Analysis Techniques #FOS: Computer and information sciences #FOS: Physical sciences #Graph theory and applications #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1806.07868
openalex publication_date 2018/06/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Vertices with high betweenness and closeness centrality represent influential\nentities in a network. An important problem for time varying networks is to\nknow a-priori, using minimal computation, whether the influential vertices of\nthe current time step will retain their high centrality, in the future time\nsteps, as the network evolves. In this paper, based on empirical evidences from\nseveral large real world time varying networks, we discover a certain class of\nnetworks where the highly central vertices are part of the innermost core of\nthe network and this property is maintained over time. As a key contribution of\nthis work, we propose novel heuristics to identify these networks in an optimal\nfashion and also develop a two-step algorithm for predicting high centrality\nvertices. Consequently, we show for the first time that for such networks,\nexpensive shortest path computations in each time step as the network changes\ncan be completely avoided; instead we can use time series models (e.g., ARIMA\nas used here) to predict the overlap between the high centrality vertices in\nthe current time step to the ones in the future time steps. Moreover, once the\nnew network is available in time, we can find the high centrality vertices in\nthe top core simply based on their high degree.\n