IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v540y2020ics0378437119318060.html
   My bibliography  Save this article

A subset selection based approach to structural reducibility of complex networks

Author

Listed:
  • Tripathi, Richa
  • Reza, Amit

Abstract

Most of the real world networks such as the internet network, collaboration networks, brain networks, citation networks, powerline and airline networks are very large and to study their structure and dynamics one often requires working with large connectivity (adjacency) matrices. However, it is almost always true that a few or sometimes most of the nodes and their connections are not very crucial for network functioning or that the network is robust to a failure of certain nodes and their connections to the rest of the network. In the present work, we aim to extract the size reduced representation of complex networks such that new representation has the most relevant network nodes and connections and retains its spectral properties. To achieve this, we use the Subset Selection (SS) procedure. The SS method, in general, is used to retrieve maximum information (based on Frobenius norm) from a matrix in terms of its most informative columns. The retrieved matrix, typically known as subset has columns of an original matrix that have the least linear dependency. We present the application of SS procedure to many adjacency matrices of real-world networks and model network types to extract their subset. The subset owing to its small size can play a crucial role in analyzing spectral properties of large complex networks where space and time complexity of analyzing full adjacency matrices are too expensive. The adjacency matrix constructed from the obtained subset has a smaller size and represents the most important network structure. We observed that the subset network which is almost half the size of the original network has better information flow efficiency than the original network. Also, we found that the contribution to the Inverse Participation ratio of the network comes almost entirely from nodes that are there in the subset. This implies that the SS procedure can extract the top most influential nodes without the need for analyzing the full adjacency matrix.

