[논문]Analysis of Effect of an Additional Edge on Eigenvector Centrality of Graph

Han, Chi-Geun; Lee, Sang-Hoon

doi:10.9708/jksci.2016.21.1.025

Analysis of Effect of an Additional Edge on Eigenvector Centrality of Graph 원문보기

韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information, v.21 no.1, 2016년, pp.25 - 31

Han, Chi-Geun (Dept. of Computer Science, Kyung Hee University) , Lee, Sang-Hoon (Dept. of Computer Science, Kyung Hee University)

Abstract ▼ AI-Helper

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.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 추가 에지가 있는 경우 고유 벡터 중심성을 효과적으로 계산하는 분석적 방법을 제시하였다. 본 논문에서 제시한 방법을 이용하여 [문제 1,2]의 근사해를 효과적으로 찾을 수 있다는 것을 실험계산을 통해 보였다.
그러나, 이러한 방법을 활용하게 되면, 각 생성 가능한 그래프 별로 eigensystem을 풀어야 하므로, 답을 얻기 위해서는 많은 시간이 필요하게 된다. 본 연구는 이들 답을 얻기 위해 완전한 답은 아니지만, 근사적인 해를 쉽게 얻을 수 있는 분석적 방법을 제시한다.
본 연구에서는 고유 벡터 중심성이 추가 에지에 대해 변화하는 정도를 추정하는 방법에 대한 것이다. 고유 벡터 중심성을 선택한 이유는 고유 벡터 중심성이 eigensystem을 활용하는 spectral measure의 가장 기본적인 중심성이고, 그래프의 변화에 따른 중심성의 민감도(sensitivity)에 관한 연구가 고유 벡터를 구하는 방법에 대해서는 많이 진행되어 있기 때문이다.
본 연구에서는 주어진 그래프 G = (V,E), V = {v1,v2,...,vn}:노드의 집합, E :에지의 집합, 에서 각 노드에 대한 고유 벡터 중심성 c∈Rn을 얻은 후, 추가 에지 한 개에 의한 각 노드의 새로운 고유 벡터 중심성 c′∈Rn를 계산하는 방법을 연구한다.
[문제 1]은 전체 노드의 중심성을 가장 많이 변화시키는 추가 에지를 찾는 것이다. 본 절에서는 이 문제를 효과적으로 해결할 수 있는 분석적 방법을 제시한다.
#이면, f^*_ab는 {f^*_ij, (i,j)∉E} 집합의 원소들을 내림차순으로 정렬하였을 때 몇 등에 해당하는지를 찾는다. 즉, 최대 변화를 가져올 것으로 추정된 추가 에지가 실제적으로 몇 번째의 큰 변화량을 가져오는지 확인하여, 분석적 방법의 정확성을 확인하고자 한다. 다음 [표 4]는 50개의 그래프에 대해 추정된 추가 에지가 실제적으로 몇 번째 내에 위치하고 있는지에 대한 누적결과를 보여 주고 있다.

가설 설정

본 연구에서는 연결된 무방향 단순(connected undirected simple) 그래프를 가정한다. 2장에서는 관련 연구를 설명하고, 3장에서는 에지 추가에 따른 모든 노드의 중심성의 변화량 추정방법, 에지 추가에 따른 각 노드의 중심성 변화량 추정방법을 설명한다.

제안 방법

