Optimizing Leader Influence in Networks Through Selection of Direct Followers

DOI10.1109/TAC.2018.2850287zbMATH Open1482.91166arXiv1806.07070OpenAlexW2963830476WikidataQ129610499 ScholiaQ129610499MaRDI QIDQ4629892FDOQ4629892

Authors: Van Sy Mai, Eyad H. Abed 

Publication date: 28 March 2019

Published in: IEEE Transactions on Automatic Control (Search for Journal in Brave)

Abstract: 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 $el{l}_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\mathrm{\%}$ or higher depending on the number of direct followers.

Full work available at URL: https://arxiv.org/abs/1806.07070

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Approximation algorithms (68W25)

Cited In (4)

• A first hitting time approach to finding effective spreaders in a network
• Edge Deletion Algorithms for Minimizing Spread in SIR Epidemic Models
• A Dominating Set Based Approach to Identify Effective Leader Group of Social Network
• Joint Centrality Distinguishes Optimal Leaders in Noisy Networks

This page was built for publication: Optimizing Leader Influence in Networks Through Selection of Direct Followers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4629892)