Exploring the gravitational model for ranking influential nodes in directed acyclic networks

Abstract In Social Network Analysis (SNA), the application of Directed Acyclic Graphs (DAGs) provides unique opportunities to explore structures where relationships have direction and do not form cycles, such as citation networks and organizational hierarchies. Recently, the gravitational model has gained recognition as an effective method for identifying influential spreaders within complex networks, a problem of relevance in SNA. While there have been numerous investigations into the gravitational model in undirected and cyclic graphs, the unique challenges and dynamics associated with DAGs have yet to be fully explored. In this study, we conduct a comprehensive analysis of the gravitational model for ranking nodes in DAGs. First, we introduce an efficient linear-time algorithm specifically designed to compute the gravitational index of nodes in large-scale DAGs. Next, using thousands of synthetic and empirical DAGs, we compare the impact of the gravitational index on the accuracy and resolution of node rankings across different mass indexes. We then examine how DAG structural properties influence the monotonicity of node rankings, with a particular focus on the k-shell index. We find that, in DAGs, the gravitational formula effectively enhances the monotonicity of k-shell centrality, though it is less effective for other types of centrality indexes. We also find that smaller, shorter, and highly centralized DAGs exhibit low ranking resolution across all centrality indexes examined in this study, including the gravity-based ones. Despite this challenge, our results demonstrate that the application of gravity-based models improves the ranking accuracy of several centrality measures across most of the studied DAG datasets.