CENTRALITY MEASURES ON BRINKMANN GRAPH: BEFORE AND AFTER NODE DELETION

  • Masrurotullaily Masrurotullaily Department of Mathematics Education, Universitas Islam Negeri Kiai Haji Achmad Siddiq Jember
DOI: https://doi.org/10.30598/barekengvol16iss3pp1097-1104
Keywords: degree, betweenness, closeness, centrality, Brinkmann, node deletion

Abstract

Brinkmann graph is a 4-regular graph with 21 nodes and 42 edges discovered by Gunnar Brinkmann in 1992. To our knowledge, the research specifically on Brinkmann graph is still hard to find. Therefore, this research was carried out to analyze the Brinkmann graph in term of its centrality. The centrality measures used are degree, betweenness, and closeness centrality. In this paper, we presented the centrality measures not only on the Brinkmann graph but also on the Brinkmann graph after node deletion to see how the impact of node deletion to the centrality of graph. Before deletion, the results showed that according to the betweenness centrality, there exist 7 nodes who act as mediators or bridges in the Brinkmann graph. Therefore, when a node among these nodes has deleted, it affected not only any other mediator nodes and the furthest nodes from the deleted node but also the nodes that are adjacent to the deleted nodes.

Downloads

Download data is not yet available.

References

W. D. Joyner and C. G. Melles, Adventures in Graph Theory. Springer International Publishing, 2017. [Online]. Available: https://books.google.co.id/books?id=NdFEDwAAQBAJ

W. Commons, “File:Brinkmann graph LS.svg — Wikimedia Commons, the free media repository.” 2020. [Online]. Available: https://commons.wikimedia.org/w/index.php?title=File:Brinkmann_graph_LS.svg&oldid=453381461

J. Liang, D. Lou, Z. Qin, and Q. Yu, “A polynomial algorithm determining cyclic vertex connectivity of 4-regular graphs,” J Comb Optim, vol. 38, no. 2, pp. 589–607, 2019.

N. Ramya and M. Muthukumar, “On coloring of 4-regular graphs,” International Journal of Pure and Applied Mathematics, vol. 116, 2020.

G. Lancia, E. Pippia, and F. Rinaldi, “Proving hamiltonian properties in connected 4-regular graphs: an ILP-based approach,” arXiv preprint arXiv:2112.05087, 2021.

W. Liu, Q. Cui, and Y. Wang, “On 4-connected 4-regular graphs without even cycle decompositions,” Discrete Mathematics, vol. 345, no. 10, p. 113012, 2022, doi: https://doi.org/10.1016/j.disc.2022.113012.

S. P. Tahalea, E. Salouw, and A. W. A. Wibowo, “TOURISM ON INSTAGRAM: A SOCIAL NETWORK ANALYSIS,” BAREKENG, vol. 16, no. 1, pp. 199–206, Mar. 2022.

J. Zhang and Y. Luo, “Degree centrality, betweenness centrality, and closeness centrality in social network,” in 2017 2nd international conference on modelling, simulation and applied mathematics (MSAM2017), 2017, pp. 300–303.

C. Sciarra, G. Chiarotti, F. Laio, and L. Ridolfi, “A change of perspective in network centrality,” Scientific Reports, vol. 8, no. 1, p. 15269, 2018, doi: 10.1038/s41598-018-33336-8.

K. Das, S. Samanta, and M. Pal, “Study on centrality measures in social networks: a survey,” Social Network Analysis and Mining, vol. 8, no. 1, p. 13, 2018, doi: 10.1007/s13278-018-0493-2.

R. B. Bapat, Graphs and Matrices. Springer London, 2014. [Online]. Available: https://books.google.co.id/books?id=LWCSBAAAQBAJ

Y. Yustiawan, W. Maharani, and A. A. Gozali, “Degree Centrality for Social Network with Opsahl Method,” Procedia Computer Science, vol. 59, pp. 419–426, 2015, doi: 10.1016/j.procs.2015.07.559.

J. Matta, G. Ercal, and K. Sinha, “Comparing the speed and accuracy of approaches to betweenness centrality approximation,” Computational Social Networks, vol. 6, no. 1, p. 2, 2019, doi: 10.1186/s40649-019-0062-5.

I. Tsalouchidou, R. Baeza-Yates, F. Bonchi, K. Liao, and T. Sellis, “Temporal betweenness centrality in dynamic graphs,” International Journal of Data Science and Analytics, vol. 9, no. 3, pp. 257–272, 2020, doi: 10.1007/s41060-019-00189-x.

R. Goldstein and M. S. Vitevitch, “The influence of closeness centrality on lexical processing,” Front Psychol, vol. 8, p. 1683, 2017.

Published
2022-09-01
How to Cite
[1]
M. Masrurotullaily, “CENTRALITY MEASURES ON BRINKMANN GRAPH: BEFORE AND AFTER NODE DELETION”, BAREKENG: J. Math. & App., vol. 16, no. 3, pp. 1097-1104, Sep. 2022.
Issue
Vol 16 No 3 (2022): BAREKENG: Journal of Mathematics and Its Applications
Section
Articles

Copyright (c) 2022 Masrurotullaily Masrurotullaily

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Authors who publish with this Journal agree to the following terms:

  1. Author retain copyright and grant the journal right of first publication with the work simultaneously licensed under a creative commons attribution license that allow others to share the work within an acknowledgement of the work’s authorship and initial publication of this journal.
  2. Authors are able to enter into separate, additional contractual arrangement for the non-exclusive distribution of the journal’s published version of the work (e.g. acknowledgement of its initial publication in this journal).
  3. Authors are permitted and encouraged to post their work online (e.g. in institutional repositories or on their websites) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published works.