Jul 2026· Mathematics of Operations Research· 1 citation· 24 references
TL;DR
It is shown that, under mild regularity conditions, the realized values of row-normalized centralities concentrate around their expectations, and this greatly simplifies the analysis of these stochastic networks.
Abstract
In many applications, network effects are normalized: in opinion dynamics, agents take a weighted average of their friends’ beliefs, or in social media models, users’ adoption decisions depends on the fraction of their peers who also adopt. The outcome of these processes share a common network property: a weighted Katz–Bonacich centrality but one defined over the network’s row-normalized adjacency matrix, which measures relative spillovers. This row-normalized centrality measure is well-understood in deterministic settings in which the full network structure is known, but in many instances, only probabilistic information about the network is available. We show that, under mild regularity conditions, the realized values of row-normalized centralities concentrate around their expectations, and this greatly simplifies the analysis of these stochastic networks. We use this result to further show that optimizing an objective over a stochastic network can be reduced to an optimization problem over an appropriately defined deterministic network. Together, these results yield a general and tractable approach for analyzing network processes and targeting problems in stochastic networks when spillovers are determined by normalized rather than raw connections. We demonstrate the usefulness of these techniques in applications to pricing, network games, and social dynamics.
This paper studies the problem of steering collective beliefs in social networks when only a small fraction of nodes can be directly influenced. We propose a sparse optimal control framework built on the Network Drift-Diffusion Model (NDDM). Two intervention mechanisms are considered: direct control and latent (indirect) control. To select which nodes to actuate, we compare six centrality measures---Degree, Betweenness, Eigenvector, Closeness, PageRank, and K-shell---and keep only the top 5\%--30\% as control inputs. The optimal feedback law follows from the Hamilton-Jacobi-Bellman (HJB) equation, which reduces to solving Riccati-type differential equations. We test our approach on Erdős-Rényi (ER), Barabási-Albert (BA), and Watts-Strogatz (WS) networks. The results show that the best centrality choice depends strongly on the network topology, and the system undergoes phase transitions as control parameters vary.
Bo Wang· Frontiers in Computing and I...· 0 citations
Time-evolving networks, or temporal networks, play a crucial role in modeling dynamic interactions across various domains, including biology, social sciences, and information technology. Unlike static networks, these systems undergo continuous changes in topology and edge weights, influencing processes such as information flow, transportation efficiency, and neural activity. Understanding and controlling these networks are essential for predicting future behavior and optimizing dynamic processes. This work focuses on the problem of dynamic centrality, a measure of node importance in time-dependent networks. Specifically, we address how to steer network centrality to a desired state by making minimal modifications to the network structure. This problem is formulated as an optimal control problem for an ordinary differential equation, either matrix- or vector-based, where the control acts on network edges. The proposed framework generalizes centrality control problems studied in static networks and leverages the Pontryagin Maximum Principle for efficient solutions. For large-scale problems, the required matrix-function actions are approximated by Krylov-type techniques, avoiding the explicit formation of dense matrix functions. Numerical experiments on synthetic and real temporal networks show that the proposed framework can effectively steer receive centrality under prescribed control constraints.
The Influence-Spreading Model (ISM) introduces three probabilistic centrality measures: out-centrality, in-centrality, and ISM betweenness centrality. Out-centrality measures the average probability that a node influences others, while in-centrality measures the average probability that others influence a node. ISM betweenness centrality measures the change in total probabilistic influence when a node is removed. These measures depend on edge transmission probabilities and allow walks up to a specified maximum length. We compare the ISM centrality measures to commonly used weighted variants of out-degree, in-degree, closeness, shortest-path betweenness, and Katz centrality in directed, weighted networks using four real-world online social networks and nine synthetic networks generated by Erd\H{o}s-R\'enyi, navigable small-world, and directed scale-free models. For the synthetic networks, the edge probabilities are drawn from three beta distributions. We evaluate the similarity in centrality values and their ranking using Pearson correlation and Spearman's rank correlation coefficients. Results show strong correlations between the ISM out-centrality and weighted out-degree and outward Katz centrality, particularly for low edge probabilities. Conversely, relationships between the ISM in-centrality and other measures vary with network topology, sometimes yielding negative correlations. Correlations between the ISM betweenness and the shortest-path betweenness are also topology-dependent and weaken as alternative influence paths become more relevant. Overall, standard centrality measures can approximate the influence of broadcasting influence but often miss the nuances of receiving influence and probabilistic intermediary roles.
Temporal networks offer a suitable representation for complex systems in which interactions vary over time, such as communication, transportation, and social networks. Identifying influential nodes in such networks is more challenging than in static graphs because node importance depends not only on network structure but also on the timing and ordering of interactions. Although many temporal centrality measures have been proposed, the literature remains fragmented, with limited consensus on their comparative performance and applicability. This paper presents a critical and comparative survey of centrality measures in temporal networks. We review both temporal extensions of classical centrality metrics and measures specifically designed for temporal graphs, and propose a functional taxonomy that categorizes existing approaches according to the primary mechanism through which influence is quantified in temporal networks. The proposed taxonomy organizes temporal centrality measures into interaction-based, path-based, walk-based, spectral-based and robustness-based categories, providing a unified perspective on their underlying principles. In addition, we provide comparative insights to help select appropriate temporal centrality measures under different network characteristics and application settings. To complement the survey, we conduct experiments on multiple real-world temporal network datasets. The measures are evaluated through influence spreading experiments using epidemic diffusion models, ranking consistency analysis based on Kendall's rank correlation, and runtime complexity analysis to assess computational efficiency and scalability. Finally, we highlight key open challenges and future research directions, including scalability for million-sized networks and the need for standardized evaluation frameworks.
This paper studies how network structures affect the efficiency of information aggregation in social learning environments. We consider a model in which rational agents sequentially choose actions based on private signals and observations of their neighbors'actions in a network. Focusing on comparisons of expected payoffs at a given finite period, we show that there exists an information structure under which the star network achieves a strictly higher expected payoff than any other network, and another information structure under which the complete network achieves a strictly higher expected payoff than any other network. Taken together, these results imply that no network is uniformly optimal across all information structures. Our analysis highlights a trade-off between the responsiveness effect and the overturning effect: disconnected networks preserve responsiveness of actions to private signals, whereas highly connected networks facilitate the aggregation of extreme information that overturns public beliefs.
Consider a setting where N players, partitioned into K observable types, form a directed network. Agents’ preferences over the form of the network consist of an arbitrary network benefit function (e.g., agents may have preferences over their network centrality) and a private, or dyadic, component which is additively separable in own links. This latter component allows for unobserved heterogeneity in the costs of sending and receiving links across agents (respectively out- and in- degree heterogeneity) as well as homophily/heterophily across the K types of agents. In contrast, the network benefit function allows agents’ preferences over links to vary with the presence or absence of links elsewhere in the network (and hence with the link formation behavior of their peers). In the null model, which excludes the network benefit function, links form independently across dyads in the manner described by Charbonneau (2017) among others. Under the alternative, there is interdependence across linking decisions (i.e., strategic interaction). We show how to test the null with power optimized in specific directions. These alternative directions include many common models of strategic network formation (e.g., “connections” models, “structural hole” models etc.). Our random utility specification induces an exponential family structure under the null which we exploit to construct a similar test which exactly controls size (despite the the null being a composite one with many nuisance parameters). We further show how to construct locally best tests for specific alternatives without making any assumptions about equilibrium selection. To make our tests feasible, we introduce a new MCMC algorithm for simulating the null distributions of our test statistics.
Andrin Pelican, Bryan S. Graham· The Review of Economic Studi...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
