nach oben

Erschienen in:

2023 | OriginalPaper | Buchkapitel

Optimal Bond Percolation in Networks by a Fast-Decycling Framework

verfasst von : Leilei Wu, Xiao-Long Ren

Erschienen in: Complex Networks and Their Applications XI

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Keeping a physical distance and creating social bubbles are popular measures that have been implemented to prevent infection and slow transmission of COVID-19. Such measures aim to reduce the risk of infection by decreasing the interactions among social networks. This, theoretically, corresponds to the optimal bond percolation (OBP) problem in networks, which is the problem of finding the minimum set of edges whose removal or deactivation from a network would dismantle it into isolated sub-components at most size C. To solve the OBP problem, we proposed a fast-decycling framework composed of three stages: (1) recursively removes influential edges from the 2-core of the network, (2) breaks large trees, and (3) reinserts the unnecessarily removed edges through an explosive percolation process. The proposed approaches perform better than existing OBP algorithms on real-world networks. Our results shed light on the faster design of a more practical social distancing and social bubble policy.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel An Analysis of Bitcoin Dust Through Authenticated Queries

Nächstes Kapitel Integrating Temporal Graphs via Dual Networks: Dense Graph Discovery

Helbing, D.: Globally networked risks and how to respond. Nature 497(7447), 51–59 (2013)CrossRef

Alvarez-Rodriguez, U., Battiston, F., de Arruda, G.F., Moreno, Y., Perc, M., Latora, V.: Evolutionary dynamics of higher-order interactions in social networks. Nat. Human Behav. pp. 1–10 (2021)

Acuto, M.: Covid-19: lessons for an urban (izing) world. One Earth 2(4), 317–319 (2020)CrossRef

World Health Organization.: Who coronavirus (covid-19) dashboard. https://covid19.who.int. [Online; Accessed 20 June 2022]. Globally, as of 5:24 pm CEST, 17 June 2022, there have been 535,863,950 confirmed cases of COVID-19, including 6,314,972 deaths, reported to WHO. As of 15 June 2022, a total of 11,902,271,619 vaccine doses have been administered (2022)

Phillips, N., et al.: The coronavirus is here to stay-here’s what that means. Nature 590(7846), 382–384 (2021)CrossRef

Lokhande, T., Yang, X., Xie, Y., Cook, K., Liang, J., LaBelle, S., Meyers, C.: Gis-based classroom management system to support covid-19 social distance planning. Comput. Urban Sci. 2(1), 1–12 (2022)CrossRef

Ren, X.-L.: The dismantling problem in complex networks and its applications. Ph.D. thesis, ETH Zurich (2021)

Del Ferraro, G., Moreno, A., Min, B., Morone, F., Pérez-Ramírez, Ú., Pérez-Cervera, L., Parra, L.C., Holodny, A., Canals, S., Makse, H.A.: Finding influential nodes for integration in brain networks using optimal percolation theory. Nat. Commun. 9(1), 2274 (2018)CrossRef

Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23(2), 298–305 (1973)CrossRefMATH

10.

Lipton, R., Rose, D., Tarjan, R.: Generalized nested dissection. SIAM J. Numer. Anal. 16(2), 346–358 (1979)CrossRefMATH

11.

Pothen, A., Simon, H.D., Liou, K.-P.: Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl. 11(3), 430–452 (1990)CrossRefMATH

12.

Bui, T.N., Jones, C.: Finding good approximate vertex and edge partitions is NP-hard. Inf. Process. Lett. 42(3), 153–159 (1992)CrossRefMATH

13.

Guattery, S., Miller, G.L.: On the quality of spectral separators. SIAM J. Matrix Anal. Appl. 19(3), 701–719 (1998)CrossRefMATH

14.

Requião da Cunha, B., González-Avella, J.C., Gonçalves, S.: Fast fragmentation of networks using module-based attacks. PLoS ONE 10(11), 1–15 (2015)CrossRef

15.

Tian, L., Bashan, A., Shi, D.-N., Liu, Y.-Y.: Articulation points in complex networks. Nat. Commun. 8(1), 1–9 (2017)CrossRef

16.

Ren, X.-L., Gleinig, N., Tolić, D., Antulov-Fantulin, N.: Underestimated cost of targeted attacks on complex networks. Complexity 2018 (2018)

17.

Braunstein, A., Dall’Asta, L., Semerjian, G., Zdeborová, L.: Network dismantling. Proc. Natl. Acad. Sci. U.S.A. 113(44), 12368–12373 (2016)CrossRef

18.

Ren, X.-L., Gleinig, N., Helbing, D., Antulov-Fantulin, N.: Generalized network dismantling. Proc. Natl. Acad. Sci. U.S.A. 116(14), 6554–6559 (2019)CrossRefMATH

19.

Ren, X.-L.: Network dismantling: from vertex separator to edge separator using explosive percolation. (Res. Gate) preprint (2020)

