Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Closeness centrality reconstruction of tree graphs

  • Published:
Central European Journal of Operations Research Aims and scope Submit manuscript

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\) in short time; the second one is a metaheuristic with some variants, they are intended to give further improvement on \(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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Algorithm 1
Fig. 2
Fig. 3
Algorithm 2
Fig. 4
Algorithm 3
Algorithm 4
Algorithm 5
Fig. 5
Fig. 6
Algorithm 6
Algorithm 7
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Data availability

The datasets generated during and/or analysed during the current study are available from the corresponding author on reasonable request.

Notes

  1. The ’outer’ nodes are the leaves, ’inner’ nodes are the non-leaves.

  2. This is a change-making-like problem (Wright 1975).

References

  • Albert R, Barabási A-L (2002) Statistical mechanics of complex networks. Rev Modern Phys 74(1):47

    Article  Google Scholar 

  • Bavelas A (1950) Communication patterns in task-oriented groups. J Acoust Soc Am 22(6):725–730

    Article  Google Scholar 

  • Candès EJ, Recht B (2009) Exact matrix completion via convex optimization. Found Comput Math 9(6):717–772

    Article  Google Scholar 

  • Champin PA, Solnon C (2003) Measuring the similarity of labeled graphs. In: International conference on case-based reasoning. Lecture notes in computer science, vol 2689

  • Ćirković P, Đor\({\bar{\!}{{{\rm b}}}}\)ević P, Milićević M, Davidović T (2022) Metaheuristic approach to spectral reconstruction of graphs. In: Mathematical optimization theory and operations research (MOTOR). LNCS, vol 13367

  • Comellas F, Diaz-Lopez J (2008) Spectral reconstruction of complex networks. Phys A Stat Mech Appl 387(25):6436–6442

    Article  Google Scholar 

  • Comellas F, Paz-Sanchez J (2008) Reconstruction of networks from their betweenness centrality. In Applications of evolutionary computing. Springer, Berlin, pp. 31-37

  • Csárdi G, Nepusz T (2006) The igraph software package for complex network research. Inter J Compl Syst, 1695. https://igraph.org

  • Das K, Samanta S, Pal M (2018) Study on centrality measures in social networks: a survey. Soc Netw Anal Min 8(1):4686

    Article  Google Scholar 

  • Erdős P, Gallai T (1961) Gráfok előírt fokú pontokkal (Graphs with points of prescribed degrees, in Hungarian). Matematikai Lapok 11:264–274

    Google Scholar 

  • Erdős P, Király Z, Miklós I (2013) On the swap-distances of different realizations of a graphical degree sequence. Comb Probab Comput 22(3):366–383

    Article  Google Scholar 

  • Erdős D, Gemulla R, Terzi E (2014) Reconstructing graphs from neighborhood data. ACM Trans Knowl Discov Data 8(4):1–22

    Article  Google Scholar 

  • Hakimi SL (1962) On realizability of a set of integers as degrees of the vertices of a linear graph I. J Soc Indust Appl Math 10(3):496–506

    Article  Google Scholar 

  • Hakimi SL, Yau SS (1965) Distance matrix of a graph and its realizability. Quart Appl Math 22(4):305–317

    Article  Google Scholar 

  • Havel V (1955) A remark on the existence of finite graphs. Casopis Pest Mat 80:477–480

    Article  Google Scholar 

  • Hein JJ (1989) An optimal algorithm to reconstruct trees from additive distance data. Bull Math Biol 51(5):597–603

    Article  Google Scholar 

  • Homolya V, Vinkó T (2022) Closeness centrality reconstruction of tree graphs - Supplementary Information. http://www.inf.u-szeged.hu/~tvinko/CCrec

  • Ipsen M, Mikhailov AS (2002) Evolutionary reconstruction of networks. Phys Rev E 66(4):046109

    Article  Google Scholar 

  • Kelly PJ (1957) A congruence theorem for trees. Pac J Math 7(1):961–968

    Article  Google Scholar 

  • Kim H, Toroczkai Z, Erdős P, Miklós I, Székely L (2009) Degree-based graph construction. J Phys A Math Theor 42(39):392001

    Article  Google Scholar 

  • Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220(4598):671–680

    Article  Google Scholar 

  • Lozano M, Rodriguez FJ (2021) Network reconstruction from betweenness centrality by artificial bee colony. Swarm Evol Comput 62:100851

    Article  Google Scholar 

  • Martello S, Toth P (1990) Knapsack problems: algorithms and computer implementations. John Wiley & Sons Inc, Hoboken

    Google Scholar 

  • Newman MEJ (2010) Networks: an introduction. Oxford University Press, Oxford

  • Pandey PK, Adhikar B (2017) A parametric model approach for structural reconstruction of scale-free networks. IEEE Trans Knowl Data Eng 29(10):2072–2085

    Article  Google Scholar 

  • Saxena A, Iyengar S (2020) Centrality measures in complex networks: A survey. arXiv preprint arXiv:2011.07190

  • Tripathi A, Vijay S (2003) A note on a theorem of Erdős & Gallai. Discr Math 265(1–3):417–420

    Article  Google Scholar 

  • Ulam S (1960) A collection of mathematical problems. Interscience tracts in pure and applied mathematics, no. 8. Interscience Publishers, New York-London

  • Varga LG, Nyúl LG, Nagy A, Balázs P (2014) Local and global uncertainty in binary tomographic reconstruction. Comput Vis Image Underst 129:52–62

    Article  Google Scholar 

  • Vuokko N, Terzi E (2010) Reconstructing randomized social networks. In SDM SIAM international conference on data mining, pp. 49-59

  • Wright JW (1975) The change-making problem. J ACM 22(1):125–128

    Article  Google Scholar 

  • Yin J-H, Li J-S (2005) Two sufficient conditions for a graphic sequence to have a realization with prescribed clique size. Discr Math 301(2–3):218–227

    Article  Google Scholar 

Download references

Acknowledgements

We thank our reviewers for their critical comments and valuable suggestions that highlighted important details and helped us in improving our paper. The research leading to these results has received funding from the national project TKP2021-NVA-09. Project no. TKP2021-NVA-09 has been implemented with the support provided by the Ministry of Innovation and Technology of Hungary from the National Research, Development and Innovation Fund, financed under the TKP2021-NVA funding scheme. It was also supported by the grant SNN-135643 of the National Research, Development and Innovation Office, Hungary.

Author information

Authors and Affiliations

  1. Department of Computational Optimization, University of Szeged, Szeged, Hungary

    Viktor Homolya & Tamás Vinkó

Authors
  1. Viktor Homolya
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tamás Vinkó
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tamás Vinkó.

Ethics declarations

Conflict of interest

The authors declare no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Homolya, V., Vinkó, T. Closeness centrality reconstruction of tree graphs. Cent Eur J Oper Res 32, 1061–1088 (2024). https://doi.org/10.1007/s10100-023-00900-1

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10100-023-00900-1

Keywords

Search

Navigation