nach oben

Erschienen in:

2024 | OriginalPaper | Buchkapitel

Approximation Algorithms for k-Median Problems on Complex Networks: Theory and Practice

verfasst von : Roldan Pozo

Erschienen in: Complex Networks & Their Applications XII

Verlag: Springer Nature Switzerland

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Finding the \(k\)-median in a network involves identifying a subset of k vertices that minimize the total distance to all other vertices in a graph. While known to be computationally challenging (NP-hard) several approximation algorithms have been proposed, most with high-order polynomial-time complexity. However, the graph topology of complex networks with heavy-tailed degree distributions present characteristics that can be exploited to yield custom-tailored algorithms. We compare eight algorithms specifically designed for complex networks and evaluate their performance based on accuracy and efficiency for problems of varying sizes and application areas. Rather than relying on a small number of problems, we conduct over 16,000 experiments covering a wide range of network sizes and \(k\)-median values. While individual results vary, a few methods provide consistently good results. We draw general conclusions about how algorithms perform in practice and provide general guidelines for solutions.

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 Efficient Complex Network Representation Using Prime Numbers

Nächstes Kapitel Score and Rank Semi-monotonicity for Closeness, Betweenness and Harmonic Centrality

Certain commercial products or company names are identified here to describe our study adequately. Such identification does not imply recommendation or endorsement by the National Institute of Standards and Technology, nor does it imply that the products or names identified are necessarily the best available for the purpose.

Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristic for k-median and facility location problems. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pp. 21–29 (2001)

Bae, J., Kim, S.: Identifying and ranking influential spreaders in complex networks by neighborhood coreness. Physica A: Stat. Mech. Appl. 395, 549–559 (2014). https://doi.org/10.1016/j.physa.2013.10.047

DuBois, C.L.: UCI Network Data Repository. University of California, School of Information and Computer Sciences, Irvine, CA (2008). http://networkdata.ics.uci.edu

Granovetter, M.: Threshold models of collective behavior. Am. J. Sociol. 83(6), 1420–1443 (1978)CrossRef

Hethcote, H.W.: The mathematics of infectious diseases. SIAM Rev. 42(4), 599–653 (2000)MathSciNetCrossRef

Hirsch, J.E.: An index to quantify an individual’s scientific research output that takes into account the effect of multiple coauthorship. Scientometrics 85(3), 741–754 (2010). https://doi.org/10.1007/s11192-010-0193-9

Kariv, O., Hakimi, S.L.: An algorithmic approach to network location problems. i: The p-centers. SIAM J. Appl. Math. 37(3), 513–538 (1979)

Kempe, D., Kleinberg, J., Tardos, É.: Maximizing the spread of influence through a social network. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137–146 (2003)

Kitsak, M., et al.: Identification of influential spreaders in complex networks. Nat. Phys. 6(11), 888–893 (2010)CrossRef

10.

Kunegis, J.: Konect - The koblenz network collection. In: Proceedings of the International Web Observatory Workshop, pp. 1343–1350. Boston, MA (2013). http://konect.uni-koblenz.de/networks

11.

Leskovec, J., Krevl, A.: Snap datasets: stanford large network dataset collection (2014). http://snap.stanford.edu/data

12.

Lü, L., Zhou, T., Zhang, Q.M., Stanley, H.E.: The h-index of a network node and its relation to degree and coreness. Nature Communications 7(1), 10, 168 (2016). https://doi.org/10.1038/ncomms10168

13.

Mislove, A., Marcon, M., Gummadi, K.P., Druschel, P., Bhattacharjee, B.: Measurement and analysis of online social networks. In: Proceedings of the 5th ACM/Usenix Internet Measurement Conference (IMC’07). San Diego, CA (2007)

14.

Newman, M.: Networks. Oxford University Press, Oxford (2018)CrossRef

15.

Porter, M.A., Gleeson, J.P.: Dynamical Systems on Networks. FADSRT, vol. 4. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-26641-1CrossRef

16.

Pozo, R.: NGraph Network Toolkit (2019). https://math.nist.gov/~RPozo/ngraph

17.

Reese, J.: Solution methods for the p-median problem: an annotated bibliography. Networks 48(3), 125–142 (2006). https://doi.org/10.1002/net.20128

18.

Zhang, J.X., Chen, D.B., Dong, Q., Zhao, Z.D.: Identifying a set of influential spreaders in complex networks. Sci. Rep. 6(1), 27, 823 (2016). https://doi.org/10.1038/srep27823

Titel: Approximation Algorithms for k-Median Problems on Complex Networks: Theory and Practice
verfasst von: Roldan Pozo
Verlag: Springer Nature Switzerland
Buch: Complex Networks & Their Applications XII
Print ISBN: 978-3-031-53471-3

Electronic ISBN: 978-3-031-53472-0

Copyright-Jahr: 2024
DOI: https://doi.org/10.1007/978-3-031-53472-0_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"

Premium Partner