TY - GEN
T1 - Mixed Integer Programming and LP Rounding for Opinion Maximization on Directed Acyclic Graphs
AU - Chen, Po-An
AU - Cheng, Ya Wen
AU - Tseng, Yao Wei
N1 - Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2022
Y1 - 2022
N2 - Gionis et al. have already proposed a greedy algorithm and some heuristics for the opinion maximization problem. Unlike their approach, we adopt mathematical programming to solve the opinion maximization problem on specific classes of networks. We find that on directed acyclic graphs, opinion influence between nodes will not cycle, but would spread outwards from influencers. Based on such an insight, we model the problem as a mixed integer programming (MIP) problem and relax the MIP to a linear program (LP). With MIP, we obtain optimal solutions for the opinion maximization problem and derive approximation solutions with LP randomized rounding algorithms. We conduct experiments for one LP randomized rounding algorithm and give an analysis of the approximation ratio for the other LP randomized rounding algorithm.
AB - Gionis et al. have already proposed a greedy algorithm and some heuristics for the opinion maximization problem. Unlike their approach, we adopt mathematical programming to solve the opinion maximization problem on specific classes of networks. We find that on directed acyclic graphs, opinion influence between nodes will not cycle, but would spread outwards from influencers. Based on such an insight, we model the problem as a mixed integer programming (MIP) problem and relax the MIP to a linear program (LP). With MIP, we obtain optimal solutions for the opinion maximization problem and derive approximation solutions with LP randomized rounding algorithms. We conduct experiments for one LP randomized rounding algorithm and give an analysis of the approximation ratio for the other LP randomized rounding algorithm.
KW - Directed acyclic graphs
KW - LP randomized rounding
KW - Mixed integer programming
KW - Opinion maximization
UR - http://www.scopus.com/inward/record.url?scp=85122540154&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-93409-5_71
DO - 10.1007/978-3-030-93409-5_71
M3 - Conference contribution
AN - SCOPUS:85122540154
SN - 9783030934088
T3 - Studies in Computational Intelligence
SP - 867
EP - 878
BT - Complex Networks and Their Applications X - Proceedings of the 10th International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2021
A2 - Benito, Rosa Maria
A2 - Cherifi, Chantal
A2 - Cherifi, Hocine
A2 - Moro, Esteban
A2 - Rocha, Luis M.
A2 - Sales-Pardo, Marta
PB - Springer Science and Business Media Deutschland GmbH
T2 - 10th International Conference on Complex Networks and Their Applications, COMPLEX NETWORKS 2021
Y2 - 30 November 2021 through 2 December 2021
ER -