Efficient update and k-highest computation algorithms for vertex and edge betweenness centralities정점 및 간선 매개 중심성의 효율적인 갱신 및 k-최대값 계산 기법

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 778
  • Download : 0
The centrality is one of the essential concepts for the analysis of networks, and the betweenness centrality is one of the most prominent measures among several centrality measures. The betweenness centrality of a vertex/edge in a graph is a measure for the participation of the vertex/edge in the shortest paths in the graph. It represents the relative importance of a vertex/edge in the graph, and allows an understanding of the extent to which a vertex/edge contributes in the flow of information. This dissertation deals with problems related to the betweenness centrality problem. First, We study an update problem of the betweenness centrality problem. We present three efficient algorithms for updating vertex and edge betweenness centralities. Traditionally, when a graph is changed, the betweenness centralities of all the vertices should be recomputed from the scratch using the entire graph. For two update algorithms (namely QUBE and QUBE+), we identify a subgraph such that the subgraph includes vertices which should be updated and then efficiently update the betweenness centralities of vertices in the subgraph. Therefore, the proposed algorithms substantially reduces the number of shortest paths to be considered. Another update algorithm called k-QUBE is presented. k-QUBE decomposes the graph into k-connected components and it prunes numerous shortest path computations base on the decomposition. As the cost of calculating the betweenness centrality mainly depends on the number of shortest paths to be considered, the proposed algorithms significantly reduce the cost of the computation. Also, our proposed algorithms are able to process both of an incremental update and a decremental update, i.e., an edge insertion, an edge deletion, and an edge weight change. Second, We focus on the top-k problem of the betweenness centrality. In many applications, we are only interested in the k-highest betweenness centrality vertices rather than the betweenness centralities of all the vertices in a graph. This is reasonable since a vertex with a higher centrality is viewed as a more important vertex than a vertex with a lower centrality, and we are only interested in the important vertices in many applications such as finding influencers in a social network, and locating bottlenecked junctions/routers in a transportation network/the Internet. To efficiently find the exact k-highest betweenness centrality vertices in a graph, we divide the problem into two subproblems and address each subproblem by using the novel properties of a subgraph called minimum union cycle. For the experiments, we use various types of real network graphs. From experimental results, we show that the proposed update algorithms can efficiently update the betweenness centralities when a graph is changed. Also, we show that the proposed top-k algorithm can efficiently finds the k-highest betweenness centrality vertices in a graph without actually calculating betweenness centralities for all the vertices in the graph. Furthermore, we implement a community detection algorithm using our proposed algorithm to show how much benefit can be obtained from the proposed algorithm in a practical application. As a result, the community detection algorithm using our algorithm tremendously reduces the time taken for detecting communities in a network.
Advisors
Choi, Sungheeresearcher최성희researcherChung, Chin-Wanresearcher정진완researcher
Description
한국과학기술원 :전산학부,
Publisher
한국과학기술원
Issue Date
2016
Identifier
325007
Language
eng
Description

학위논문(박사) - 한국과학기술원 : 전산학부, 2016.8 ,[v, 91 p. :]

Keywords

graph; betweenness centrality; update algorithm; k-highest algorithm; 그래프; 매개 중심성; 갱신 알고리즘; k-최대값 알고리즘

URI
http://hdl.handle.net/10203/222422
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=663213&flag=dissertation
Appears in Collection
CS-Theses_Ph.D.(박사논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0