Maximizing the influence of a social network users' coalition based on approximated centrality metrics and a greedy algorithm
Abstract
Maximizing the influence of a social network users' coalition based on approximated centrality metrics and a greedy algorithm
Incoming article date: 11.11.2025This paper examines the problem of assessing the influence of social network users and their groups in disseminating information among audiences. Forming a network of user subsets to initiate informational influence is a computationally complex problem with a stochastically uncertain outcome. Existing centrality metrics typically involve searching for all shortest paths in a graph or solving large-scale systemic sources. This paper provides approximate estimates of the influence of individual network participants and their subsets, based on modifications of the Flageolet-Martin algorithm. A greedy algorithm based on electronic metrics is also proposed, enabling coalition formation by iteratively supplementing it with quasi-optimal elements. The obtained results can be applied to problems of information analysis, forecasting, and planning in social networks.
Keywords: Social network, informational influence, coalition, influence, connection graph, centrality metric, closeness centrality, shortest path, route, approximate estimate, greedy algorithm