2018/06/19 by Van Sy Mai, Mai, Van Sy, Eyad H. Abed +1
Computer Science · Physics and Astronomy · #Complex Network Analysis Techniques #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #FOS: Mathematics #Opinion Dynamics and Social Influence #Optimization and Control (math.OC) #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1806.07070
openalex publication_date 2018/06/19 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
The paper considers the problem of a leader that seeks to optimally influence the opinions of agents in a directed network through connecting with a limited number of the agents ("direct followers"), possibly in the presence of a fixed competing leader. The settings involving a single leader and two competing leaders are unified into a general combinatoric optimization problem, for which two heuristic approaches are developed. The first approach is based on a convex relaxation scheme, possibly in combination with the ℓ1-norm regularization technique, and the second is based on a greedy selection strategy. The main technical novelties of this work are in the establishment of supermodularity of the objective function and convexity of its continuous relaxation. The greedy approach is guaranteed to have a lower bound on the approximation ratio sharper than (1-1/e), while the convex approach can benefit from efficient (customized) numerical solvers to have practically comparable solutions possibly with faster computation times. The two approaches can be combined to provide improved results. In numerical examples, the approximation ratio can be made to reach 90% or higher depending on the number of direct followers.