We study algorithmic strategies to effectively contain diffusion via edge immunization. We consider the scenarios where the epidemic characteristics are known and unknown, and accordingly present approaches relying upon the epidemic dynamics and the network topology. In particular, for the former, we propose the greedy and inverse greedy immune schemes to greedily minimize the immune edge set, whose performance is guaranteed by the exhaustive search. We also present strategies to scale up the associated methods such that they can more efficiently obtain better solutions. For the latter, we find that the epidemic incidence of the immunized network is determined by both local and global connection patterns, characterized by the critical threshold in network epidemiology and the largest connected component in network percolation, respectively. Thus, we propose network topology-based strategies that obtain the immune edge set by simultaneously minimizing both the factors. We conduct extensive experiments on synthetic and empirical social networks to evaluate the proposed methods. Results show that our methods outperform the state-of-the-art by a large margin. Besides, the developed topology-based strategies can always obtain comparable results to the greedy strategies, which are computationally much cheaper than existing approaches and thus favorable to tackle large-scale networks.

Diffusion probabilistic models (DPMs) have recently demonstrated impressive generative capabilities. There is emerging evidence that their sample reconstruction ability can yield meaningful representations for recognition tasks. In this paper, we demonstrate that the objectives underlying generation and representation learning are not perfectly aligned. Through a spectral analysis, we find that minimizing the mean squared error (MSE) between the original graph and its reconstructed counterpart does not necessarily optimize representations for downstream tasks. Instead, focusing on reconstructing a small subset of features, specifically those capturing global information, proves to be more effective for learning powerful representations. Motivated by these insights, we propose a novel framework, the Smooth Diffusion Model for Graphs (SDMG), which introduces a multi-scale smoothing loss and low-frequency information encoders to promote the recovery of global, low-frequency details, while suppressing irrelevant high-frequency noise. Extensive experiments validate the effectiveness of our method, suggesting a promising direction for advancing diffusion models in graph representation learning.

A great number of studies have demonstrated that many complex systems could benefit a lot from complex networks, through either a direct modeling on which dynamics among agents could be investigated in a global view or an indirect representation by the aid of that the leading factors could be captured more clearly. Hence, in the context of networks, this article copes with the continuous network dismantling problem which aims to find the key node set whose removal would break down a given network more thoroughly and thus is more capable of suppressing virus or misinformation. To achieve this goal effectively and efficiently, we propose the external-degree and internal-size component suppression (EDIS) framework based on the network percolation, where we constrain the search space by a well-designed local goal function and candidate selection approach such that EDIS could obtain better results than the-state-of-the-art in networks of millions of nodes in seconds. We also contribute two strategies with time complexity${\mathcal {O}}(m\log _{\vartheta } m)$and space complexity${\mathcal {O}}(m)$, of networks of m edges, under such framework by well studying the evolving characteristics of the associated connected components as nodes are occupied, where$\vartheta \gt 1$is a hyperparameter. Our results on 12 empirical networks from various domains demonstrate that the proposed method has far better performance than the-state-of-the-art over both effectiveness and computing time. Our study could play important roles in many real-world scenarios, such as the containment of misinformation or epidemics, the distribution of resources or vaccine, the decision of which group of individuals set to quarantine, or the detection of the resilience of a network-based system under intentional attacks.

Network (or graph) sparsification accelerates many downstream analyses. For graph sparsification, sampling methods derived from local heuristic considerations are common in practice, due to their efficiency in generating sparse subgraphs using only local information. Filtering-based edge sampling is the most typical approach in this respect, yet it heavily depends on an appropriate definition of edge importance. Instead, we propose a generalized node-focused edge sampling framework by preserving scaled/expected local node characteristics. Apart from expected degrees, these local node characteristics include the expected number of triangles and the expected number of non-closed wedges associated with a node. From a technical point of view, we adapt a game-theoretic sampling method from uncertain graph generation to obtain sparse subgraphs that approximate the expected local properties. We include a tolerance threshold for much faster convergence. Within this framework, we provide appropriate algorithmic variants for sparsification. Moreover, we propose a network measure called tri-wedge assortativity for the selection of the most suitable variant when sparsifying a given network. Extensive experimental studies on functional climate, observed real-world, and synthetic networks show the effectiveness of our method in preserving overall structural network properties – on average consistently better than the state of the art.

Network (or graph) sparsification compresses a graph by removing inessential edges. By reducing the data volume, it accelerates or even facilitates many downstream analyses. Still, the accuracy of many sparsification methods, with filtering-based edge sampling being the most typical one, heavily relies on an appropriate definition of edge importance. Instead, we propose a different perspective with a generalized local-property-based sampling method, which preserves (scaled) local node characteristics. Apart from degrees, these local node characteristics we use are the expected (scaled) number of wedges and triangles a node belongs to. Through such a preservation, main complex structural properties are preserved implicitly. We adapt a game-theoretic framework from uncertain graph sampling by including a threshold for faster convergence (at least 4 times faster empirically) to approximate solutions. Extensive experimental studies on functional climate networks show the effectiveness of this method in preserving macroscopic to meso-scopic and microscopic network structural properties.