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.
중심성 (centrality)는 네트워크 분석을 위한 주요한 개념이며, 이러한 여러 중심성 단위들 중에 매개 중심성 (betweenness centrality)는 가장 중요한 개념이다. 그래프에서 임의의 정점 또는 간선에 대한 매개 중심성은 해당 정점 혹은 간선이 그래프에 존재하는 모든 최단 경로들 중에 얼마나 참여하고 있는지를 상대적으로 나타내는 단위이다. 이러한 매개 중심성은 해당 정점 또는 간선이 그래프에서 가지는 상대적인 중요도를 나타내며, 그래프 네트워크에서 정보의 흐름에 대한 정점 혹은 간선의 기여도에 대한 이해를 제공한다. 본 학위 논문에서는 이 매개 중심성에 관련된 두 문제에 대해서 논의하도록 한다.
첫째, 그래프가 변경 되었을때, 매개 중심성을 갱신하는 방법 대해 연구한다. 본 학위 논문에서는 총 3가지의 갱신 알고리즘을 제안한다. 그래프에 변화가 생겼을 경우, 기존에는 모든 정점 또는 간선에 대해 변경된 매개 중심성 값을 새로 계산하여야만 했지만, QUBE와 QUBE+라고 불리는 갱신 알고리즘에서는 그래프 변경으로 인해 매개 중심성 값이 갱신 되어야 하는 정점을 포함하는 부분 그래프 (subgraph) 를 찾고 이 부분 그래프의 정점들에 대해 효율적으로 매개 중심성을 갱신한다. 이는 매개 중심성 계산에 고려 하여야 하는 최단 경로의 개수를 비약적으로 줄일 수 있다.
또한 k-QUBE라고 불리는 갱신 알고리즘은 그래프를 k-연결 성분 (k-connected component)으로 나눈 뒤 나누어진 성분(component)을 기반으로 최단 경로 계산 중 가지치기 (pruning)를 수행한다.
매개 중심성의 계산이 고려 하여야 하는 최단 경로의 개수에 주로 의존되는 점을 생각할 때, 본 연구에서 제안하는 방법들은 매개 중심성 갱신에 시간 비용면에서 큰 향상을 가져온다. 또한, 간선 삽입, 삭제 그리고 간선의 무게(weight) 변경 등 증가적 (incremental) 그래프 변경 뿐만 아니라 감소적(decremental) 그래프 변경에 대응하여 매개 중심성 값을 효율적으로 갱신하는 할 수 있다.
둘째, 매개 중심성 문제의 상위-k 문제에 대해 연구한다. 매개 중심성을 활용하는 많은 활용 예에서 모든 정점의 매개 중심성에 관심이 있기 보다는 매개 중심성 값이 상대적으로 높은 상위-k개의 정점에 관심을 가지는 경우가 많이 있다. 이유는 앞서 말한 것 과 같이 매개 중심성은 정점에 대한 상대적인 중요도를 나타내는데 많은 활용예에서 정점들 간의 모든 상대적 중요도를 알고 싶어 하기 보단 좀 더 중요한 정점을 찾는 것 집중하기 때문이다. 예로, 소셜 네트워크에서 영향력이 높은 사용자를 찾거나 수송 네트워크 혹은 인터넷에서 과부하되더나 병목현상을 초래하는 도로, 교차로 혹은 라우터를 찾는 등의 활용 예를 들 수 있다. 효율적으로 이러한 상위-k 매개 중심성을 가지는 정점을 찾기 위하여 이 문제를 두 개의 소 문제들로 나누고 각각의 소 문제들을 그래프에서 최소 순환경로 모음 (minimum union cycle) 이라고 불리는 부분 그래프의 특성들을 활용해 풀어냈다.
본 논문에서 제안하는 방법들에 대한 효율성을 검증하기 위해 여러 종류의 아홉가지 실제 네트워크 그래프를 가지고 실험을 수행하였다. 실험 결과들로 부터 제안된 매개 중심성 갱신 방법이 완전 동적인 그래프에서 효울적으로 매개 중심성 값을 갱신함을 보였다. 또한, 상위-k 매개 중심성 문제에 대한 제안된 방법 역시 효율적으로 모든 정점에대한 매개 중심성을 계산하지 않고 상위 매개 중심성 값을 가지는 k개의 정점을 찾아냄을 보였다. 마지막으로, 실제 매개 중심성을 활용하는 활용 예에 본 연구에서 제안된 방법을 활용 했을 경우 얼마나 큰 이득을 가져오는지 보여주기 위하여 매개 중심성을 활용하는 대표적인 활용 예인 네트워크에서 커뮤니티를 찾는 문제 (community detection problem) 에 적용하였다. 결과, 본 연구에서 제안된 방법에 기반한 커뮤니티 찾기 방법은 기존 방법 대비 비약적인 속도 향상을 가져왔다.
