nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Relaxation and Matrix Randomized Rounding for the Maximum Spectral Subgraph Problem

verfasst von : Cristina Bazgan, Paul Beaujean, Éric Gourdin

Erschienen in: Combinatorial Optimization and Applications

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

Modifying the topology of a network to mitigate the spread of an epidemic with epidemiological constant \(\lambda \) amounts to the NP-hard problem of finding a partial subgraph with maximum number of edges and spectral radius bounded above by \(\lambda \). A software-defined network (SDN) capable of real-time topology reconfiguration can then use an algorithm for finding such subgraph to quickly remove spreading malware threats without deploying specific security countermeasures.

In this paper, we propose a novel randomized approximation algorithm based on the relaxation and rounding framework that achieves a \(O(\log n)\) approximation in the case of finding a subgraph with spectral radius bounded by \(\lambda \in (\log n, \lambda _1(G))\) where \(\lambda _1(G)\) is the spectral radius of the input graph and n its number of nodes. We combine this algorithm with a maximum matching algorithm to obtain a \(O(\log ^2 n)\) approximation algorithm for all values of \(\lambda \). We also describe how the mathematical programming formulation we give has several advantages over previous approaches which attempted at finding a subgraph with minimum spectral radius given an edge removal budget.

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 New Results About the Linearization of Scaffolds Sharing Repeated Contigs

Nächstes Kapitel Bipartite Communities via Spectral Partitioning

Bhatia, R.: Matrix Analysis, vol. 169. Springer, Heidelberg (2013). https://doi.org/10.1007/978-1-4612-0653-8CrossRefMATH

Chakrabarti, D., Wang, Y., Wang, C., Leskovec, J., Faloutsos, C.: Epidemic thresholds in real networks. ACM Trans. Inf. Syst. Secur. (TISSEC) 10(4), 1 (2008)CrossRef

Chung, F., Radcliffe, M.: On the spectra of general random graphs. Electron. J. Comb. 18(1), 215 (2011)MathSciNetMATH

Ganesh, A., Massoulié, L., Towsley, D.: The effect of network topology on the spread of epidemics. In: Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2005), vol. 2, pp. 1455–1466 (2005)

Ghosh, A., Boyd, S.: Growing well-connected graphs. In: Proceedings of the IEEE Conference on Decision and Control (CDC 2006), pp. 6605–6611. IEEE (2006)

Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM (JACM) 42(6), 1115–1145 (1995)MathSciNetCrossRef

Kolla, A., Makarychev, Y., Saberi, A., Teng, S-H.: Subgraph sparsification and nearly optimal ultrasparsifiers. In: Proceedings of the ACM Symposium on Theory of Computing (STOC 2010), pp. 57–66. ACM (2010)

Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796–817 (2001)MathSciNetCrossRef

Le, C.M., Levina, E., Vershynin, R.: Concentration and regularization of random graphs. Random Struct. Algorithms 51(3), 538–561 (2017)MathSciNetCrossRef

10.

Mehdi, S.A., Khalid, J., Khayam, S.A.: Revisiting traffic anomaly detection using software defined networking. In: Sommer, R., Balzarotti, D., Maier, G. (eds.) RAID 2011. LNCS, vol. 6961, pp. 161–180. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23644-0_9CrossRef

11.

Mosk-Aoyama, D.: Maximum algebraic connectivity augmentation is NP-hard. Oper. Res. Lett. 36(6), 677–679 (2008)MathSciNetCrossRef

12.

Motwani, R., Raghavan, P.: Randomized Algorithms. Chapman & Hall/CRC, Boca Raton (2010)MATH

13.

Nie, J.: Polynomial matrix inequality and semidefinite representation. Math. Oper. Res. 36(3), 398–415 (2011)MathSciNetCrossRef

14.

Pan, V.Y., Chen, Z.Q.: The complexity of the matrix eigenproblem. In: Proceedings of the ACM Symposium on Theory of Computing (STOC 1999), pp. 507–516 (1999)

15.

Parrilo, P.A.: Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96(2), 293–320 (2003)MathSciNetCrossRef

16.

Aditya Prakash, B., Chakrabarti, D., Faloutsos, M., Valler, N., Faloutsos, C.: Threshold conditions for arbitrary cascade models on arbitrary networks. In: Proceedings of the IEEE International Conference on Data Mining (ICDM 2011), pp. 537–546 (2011)

17.

Raghavan, P., Tompson, C.D.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7(4), 365–374 (1987)MathSciNetCrossRef

18.

Raghavendra, P.: Optimal algorithms and inapproximability results for every CSP? In: Proceedings of the ACM Symposium on Theory of Computing (STOC 2008), pp. 245–254. ACM (2008)

19.

Saha, S., Adiga, A., Aditya Prakash, B., Vullikanti, A.K.S.: Approximation algorithms for reducing the spectral radius to control epidemic spread. In: Proceedings of the SIAM International Conference on Data Mining (SDM 2015), pp. 568–576 (2015)CrossRef

20.

Shin, S., Gu, G.: CloudWatcher: network security monitoring using OpenFlow in dynamic cloud networks (or: how to provide security monitoring as a service in clouds?). In: Proceedings of the IEEE International Conference on Network Protocols (ICNP 2012), pp. 1–6. IEEE (2012)

21.

Stevanović, D.: Resolution of AutoGraphiX conjectures relating the index and matching number of graphs. Linear Algebra Appl. 8(433), 1674–1677 (2010)MathSciNetCrossRef

22.

Tropp, J.A., et al.: An introduction to matrix concentration inequalities. Found. Trends® Mach. Learn. 8(1–2), 1–230 (2015)MATH

23.

van Handel, R.: Structured random matrices. In: Carlen, E., Madiman, M., Werner, E.M. (eds.) Convexity and Concentration. TIVMA, vol. 161, pp. 107–156. Springer, New York (2017). https://doi.org/10.1007/978-1-4939-7005-6_4CrossRef

24.

Van Mieghem, P.: Graph Spectra for Complex Networks. Cambridge University Press, Cambridge (2010)CrossRef

25.

Van Mieghem, P., Omic, J., Kooij, R.: Virus spread in networks. IEEE/ACM Trans. Netw. (TON) 17(1), 1–14 (2009)CrossRef

26.

Van Mieghem, P., et al.: Decreasing the spectral radius of a graph by link removals. Phys. Rev. E 84(1), 016101 (2011)CrossRef

27.

Wang, G., Ng, T.S., Shaikh, A.: Programming your network at run-time for big data applications. In: Proceedings of the Workshop on Hot Topics in Software Defined Networks (HotSDN 2012), pp. 103–108. ACM (2012)

28.

Wang, Y., Chakrabarti, D., Wang, C., Faloutsos, C.: Epidemic spreading in real networks: an eigenvalue viewpoint. In: Proceedings of the International Symposium on Reliable Distributed Systems (SRDS 2003), pp. 25–34. IEEE (2003)

29.

Zhang, Y., Adiga, A., Vullikanti, A., Aditya Prakash, B.: Controlling propagation at group scale on networks. In: Proceedings of the International Conference on Data Mining (ICDM 2015), pp. 619–628 (2015)

Titel: Relaxation and Matrix Randomized Rounding for the Maximum Spectral Subgraph Problem
verfasst von: Cristina Bazgan
Paul Beaujean
Éric Gourdin
Verlag: Springer International Publishing
Buch: Combinatorial Optimization and Applications
Print ISBN: 978-3-030-04650-7

Electronic ISBN: 978-3-030-04651-4

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-030-04651-4_8

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"