20.

Morone, F., Makse, H.A.: Influence maximization in complex networks through optimal percolation. Nature 524(7563), 65–68 (2015)CrossRef

21.

Chen, W., Wang, C., Wang, Y.: Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1029–1038. ACM (2010)

22.

Chen, Y., Paul, G., Havlin, S., Liljeros, F., Stanley, H.E.: Finding a better immunization strategy. Phys. Rev. Lett. 101(5), 58701 (2008)CrossRef

23.

Clusella, P., Grassberger, P., Pérez-Reche, F.J., Politi, A.: Immunization and targeted destruction of networks using explosive percolation. Phys. Rev. Lett. 117, 208301 (2016)CrossRef

24.

Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46(6), 787–832 (1999)CrossRefMATH

25.

Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings and graph partitioning. In: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing — STOC 04. ACM Press (2004)

26.

Feige, U., Hajiaghayi, M., Lee, J.R.: Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput. 38, 629–657 (2008)CrossRefMATH

27.

Fan, C., Zeng, L., Sun, Y., Liu, Y.-Y.: Finding key players in complex networks through deep reinforcement learning. Nat. Mach. Intell. 1–8 (2020)

28.

Mugisha, S., Zhou, H.-J.: Identifying optimal targets of network attack by belief propagation. Phys. Rev. E 94, 012305 (2016)CrossRef

29.

Ren, X.-L., Antulov-Fantulin, N.: Ensemble approach for generalized network dismantling. In: International Conference on Complex Networks and Their Applications, pp. 783–793. Springer (2019)

30.

Zdeborová, L., Zhang, P., Zhou, H.-J.: Fast and simple decycling and dismantling of networks. Sci. Rep. 6, 37954 (2016)CrossRef

31.

Achlioptas, D., D’Souza, R.M., Spencer, J.: Explosive percolation in random networks. Science 323(5920), 1453–1455 (2009)CrossRefMATH

32.

Kunegis, J.: The Koblenz network collection. In: Proceedings of the International Web Observatory Workshop, pp. 1343–1350 (2013)

33.

Ribeiro, H.V., Alves, L.G.A., Martins, A.F., Lenzi, E.K., Perc, M.: The dynamical structure of political corruption networks. J. Complex Netw. 6, 989–1003 (2018)CrossRef

34.

Xu, Z., Harriss, R.: Exploring the structure of the us intercity passenger air transportation network: a weighted complex network approach. GeoJournal 73(2), 87–102 (2008)CrossRef

35.

Broadbent, S.R., Hammersley, J.M.: Percolation processes: I. Crystals and mazes. In: Mathematical Proceedings of the Cambridge Philosophical Society, vol. 53, pp. 629–641. Cambridge University Press (1957)

36.

Seidman, S.B.: Network structure and minimum degree. Soc. Netw. 5(3), 269–287 (1983)CrossRef

37.

Dorogovtsev, S.N., Goltsev, A.V., Mendes, J.F.F.: K-core organization of complex networks. Phys. Rev. Lett. 96(4), 040601 (2006)CrossRef

38.

Kitsak, M., Gallos, L.K., Havlin, S., Liljeros, F., Muchnik, L., Stanley, H.E., Makse, H.A.: Identification of influential spreaders in complex networks. Nat. Phys. 6(11), 888–893 (2010)CrossRef

39.

Shang, Y.: Attack robustness and stability of generalized k-cores. New J. Phys. 21(9), 093013 (2019)CrossRef

40.

Shang, Y.: Generalized k-cores of networks under attack with limited knowledge. Chaos, Solitons Fractals 152, 111305 (2021)CrossRefMATH

41.

Wandelt, S., Sun, X., Feng, D., Zanin, M., Havlin, S.: A comparative analysis of approaches to network-dismantling. Sci. Rep. 8(1), 1–15 (2018)CrossRef

42.

Liu, X., Li, D., Ma, M., Szymanski, B.K., Stanley, H.E., Gao, J.: Network resilience. Phys. Rep. 971, 1–108 (2022)CrossRefMATH

43.

Cohen, R., Havlin, S.: Complex networks: structure, robustness and function. Cambridge University Press (2010)

44.

Callaway, D.S., Newman, M.E.J., Strogatz, S.H., Watts, D.J.: Network robustness and fragility: percolation on random graphs. Phys. Rev. Lett. 85(25), 5468–5471 (2000)CrossRef

Titel: Optimal Bond Percolation in Networks by a Fast-Decycling Framework
verfasst von: Leilei Wu
Xiao-Long Ren
Verlag: Springer International Publishing
Buch: Complex Networks and Their Applications XI
Print ISBN: 978-3-031-21130-0

Electronic ISBN: 978-3-031-21131-7

Copyright-Jahr: 2023
DOI: https://doi.org/10.1007/978-3-031-21131-7_40

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner