Fast Geometric Embedding for Node Influence Maximization
This provides a scalable solution for network analysis tasks like influence maximization, though it is incremental as it builds on existing embedding and centrality methods.
The paper tackles the computational expense of classical centrality measures on large-scale graphs by introducing an efficient force layout algorithm that embeds graphs into a low-dimensional space, using radial distance as a proxy for centrality, and demonstrates strong correlations with measures like degree and PageRank while enabling fast and scalable node influence maximization.
Computing classical centrality measures such as betweenness and closeness is computationally expensive on large-scale graphs. In this work, we introduce an efficient force layout algorithm that embeds a graph into a low-dimensional space, where the radial distance from the origin serves as a proxy for various centrality measures. We evaluate our method on multiple graph families and demonstrate strong correlations with degree, PageRank, and paths-based centralities. As an application, it turns out that the proposed embedding allows to find high-influence nodes in a network, and provides a fast and scalable alternative to the standard greedy algorithm.