{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:34:40Z","timestamp":1772120080335,"version":"3.50.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,3,3]],"date-time":"2025-03-03T00:00:00Z","timestamp":1740960000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,3,3]],"date-time":"2025-03-03T00:00:00Z","timestamp":1740960000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Finding the\n                    <jats:italic>k<\/jats:italic>\n                    -median in a network involves identifying a subset of k vertices that minimize the total distance to all other vertices in a graph. This problem has been extensively studied in computer science, graph theory, operations research, and numerous areas due to its significance in a wide range of applications. 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 20,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.\n                  <\/jats:p>","DOI":"10.1007\/s41109-025-00692-0","type":"journal-article","created":{"date-parts":[[2025,3,3]],"date-time":"2025-03-03T06:45:23Z","timestamp":1740984323000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An extended analysis of approximation algorithms for k-median problems on complex networks"],"prefix":"10.1007","volume":"10","author":[{"given":"Roldan","family":"Pozo","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,3,3]]},"reference":[{"key":"692_CR1","doi-asserted-by":"crossref","unstructured":"Arya V, Garg N, Khandekar R, Meyerson A, Munagala K, Pandit V (2001) 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\u201329","DOI":"10.1145\/380752.380755"},{"key":"692_CR2","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/j.physa.2013.10.047","volume":"395","author":"J Bae","year":"2014","unstructured":"Bae J, Kim S (2014) Identifying and ranking influential spreaders in complex networks by neighborhood coreness. Physica A 395:549\u2013559. https:\/\/doi.org\/10.1016\/j.physa.2013.10.047","journal-title":"Physica A"},{"key":"692_CR3","unstructured":"DuBois CL (2008) UCI Network Data Repository, University of California, School of Information and Computer Sciences, Irvine, CA. http:\/\/networkdata.ics.uci.edu"},{"issue":"6","key":"692_CR4","doi-asserted-by":"publisher","first-page":"1420","DOI":"10.1086\/226707","volume":"83","author":"M Granovetter","year":"1978","unstructured":"Granovetter M (1978) Threshold models of collective behavior. Am J Sociol 83(6):1420\u20131443","journal-title":"Am J Sociol"},{"issue":"4","key":"692_CR5","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1137\/S0036144500371907","volume":"42","author":"HW Hethcote","year":"2000","unstructured":"Hethcote HW (2000) The mathematics of infectious diseases. SIAM Rev 42(4):599\u2013653","journal-title":"SIAM Rev"},{"issue":"3","key":"692_CR6","doi-asserted-by":"publisher","first-page":"741","DOI":"10.1007\/s11192-010-0193-9","volume":"85","author":"JE Hirsch","year":"2010","unstructured":"Hirsch JE (2010) An index to quantify an individual\u2019s scientific research output that takes into account the effect of multiple coauthorship. Scientometrics 85(3):741\u2013754. https:\/\/doi.org\/10.1007\/s11192-010-0193-9","journal-title":"Scientometrics"},{"issue":"3","key":"692_CR7","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1137\/0137040","volume":"37","author":"O Kariv","year":"1979","unstructured":"Kariv O, Hakimi SL (1979) An algorithmic approach to network location problems. i: the p-centers. SIAM J Appl Math 37(3):513\u2013538","journal-title":"SIAM J Appl Math"},{"key":"692_CR8","doi-asserted-by":"crossref","unstructured":"Kempe D, Kleinberg J, Tardos \u00c9 (2003) 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\u2013146","DOI":"10.1145\/956750.956769"},{"issue":"11","key":"692_CR9","doi-asserted-by":"publisher","first-page":"888","DOI":"10.1038\/nphys1746","volume":"6","author":"M Kitsak","year":"2010","unstructured":"Kitsak M, Gallos LK, Havlin S, Liljeros F, Muchnik L, Stanley HE, Makse HA (2010) Identification of influential spreaders in complex networks. Nat Phys 6(11):888\u2013893","journal-title":"Nat Phys"},{"key":"692_CR10","doi-asserted-by":"crossref","unstructured":"Kunegis J (2013) Konect\u2014the koblenz network collection. In: Proceedings of the international web observatory workshop. Boston, MA pp 1343\u20131350. http:\/\/konect.uni-koblenz.de\/networks","DOI":"10.1145\/2487788.2488173"},{"key":"692_CR11","unstructured":"Leskovec J, Krevl A (2014) Snap datasets: stanford large network dataset collection. http:\/\/snap.stanford.edu\/data"},{"issue":"1","key":"692_CR12","doi-asserted-by":"publisher","first-page":"10168","DOI":"10.1038\/ncomms10168","volume":"7","author":"L L\u00fc","year":"2016","unstructured":"L\u00fc L, Zhou T, Zhang QM, Stanley HE (2016) The h-index of a network node and its relation to degree and coreness. Nat Commun 7(1):10168. https:\/\/doi.org\/10.1038\/ncomms10168","journal-title":"Nat Commun"},{"key":"692_CR13","doi-asserted-by":"crossref","unstructured":"Mislove A, Marcon M, Gummadi KP, Druschel P, Bhattacharjee B (2007) Measurement and analysis of online social networks. In: Proceedings of the 5th ACM\/Usenix internet measurement conference (IMC\u201907), San Diego, CA","DOI":"10.1145\/1298306.1298311"},{"key":"692_CR14","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198805090.001.0001","volume-title":"Networks","author":"M Newman","year":"2018","unstructured":"Newman M (2018) Networks. Oxford University Press, Oxford"},{"key":"692_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26641-1","volume-title":"Dynamical systems on networks","author":"MA Porter","year":"2016","unstructured":"Porter MA, Gleeson JP (2016) Dynamical systems on networks. Springer Internationl Publishing, Berlin"},{"key":"692_CR16","unstructured":"Pozo R (2019) NGraph Network Toolkit. https:\/\/math.nist.gov\/~RPozo\/ngraph"},{"key":"692_CR17","doi-asserted-by":"publisher","unstructured":"Pozo R (2023) Approximation algorithms for k-median problems on complex networks: theory and practice. In: International conference on complex networks and their applications. Springer, Berlin, pp 89\u2013101. https:\/\/doi.org\/10.1007\/978-3-031-53472-0_8","DOI":"10.1007\/978-3-031-53472-0_8"},{"issue":"3","key":"692_CR18","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1002\/net.20128","volume":"48","author":"J Reese","year":"2006","unstructured":"Reese J (2006) Solution methods for the p-median problem: an annotated bibliography. Networks 48(3):125\u2013142. https:\/\/doi.org\/10.1002\/net.20128","journal-title":"Networks"},{"issue":"6684","key":"692_CR19","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"DJ Watts","year":"1998","unstructured":"Watts DJ, Strogatz SH (1998) Collective dynamics of \u2018small-world\u2019 networks. Nature 393(6684):440\u2013442. https:\/\/doi.org\/10.1038\/30918","journal-title":"Nature"},{"issue":"1","key":"692_CR20","doi-asserted-by":"publisher","first-page":"27823","DOI":"10.1038\/srep27823","volume":"6","author":"JX Zhang","year":"2016","unstructured":"Zhang JX, Chen DB, Dong Q, Zhao ZD (2016) Identifying a set of influential spreaders in complex networks. Sci Rep 6(1):27823. https:\/\/doi.org\/10.1038\/srep27823","journal-title":"Sci Rep"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-025-00692-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41109-025-00692-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-025-00692-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,3]],"date-time":"2025-03-03T06:45:28Z","timestamp":1740984328000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-025-00692-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,3]]},"references-count":20,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,12]]}},"alternative-id":["692"],"URL":"https:\/\/doi.org\/10.1007\/s41109-025-00692-0","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-4248706\/v1","asserted-by":"object"}]},"ISSN":["2364-8228"],"issn-type":[{"value":"2364-8228","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,3]]},"assertion":[{"value":"10 April 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 January 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 March 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"6"}}