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

• URL: http://arxiv.org/abs/2502.02197v2
• Date: Sat, 05 Jul 2025 12:39:26 GMT
• Title: An Efficient Local Search Approach for Polarized Community Discovery in Signed Networks
• Authors: Linus Aronsson, Morteza Haghir Chehreghani,
• Abstract summary: We propose a method for identifying $k$ polarized communities.<n>We introduce a novel optimization objective that avoids size-imbalanced solutions.<n> Experiments on real-world and synthetic datasets demonstrate that our method consistently outperforms state-of-the-art baselines in solution quality.
• Score: 3.2688425993442696
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Signed networks, where edges are labeled as positive or negative to represent friendly or antagonistic interactions, offer a natural framework for analyzing polarization, trust, and conflict in social systems. Detecting meaningful group structures in such networks is crucial for understanding online discourse, political divisions, and trust dynamics. A key challenge is to identify communities that are internally cohesive and externally antagonistic, while allowing for neutral or unaligned vertices. In this paper, we propose a method for identifying $k$ polarized communities that addresses a major limitation of prior methods: their tendency to produce highly size-imbalanced solutions. We introduce a novel optimization objective that avoids such imbalance. In addition, it is well known that approximation algorithms based on local search are highly effective for clustering signed networks when neutral vertices are not allowed. We build on this idea and design the first local search algorithm that extends to the setting with neutral vertices while scaling to large networks. By connecting our approach to block-coordinate Frank-Wolfe optimization, we prove a linear convergence rate, enabled by the structure of our objective. Experiments on real-world and synthetic datasets demonstrate that our method consistently outperforms state-of-the-art baselines in solution quality, while remaining competitive in 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)
• Asymmetrically Decentralized Federated Learning [22.21977974314497]
  Decentralized Federated Learning (DFL) has emerged, which discards the server with a peer-to-peer (P2P) communication framework. This paper proposes DFedSGPSM algorithm, which is based on asymmetric topologies and utilizes the Push- Aware protocol.
  arXiv  Detail & Related papers  (2023-10-08T09:46:26Z)
• Adaptive Consensus: A network pruning approach for decentralized optimization [0.5432724320036953]
  We consider network-based decentralized optimization problems, where each node in the network possesses a local function. The objective is to collectively attain a consensus solution that minimizes the sum of all the local functions. We propose an adaptive randomized communication-efficient algorithmic framework that reduces the volume of communication.
  arXiv  Detail & Related papers  (2023-09-06T00:28:10Z)
• 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)
• Networked Communication for Decentralised Agents in Mean-Field Games [59.01527054553122]
  We introduce networked communication to the mean-field game framework. We prove that our architecture has sample guarantees bounded between those of the centralised- and independent-learning cases.
  arXiv  Detail & Related papers  (2023-06-05T10:45:39Z)
• 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)
• Large-Scale Sequential Learning for Recommender and Engineering Systems [91.3755431537592]
  In this thesis, we focus on the design of an automatic algorithms that provide personalized ranking by adapting to the current conditions. For the former, we propose novel algorithm called SAROS that take into account both kinds of feedback for learning over the sequence of interactions. The proposed idea of taking into account the neighbour lines shows statistically significant results in comparison with the initial approach for faults detection in power grid.
  arXiv  Detail & Related papers  (2022-05-13T21:09:41Z)
• 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)
• SSSNET: Semi-Supervised Signed Network Clustering [4.895808607591299]
  We introduce a novel probabilistic balanced normalized cut loss for training nodes in a GNN framework for semi-supervised signed network clustering, called SSSNET. The main novelty approach is a new take on the role of social balance theory for signed network embeddings.
  arXiv  Detail & Related papers  (2021-10-13T10:36:37Z)
• 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)
• Learning Connectivity of Neural Networks from a Topological Perspective [80.35103711638548]
  We propose a topological perspective to represent a network into a complete graph for analysis. By assigning learnable parameters to the edges which reflect the magnitude of connections, the learning process can be performed in a differentiable manner. This learning process is compatible with existing networks and owns adaptability to larger search spaces and different tasks.
  arXiv  Detail & Related papers  (2020-08-19T04:53:31Z)
• Non-Local Spatial Propagation Network for Depth Completion [82.60915972250706]
  We propose a robust and efficient end-to-end non-local spatial propagation network for depth completion. The proposed network takes RGB and sparse depth images as inputs and estimates non-local neighbors and their affinities of each pixel. We show that the proposed algorithm is superior to conventional algorithms in terms of depth completion accuracy and robustness to the mixed-depth problem.
  arXiv  Detail & Related papers  (2020-07-20T12:26:51Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  Simple algorithms have been shown to lead to good empirical results in many contexts. Several works have pursued rigorous analytical justification for studying non optimization problems. A key insight in these analyses is that perturbations play a critical role in allowing local descent algorithms.
  arXiv  Detail & Related papers  (2020-03-31T16:54:22Z)
• 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.

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