In a recent work we introduced a problem about finding the highest polarized bipartition on a weighted and labeled graph that represents a debate developed trough some social network, where nodes represent user’s opinions and edges agreement or disagreement between users. Finding this target bipartition is an optimization problem that can be seen as a generalization of the maxcut problem, so we first introduced a basic local search algorithm to find approximate solutions of the problem. In this paper we go one step further, and we present an exact algorithm for finding the optimal solution, based on an integer programming formulation, and compare the performance of a new variant of our local search algorithm with the exact algorithm. Our results show that at least on real instances of the problem, obtained from Reddit debates, the approximate solutions obtained are almost always identical to the optimal solutions.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com