Closeness centrality reconstruction of tree graphs

Viktor Homolya () and Tamás Vinkó ()
Additional contact information
Viktor Homolya: University of Szeged
Tamás Vinkó: University of Szeged

Central European Journal of Operations Research, 2024, vol. 32, issue 4, No 10, 1088 pages

Abstract: Abstract This paper deals with a problem which belongs to the general question: how to reconstruct a graph from limited amount of information. As given information, we use the closeness centrality, which assigns a non-negative number to each node of the graph in question: the reciprocal of the sum of the length of the shortest paths between the node and all other nodes in the graph. Here we consider the case when the original graph is a tree and it is also known which nodes are the leaves. Based on some theoretical results, three algorithms are proposed. The first one aims at finding a non-exact solution $$G_P$$ G P in short time; the second one is a metaheuristic with some variants, they are intended to give further improvement on $$G_P$$ G P ; and the third one is designed for giving accurate results. Detailed explanations of these algorithms are given, together with numerical experiments to demonstrate their efficiency.

Keywords: Graph theory; Reconstruction from centrality; Closeness centrality; Heuristics (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10100-023-00900-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:cejnor:v:32:y:2024:i:4:d:10.1007_s10100-023-00900-1

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10100

DOI: 10.1007/s10100-023-00900-1

Access Statistics for this article

Central European Journal of Operations Research is currently edited by Ulrike Leopold-Wildburger

More articles in Central European Journal of Operations Research from Springer, Slovak Society for Operations Research, Hungarian Operational Research Society, Czech Society for Operations Research, Österr. Gesellschaft für Operations Research (ÖGOR), Slovenian Society Informatika - Section for Operational Research, Croatian Operational Research Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().