Abstract
This paper focuses on the uncapacitated k-median facility location problem, which asks to locate k facilities in a network that minimize the total routing time, taking into account the constraints of nodes that are able to serve as servers and clients, as well as the level of demand in each client node. This problem is important in a wide range of applications from operation research to mobile ad-hoc networks. Existing algorithms for this problem often lead to high computational costs when the underlying network is very large, or when the number k of required facilities is very large. We aim to improve existing algorithms by taking into considerations of the community structures of the underlying network. More specifically, we extend the strategy of local search with single swap with a community detection algorithm. As a real-world case study, we analyze in detail Auckland North Shore spatial networks with varying distance threshold and compare the algorithms on these networks. The results show that our algorithm significantly reduces running time while producing equally optimal results.
Z. Zhang—This work is partially supported by China National Key Research and Development Program No. 2016YFB0800301.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
References
Auckland council district plan operative north shore section 2002. Accessed 30 Sept 2017. http://temp.aucklandcouncil.govt.nz/EN/planspoliciesprojects/plansstrategies/DistrictRegionalPlans/northshorecitydistrictplan/Pages/home.aspx
Auckland open data. Accessed 30 Sept 2017. https://aucklandopendata-aucklandcouncil.opendata.arcgis.com/datasets
Ahlgren, B., Dannewitz, C., Imbrenda, C., Kutscher, D., Ohlman, B.: A survey of information-centric networking. IEEE Commun. Mag. 50(7), 26–36 (2012)
Aikens, C.H.: Facility location models for distribution planning. Eur. J. Oper. Res. 22(3), 263–279 (1985)
Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for k-median and facility location problems. SIAM J. Comput. 33(3), 544–562 (2004)
Barabási, A.-L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999)
Bell, M.G., Iida, Y., et al.: Transportation Network Analysis. Wiley, New York (1997)
Blondel, V.D., Guillaume, J.-L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. J. Stat. Mech. Theor. Exp. 2008(10), P10008 (2008)
Chaudhuri, S., Garg, N., Ravi, R.: The p-neighbor k-center problem. Inf. Process. Lett. 65(3), 131–134 (1998)
Chrobak, M., Kenyon, C., Young, N.E.: The reverse greedy algorithm for the metric K-median problem. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 654–660. Springer, Heidelberg (2005). https://doi.org/10.1007/11533719_66
Church, R., Velle, C.R.: The maximal covering location problem. Pap. Reg. Sci. 32(1), 101–118 (1974)
Dai, F., Wu, J.: On constructing k-connected k-dominating set in wireless networks. In: Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium, 10 pp. IEEE (2005)
Fortunato, S.: Community detection in graphs. Phys. Rep. 486(3), 75–174 (2010)
Frank, C., Römer, K.: Distributed facility location algorithms for flexible configuration of wireless sensor networks. In: Aspnes, J., Scheideler, C., Arora, A., Madden, S. (eds.) DCOSS 2007. LNCS, vol. 4549, pp. 124–141. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-73090-3_9
Girvan, M., Newman, M.E.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. 99(12), 7821–7826 (2002)
González-Brevis, P., Gondzio, J., Fan, Y., Poor, H.V., Thompson, J., Krikidis, I., Chung, P.-J.: Base station location optimization for minimal energy consumption in wireless networks. In: IEEE 73rd Vehicular Technology Conference (VTC Spring), pp. 1–5. IEEE (2011)
Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. J. Algorithms 31(1), 228–248 (1999)
Huang, C.-M., Lan, K.-C., Tsai, C.-Z.: A survey of opportunistic networks. In: 22nd International Conference on Advanced Information Networking and Applications-Workshops, AINAW 2008, pp. 1672–1677. IEEE (2008)
Lambiotte, R., Blondel, V.D., De Kerchove, C., Huens, E., Prieur, C., Smoreda, Z., Van Dooren, P.: Geographical dispersal of mobile communication networks. Phys. A Stat. Mech. Appl. 387(21), 5317–5325 (2008)
Lewis, F.L., et al.: Wireless sensor networks. In: Smart Environments: Technologies, Protocols, and Applications, pp. 11–46 (2004)
Liao, K., Guo, D.: A clustering-based approach to the capacitated facility location problem. Trans. GIS 12(3), 323–339 (2008)
Liu, J., Minnes, M.: Deciding the isomorphism problem in classes of unary automatic structures. Theor. Comput. Sci. 412(18), 1705–1717 (2011)
Liu, J., Wei, Z.: Community detection based on graph dynamical systems with asynchronous runs. In: Second International Symposium on Computing and Networking (CANDAR), pp. 463–469. IEEE (2014)
Miller, H.J., Han, J.: Geographic Data Mining and Knowledge Discovery. CRC Press (2009)
Moskvina, A., Liu, J.: How to build your network? A structural analysis. In: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, pp. 2597–2603. AAAI Press (2016)
Moskvina, A., Liu, J.: Togetherness: an algorithmic approach to network integration. In: IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pp. 223–230. IEEE (2016)
Newman, M.E.: Modularity and community structure in networks. Proc. Natl. Acad. Sci. 103(23), 8577–8582 (2006)
Pantazopoulos, P., Stavrakakis, I., Passarella, A., Conti, M.: Efficient social-aware content placement in opportunistic networks. In: Seventh International Conference on Wireless On-Demand Network Systems and Services (WONS), pp. 17–24. IEEE (2010)
Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393(6684), 440 (1998)
Yan, B., Chen, Y., Liu, J.: Dynamic relationship building: exploitation versus exploration on a social network. In: Bouguettaya, A., et al. (eds.) WISE 2017. LNCS, vol. 10569, pp. 75–90. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-68783-4_6
Yang, K.-Q., Yang, L., Gong, B.-H., Lin, Z.-C., He, H.-S., Huang, L.: Geographical networks: geographical effects on network properties. Front. Phys. China 3(1), 105–111 (2008)
Zhong, C., Arisona, S.M., Huang, X., Batty, M., Schmitt, G.: Detecting the dynamics of urban structure through spatial network analysis. Int. J. Geogr. Inf. Sci. 28(11), 2178–2199 (2014)
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Xu, R., Zhang, Z., Liu, J., Situ, N., Jin, J.H. (2018). Facility Location Selection Using Community-Based Single Swap: A Case Study. In: Zhu, L., Zhong, S. (eds) Mobile Ad-hoc and Sensor Networks. MSN 2017. Communications in Computer and Information Science, vol 747. Springer, Singapore. https://doi.org/10.1007/978-981-10-8890-2_5
Download citation
DOI: https://doi.org/10.1007/978-981-10-8890-2_5
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-10-8889-6
Online ISBN: 978-981-10-8890-2
eBook Packages: Computer ScienceComputer Science (R0)