Mixed Integer Programming and LP Rounding for Opinion Maximization on Directed Acyclic Graphs

Po-An Chen; Ya Wen Cheng; Yao Wei Tseng

doi:10.1007/978-3-030-93409-5_71

Mixed Integer Programming and LP Rounding for Opinion Maximization on Directed Acyclic Graphs

Po-An Chen^*, Ya Wen Cheng, Yao Wei Tseng

^*Corresponding author for this work

Institute of Information Management

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

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.

Original language	English
Title of host publication	Complex Networks and Their Applications X - Proceedings of the 10th International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2021
Editors	Rosa Maria Benito, Chantal Cherifi, Hocine Cherifi, Esteban Moro, Luis M. Rocha, Marta Sales-Pardo
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	867-878
Number of pages	12
ISBN (Print)	9783030934088
DOIs	https://doi.org/10.1007/978-3-030-93409-5_71
State	Published - 2022
Event	10th International Conference on Complex Networks and Their Applications, COMPLEX NETWORKS 2021 - Madrid, Spain Duration: 30 Nov 2021 → 2 Dec 2021

Publication series

Name	Studies in Computational Intelligence
Volume	1015
ISSN (Print)	1860-949X
ISSN (Electronic)	1860-9503

Conference

Conference	10th International Conference on Complex Networks and Their Applications, COMPLEX NETWORKS 2021
Country/Territory	Spain
City	Madrid
Period	30/11/21 → 2/12/21

Keywords

Directed acyclic graphs
LP randomized rounding
Mixed integer programming
Opinion maximization

Access to Document

10.1007/978-3-030-93409-5_71

Cite this

Chen, P.-A., Cheng, Y. W., & Tseng, Y. W. (2022). Mixed Integer Programming and LP Rounding for Opinion Maximization on Directed Acyclic Graphs. In R. M. Benito, C. Cherifi, H. Cherifi, E. Moro, L. M. Rocha, & M. Sales-Pardo (Eds.), Complex Networks and Their Applications X - Proceedings of the 10th International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2021 (pp. 867-878). (Studies in Computational Intelligence; Vol. 1015). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-93409-5_71

Chen, Po-An ; Cheng, Ya Wen ; Tseng, Yao Wei. / Mixed Integer Programming and LP Rounding for Opinion Maximization on Directed Acyclic Graphs. Complex Networks and Their Applications X - Proceedings of the 10th International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2021. editor / Rosa Maria Benito ; Chantal Cherifi ; Hocine Cherifi ; Esteban Moro ; Luis M. Rocha ; Marta Sales-Pardo. Springer Science and Business Media Deutschland GmbH, 2022. pp. 867-878 (Studies in Computational Intelligence).

@inproceedings{34a2a519285349aaa6c40507daf5bf7c,

title = "Mixed Integer Programming and LP Rounding for Opinion Maximization on Directed Acyclic Graphs",

abstract = "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.",

keywords = "Directed acyclic graphs, LP randomized rounding, Mixed integer programming, Opinion maximization",

author = "Po-An Chen and Cheng, {Ya Wen} and Tseng, {Yao Wei}",

note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 10th International Conference on Complex Networks and Their Applications, COMPLEX NETWORKS 2021 ; Conference date: 30-11-2021 Through 02-12-2021",

year = "2022",

doi = "10.1007/978-3-030-93409-5_71",

language = "English",

isbn = "9783030934088",

series = "Studies in Computational Intelligence",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "867--878",

editor = "Benito, {Rosa Maria} and Chantal Cherifi and Hocine Cherifi and Esteban Moro and Rocha, {Luis M.} and Marta Sales-Pardo",

booktitle = "Complex Networks and Their Applications X - Proceedings of the 10th International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2021",

address = "德國",

}

Chen, P-A, Cheng, YW & Tseng, YW 2022, Mixed Integer Programming and LP Rounding for Opinion Maximization on Directed Acyclic Graphs. in RM Benito, C Cherifi, H Cherifi, E Moro, LM Rocha & M Sales-Pardo (eds), Complex Networks and Their Applications X - Proceedings of the 10th International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2021. Studies in Computational Intelligence, vol. 1015, Springer Science and Business Media Deutschland GmbH, pp. 867-878, 10th International Conference on Complex Networks and Their Applications, COMPLEX NETWORKS 2021, Madrid, Spain, 30/11/21. https://doi.org/10.1007/978-3-030-93409-5_71

Mixed Integer Programming and LP Rounding for Opinion Maximization on Directed Acyclic Graphs. / Chen, Po-An; Cheng, Ya Wen; Tseng, Yao Wei.
Complex Networks and Their Applications X - Proceedings of the 10th International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2021. ed. / Rosa Maria Benito; Chantal Cherifi; Hocine Cherifi; Esteban Moro; Luis M. Rocha; Marta Sales-Pardo. Springer Science and Business Media Deutschland GmbH, 2022. p. 867-878 (Studies in Computational Intelligence; Vol. 1015).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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

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 -

Chen PA, Cheng YW, Tseng YW. Mixed Integer Programming and LP Rounding for Opinion Maximization on Directed Acyclic Graphs. In Benito RM, Cherifi C, Cherifi H, Moro E, Rocha LM, Sales-Pardo M, editors, Complex Networks and Their Applications X - Proceedings of the 10th International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2021. Springer Science and Business Media Deutschland GmbH. 2022. p. 867-878. (Studies in Computational Intelligence). doi: 10.1007/978-3-030-93409-5_71