본문 바로가기
  • Home

Analysis of Effect of an Additional Edge on Eigenvector Centrality of Graph

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2016, 21(1), pp.25-31
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

Chi-Geun Han 1 Sang-Hoon Lee 1

1경희대학교

Accredited

ABSTRACT

There are many methods to describe the importance of a node, centrality, in a graph. In this paper, we focus on the eigenvector centrality. In this paper, an analytical method to estimate the difference of centrality with an additional edge in a graph is proposed. In order to validate the analytical method to estimate the centrality, two problems, to decide an additional edge that maximizes the difference of all centralities of all nodes in the graph and to decide an additional edge that maximizes the centrality of a specific node, are solved using three kinds of random graphs and the results of the estimated edge and observed edge are compared. Though the estimated centrality difference is slightly different from the observed real centrality in some cases, it is shown that the proposed method is effective to estimate the centrality difference with a short running time.

Citation status

* References for papers published after 2022 are currently being built.