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

Optimal compression for bipartite networks

Author

Listed:
  • Huang, Shuhong
  • Wang, Xiangrong
  • Peng, Liyang
  • Xie, Jiarong
  • Sun, Jiachen
  • Hu, Yanqing

Abstract

Bipartite network is crucial for recommendation systems as user-product behaviors are thoroughly described by bipartite interactions. Almost all of the state-of-the-art network compression algorithms are designed for general networks without harnessing the unique bipartite structure. Until 2017, Basu and Varshney proposed a compression algorithm, BSZIP, selectively for bipartite networks. However, the performance of this algorithm is not clear. Here, we derive the structural entropy which is equivalent to the compression limit for unlabeled random bipartite networks. Theoretically, we show that BSZIP algorithm asymptotically achieves the analytical limit.

Suggested Citation

  • Huang, Shuhong & Wang, Xiangrong & Peng, Liyang & Xie, Jiarong & Sun, Jiachen & Hu, Yanqing, 2021. "Optimal compression for bipartite networks," Chaos, Solitons & Fractals, Elsevier, vol. 151(C).
    • Handle: RePEc:eee:chsofr:v:151:y:2021:i:c:s0960077921005610
    DOI: 10.1016/j.chaos.2021.111207
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0960077921005610
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.chaos.2021.111207?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. Serguei Saavedra & Daniel B. Stouffer & Brian Uzzi & Jordi Bascompte, 2011. "Strong contributors to network persistence are the most vulnerable to extinction," Nature, Nature, vol. 478(7368), pages 233-235, October.
    2. Samir Suweis & Filippo Simini & Jayanth R. Banavar & Amos Maritan, 2013. "Emergence of structural and dynamical properties of ecological mutualistic networks," Nature, Nature, vol. 500(7463), pages 449-452, August.
    3. María J. Palazzi & Albert Solé-Ribalta & Violeta Calleja-Solanas & Sandro Meloni & Carlos A. Plata & Samir Suweis & Javier Borge-Holthoefer, 2021. "An ecological approach to structural flexibility in online communication systems," Nature Communications, Nature, vol. 12(1), pages 1-11, December.
    4. Jiarong Xie & Fanhui Meng & Jiachen Sun & Xiao Ma & Gang Yan & Yanqing Hu, 2021. "Detecting and modelling real percolation and phase transitions of information on social media," Nature Human Behaviour, Nature, vol. 5(9), pages 1161-1168, September.
    5. Jiachen Sun & Ling Feng & Jiarong Xie & Xiao Ma & Dashun Wang & Yanqing Hu, 2020. "Revealing the predictability of intrinsic structure in complex networks," Nature Communications, Nature, vol. 11(1), pages 1-10, December.
    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. Sun, Jiachen & Feng, Ling & Du, Mingwei & Ma, Xiao & Fan, Zhengping & Gloor, Peter & Hu, Yanqing, 2021. "Ultra-efficient information detection on large-scale online social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 581(C).
    2. Antonios Garas & Celine Rozenblat & Frank Schweitzer, 2015. "The network structure of city-firm relations," Papers 1512.02859, arXiv.org.
    3. Sebastián Bustos & Charles Gomez & Ricardo Hausmann & César A Hidalgo, 2012. "The Dynamics of Nestedness Predicts the Evolution of Industrial Ecosystems," PLOS ONE, Public Library of Science, vol. 7(11), pages 1-8, November.
    4. Liang, Yuan & Qi, Mingze & Huangpeng, Qizi & Duan, Xiaojun, 2023. "Percolation of interlayer feature-correlated multiplex networks," Chaos, Solitons & Fractals, Elsevier, vol. 176(C).
    5. Ai, Jun & He, Tao & Su, Zhan, 2023. "Identifying influential nodes in complex networks based on resource allocation similarity," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 627(C).
    6. Chengyi Tu & Joel Carr & Samir Suweis, 2016. "A data driven network approach to rank countries production diversity and food specialization," Papers 1606.01270, arXiv.org.
    7. Luiz G. A. Alves & Giuseppe Mangioni & Isabella Cingolani & Francisco A. Rodrigues & Pietro Panzarasa & Yamir Moreno, 2018. "The nested structural organization of the worldwide trade multi-layer network," Papers 1803.02872, arXiv.org, revised Sep 2019.
    8. Wang, Xiangrong & Peron, Thomas & Dubbeldam, Johan L.A. & Kéfi, Sonia & Moreno, Yamir, 2023. "Interspecific competition shapes the structural stability of mutualistic networks," Chaos, Solitons & Fractals, Elsevier, vol. 172(C).
    9. Matthieu Cristelli & Andrea Tacchella & Luciano Pietronero, 2015. "The Heterogeneous Dynamics of Economic Complexity," PLOS ONE, Public Library of Science, vol. 10(2), pages 1-15, February.
    10. Tu, Chengyi & Luo, Jianhong & Fan, Ying & Pan, Xuwei, 2023. "Dimensionality reduction in stochastic complex dynamical networks," Chaos, Solitons & Fractals, Elsevier, vol. 175(P1).
    11. Yicheol Han & Stephan J. Goetz, 2015. "The Economic Resilience of U.S. Counties during the Great Recession," The Review of Regional Studies, Southern Regional Science Association, vol. 45(2), pages 131-149, Fall.
    12. Junya Wang & Yi-Jiao Zhang & Cong Xu & Jiaze Li & Jiachen Sun & Jiarong Xie & Ling Feng & Tianshou Zhou & Yanqing Hu, 2024. "Reconstructing the evolution history of networked complex systems," Nature Communications, Nature, vol. 15(1), pages 1-11, December.
    13. Chengyi Tu & Joel Carr & Samir Suweis, 2016. "A Data Driven Network Approach to Rank Countries Production Diversity and Food Specialization," PLOS ONE, Public Library of Science, vol. 11(11), pages 1-15, November.
    14. Fraccascia, Luca & Yazan, Devrim Murat & Albino, Vito & Zijm, Henk, 2020. "The role of redundancy in industrial symbiotic business development: A theoretical framework explored by agent-based simulation," International Journal of Production Economics, Elsevier, vol. 221(C).
    15. Omar A. Alismaiel & Javier Cifuentes-Faura & Waleed Mugahed Al-Rahmi, 2022. "Online Learning, Mobile Learning, and Social Media Technologies: An Empirical Study on Constructivism Theory during the COVID-19 Pandemic," Sustainability, MDPI, vol. 14(18), pages 1-15, September.
    16. Michel Alexandre & Felipe Jordão Xavier & Thiago Christiano Silva & Francisco A. Rodrigues, 2022. "Nestedness in the Brazilian Financial System," Working Papers Series 566, Central Bank of Brazil, Research Department.
    17. Fanhui Meng & Haoming Sun & Jiarong Xie & Chengjun Wang & Jiajing Wu & Yanqing Hu, 2021. "Preference for Number of Friends in Online Social Networks," Future Internet, MDPI, vol. 13(9), pages 1-13, September.
    18. Sandra Hervías-Parejo & Mar Cuevas-Blanco & Lucas Lacasa & Anna Traveset & Isabel Donoso & Ruben Heleno & Manuel Nogales & Susana Rodríguez-Echeverría & Carlos J. Melián & Victor M. Eguíluz, 2024. "On the structure of species-function participation in multilayer ecological networks," Nature Communications, Nature, vol. 15(1), pages 1-16, December.
    19. Jin-Hee Cho & Jianxi Gao, 2016. "Cyber War Game in Temporal Networks," PLOS ONE, Public Library of Science, vol. 11(2), pages 1-16, February.
    20. Mika J. Straka & Guido Caldarelli & Tiziano Squartini & Fabio Saracco, 2017. "From Ecology to Finance (and Back?): Recent Advancements in the Analysis of Bipartite Networks," Papers 1710.10143, arXiv.org.

    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:chsofr:v:151:y:2021:i:c:s0960077921005610. 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: Thayer, Thomas R. (email available below). General contact details of provider: https://www.journals.elsevier.com/chaos-solitons-and-fractals .

    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.