IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v262y2017i2p708-719.html
   My bibliography  Save this article

Higher order assortativity in complex networks

Author

Listed:
  • Arcagni, Alberto
  • Grassi, Rosanna
  • Stefani, Silvana
  • Torriero, Anna

Abstract

Assortativity was first introduced by Newman and has been extensively studied and applied to many real world networked systems since then. Assortativity is a graph metric and describes the tendency of high degree nodes to be directly connected to high degree nodes and low degree nodes to low degree nodes. It can be interpreted as a first order measure of the connection between nodes, i.e. the first autocorrelation of the degree–degree vector. Even though assortativity has been used so extensively, to the author’s knowledge, no attempt has been made to extend it theoretically. Indeed, Newman assortativity is about “being adjacent”, but even though two nodes may not by connected through an edge, they could have possibly a strong level of connectivity through a large number of walks and paths between them. This is the scope of our paper. We introduce, for undirected and unweighted networks, higher order assortativity by extending the Newman index based on a suitable choice of the matrix driving the connections. Higher order assortativity be defined for paths, shortest paths and random walks of a given length. The Newman assortativity is a particular case of each of these measures when the matrix is the adjacency matrix, or, in other words, the autocorrelation is of order 1. Our higher order assortativity indices help discriminating networks having the same Newman index and may reveal new topological network features. An application to airline network (Italy and US) and to Enron email network, as well as examples and simulations, are discussed.

