Journal of Internet Computing and Services (인터넷정보학회논문지)

Korean Society for Internet Information (한국인터넷정보학회)
권호 표지
DOI QR코드

DOI QR Code

Effect Analysis of an Additional Edge on Centrality and Ranking of Graph Using Computational Experiments

실험계산을 통한 에지 한 개 추가에 따른 그래프의 중심성 및 순위 변화 분석

  • Han, Chi-Geun (Dept. of Computer Engineering, Kyung Hee University) ;
  • Lee, Sang-Hoon (Dept. of Computer Engineering, Kyung Hee University)
  • Received : 2015.03.09
  • Accepted : 2015.08.18
  • Published : 2015.10.31
Download PDF
⟨ Previous Next ⟩

Abstract

The centrality is calculated to describe the importance of a node in a graph and ranking is given according to the centrality for each node. There are many centrality measures and we use degree centrality, closeness centrality, eigenvector centrality, and betweenness centrality. In this paper, we analyze the effect of an additional edge of a graph on centrality and ranking through experimental computations. It is found that the effect of an additional edge on centrality and ranking of the nodes in the graph is different according to the graph structure using PCA. The results can be used for define the graph characteristics.

그래프에서 각 노드에 대해 그래프 내의 중요도를 나타내는 중심성(centrality)을 계산할 수 있고, 그 값에 따라 각 노드는 중요도 순위(ranking)를 갖는다. 중심성을 나타내는 방법으로는 여러 척도가 있는데, 본 연구에서는 연결도(degree) 중심성, 밀접도(closeness) 중심성, 특성벡터(eigenvector) 중심성, betweenness 중심성에 국한하여 연구를 수행하였다. 본 연구는 그래프에서 에지를 하나 추가할 경우, 그래프 내 노드 전체에 미치는 노드의 중심성 및 순위의 변화를 실험계산을 통해 확인한다. 그리고, 추가되는 에지가 노드 전체의 중심성 및 순위에 미치는 영향은 그래프의 형태에 따라 달라진다는 것을 PCA(Principal Component Analysis)를 통해 밝혔다. 이 사실은 그래프의 구조적 특성을 구분하는 방법으로도 사용될 수 있다.

Keywords

References

  1. P. Boldi and S. Vigna, "Axioms for Centrality", Social and Information Networks, Nov. 2013. http://dx.doi.org/10.1080/15427951.2013.865686
  2. 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. http://dx.doi.org/10.1007/s10791-005-5661-0
  3. K. Avrachenkov and N. Litvak, "The Effect of New Links on Google Pagerank", Stochastic Models, 22 (2), pp. 319-331, 2006. http://dx.doi.org/10.1080/15326340600649052
  4. J. Ronqui and T. Gonzalo, "Analyzing Complex Networks Through Correlations in Centrality Measurements", Social and Information Networks, June 2014. http://dx.doi.org/10.1088/1742-5468/2015/05/P05030
  5. 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. http://dx.doi.org/10.1016/j.socnet.2005.05.001
  6. S. Segarra and A. Ribeiro, "Stability and Continuity of Centrality Measures in Weighted Graphs", Social and Information Networks, Oct. 2014. http://arxiv.org/abs/1410.5119
  7. 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. http://dx.doi.org/10.1137/090772745
  8. 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. http://dl.acm.org/citation.cfm?id=384003
  9. P. Erdos and A. Renyl, "On Random Graphs, I", Publicationes Mathematicae 6, pp. 290-297, 1959. http://ftp.math-inst.hu/-p_erdos/1959-11.pdf
  10. A.-L. Barabasi and R. Albert, "Emergence of Scaling in Random Networks", Science, 286, pp. 509-512, 1997. ISBN: 978-140084135-6;0691113572;978-069111357-9
  11. I. Jolliffe, "Principal Component Analysis", Springer Series in Statistics, 2002. http://dx.doi.org/
  12. W. Zachary, "An Information Flow Model for Conflict and Fission in Small Groups", J. of Anthropological Research 33, pp. 452-473, 1977. http://www.jstor.org/stable/3629752 https://doi.org/10.1086/jar.33.4.3629752
  13. D. Lusseau, K. Schneider, O. Boisseau, P. Haase, E. Slooten, and S. Dawson, "The Bottlenose Dolphin Community of Doubtful Sound Features a Large Proportion of Long-Lasting Associations", Behavioral Ecology and Sociobiology, Vol. 54, No. 4, pp 396-405, Sept. 2003. http://dx.doi.org/10.1007/s00265-003-0651-y
  14. C. Correa, T. Crnovrsanin, and K. Ma, "Visual Reasoning about social networks using centrality sensitivity", IEEE Trans. on Visualization and Computer Graphics, Vol. 18, No. 1, pp. 106-120, 2012. http://dx.doi.org/10.1109/TVCG.2010.260
  15. D. Watts and S. Strogatz, "Collective Dynamics of 'Small-World' Networks", Nature, Vol. 393, No. 6684, pp. 440-442, 1998. http://dx.doi.org/10.1038/30918

Cited by

  1. Study of the Activation Plan for Rural Tourism of the Jeollabuk-do Using Big Data Analysis vol.27, pp.S, 2016, https://doi.org/10.7856/kjcls.2016.27.S.665