고유 벡터 중심성을 선택한 이유는 고유 벡터 중심성이 eigensystem을 활용하는 spectral measure의 가장 기본적인 중심성이고, 그래프의 변화에 따른 중심성의 민감도(sensitivity)에 관한 연구가 고유 벡터를 구하는 방법에 대해서는 많이 진행되어 있기 때문이다. 가독성을 증가시키고 어휘의 단순화를 위해 지금부터 본 논문에서는 의미의 혼돈이 없는 한 고유 벡터 중심성을 단순히 중심성으로만 표시하기로 한다.
3장에서 설명한 두 가지 문제를 포함하여, 총 4 종류의 평가 항목을 정의한다. 각 평가항목은 실제로 측정한 값과 분석방법을 통한 추정치를 비교하는 방식으로 분석방법의 타당성을 검증한다. 4 종류의 평가항목과 그 결과는 다음과 같다.
노드 수가 많은 그래프의 문제에 대해서 추가 가능한 모든 에지들을 생성한 후 중심성이 어떻게 변화하는지를 확인하는 방법은 추가 가능한 에지 한 개를 추가할 때 마다 eigensystem을 풀어야 하므로 많은 시간이 소요된다. 따라서, 다음 두 절에서는 추가 에지 별로 새로운 그래프를 생성하지 않고, [문제 1,2]를 효과적으로 해결할 수 있는 분석적 방법을 제시한다.
본 연구에서는 3장의 분석방법의 유효성을 검증하기 위해 실험계산을 수행하였다. 실험계산을 위해 3종류의 무작위 그래프 생성 방법을 사용하였는데, 세 종류 무작위 생성 그래프를 Erdös와 Rényi의 그래프 (E그래프)[11], Barabási와 Albert 의 그래프 (B그래프)[12], Watts와 Strogatz의 그래프 (W그래프)[13]라 칭한다.
본 장에서는 먼저 고유 벡터 중심성을 예를 들어 설명하고, 본 논문에서 해결하고자 하는 문제를 정의한 후 그 문제들을 해결할 수 있는 분석적 방법을 제시한다. 그리고 분석적 방법에 내재하고 있는 오차에 대해 설명한다.
W그래프는 small-world 성질을 갖고 있는 노드의 평균 연결도가 m_w인 무작위 그래프이다. 생성 방법에 따라 생성된 에지의 개수가 비슷하도록 최대한 생성 파라미터를 조정하였다.
실험계산을 위해 3종류의 무작위 그래프 생성 방법을 사용하였는데, 세 종류 무작위 생성 그래프를 Erdös와 Rényi의 그래프 (E그래프)[11], Barabási와 Albert 의 그래프 (B그래프)[12], Watts와 Strogatz의 그래프 (W그래프)[13]라 칭한다.
제안한 방법은 지속적으로 변화하는 커뮤니티의 구조에서 가장 취약한 연결고리를 실시간으로 파악하거나, 자신의 중심성을 극대화시킬 방법을 찾는 현실적인 방법이 될 수 있다. 이후 연구로 Eigensystem을 기반으로 하는 PageRank 방법[14] 등에 본 방법을 확장할 수 있는 방안을 모색하도록 한다. 또한 Bandwidth Minimization 문제[15]에 대해 추가 에지에 따른 노드 중심성 변화와 해의 관계를 연구할 계획이다.

대상 데이터

에지의 개수가 클수록 추정한 에지가 1등이 될 가능성이 높음을 알 수 있다. 각 그래프에서 추가 가능한 에지의 개수는 315개~351개이다. 모든 그래프에 대해, 추정된 변화량을 최대로 하는 에지는 실제로 변화량을 최대로 하는 에지 순서로 6등 이내의 에지인 것으로 확인되었으므로, 추정된 에지의 신뢰성이 있음을 보여 주고 있다.

이론/모형

Q는 이미 알고 있는 행렬, #는 미지수 벡터, #는 알고 있는 벡터이므로, By = d,B∈R^{n × n}, y, d∈Rⁿ 형태의 선형연립방정식이 된다. 여기서 Q는 nonsingular 일 수 있으므로 역행렬을 직접 구할 수 없으므로, (식 3)을 풀기 위해 singular value decomposition (SVD) 방법을 사용한다. 즉, Q의 SVD를 통해 Q = UΣV^T, U, V∈R^{n × n} orthonormal 행렬, # = diag(σ₁,.
Chartier et al.은 n개의 팀이 모여 리그로 게임을 하여 나온 결과를 이용한 팀 순위의 결정에서 일부 게임의 승패가 달라졌을 때, 팀의 순위에 어떤 영향을 주는지를 선형대수 기반인 Colley, Massey, Markov 방법에 따라 분석했다[7]. Ng et al.

성능/효과

