{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:35:42Z","timestamp":1772120142935,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T00:00:00Z","timestamp":1676592000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T00:00:00Z","timestamp":1676592000000},"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>This paper is concerned with distributed detection of central nodes in complex networks using closeness centrality. Closeness centrality plays an essential role in network analysis. Distributed tasks such as leader election can make effective use of centrality information for highly central nodes, but complete network information is not locally available. Evaluating closeness centrality exactly requires complete knowledge of the network; for large networks, this may be inefficient, so closeness centrality should be approximated. Here, situations for decentralised network view construction where a node has zero knowledge about other nodes on the network at initial and there is no central node to coordinate evaluations of node closeness centrality are considered. Unlike centralized methods for detection of central nodes, in decentralized methods an approximated view of the network must be available at each node, then each node can evaluate its own closeness centrality before it can share it with others when applicable. Based on our knowledge, there is no much work done under this setting where the leading approach consists of running the breadth-first search Skiena (1998) on each node with a limited number of iterations (which is less than the diameter of the graph into consideration), as done by You et al. (2017), Wehmuth and Ziviani (2012), before each node evaluates its centrality. Running the breadth-first search on each node in a decentralized fashion requires high cost in terms of communication. Our contribution is to consider a better way of constructing network view in a decentralised manner with less communication cost. This paper refines a distributed centrality computation algorithm by You et al. (2017) by pruning nodes which are almost certainly not most central. For example, in a large network, leave nodes can not play a central role. This leads to a reduction in the number of messages exchanged to determine the centrality of the remaining nodes. Our results show that our approach reduces the number of messages for networks which contain many prunable nodes. Our results also show that reducing the number of messages may have a positive impact on running time and memory size.<\/jats:p>","DOI":"10.1007\/s41109-023-00539-6","type":"journal-article","created":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T12:35:16Z","timestamp":1676637316000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Distributed Identification of Central Nodes with Less Communication"],"prefix":"10.1007","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6165-8402","authenticated-orcid":false,"given":"Jordan F.","family":"Masakuna","sequence":"first","affiliation":[]},{"given":"Pierre K.","family":"Kafunda","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,2,17]]},"reference":[{"issue":"4","key":"539_CR1","doi-asserted-by":"publisher","first-page":"e90283","DOI":"10.1371\/journal.pone.0090283","volume":"9","author":"K Batool","year":"2014","unstructured":"Batool K, Niazi MA (2014) Towards a methodology for validation of centrality measures in complex networks. PLoS ONE 9(4):e90283","journal-title":"PLoS ONE"},{"issue":"6","key":"539_CR2","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1121\/1.1906679","volume":"22","author":"A Bavelas","year":"1950","unstructured":"Bavelas A (1950) Communication Patterns in Task-Oriented Groups. The Journal of the Acoustical Society of America 22(6):725\u2013730","journal-title":"The Journal of the Acoustical Society of America"},{"issue":"3","key":"539_CR3","first-page":"145","volume":"65","author":"J Cohen","year":"1962","unstructured":"Cohen J (1962) The statistical power of abnormal-social psychological research: a review. Psychol Sci Public Interest 65(3):145","journal-title":"Psychol Sci Public Interest"},{"key":"539_CR4","unstructured":"Coulouris GF, Dollimore J, Kindberg T (2005) Distributed systems: concepts and design. Pearson Education"},{"issue":"3","key":"539_CR5","doi-asserted-by":"publisher","first-page":"279","DOI":"10.4300\/JGME-D-12-00156.1","volume":"4","author":"MS Gail","year":"2012","unstructured":"Gail MS, Richard F (2012) Using effect size-or why the P value is not enough. J Grad Med Educ 4(3):279\u2013282","journal-title":"J Grad Med Educ"},{"issue":"26","key":"539_CR6","doi-asserted-by":"publisher","first-page":"13","DOI":"10.3182\/20120914-2-US-4030.00040","volume":"45","author":"F Garin","year":"2012","unstructured":"Garin F, Varagnolo D, Johansson KH (2012) Distributed estimation of diameter, radius and eccentricities in anonymous networks. IFAC Proc 45(26):13\u201318","journal-title":"IFAC Proc"},{"key":"539_CR7","unstructured":"Hagberg A, Schult D, Swart P, Conway D, S\u00e9guin-Charbonneau L, Ellison C, Edwards B, Torrents J (2013) Networkx. High productivity software for complex networks. Webov\u00e1 str\u00e1 nka https:\/\/networkx.lanl.gov\/wiki"},{"issue":"1","key":"539_CR8","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0378-8733(94)00248-9","volume":"17","author":"P Hage","year":"1995","unstructured":"Hage P, Harary F (1995) Eccentricity and centrality in networks. Soc Networks 17(1):57\u201363","journal-title":"Soc Networks"},{"key":"539_CR9","unstructured":"Masakuna JF (2020) Active strategies for coordination of solitary robots. Ph.D. thesis, Stellenbosch University"},{"issue":"1\/2","key":"539_CR10","doi-asserted-by":"publisher","first-page":"81","DOI":"10.2307\/2332226","volume":"30","author":"MG Kendall","year":"1938","unstructured":"Kendall MG (1938) A new measure of rank correlation. Biometrika 30(1\/2):81\u201393","journal-title":"Biometrika"},{"issue":"2","key":"539_CR11","first-page":"661","volume":"52","author":"C Kim","year":"2013","unstructured":"Kim C, Wu M (2013) Leader election on tree-based centrality in ad hoc networks. Telecommun Syst 52(2):661\u2013670","journal-title":"Telecommun Syst"},{"issue":"1","key":"539_CR12","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1109\/TCOM.1979.1094280","volume":"27","author":"S Lam","year":"1979","unstructured":"Lam S, Reiser M (1979) Congestion control of store-and-forward networks by input buffer limits-an analysis. IEEE Trans Commun 27(1):127\u2013134","journal-title":"IEEE Trans Commun"},{"key":"539_CR13","doi-asserted-by":"crossref","unstructured":"Leskovec J, Kleinberg J, Faloutsos C (2005) Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proceedings of the eleventh ACM SIGKDD international conference on knowledge discovery in data mining, pp 177\u2013187. ACM","DOI":"10.1145\/1081870.1081893"},{"issue":"1","key":"539_CR14","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1217299.1217301","volume":"1","author":"J Leskovec","year":"2007","unstructured":"Leskovec J, Kleinberg J, Faloutsos C (2007) Graph evolution: densification and shrinking diameters. ACM Trans Knowl Discov Data 1(1):2","journal-title":"ACM Trans Knowl Discov Data"},{"key":"539_CR15","doi-asserted-by":"crossref","unstructured":"Meghanathan N (2015) Correlation coefficient analysis of centrality metrics for complex network graphs. In: Computer science on-line conference, pp 11\u201320. Springer","DOI":"10.1007\/978-3-319-18503-3_2"},{"key":"539_CR16","unstructured":"Naz A (2017) Distributed algorithms for large-scale robotic ensembles: centrality, synchronization and self-reconfiguration. Ph.D. thesis, Universit\u00e9 Bourgogne Franche-Comt\u00e9"},{"issue":"6","key":"539_CR17","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/s00359-006-0099-4","volume":"192","author":"ME Nelson","year":"2006","unstructured":"Nelson ME, MacIver MA (2006) Sensory acquisition in active sensing systems. J Comp Physiol A 192(6):573\u2013586","journal-title":"J Comp Physiol A"},{"key":"539_CR18","unstructured":"Ram\u00edrez RJ, Santoro N (1979) Distributed control of updates in multiple-copy databases: a time optimal algorithm. In: Proceedings of the 4th berkeley conference on distributed data management and computer networks (Berkeley, CA), pp 191\u2013207"},{"key":"539_CR19","unstructured":"Sheth A, Hartung C, Han R (2005) A decentralized fault diagnosis system for wireless sensor networks. In: IEEE international conference on mobile adhoc and sensor systems, pp 1\u20133. IEEE"},{"key":"539_CR20","volume-title":"The algorithm design manual","author":"SS Skiena","year":"1998","unstructured":"Skiena SS (1998) The algorithm design manual, vol 1. Springer, New York"},{"key":"539_CR21","first-page":"663","volume":"15","author":"C Spearman","year":"1961","unstructured":"Spearman C (1961) General intelligence objectively determined and measured. Am J Psychol 15:663\u2013671","journal-title":"Am J Psychol"},{"issue":"3","key":"539_CR22","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1109\/MRA.2012.2206473","volume":"19","author":"T Tomic","year":"2012","unstructured":"Tomic T, Schmid K, Lutz P, Domel A, Kassecker M, Mair E, Grixa IL, Ruess F, Suppa M, Burschka D (2012) Toward a fully autonomous UAV: research platform for indoor and outdoor urban search and rescue. IEEE Robot Autom Magaz 19(3):46\u201356","journal-title":"IEEE Robot Autom Magaz"},{"key":"539_CR23","doi-asserted-by":"crossref","unstructured":"Wehmuth K, Ziviani A (2012) Distributed assessment of the closeness centrality ranking in complex networks. In: The fourth annual workshop on simplifying complex networks for practitioners, pp 43\u201348. ACM","DOI":"10.1145\/2184356.2184368"},{"key":"539_CR24","doi-asserted-by":"crossref","unstructured":"Wilcoxon F (1992) individual comparisons by ranking methods. In: Breakthroughs in statistics, pp 196\u2013202. Springer","DOI":"10.1007\/978-1-4612-4380-9_16"},{"issue":"5","key":"539_CR25","doi-asserted-by":"publisher","first-page":"2080","DOI":"10.1109\/TAC.2016.2604373","volume":"62","author":"K You","year":"2017","unstructured":"You K, Tempo R, Qiu L (2017) Distributed algorithms for computation of centrality measures in complex networks. IEEE Trans Autom Control 62(5):2080\u20132094","journal-title":"IEEE Trans Autom Control"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-023-00539-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41109-023-00539-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-023-00539-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T12:36:00Z","timestamp":1676637360000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-023-00539-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,17]]},"references-count":25,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["539"],"URL":"https:\/\/doi.org\/10.1007\/s41109-023-00539-6","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-1622718\/v1","asserted-by":"object"}]},"ISSN":["2364-8228"],"issn-type":[{"value":"2364-8228","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,17]]},"assertion":[{"value":"4 May 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 February 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 February 2023","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":"Ethics approval and consent to participate"}},{"value":"The authors declare that they have no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"13"}}