Users have worked on analyzing various networks to see meaningful implications. Efficient algorithms for important and useful network queries enable such users to quickly get rich information from network data. Thus, it is essential to develop such query processing algorithms for effective network analysis. This dissertation deals with proposing efficient algorithms for several important and useful network queries.
As useful query processing for social network analysis, query processing for influence maximization (IMAX query) is introduced. An IMAX query asks to find k seed nodes which maximize the spread of influence on targets specified in the query. This query can help to understand the relationship between influential users and target users. In this dissertation, first we formulate IMAX query processing, analyze it theoretically, and show the NP-hardness of it.
To efficiently answer an IMAX query, we propose an expectation model for the influence spread of a given seed set and a fast greedy-based approximation method using the expectation model.
For the expectation model, we exploit a relationship of paths between users in social networks.
For the greedy method, we work out an efficient incremental updating of the marginal gain to our objective function. We conduct experiments to evaluate the proposed method with real-life datasets, and compare the results with those of existing methods that are adapted to the problem.
From our experimental results, the proposed method is at least an order of magnitude faster than the existing methods in most cases while achieving similar accuracy.
We consider another useful query processing for network analysis, which is a distance sensitivity query. A distance sensitivity query asks to the shortest distance from a node to another node given a set of failed nodes/edges. An efficient query processing algorithm for this query computes the shortest distance in dynamic networks such as road networks and computer networks. In addition, it can be used in various situations for network analysis such as finding a detour in computer networks with failed nodes/edges and friend recommendation in social networks with blocked users. In this dissertation, we focus on improving an existing randomized algorithm for the distance sensitivity query. We find and eliminate unnecessary computations in the existing algorithm. We also devise an efficient and effective way of using randomly generated subgraphs. As a result, we propose two improved algorithms which guarantee high success probability of finding the exact answer of any given query. The first algorithm improves the query time. The second algorithm significantly improves the preprocessing time and the space.
It also improves the query time with some constraint on the number of failures. Along with these improvements, the proposed algorithms can have at least the same lower bound, for the success probability, which is proved to be guaranteed by the existing algorithm.
많은 사용자들이 유의미한 정보들을 뽑아내기 위해 다양한 네트워크들을 분석해왔다. 중요하고 유용한 네트워크 질의들을 위한 효율적인 알고리즘들은 사용자들이 빠르게 풍부한 정보를 얻는 것을 가능하게 하므로,
효과적인 네트워크 분석을 위해서 그러한 알고리즘들을 개발하는 것은 필수적이다. 본 학위논문에서는 여러 중요하고 유용한 네트워크 질의를 처리하는 효율적인 알고리즘을 제안하는 것을 다룬다.
네트워크 분석을 위한 유용한 질의 처리로서 영향력 극대화 질의 처리 문제가 소개된다. 영향력 극대화 질의는 질의에 정의된 특정 대상에 대한 영향력 확산을 최대화하는 k개의 시드 노드들을 찾는 것이다. 이 질의는 영향력이 높은 사용자들의 분포와 대상 사용자들의 분포 사이에 관계를 이해하는 데 큰 도움을 줄 것으로 사료된다.
본 학위 논문에서는 양향력 극대화 질의 처리를 정의하고 이론적으로 분석하여 그것이 NP-hard 임을 증명한다.
NP-hard인 영향력 극대화 질의 처리를 효율적으로 해결하기 위해 목표 함수의 값에 대한 예측 모델을 제안하고
그 예측 모델을 사용하여 빠른 그리디 기반의 근사 방법을 제안한다. 그러한 예측 모델을 제안하기 위해서 소셜 네트워크 사용자들 사이에 존재하는 경로들의 관계가 이용되고 그리디 방법을 위해서는 최대화하려는 목표 함수에 대한 각 노드별 기여를 효율적으로 업데이트 하는 방법이 연구된다. 제안된 방법은 실제 데이터들을 가지고 실험적으로 이미 존재하는 다른 방법들과 비교 평가된다. 실험 결과는 제안된 방법이 높은 정확도를 가지면서 대부분의 경우에 비교 방법들에 비해 매우 효율적임을 보인다.
다음으로 어떤 노드나 엣지들이 고장났을 때 한 노드에서 다른 노드로 가는 최단 거리를 묻는 거리 민감성 질의(distance sensitivity query)를 고려한다. 이 질의 처리를 위한 효율적인 방법은 도로 네트워크나 컴퓨터 네트워크와 같은 동적 네트워크에서 최단 거리를 계산할 때 사용된다. 또한, 이것은 소셜 네트워크 상에서 친구 추천이나 컴퓨터 네트워크에서 우회 경로를 찾는 것과 같은 네트워크 분석 속에서 다양한 상황과 목적을 위해 이용될 수 있다. 본 학위 논문에서는 거리 민감성 질의를 위한 기존 랜덤 알고리즘을 향상 시키는 것을 목표로 한다. 이를 위해 불필요한 계산을 찾아 없애고, 랜덤하게 생성된 서브그래프들을 효과적 그리고 효율적으로 사용하는 방법을 고안한다. 그 결과, 두 개의 향상된 방법을 제안한다. 첫 번째로 제안된 방법은 기존 방법과 비교하여 질의 시간 면에서 향상을 보이고, 두 번째 방법은 사전 처리 시간과 사용하는 공간 면에서 분명한 향상을 보인다. 고장 개수에 대한 특정 조건 하에서 두 번째 방법은 기존 방법과 비교하여 질의 시간 면에서 더 효율적이다. 이러한 향상과 함께 제안하는 방법들 모두 기존 방법에서 증명된 질의의 정답을 찾는 성공 확률에 대한 보장과 적어도 동일한 성공 확률을 보장한다.
