  Identifying the most influential nodes in information networks has been the
focus of many research studies. This problem has crucial applications in
various contexts, such as controlling the propagation of viruses or rumours in
real-world networks. While existing approaches mostly rely on the structural
properties of networks and generate static rankings, in this work we propose a
novel method that is responsive to any change in the diffusion dynamics. The
main idea is to approximate the influential ability (influentiality) of a node
with the reachability of other nodes from that node in a set of random
sub-graphs. To this end, several random sub-graphs are sampled from the
original network and then a hyper-graph is created in which each sub-graph is
represented with a hyper-edge. From a theoretical standpoint, one can argue
that a factor of the degree of nodes in the hyper-graph approximates
influentiality. From an empirical perspective, the proposed model not only
achieves the highest correlation with the ground-truth ranking, but also the
ranking generated by this method hits the highest level of uniqueness and
uniformity. Theoretical and practical analysis of the running time of this
method also confirms a competitive running time compared with state-of-the-art
methods.
