Analysis of Effect of an Additional Edge on Eigenvector Centrality of Graph (에지 한 개 추가에 따른 그래프의 고유벡터 중심성 변화 분석)

Chi-Geun Han (한치근); Sang-Hoon Lee (이상훈)

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 ¹, Sang-Hoon Lee ¹

¹경희대학교

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.

KEYWORDS

graph, eigenvector centrality

Citation status

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

[other] P. Boldi / 2013 / Axioms for Centrality / Social and Information Networks

[journal] R. Lempel / 2005 / Rank-Stability and Rank-Similarity of Link-Based Web Ranking Algorithms in Authority-Connected Graphs / Information Retrieval 8(2) : 245~264

[journal] K. Avrachenkov / 2006 / The Effect of New Links on Google Pagerank, Stochastic Models 22(2) : 319~331

[other] J. Ronqui / 2014 / Analyzing Complex Networks Through Correlations in Centrality Measurements / Social and Information Networks

[journal] S. Borgatti / 2006 / On the Robustness of Centrality Measures under Conditions of Imperfect Data / Social Networks 28(2) : 124~136

[other] S. Segarra / 2014 / Stability and Continuity of Centrality Measures in Weighted Graphs / Social and Information Networks

[journal] T. Chartier / 2011 / Sensitivity and Stability of Ranking Vectors / SIAM J. Sci. Comput. 33(3) : 1077~1102

[confproc] A. Ng / 2001 / Stable Algorithms for Link Analysis / SIGIR '01 Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval : 258~266

[journal] C. Correa / 2012 / Visual Reasoning about Social Networks using Centrality Sensitivity / IEEE Transactions on Visualization and Computer Graphics 18(1) : 106~120

[book] G. Golub / 1988 / Matrix Computations / Johns Hopkins

[book] P. Erdös / 1959 / On Random Graphs, I / Publicationes Mathematicae : 290~297

[journal] A.-L. Barabási / 1997 / Emergence of Scaling in Random Networks / Science 286 : 509~512

[journal] D. Watts / 1998 / Collective Dynamics of 'Small-World' Networks / Nature 393(6684) : 440~442

[journal] 이우기 / 2005 / Detecting Intentionally Biased Web Pages In terms of Hypertext Information / 한국컴퓨터정보학회논문지 / 한국컴퓨터정보학회 10(1) : 59~66

[journal] 이상운 / 2015 / Maximum Degree Vertex Central Located Algorithm for Bandwidth Minimization Problem / 한국컴퓨터정보학회논문지 / 한국컴퓨터정보학회 20(7) : 41~47

KJCKorea
Journal Central

Journal of The Korea Society of Computer and Information 2023 KCI Impact Factor : 0.65