Suggested Citation

  • Tripathi, Richa & Reza, Amit, 2020. "A subset selection based approach to structural reducibility of complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 540(C).
    • Handle: RePEc:eee:phsmap:v:540:y:2020:i:c:s0378437119318060
    DOI: 10.1016/j.physa.2019.123214
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437119318060
    Download Restriction: Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000
    File URL: https://libkey.io/10.1016/j.physa.2019.123214?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. Xu, Shuang & Wang, Pei & Zhang, Chunxia, 2019. "Identification of influential spreaders in bipartite networks:A singular value decomposition approach," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 513(C), pages 297-306.
    2. Réka Albert & Hawoong Jeong & Albert-László Barabási, 1999. "Diameter of the World-Wide Web," Nature, Nature, vol. 401(6749), pages 130-131, September.
    3. Réka Albert & Hawoong Jeong & Albert-László Barabási, 2000. "Error and attack tolerance of complex networks," Nature, Nature, vol. 406(6794), pages 378-382, July.
    4. Manlio De Domenico & Vincenzo Nicosia & Alexandre Arenas & Vito Latora, 2015. "Structural reducibility of multilayer networks," Nature Communications, Nature, vol. 6(1), pages 1-9, November.
    5. Manlio De Domenico & Albert Solé-Ribalta & Elisa Omodei & Sergio Gómez & Alex Arenas, 2015. "Ranking in interconnected multilayer networks reveals versatile nodes," Nature Communications, Nature, vol. 6(1), pages 1-6, November.
    6. Pagani, Giuliano Andrea & Aiello, Marco, 2013. "The Power Grid as a complex network: A survey," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(11), pages 2688-2700.
    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. Kashin Sugishita & Yasuo Asakura, 2021. "Vulnerability studies in the fields of transportation and complex networks: a citation network analysis," Public Transport, Springer, vol. 13(1), pages 1-34, March.
    2. Quan Ye & Guanghui Yan & Wenwen Chang & Hao Luo, 2023. "Vital node identification based on cycle structure in a multiplex network," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 96(2), pages 1-16, February.
    3. He, Xuan & Zhao, Hai & Cai, Wei & Li, Guang-Guang & Pei, Fan-Dong, 2015. "Analyzing the structure of earthquake network by k-core decomposition," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 421(C), pages 34-43.
    4. Gangwal, Utkarsh & Singh, Mayank & Pandey, Pradumn Kumar & Kamboj, Deepak & Chatterjee, Samrat & Bhatia, Udit, 2022. "Identifying early-warning indicators of onset of sudden collapse in networked infrastructure systems against sequential disruptions," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 591(C).
    5. Laurienti, Paul J. & Joyce, Karen E. & Telesford, Qawi K. & Burdette, Jonathan H. & Hayasaka, Satoru, 2011. "Universal fractal scaling of self-organized networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 390(20), pages 3608-3613.
    6. Sodam Baek & Kibae Kim & Jorn Altmann, 2014. "Role of Platform Providers in Service Networks: The Case of Salesforce.com AppExchange," TEMEP Discussion Papers 2014112, Seoul National University; Technology Management, Economics, and Policy Program (TEMEP), revised May 2014.
    7. Sun, Chenshuo & Pei, Xin & Hao, Junheng & Wang, Yewen & Zhang, Zuo & Wong, S.C., 2018. "Role of road network features in the evaluation of incident impacts on urban traffic mobility," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 101-116.
    8. Filiposka, Sonja & Juiz, Carlos, 2015. "Community-based complex cloud data center," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 419(C), pages 356-372.
    9. P.B., Divya & Lekha, Divya Sindhu & Johnson, T.P. & Balakrishnan, Kannan, 2022. "Vulnerability of link-weighted complex networks in central attacks and fallback strategy," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 590(C).
    10. Kashyap, G. & Ambika, G., 2019. "Link deletion in directed complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 514(C), pages 631-643.
    11. Gong, Xiao-Li & Liu, Jian-Min & Xiong, Xiong & Zhang, Wei, 2022. "Research on stock volatility risk and investor sentiment contagion from the perspective of multi-layer dynamic network," International Review of Financial Analysis, Elsevier, vol. 84(C).
    12. Tran, Huy T. & Balchanos, Michael & Domerçant, Jean Charles & Mavris, Dimitri N., 2017. "A framework for the quantitative assessment of performance-based system resilience," Reliability Engineering and System Safety, Elsevier, vol. 158(C), pages 73-84.
    13. Kibae Kim & Jörn Altmann, 2015. "Effect of Homophily on Network Formation," TEMEP Discussion Papers 2015121, Seoul National University; Technology Management, Economics, and Policy Program (TEMEP), revised Mar 2017.
    14. Zhang, Xue-Jun & Xu, Guo-Qiang & Zhu, Yan-Bo & Xia, Yong-Xiang, 2016. "Cascade-robustness optimization of coupling preference in interconnected networks," Chaos, Solitons & Fractals, Elsevier, vol. 92(C), pages 123-129.
    15. Elisa Frutos Bernal & Angel Martín del Rey, 2019. "Study of the Structural and Robustness Characteristics of Madrid Metro Network," Sustainability, MDPI, vol. 11(12), pages 1-24, June.
    16. Li, Hui & Zhao, Hai & Cai, Wei & Xu, Jiu-Qiang & Ai, Jun, 2013. "A modular attachment mechanism for software network evolution," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(9), pages 2025-2037.
    17. Luka Naglić & Lovro Šubelj, 2019. "War pact model of shrinking networks," PLOS ONE, Public Library of Science, vol. 14(10), pages 1-14, October.
    18. Modjtaba Ghorbani & Matthias Dehmer & Frank Emmert-Streib, 2020. "Properties of Entropy-Based Topological Measures of Fullerenes," Mathematics, MDPI, vol. 8(5), pages 1-23, May.
    19. Wei, Ye & Jin, Ying & Ma, Dingyu & Xiu, Chunliang, 2021. "Impact of colored motif characteristics on the survivability of passenger airline networks in China," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 566(C).
    20. Yuji Yamamoto & Keiko Yokoyama, 2011. "Common and Unique Network Dynamics in Football Games," PLOS ONE, Public Library of Science, vol. 6(12), pages 1-6, December.

    More about this item

    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:eee:phsmap:v:540:y:2020:i:c:s0378437119318060. 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.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    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.