An Efficient Local Search Approach for Polarized Community Discovery in Signed Networks

• URL: http://arxiv.org/abs/2502.02197v1
• Date: Tue, 04 Feb 2025 10:22:01 GMT
• Title: An Efficient Local Search Approach for Polarized Community Discovery in Signed Networks
• Authors: Linus Aronsson, Morteza Haghir Chehreghani,
• Abstract summary: We study signed networks, where edges are labeled as positive or negative to indicate friendly or antagonistic interactions. We develop an approach based on Frank-Wolfe optimization, leading to a local search procedure with provable convergence guarantees. Our method is both scalable and efficient, outperforming state-of-the-art baselines in solution quality while remaining competitive in terms of computational efficiency.
• Score: 3.2688425993442696
• License:
• Abstract: Signed networks, where edges are labeled as positive or negative to indicate friendly or antagonistic interactions, offer a natural framework for studying polarization, trust, and conflict in social systems. Detecting meaningful group structures in these networks is crucial for understanding online discourse, political division, and trust dynamics. A key challenge is to identify groups that are cohesive internally yet antagonistic externally, while allowing for neutral or unaligned vertices. In this paper, we address this problem by identifying $k$ polarized communities that are large, dense, and balanced in size. We develop an approach based on Frank-Wolfe optimization, leading to a local search procedure with provable convergence guarantees. Our method is both scalable and efficient, outperforming state-of-the-art baselines in solution quality while remaining competitive in terms of computational efficiency.

Related papers

• Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networks [103.78912399195005]
  Combinatorial optimization (CO) is the fundamental problem at the intersection of computer science, applied mathematics, etc. In this paper, we design a family of non-autoregressive neural networks to solve CO problems under positive linear constraints. We validate the effectiveness of this framework in solving representative CO problems including facility location, max-set covering, and traveling salesman problem.
  arXiv  Detail & Related papers  (2024-09-06T14:58:31Z)
• The Impact of Adversarial Node Placement in Decentralized Federated Learning Networks [6.661122374160369]
  As Federated Learning (FL) grows in popularity, new decentralized frameworks are becoming widespread. This paper analyzes the performance of decentralized FL for various adversarial placement strategies when adversaries can jointly coordinate their placement within a network. We propose a novel attack algorithm that prioritizes adversarial spread over adversarial centrality by maximizing the average network distance between adversaries.
  arXiv  Detail & Related papers  (2023-11-14T06:48:50Z)
• Rebalancing Social Feed to Minimize Polarization and Disagreement [24.939887831898453]
  We propose a novel problem formulation aimed at slightly nudging users' social feeds in order to strike a balance between relevance and diversity. Our approach is based on re-weighting the relative importance of the accounts that a user follows, so as to calibrate the frequency with which the content produced by various accounts is shown to the user.
  arXiv  Detail & Related papers  (2023-08-28T10:59:05Z)
• Network polarization, filter bubbles, and echo chambers: An annotated review of measures and reduction methods [0.0]
  Polarization arises when the underlying network becomes characterized by highly connected groups with weak inter-group connectivity. This work presents an annotated review of network polarization measures and models used to handle the polarization.
  arXiv  Detail & Related papers  (2022-07-27T21:23:27Z)
• One More Step Towards Reality: Cooperative Bandits with Imperfect Communication [15.440053226788562]
  We study cooperative bandit learning under three typical real-world communication scenarios. We propose decentralized algorithms that achieve competitive performance. We present an improved delayed-update algorithm that outperforms the existing state-of-the-art on various network topologies.
  arXiv  Detail & Related papers  (2021-11-24T13:19:11Z)
• Finite-Time Consensus Learning for Decentralized Optimization with Nonlinear Gossiping [77.53019031244908]
  We present a novel decentralized learning framework based on nonlinear gossiping (NGO), that enjoys an appealing finite-time consensus property to achieve better synchronization. Our analysis on how communication delay and randomized chats affect learning further enables the derivation of practical variants.
  arXiv  Detail & Related papers  (2021-11-04T15:36:25Z)
• Unsupervised Domain-adaptive Hash for Networks [81.49184987430333]
  Domain-adaptive hash learning has enjoyed considerable success in the computer vision community. We develop an unsupervised domain-adaptive hash learning method for networks, dubbed UDAH.
  arXiv  Detail & Related papers  (2021-08-20T12:09:38Z)
• Contingency-Aware Influence Maximization: A Reinforcement Learning Approach [52.109536198330126]
  influence (IM) problem aims at finding a subset of seed nodes in a social network that maximize the spread of influence. In this study, we focus on a sub-class of IM problems, where whether the nodes are willing to be the seeds when being invited is uncertain, called contingency-aware IM. Despite the initial success, a major practical obstacle in promoting the solutions to more communities is the tremendous runtime of the greedy algorithms.
  arXiv  Detail & Related papers  (2021-06-13T16:42:22Z)
• Competing Adaptive Networks [56.56653763124104]
  We develop an algorithm for decentralized competition among teams of adaptive agents. We present an application in the decentralized training of generative adversarial neural networks.
  arXiv  Detail & Related papers  (2021-03-29T14:42:15Z)
• Hide and Seek: Outwitting Community Detection Algorithms [17.144388833011536]
  Community affiliation plays an important role in determining a node's contextual position in a network. This study focuses on hiding such sensitive communities so that the community affiliation of the targeted nodes can be concealed. We introduce NEURAL, a novel method that greedily optimize a node-centric objective function to determine the rewiring strategy.
  arXiv  Detail & Related papers  (2021-02-22T03:50:44Z)
• On the use of local structural properties for improving the efficiency of hierarchical community detection methods [77.34726150561087]
  We study how local structural network properties can be used as proxies to improve the efficiency of hierarchical community detection. We also check the performance impact of network prunings as an ancillary tactic to make hierarchical community detection more efficient.
  arXiv  Detail & Related papers  (2020-09-15T00:16:12Z)

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

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.