Related papers: On the Complexity of the Bipartite Polarization Problem: from Neutral to Highly Polarized Discussions

On the Complexity of the Bipartite Polarization Problem: from Neutral to Highly Polarized Discussions

URL: http://arxiv.org/abs/2307.11621v1
Date: Fri, 21 Jul 2023 14:40:41 GMT
Title: On the Complexity of the Bipartite Polarization Problem: from Neutral to Highly Polarized Discussions
Authors: Teresa Alsinet, Josep Argelich, Ram\'on B\'ejar and Santi Mart\'inez
Abstract summary: The Bipartite Polarization Problem is an optimization problem where the goal is to find the highest polarized bipartition on a weighted and labelled graph. We introduce an instance generation model where a single parameter controls the polarization of the instances in such a way that this correlates with the average complexity to solve those instances.
Score: 1.5675763601034223
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The Bipartite Polarization Problem is an optimization problem where the goal is to find the highest polarized bipartition on a weighted and labelled graph that represents a debate developed through some social network, where nodes represent user's opinions and edges agreement or disagreement between users. This problem can be seen as a generalization of the maxcut problem, and in previous work approximate solutions and exact solutions have been obtained for real instances obtained from Reddit discussions, showing that such real instances seem to be very easy to solve. In this paper, we investigate further the complexity of this problem, by introducing an instance generation model where a single parameter controls the polarization of the instances in such a way that this correlates with the average complexity to solve those instances. The average complexity results we obtain are consistent with our hypothesis: the higher the polarization of the instance, the easier is to find the corresponding polarized bipartition.

Related papers

How many classifiers do we need? [50.69951049206484]
We provide a detailed analysis of how the disagreement and the polarization among classifiers relate to the performance gain achieved by aggregating individual classifiers. We prove results for the behavior of the disagreement in terms of the number of classifiers. Our theories and claims are supported by empirical results on several image classification tasks with various types of neural networks.
arXiv Detail & Related papers (2024-11-01T02:59:56Z)
PARTNER: Level up the Polar Representation for LiDAR 3D Object Detection [81.16859686137435]
We present PARTNER, a novel 3D object detector in the polar coordinate. Our method outperforms the previous polar-based works with remarkable margins of 3.68% and 9.15% on and ONCE validation set.
arXiv Detail & Related papers (2023-08-08T01:59:20Z)
Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
arXiv Detail & Related papers (2023-06-21T17:03:22Z)
Approximating a RUM from Distributions on k-Slates [88.32814292632675]
We find a generalization-time algorithm that finds the RUM that best approximates the given distribution on average. Our theoretical result can also be made practical: we obtain a that is effective and scales to real-world datasets.
arXiv Detail & Related papers (2023-05-22T17:43:34Z)
The star-shaped space of solutions of the spherical negative perceptron [4.511197686627054]
We show that low-energy configurations are often found in complex connected structures. We identify a subset of atypical high-margin connected with most other solutions.
arXiv Detail & Related papers (2023-05-18T00:21:04Z)
PolarMask++: Enhanced Polar Representation for Single-Shot Instance Segmentation and Beyond [47.518550130850755]
PolarMask reformulates the instance segmentation problem as predicting the contours of objects in the polar coordinate. Two modules are carefully designed (i.e. soft polar centerness and polar IoU loss) to sample high-quality center examples. PolarMask is fully convolutional and can be easily embedded into most off-the-shelf detection methods.
arXiv Detail & Related papers (2021-05-05T16:55:53Z)
Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem [12.098400820502635]
We consider the Spanning Tree (MST) problem in a single- and multi-objective version. We introduce a biased mutation, which puts more emphasis on the selection of edges of low rank in terms of low domination number. We show that a combined mutation operator which decides for unbiased or biased edge selection exhibits an upper bound -- as unbiased mutation -- in the worst case.
arXiv Detail & Related papers (2020-04-22T07:47:00Z)
Joint Wasserstein Distribution Matching [89.86721884036021]
Joint distribution matching (JDM) problem, which aims to learn bidirectional mappings to match joint distributions of two domains, occurs in many machine learning and computer vision applications. We propose to address JDM problem by minimizing the Wasserstein distance of the joint distributions in two domains. We then propose an important theorem to reduce the intractable problem into a simple optimization problem, and develop a novel method to solve it.
arXiv Detail & Related papers (2020-03-01T03:39:00Z)
On the Sample Complexity and Optimization Landscape for Quadratic Feasibility Problems [7.722592882475735]
We consider the problem of recovering a complex vector $mathbfxin mathbbCn$ from $mangle A-imathbfx, mathbfxr_i=1m arbitrary. In general, not only is the the quadratic problem NP-hard to solve, but it may in fact be unidentifiable.
arXiv Detail & Related papers (2020-02-04T00:35:09Z)
Searching for polarization in signed graphs: a local spectral approach [16.384728228938574]
This paper formulates the problem of finding local polarized communities in signed graphs as a locally-biased eigen-problem. We show that the locally-biased vector can be used to find communities with approximation guarantee with respect to a local analogue of the Cheeger constant on signed graphs.
arXiv Detail & Related papers (2020-01-26T06:30:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.