Closeness centrality reconstruction of tree graphs

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.