(3) 주체들 간의 최단경로에 많이 사용 된다. (4) 주체에 직접 연결된 주체들뿐만 아니라, 주변 주체들의 각 중요도가 높다라는 성질이 있다. 이 들 성질이 높은 정도를 수치화 하여 각각 (1) 연결도(degree) 중심성, (2) 밀접도(closeness) 중심성, (3) betweenness 중심성, (4) 고유 벡터 중심성을 정의한다.
[표 4]~[표 7]을 통해 scale-free 그래프인 B그래프에서 본 논문에서 제안한 분석적 방법이 작은 오차를 갖고, [문제 1,2]를 대부분의 경우 해결한다는 것을 알 수 있다.
[표 6]은 제안한 방법이 모든 그래프에서 높은 일치율을 보였고, 특히 B그래프인 경우 일치하는 확률이 가장 높다는 것을 보여 주고 있다. 이는 [표 5]에서 관찰한 바와 같이, B그래프의 중심성이 뚜렷한 특징으로부터 기인한다.
반면, 추가 가능한 에지에 대해 실제값 k^*_ij을 구한다면, 매번 eigensystem를 실제로 해결하여야 하고 (O(n³) 소요), 각 노드 당 O(n)개수의 연결 가능한 에지가 있으므로, 시간복잡도는 O(n×n³)= O(n⁴)가 된다. 따라서, [문제 2]를 제안한 방법으로 해결하는 것이 실제값을 계산하여 해결하는 것 보다 시간적으로 매우 효과적인 것을 알 수 있다.
본 논문에서는 추가 에지가 있는 경우 고유 벡터 중심성을 효과적으로 계산하는 분석적 방법을 제시하였다. 본 논문에서 제시한 방법을 이용하여 [문제 1,2]의 근사해를 효과적으로 찾을 수 있다는 것을 실험계산을 통해 보였다.
제안한 방법은 지속적으로 변화하는 커뮤니티의 구조에서 가장 취약한 연결고리를 실시간으로 파악하거나, 자신의 중심성을 극대화시킬 방법을 찾는 현실적인 방법이 될 수 있다. 이후 연구로 Eigensystem을 기반으로 하는 PageRank 방법[14] 등에 본 방법을 확장할 수 있는 방안을 모색하도록 한다.

후속연구

이후 연구로 Eigensystem을 기반으로 하는 PageRank 방법[14] 등에 본 방법을 확장할 수 있는 방안을 모색하도록 한다. 또한 Bandwidth Minimization 문제[15]에 대해 추가 에지에 따른 노드 중심성 변화와 해의 관계를 연구할 계획이다.

참고문헌 (15)

P. Boldi and S. Vigna, "Axioms for Centrality", Social and Information Networks, Nov. 2013.
R. Lempel and S. Moran, "Rank-Stability and Rank-Similarity of Link-Based Web Ranking Algorithms in Authority-Connected Graphs", Information Retrieval, Vol. 8, No. 2, pp 245-264, 2005.

상세보기
K. Avrachenkov and N. Litvak, "The Effect of New Links on Google Pagerank, Stochastic Models", 22 (2), pp. 319-331, 2006.

상세보기
J. Ronqui and T. Gonzalo, "Analyzing Complex Networks Through Correlations in Centrality Measurements", Social and Information Networks, June 2014.
S. Borgatti, K. Carley and D. Krackhardt, "On the Robustness of Centrality Measures under Conditions of Imperfect Data", Social Networks 28.2, pp.124-136, 2006.

상세보기
S. Segarra and A. Ribeiro, "Stability and Continuity of Centrality Measures in Weighted Graphs", Social and Information Networks, Oct. 2014.
T. Chartier, E. Kreutzer, A. Langville, and K. Pedings, "Sensitivity and Stability of Ranking Vectors", SIAM J. Sci. Comput., 33(3), pp. 1077-1102, 2011.

상세보기
A. Ng, A. Zheng and M. Jordan, "Stable Algorithms for Link Analysis", SIGIR '01 Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 258-266, 2001.
C. Correa and K. Ma, "Visual Reasoning about Social Networks using Centrality Sensitivity", IEEE Transactions on Visualization and Computer Graphics, Vol. 18, No. 1, pp. 106-120, 2012.

상세보기
G. Golub and C. Loan, "Matrix Computations", Johns Hopkins, 1988.
P. Erdos and A. Renyi, "On Random Graphs, I", Publicationes Mathematicae 6, pp. 290-297, 1959.
A.-L. Barabasi and R. Albert, "Emergence of Scaling in Random Networks", Science, 286, pp. 509-512, 1997.
D. Watts and S. Strogatz, "Collective Dynamics of 'Small-World' Networks", Nature 393 (6684), pp. 440-442. 1998.

상세보기
Woo-Key Lee, "Detecting Intentionally Biased Web Pages In terms of Hypertext Information", Journal of The Korea Society of Computer and Information, Vol. 10, No. 1, pp.59-66, 2005.
Sang-Un Lee, "Maximum Degree Vertex Central Located Algorithm for Bandwidth Minimization Problem", Journal of The Korea Society of Computer and Information, Vol. 20, No. 7, pp.41-47, 2015.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증