Suggested Citation

  • Arcagni, Alberto & Grassi, Rosanna & Stefani, Silvana & Torriero, Anna, 2017. "Higher order assortativity in complex networks," European Journal of Operational Research, Elsevier, vol. 262(2), pages 708-719.
  • Handle: RePEc:eee:ejores:v:262:y:2017:i:2:p:708-719
    DOI: 10.1016/j.ejor.2017.04.028
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221717303612
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2017.04.028?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Hellmann, Tim & Staudigl, Mathias, 2014. "Evolution of social networks," European Journal of Operational Research, Elsevier, vol. 234(3), pages 583-596.
    2. Lindelauf, R.H.A. & Hamers, H.J.M. & Husslage, B.G.M., 2013. "Cooperative game theoretic centrality analysis of terrorist networks: The cases of Jemaah Islamiyah and Al Qaeda," European Journal of Operational Research, Elsevier, vol. 229(1), pages 230-238.
    3. Chiara Orsini & Marija M. Dankulov & Pol Colomer-de-Simón & Almerima Jamakovic & Priya Mahadevan & Amin Vahdat & Kevin E. Bassler & Zoltán Toroczkai & Marián Boguñá & Guido Caldarelli & Santo Fortunat, 2015. "Quantifying randomness in real networks," Nature Communications, Nature, vol. 6(1), pages 1-10, December.
    4. M. Piraveenan & M. Prokopenko & A. Y. Zomaya, 2009. "Assortativeness and information in scale-free networks," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 67(3), pages 291-300, February.
    5. Li, Yongli & Luo, Peng & Fan, Zhi-ping & Chen, Kun & Liu, Jiaguo, 2017. "A utility-based link prediction method in social networks," European Journal of Operational Research, Elsevier, vol. 260(2), pages 693-705.
    6. Jeremy Staum & Mingbin Feng & Ming Liu, 2016. "Systemic risk components in a network model of contagion," IISE Transactions, Taylor & Francis Journals, vol. 48(6), pages 501-510, June.
    7. Gómez, Daniel & Figueira, José Rui & Eusébio, Augusto, 2013. "Modeling centrality measures in social network analysis using bi-criteria network flow optimization problems," European Journal of Operational Research, Elsevier, vol. 226(2), pages 354-365.
    8. Benati, Stefano & Puerto, Justo & Rodríguez-Chía, Antonio M., 2017. "Clustering data that are graph connected," European Journal of Operational Research, Elsevier, vol. 261(1), pages 43-53.
    9. Yingda Lu & Kinshuk Jerath & Param Vir Singh, 2013. "The Emergence of Opinion Leaders in a Networked Online Community: A Dyadic Model with Time Dynamics and a Heuristic for Fast Estimation," Management Science, INFORMS, vol. 59(8), pages 1783-1799, August.
    10. P. Van Mieghem & H. Wang & X. Ge & S. Tang & F. A. Kuipers, 2010. "Influence of assortativity and degree-preserving rewiring on the spectra of networks," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 76(4), pages 643-652, August.
    11. Crama, Yves & Leruth, Luc, 2007. "Control and voting power in corporate networks: Concepts and computational aspects," European Journal of Operational Research, Elsevier, vol. 178(3), pages 879-893, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Nicola Giuseppe Castellano & Roy Cerqueti & Bruno Maria Franceschetti, 2021. "Evaluating risks-based communities of Mafia companies: a complex networks perspective," Review of Quantitative Finance and Accounting, Springer, vol. 57(4), pages 1463-1486, November.
    2. Elisa Letizia & Fabrizio Lillo, 2017. "Corporate payments networks and credit risk rating," Papers 1711.07677, arXiv.org, revised Sep 2018.
    3. Jaime F. Lavin & Mauricio A. Valle & Nicolás S. Magner, 2019. "Modeling Overlapped Mutual Funds’ Portfolios: A Bipartite Network Approach," Complexity, Hindawi, vol. 2019, pages 1-20, July.
    4. Sabek, M. & Pigorsch, U., 2023. "Local assortativity in weighted and directed complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 630(C).
    5. Abreu, Mariana Piaia & Grassi, Rosanna & Del-Vecchio, Renata R., 2019. "Structure of control in financial networks: An application to the Brazilian stock market," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 522(C), pages 302-314.
    6. Arcagni, Alberto & Grassi, Rosanna & Stefani, Silvana & Torriero, Anna, 2021. "Extending assortativity: An application to weighted social networks," Journal of Business Research, Elsevier, vol. 129(C), pages 774-783.
    7. Sayari, Elaheh & Seifert, Evandro G. & Cruziniani, Fátima E. & Gabrick, Enrique C. & Iarosz, Kelly C. & Szezech, José D. & Baptista, Murilo S. & Caldas, Iberê L. & Batista, Antonio M., 2023. "Structural connectivity modifications in the brain of selected patients with tumour after its removal by surgery (a case study)," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 623(C).

    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. Rysz, Maciej & Mahdavi Pajouh, Foad & Pasiliao, Eduardo L., 2018. "Finding clique clusters with the highest betweenness centrality," European Journal of Operational Research, Elsevier, vol. 271(1), pages 155-164.
    2. Ali Tosyali & Jeongsub Choi & Byunghoon Kim & Hoshin Lee & Myong K. Jeong, 2021. "A dynamic graph-based approach to ranking firms for identifying key players using inter-firm transactions," Annals of Operations Research, Springer, vol. 303(1), pages 5-27, August.
    3. Flores Díaz, Ramón Jesús & Molina, Elisenda & Tejada, Juan, 2013. "The Shapley group value," DES - Working Papers. Statistics and Econometrics. WS ws133430, Universidad Carlos III de Madrid. Departamento de Estadística.
    4. Ballings, Michel & Van den Poel, Dirk, 2015. "CRM in social media: Predicting increases in Facebook usage frequency," European Journal of Operational Research, Elsevier, vol. 244(1), pages 248-260.
    5. Liuan Wang & Lu (Lucy) Yan & Tongxin Zhou & Xitong Guo & Gregory R. Heim, 2020. "Understanding Physicians’ Online-Offline Behavior Dynamics: An Empirical Study," Information Systems Research, INFORMS, vol. 31(2), pages 537-555, June.
    6. Markus Kinateder & Luca Paolo Merlino, 2021. "The Evolution of Networks and Local Public Good Provision: A Potential Approach," Games, MDPI, vol. 12(3), pages 1-12, July.
    7. Sylvain Béal & Eric Rémila & Philippe Solal, 2015. "Discounted Tree Solutions," Working Papers hal-01377923, HAL.
    8. Rusinowska, Agnieszka & Taalaibekova, Akylai, 2019. "Opinion formation and targeting when persuaders have extreme and centrist opinions," Journal of Mathematical Economics, Elsevier, vol. 84(C), pages 9-27.
    9. Giulia Cesari & Roberto Lucchetti & Stefano Moretti, 2017. "Generalized additive games," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(4), pages 919-939, November.
    10. Manuel, Paul & Brešar, Boštjan & Klavžar, Sandi, 2022. "The geodesic-transversal problem," Applied Mathematics and Computation, Elsevier, vol. 413(C).
    11. Takayuki Mizuno & Shohei Doi & Shuhei Kurizaki, 2020. "The power of corporate control in the global ownership network," PLOS ONE, Public Library of Science, vol. 15(8), pages 1-19, August.
    12. Marc Levy & Ariane Szafarz, 2017. "Cross-Ownership: A Device for Management Entrenchment?," Review of Finance, European Finance Association, vol. 21(4), pages 1675-1699.
    13. Tolga Akcura & Kemal Altinkemer & Hailiang Chen, 0. "Noninfluentials and information dissemination in the microblogging community," Information Technology and Management, Springer, vol. 0, pages 1-18.
    14. Su, Hung-Chung & Kao, Ta-Wei (Daniel) & Linderman, Kevin, 2020. "Where in the supply chain network does ISO 9001 improve firm productivity?," European Journal of Operational Research, Elsevier, vol. 283(2), pages 530-540.
    15. Levy, Marc, 2011. "The Banzhaf index in complete and incomplete shareholding structures: A new algorithm," European Journal of Operational Research, Elsevier, vol. 215(2), pages 411-421, December.
    16. Husslage, B.G.M. & Borm, P.E.M. & Burg, T. & Hamers, H.J.M. & Lindelauf, R., 2014. "Ranking Terrorists in Networks : A Sensitivity Analysis of Al Qaeda’s 9/11 Attack," Discussion Paper 2014-028, Tilburg University, Center for Economic Research.
    17. Param Vir Singh & Nachiketa Sahoo & Tridas Mukhopadhyay, 2014. "How to Attract and Retain Readers in Enterprise Blogging?," Information Systems Research, INFORMS, vol. 25(1), pages 35-52, March.
    18. Crama, Yves & Hübner, Georges & Leruth, Luc & Renneboog, Luc, 2021. "Identifying Ultimate Beneficial Owners : A Risk-Based Approach to Improving the Transparency of International Financial Flows," Other publications TiSEM eb0e5f55-aca6-4db8-a871-f, Tilburg University, School of Economics and Management.
    19. Leruth, Luc & Mazarei, Adnan & Regibeau, Pierre & Renneboog, Luc, 2022. "Green Energy Depends on Critical Minerals. Who Controls the Supply Chains?," Discussion Paper 2022-024, Tilburg University, Center for Economic Research.
    20. Yanhao Wei & Pinar Yildirim & Christophe Van den Bulte & Chrysanthos Dellarocas, 2016. "Credit Scoring with Social Network Data," Marketing Science, INFORMS, vol. 35(2), pages 234-258, March.

    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:eee:ejores:v:262:y:2017:i:2:p:708-719. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.