IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2508.09492.html
   My bibliography  Save this paper

Influence and Connectivity in Networks: A Generating Function Approach

Author

Listed:
  • Yang Sun
  • Wei Zhao
  • Junjie Zhou

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.

Suggested Citation

  • Yang Sun & Wei Zhao & Junjie Zhou, 2025. "Influence and Connectivity in Networks: A Generating Function Approach," Papers 2508.09492, arXiv.org.
    • Handle: RePEc:arx:papers:2508.09492
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2508.09492
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Yang Sun & Wei Zhao & Junjie Zhou, 2023. "Structural Interventions In Networks," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 64(4), pages 1533-1563, November.
    2. Francis Bloch & Matthew O. Jackson & Pietro Tebaldi, 2023. "Centrality measures in networks," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 61(2), pages 413-453, August.
    3. Ushchev, Philip & Zenou, Yves, 2020. "Social norms in networks," Journal of Economic Theory, Elsevier, vol. 185(C).
    4. , D. & Tessone, Claudio J. & ,, 2014. "Nestedness in networks: A theoretical model and some applications," Theoretical Economics, Econometric Society, vol. 9(3), September.
    5. Belhaj, Mohamed & Bervoets, Sebastian & Deroïan, Frédéric, 2016. "Efficient networks in games with local complementarities," Theoretical Economics, Econometric Society, vol. 11(1), January.
    6. Coralio Ballester & Antoni Calvó-Armengol & Yves Zenou, 2006. "Who's Who in Networks. Wanted: The Key Player," Econometrica, Econometric Society, vol. 74(5), pages 1403-1417, September.
    7. Daron Acemoglu & Vasco M. Carvalho & Asuman Ozdaglar & Alireza Tahbaz‐Salehi, 2012. "The Network Origins of Aggregate Fluctuations," Econometrica, Econometric Society, vol. 80(5), pages 1977-2016, September.
    8. Ying-Ju Chen & Yves Zenou & Junjie Zhou, 2018. "Multiple Activities in Networks," American Economic Journal: Microeconomics, American Economic Association, vol. 10(3), pages 34-85, August.
    9. Ernest Liu, 2019. "Industrial Policies in Production Networks," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 134(4), pages 1883-1948.
    10. Abhijit Banerjee & Arun G Chandrasekhar & Esther Duflo & Matthew O Jackson, 2019. "Using Gossips to Spread Information: Theory and Evidence from Two Randomized Controlled Trials," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 86(6), pages 2453-2490.
    11. Currarini, Sergio & Fumagalli, Elena & Panebianco, Fabrizio, 2017. "Peer effects and local congestion in networks," Games and Economic Behavior, Elsevier, vol. 105(C), pages 40-58.
    12. David Rezza Baqaee, 2018. "Cascading Failures in Production Networks," Econometrica, Econometric Society, vol. 86(5), pages 1819-1838, September.
    13. Bloch, Francis & Quérou, Nicolas, 2013. "Pricing in social networks," Games and Economic Behavior, Elsevier, vol. 80(C), pages 243-261.
    14. Itay P. Fainmesser & Andrea Galeotti, 2016. "Pricing Network Effects," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 83(1), pages 165-198.
    15. Ozan Candogan & Kostas Bimpikis & Asuman Ozdaglar, 2012. "Optimal Pricing in Networks with Externalities," Operations Research, INFORMS, vol. 60(4), pages 883-905, August.
    16. Filipp Ushchev & Yves Zenou, 2020. "Social norms in networks," ULB Institutional Repository 2013/387727, ULB -- Universite Libre de Bruxelles.
    17. repec:hal:pseose:hal-01013603 is not listed on IDEAS
    18. Bramoullé, Yann & Genicot, Garance, 2024. "Diffusion and targeting centrality," Journal of Economic Theory, Elsevier, vol. 222(C).
    19. Cesi Cruz & Julien Labonne & Pablo Querubín, 2017. "Politician Family Networks and Electoral Outcomes: Evidence from the Philippines," American Economic Review, American Economic Association, vol. 107(10), pages 3006-3037, October.
    20. Zhou, Junjie & Chen, Ying-Ju, 2015. "Key leaders in social networks," Journal of Economic Theory, Elsevier, vol. 157(C), pages 212-235.
    21. Leo Katz, 1953. "A new status index derived from sociometric analysis," Psychometrika, Springer;The Psychometric Society, vol. 18(1), pages 39-43, March.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Yang Sun & Wei Zhao & Junjie Zhou, 2021. "Structural Interventions in Networks," Papers 2101.12420, arXiv.org, revised Feb 2021.
    2. Thomas J. Sargent & John Stachurski, 2022. "Economic Networks: Theory and Computation," Papers 2203.11972, arXiv.org, revised Jul 2022.
    3. Jadbabaie, Ali & Kakhbod, Ali, 2019. "Optimal contracting in networks," Journal of Economic Theory, Elsevier, vol. 183(C), pages 1094-1153.
    4. Bloch, Francis & Shabayek, Shaden, 2023. "Targeting in social networks with anonymized information," Games and Economic Behavior, Elsevier, vol. 141(C), pages 380-402.
    5. Yang Sun & Wei Zhao & Junjie Zhou, 2023. "Structural Interventions In Networks," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 64(4), pages 1533-1563, November.
    6. Colombo, Luca & Labrecciosa, Paola & Rusinowska, Agnieszka, 2025. "A dynamic analysis of criminal networks," Journal of Economic Theory, Elsevier, vol. 223(C).
    7. Chen, Ying-Ju & Zenou, Yves & Zhou, Junjie, 2022. "The impact of network topology and market structure on pricing," Journal of Economic Theory, Elsevier, vol. 204(C).
    8. Harkins, Andrew, 2020. "Network Comparative Statics," The Warwick Economics Research Paper Series (TWERPS) 1306, University of Warwick, Department of Economics.
    9. Ying‐Ju Chen & Yves Zenou & Junjie Zhou, 2018. "Competitive pricing strategies in social networks," RAND Journal of Economics, RAND Corporation, vol. 49(3), pages 672-705, September.
    10. Yang Sun & Wei Zhao & Junjie Zhou, 2024. "Sequential Network Design," Papers 2409.14136, arXiv.org, revised Aug 2025.
    11. Ryan Kor & Yi Liu & Yves Zenou & Junjie Zhou, 2022. "Welfare and Distributional Effects of Joint Intervention in Networks," Papers 2206.03863, arXiv.org, revised Nov 2025.
    12. Goyal, S., 2016. "Networks and Markets," Cambridge Working Papers in Economics 1652, Faculty of Economics, University of Cambridge.
    13. Harkins, Andrew, 2020. "Network Comparative Statics," CRETA Online Discussion Paper Series 64, Centre for Research in Economic Theory and its Applications CRETA.
    14. Ostrizek, Franz & Sartori, Elia, 2023. "Screening while controlling an externality," Games and Economic Behavior, Elsevier, vol. 139(C), pages 26-55.
    15. Andrea Galeotti & Benjamin Golub & Sanjeev Goyal, 2020. "Targeting Interventions in Networks," Econometrica, Econometric Society, vol. 88(6), pages 2445-2471, November.
    16. Bramoullé, Yann & Genicot, Garance, 2024. "Diffusion and targeting centrality," Journal of Economic Theory, Elsevier, vol. 222(C).
    17. Li, Jian & Zhou, Junjie & Chen, Ying-Ju, 2022. "The limit of targeting in networks," Journal of Economic Theory, Elsevier, vol. 201(C).
    18. Jackson, Matthew O. & Zenou, Yves, 2015. "Games on Networks," Handbook of Game Theory with Economic Applications,, Elsevier.
    19. Jeon, Doh-Shin & Lefouili, Yassine & Li, Yaxin & Simcoe, Timothy, 2023. "Network Centrality and Device Ecosystems," TSE Working Papers 23-1468, Toulouse School of Economics (TSE), revised Jan 2025.
    20. Andrea Galeotti & Benjamin Golub & Sanjeev Goyal & Eduard Talam`as & Omer Tamuz, 2021. "Taxes and Market Power: A Principal Components Approach," Papers 2112.08153, arXiv.org, revised Jun 2022.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:arx:papers:2508.09492. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.