Influence and Connectivity in Networks: A Generating Function Approach

2025/08/13 by Sun, Yang, Zhao, Wei, Zhou, Junjie
#FOS: Economics and business #Theoretical Economics (econ.TH)

paper · doi:10.48550/arxiv.2508.09492

Abstract

Many widely used network centralities are based on counting walks that meet specific criteria. This paper introduces a systematic framework for walk enumeration using generating functions. We introduce a first-passage decomposition that uniquely divides any walk passing through specified nodes or links into two components: a first-reaching walk and a subsequent walk. This decomposition yields a system of interconnected equations that relate three disjoint categories of walks: unrestricted walks, walks that avoid specific elements, and walks that pass through designated sets. The framework offers a range of applications, including evaluating the effects of structural interventions, such as node or link modifications, on network walks, generalizing target centrality to multi-receiver scenarios in information networks, and comparing different strategies for adding links.

Citations

• Sequential Network Design
• Incentive Contracts and Peer Effects in the Workplace
• Structural Interventions in Networks
• Centrality Measures in Networks
• Total communicability as a centrality measure
• Optimal Pricing in Networks with Externalities
• Power and Centrality: A Family of Measures
• A New Status Index Derived from Sociometric Analysis
• Centrality and network flow
• Factoring and weighting approaches to status scores and clique identification

Related

• Network Centrality Metrics Based on Unrestricted Paths, Walks and Cycles Compared to Standard Centrality Metrics
• Updating Katz centrality by counting walks
• Subsuming Complex Networks by Node Walks
• A measure of betweenness centrality based on random walks
• Temporal Walk Centrality: Ranking Nodes in Evolving Networks