The formation of opinions is fundamentally a network-based process, where the opinions of individuals in a social network exchange, evolve, and eventually convergence towards a specific distribution. However, this dynamic process may be susceptible to manipulation by adversarial entities, who aim to maliciously influence the opinion formulation. The adversary may engage in extensive influence campaigns, disseminating misinformation among populations, thereby potentially destabilizing societies. It is thus of significance to develop strategies to defend against such attacks, which are essential for fostering a healthy environment for information sharing, social deliberation, and opinion formation. In this paper, we investigate a scenario wherein an external adversary aims to maliciously alter the opinions of a general social graph. This is achieved by targeting several selected nodes, referred to as followers. Concurrently, we explore a counter-strategy, aiming to negate the influence of the adversary with malicious intents. This involves identifying a subset of nodes to act as followers of a defending leader, thereby minimizing the adversary’s impact. Since this problem can be framed as a non-increasing supermodular minimization problem, we develop a (1-1/e) approximation greedy algorithm consequently. Moreover, to overcome the computation challenge for large-scale networks, we establish an efficient approximation to the key quantity of the greedy algorithm. This refinement significantly enhances computational efficiency and scalability, making the algorithm applicable to networks with millions of nodes. Extensive simulation results on various real-world networks demonstrate the superior performance of our improved algorithm over existing algorithms and other baseline schemes based on centrality measures. In particular, our improved algorithm scales to networks of considerable size, with negligible sacrifice on the quality of solutions.

In this paper, we study the opinion maximization problem for the leader-follower DeGroot model of opinion dynamics in a social network modelled by a directed graph with n nodes, where a small number of nodes are competing leader nodes with binary opposing opinions 0 or 1, and the rest are follower nodes. We address the problem of maximizing the overall opinion by adding k ⇐ n new edges, where each edge is incident to a 1-leader and a follower. We prove that the objective function is monotone and submodular, and then propose a deterministic greedy algorithm with an approximation ratio (1-1 over e) and O(n3) running time. We then develop a fast sampling algorithm based on l-truncated absorbing random walks and sample-materialization techniques, which has sublinear time complexity O(kn1/2 log3/2 n/ε3) for any error parameter ε > 0. We provide extensive experiments on real networks to evaluate the performance of our algorithms. The results show that for undirected graphs our fast sampling algorithm outperforms the state-of-the-art method in terms of efficiency and effectiveness. While for directed graphs our fast sampling algorithm is as effective as our deterministic greedy algorithm, both of which are much better than the baseline strategies. Moreover, our fast algorithm is scalable to large directed graphs with over 41 million nodes.

The function or performance of a network is strongly dependent on its robustness, quantifying the ability of the network to continue functioning under perturbations. While a wide variety of robustness metrics have been proposed, they have their respective limitations. In this paper, we propose to use the forest index as a measure of network robustness, which overcomes the deficiencies of existing metrics. Using such a measure as an optimization criterion, we propose and study the problem of breaking down a network by attacking some key edges. We show that the objective function of the problem is monotonic but not submodular, which impose more challenging on the problem. We thus resort to greedy algorithms extended for non-submodular function by iteratively deleting the most promising edges. We first propose a simple greedy algorithm with a proved bound for the approximation ratio and cubic-time complexity. To confront the computation challenge for large networks, we further propose an improved nearly-linear time greedy algorithm, which significantly speeds up the process for edge selection but sacrifices little accuracy. Extensive experimental results for a large set of real-world networks verify the effectiveness and efficiency of our algorithms, demonstrating that our algorithms outperform several baseline schemes.

As an important factor governing opinion dynamics, stubbornness strongly affects various aspects of opinion formation. However, a systematically theoretical study about the influences of heterogeneous stubbornness on opinion dynamics is still lacking. In this paper, we study a popular opinion model in the presence of inhomogeneous stubbornness. We show analytically that heterogeneous stubbornness has a great impact on convergence time, expressed opinion of every node, and the overall expressed opinion. We provide an explanation of the expressed opinion in terms of stubbornness-dependent spanning diverging forests. We propose quantitative indicators to quantify some social concepts, including conflict, disagreement, and polarization by incorporating heterogeneous stubbornness, and develop a nearly linear time algorithm to approximate these quantities, which has a proved theoretical guarantee for the error of each quantity. To demonstrate the performance of our algorithm, we perform extensive experiments on a large set of real networks, which indicate that our algorithm is both efficient and effective, scalable to large networks with millions of nodes.

Concomitant with the tremendous prevalence of online social media platforms, the interactions among individuals are unprecedentedly enhanced. People are free to interact with acquaintances, express and exchange their own opinions through commenting, liking, retweeting on online social media, leading to resistance, controversy and other important phenomena over controversial social issues, which have been the subject of many recent works. In this paper, we study the problem of minimizing risk of conflict in social networks by modifying the initial opinions of a small number of nodes. We show that the objective function of the combinatorial optimization problem is monotone and supermodular. We then propose a naive greedy algorithm with a (1-1/e) approximation ratio that solves the problem in cubic time. To overcome the computation challenge for large networks, we further integrate several effective approximation strategies to provide a nearly linear time algorithm with a (1-1/e-ε) approximation ratio for any error parameter ε>0. Extensive experiments on various real-world datasets demonstrate both the efficiency and effectiveness of our algorithms. In particular, the fast one scales to large networks with more than two million nodes, and achieves up to 20x speed-up over the state-of-the-art algorithm.

Individual's opinions are fundamentally shaped and evolved by their interactions with other people, and social phenomena such as disagreement and polarization are now tightly woven into daily life. The quantification and optimization of these concepts have been the subject of much recent research behind a wealth of high-impact data mining applications. In particular, researchers have addressed the question of how such concepts can be optimized by influencing the opinion of a small number of individuals or by designing the network from scratch.Here, rather than a “design-from-scratch” approach or altering the initial opinion, we study the optimization problem of recommending $k$ new links to minimize the sum of polarization and disagreement in a social network with $n$ nodes and $m$ edges. We show that our objective function of this combinatorial optimization problem is not submodular, although it is monotone. We propose a simple greedy algorithm with a constant-factor approximation that solves the problem in cubic running time, and we provide theoretical analysis of the approximation guarantee for the algorithm. To overcome the computation challenge for large networks, we also provide a fast algorithm with computation complexity $\Otil (mk\eps^{-2})$ for any $\eps>0$, where the $\Otil (\cdot)$ notation suppresses the ${\rm poly} (\log n)$ factors. Extensive experiments on real datasets demonstrate both the efficiency and effectiveness of our algorithms.

Abstract The mixing time of random walks on a graph has found broad applications across both theoretical and practical aspects of computer science, with the application effects depending on the behavior of mixing time. It is extensively believed that real-world networks, especially social networks, are fast mixing with their mixing time at most $O(\log N)$ where $N$ is the number of vertices. However, the behavior of mixing time in the real-life networks has not been examined carefully, and exactly analytical research for mixing time in models mimicking real networks is still lacking. In this paper, we first experimentally evaluate the mixing time of various real-world networks with scale-free small-world properties and show that their mixing time is much higher than anticipated. To better understand the behavior of the mixing time for real-world networks, we then analytically study the mixing time of the Apollonian network, which is simultaneously scale-free and small-world. To this end, we derive the recursive relations for all eigenvalues, especially the second largest eigenvalue modulus of the transition matrix, based on which we deduce a lower bound for the mixing time of the Apollonian network, which approximately scales sublinearly with $N$. Our results indicate that real-world networks are not always fast mixing, which has potential implications in the design of algorithms related to mixing time.