An official website of the United States government
Abstract Many statistical models for networks overlook the fact that most real-world networks are formed through a growth process. To address this, we introduce the Preferential Attachment Plus Erdős–Rényi model, where we let a random network G be the union of a preferential attachment (PA) tree T and additional Erdős–Rényi (ER) random edges. The PA tree captures the underlying growth process of a network where vertices/edges are added sequentially, while the ER component can be regarded as noise. Given only one snapshot of the final network G, we study the problem of constructing confidence sets for the root node of the unobserved growth process; the root node can be patient zero in an infection network or the source of fake news in a social network. We propose inference algorithms based on Gibbs sampling that scales to networks with millions of nodes and provide theoretical analysis showing that the size of the confidence set is small if the noise level of the ER edges is not too large. We also propose variations of the model in which multiple growth processes occur simultaneously, reflecting the growth of multiple communities; we use these models to provide a new approach to community detection.
more »
« less
This content will become publicly available on December 2, 2025
Enabling Asymptotic Truth Learning in a Social Network
Consider a network of agents that all want to guess the correct value of some ground truth state. In a sequential order, each agent makes its decision using a single private signal which has a constant probability of error, as well as observations of actions from its network neighbors earlier in the order. We are interested in enabling network-wide asymptotic truth learning – that in a network of n agents, almost all agents make a correct prediction with probability approaching one as n goes to infinity. In this paper we study both random orderings and carefully crafted decision orders with respect to the graph topology as well as sufficient or necessary conditions for a graph to support such a good ordering. We first show that on a sparse graph of average constant degree with a random ordering asymptotic truth learning does not happen. We then show a rather modest sufficient condition to enable asymptotic truth learning. With the help of this condition we characterize graphs generated from the Erdös Rényi model and preferential attachment model. In an Erdös Rényi graph, unless the graph is super sparse (with O(n) edges) or super dense (nearly a complete graph), there exists a decision ordering that supports asymptotic truth learning. Similarly, any preferential attachment network with a constant number of edges per node can achieve asymptotic truth learning under a carefully designed ordering but not under either a random ordering nor the arrival order. We also evaluated a variant of the decision ordering on different network topologies and demonstrated clear effectiveness in improving truth learning over random orderings.
more »
« less
- Award ID(s):
- 2229876
- PAR ID:
- 10575582
- Publisher / Repository:
- Proceedings of the 20th Conference on Web and Internet Economics (WINE'24)
- Date Published:
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We consider the problems of asymptotic stability and robustness in large-scale second-order consensus networks and vehicle platoons in the discrete-time domain. First, we develop a graph-theoretic methodology to design the state feedback law for the second-order consensus networks and vehicle platoons in a discrete-time framework. We analyze the stability of such networks based on algebraic properties of the Laplacian matrices of underlying graphs and each vehicle’s update cycle (also known as the time step). We further provide a necessary and sufficient condition of stability of a linear second-order consensus network in the discrete-time domain. Moreover, we evaluate the robustness of the consensus networks by employing the expected value of the steady-state dispersion of the state of the entire network, also known as squared H2-norm, as a performance measure. We show the connection between performance measures with respect to network size, connectivity, and the update cycle. The main contribution of this work is that we provide a formal framework to quantify the relation between scaling performance measures and restrictions of the vehicles’ update cycles. Specifically, we show that denser networks (i.e., networks with more communications/edges) require faster agents (i.e., smaller update cycles) to outperform or achieve the same level of robustness as sparse networks (i.e., networks with fewer communications/edges).more » « less
-
Abstract Reaction networks are commonly used within the mathematical biology and mathematical chemistry communities to model the dynamics of interacting species. These models differ from the typical graphs found in random graph theory since their vertices are constructed from elementary building blocks, i.e. the species. We consider these networks in an Erdös–Rényi framework and, under suitable assumptions, derive a threshold function for the network to have a deficiency of zero, which is a property of great interest in the reaction network community. Specifically, if the number of species is denoted by n and the edge probability by $$p_n$$ , then we prove that the probability of a random binary network being deficiency zero converges to 1 if $$p_n\ll r(n)$$ as $$n \to \infty$$ , and converges to 0 if $$p_n \gg r(n)$$ as $$n \to \infty$$ , where $$r(n)=\frac{1}{n^3}$$ .more » « less
-
Why do many modern neural-network-based graph generative models fail to reproduce typical real-world network characteristics, such as high triangle density? In this work we study the limitations of edge independent random graph models, in which each edge is added to the graph independently with some probability. Such models include both the classic Erdös-Rényi and stochastic block models, as well as modern generative models such as NetGAN, variational graph autoencoders, and CELL. We prove that subject to a bounded overlap condition, which ensures that the model does not simply memorize a single graph, edge independent models are inherently limited in their ability to generate graphs with high triangle and other subgraph densities. Notably, such high densities are known to appear in real-world social networks and other graphs. We complement our negative results with a simple generative model that balances overlap and accuracy, performing comparably to more complex models in reconstructing many graph statistics.more » « less
-
Quantifying the differences between networks is a challenging and ever-present problem in network science. In recent years, a multitude of diverse, ad hoc solutions to this problem have been introduced. Here, we propose that simple and well-understood ensembles of random networks—such as Erdős–Rényi graphs, random geometric graphs, Watts–Strogatz graphs, the configuration model and preferential attachment networks—are natural benchmarks for network comparison methods. Moreover, we show that the expected distance between two networks independently sampled from a generative model is a useful property that encapsulates many key features of that model. To illustrate our results, we calculate this within-ensemble graph distance and related quantities for classic network models (and several parameterizations thereof) using 20 distance measures commonly used to compare graphs. The within-ensemble graph distance provides a new framework for developers of graph distances to better understand their creations and for practitioners to better choose an appropriate tool for their particular task.more » « less
