Behavior and Sublinear Algorithm for Opinion Disagreement on Noisy Social Networks

• URL: http://arxiv.org/abs/2604.01890v1
• Date: Thu, 02 Apr 2026 10:55:45 GMT
• Title: Behavior and Sublinear Algorithm for Opinion Disagreement on Noisy Social Networks
• Abstract summary: Most real-life networks, including social networks, are scale-free and sparse.<n>We study noisy opinion dynamics in sparse scale-free social networks to uncover the influence of power-law topology on opinion disagreement.
• Score: 27.02356218924079
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The phenomenon of opinion disagreement has been empirically observed and reported in the literature, which is affected by various factors, such as the structure of social networks. An important discovery in network science is that most real-life networks, including social networks, are scale-free and sparse. In this paper, we study noisy opinion dynamics in sparse scale-free social networks to uncover the influence of power-law topology on opinion disagreement. We adopt the popular discrete-time DeGroot model for opinion dynamics in a graph, where nodes' opinions are subject to white noise. We first study opinion disagreement in many realistic and model networks with a scale-free topology, which approaches a constant, indicating that a scale-free structure is resistant to noise in the opinion dynamics. Moreover, existing algorithms for estimating opinion disagreement are computationally impractical for large-scale networks due to their high computational complexity. To solve this challenge, we introduce a sublinear-time algorithm to approximate this quantity with a theoretically guaranteed error. This algorithm efficiently simulates truncated random walks starting from a subset of nodes while preserving accurate estimation. Extensive experiments demonstrate its efficiency, accuracy, and scalability.

Related papers

• Teacher Knows It Best: Spontaneous Symmetry Breaking and Tipping Points in Networked Langevin Dynamics AI Sycophancy [5.868852957948178]
  We formulate a statistical physics framework to model a networked dynamical system exhibiting bistability, driven by additive noise and social conformity.<n>We apply this model to understand and mitigate AI-induced delusional spiraling-a phenomenon where algorithmic sycophancy from Large Language Models continuously reinforces inaccurate beliefs.<n>We prove mathematically that under certain conditions, a highly concentrated, rapid intervention targeting massive hubs strictly outperforms a distributed, slow approach to rescue the network.
  arXiv  Detail & Related papers  (2026-07-27T11:47:57Z)
• Heuristic algorithms for the stochastic critical node detection problem [0.0]
  Given a network, the critical node detection problem finds a subset of nodes whose removal disrupts the network connectivity.<n>In this paper, we consider a version of the critical node detection problem, where the existence of edges is given by certain probabilities.<n>We proposes and learning-based methods for the problem and compare them with existing algorithms.
  arXiv  Detail & Related papers  (2025-12-01T10:18:24Z)
• Efficient Estimation for Longitudinal Networks via Adaptive Merging [21.62069959992736]
  We propose an efficient estimation framework for longitudinal network, leveraging strengths of adaptive network merging, tensor decomposition and point process. It merges neighboring sparse networks so as to enlarge the number of observed edges and reduce estimation variance. A projected descent algorithm is proposed to facilitate estimation, where upper bound of the estimation error in each iteration is established.
  arXiv  Detail & Related papers  (2022-11-15T03:17:11Z)
• Neural Causal Models for Counterfactual Identification and Estimation [62.30444687707919]
  We study the evaluation of counterfactual statements through neural models. First, we show that neural causal models (NCMs) are expressive enough. Second, we develop an algorithm for simultaneously identifying and estimating counterfactual distributions.
  arXiv  Detail & Related papers  (2022-09-30T18:29:09Z)
• Rank Diminishing in Deep Neural Networks [71.03777954670323]
  Rank of neural networks measures information flowing across layers. It is an instance of a key structural condition that applies across broad domains of machine learning. For neural networks, however, the intrinsic mechanism that yields low-rank structures remains vague and unclear.
  arXiv  Detail & Related papers  (2022-06-13T12:03:32Z)
• An Unbiased Symmetric Matrix Estimator for Topology Inference under Partial Observability [16.60607849384252]
  This letter considers the problem of network topology inference under the framework of partial observability. We propose a novel unbiased estimator for the symmetric network topology with the Gaussian noise and the Laplacian combination rule. An effective algorithm called network inference Gauss algorithm is developed to infer the network structure.
  arXiv  Detail & Related papers  (2022-03-29T12:49:25Z)
• Residual Error: a New Performance Measure for Adversarial Robustness [85.0371352689919]
  A major challenge that limits the wide-spread adoption of deep learning has been their fragility to adversarial attacks. This study presents the concept of residual error, a new performance measure for assessing the adversarial robustness of a deep neural network. Experimental results using the case of image classification demonstrate the effectiveness and efficacy of the proposed residual error metric.
  arXiv  Detail & Related papers  (2021-06-18T16:34:23Z)
• A scalable multi-step least squares method for network identification with unknown disturbance topology [0.0]
  We present an identification method for dynamic networks with known network topology. We use a multi-step Sequential and Null Space Fitting method to deal with reduced rank noise. We provide a consistency proof that includes explicit-based Box model structure informativity.
  arXiv  Detail & Related papers  (2021-06-14T16:12:49Z)
• Vulnerability Under Adversarial Machine Learning: Bias or Variance? [77.30759061082085]
  We investigate the effect of adversarial machine learning on the bias and variance of a trained deep neural network. Our analysis sheds light on why the deep neural networks have poor performance under adversarial perturbation. We introduce a new adversarial machine learning algorithm with lower computational complexity than well-known adversarial machine learning strategies.
  arXiv  Detail & Related papers  (2020-08-01T00:58:54Z)
• Fitting the Search Space of Weight-sharing NAS with Graph Convolutional Networks [100.14670789581811]
  We train a graph convolutional network to fit the performance of sampled sub-networks. With this strategy, we achieve a higher rank correlation coefficient in the selected set of candidates.
  arXiv  Detail & Related papers  (2020-04-17T19:12:39Z)
• Binary Neural Networks: A Survey [126.67799882857656]
  The binary neural network serves as a promising technique for deploying deep models on resource-limited devices. The binarization inevitably causes severe information loss, and even worse, its discontinuity brings difficulty to the optimization of the deep network. We present a survey of these algorithms, mainly categorized into the native solutions directly conducting binarization, and the optimized ones using techniques like minimizing the quantization error, improving the network loss function, and reducing the gradient error.
  arXiv  Detail & Related papers  (2020-03-31T16:47:20Z)

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.