Estimating nodal spreading influence using partial temporal networks

Abstract

Networks facilitate the spread of information and epidemics. The average number of nodes infected via a spreading process on a network starting from a single seed node over a given long period is called the influence of that node. Estimating nodal influence early in time is essential for the epidemic/misinformation mitigation. Influence estimation has been investigated in static networks, which identifies the relation between topological properties of a node and its influence and assumes the networks are completely known. However, the networks underlying spreading processes such as social interactions are not static but temporal networks, whose links are activated or deactivated over time. When predicting nodal influence in the long-term future, the temporal network is usually only observable till the time of prediction and only locally around the node due to data accessibility. To bridge this gap, we address the question of how to utilize the partially observed temporal network (local and of short duration) around each node, to estimate the ranking of nodes in spreading influence on the full network over a long period. This would also enable us to understand which network properties of a node, in its partially observed temporal network determine its influence. Centrality metrics (nodal properties) have been proposed recently in temporal networks. However, using such a metric derived for each node from its partial network to estimate the ranking of nodes in influence is likely to be limiting. This is because the spread of information is possibly through any time-respecting path, beyond the shortest time-respecting path considered by existing metrics. To address this disparity, we systematically propose a set of novel nodal centrality metrics that encode diverse properties of (time-respecting) walks to predict nodal influence rankings. The proposed metrics derived from partial network information, in general, outperform classic centrality metrics utilizing either full or partial temporal network information. It is found that distinct centrality metrics perform the best depending on the infection probability of the spreading process. For a broad range of the infection probability, a node tends to be influential if it can reach many distinct nodes via time-respecting walks and if these nodes can be reached early in time.