Given a graph, with a source node that needs to maximize its influence over a specific target node, a set of nodes need to be determined that will enable information flow from the source to the target node. By solving this problem, we can enable a user to receive more attention from a specific target user by forming useful connections between the two. Current friend recommendation algorithms focus on suggesting nodes that are similar to the user, but these algorithms are not designed to tackle the maximum influence issue. Based on the observation that information propagation on online social networks is enabled by the sharing activity, we define the influence of a source node over target as a variation of Katz centrality. In addition, we model the reluctance, to account for awkwardness between two users. With these measures, we propose k-node suggestion problem. However, the optimization problem of recommending a node set that maximizes influence is NP-hard. Therefore, in this paper, we suggest an algorithm to find a node set sequentially. Next, we model reluctance between two nodes, which is inversely related to node similarity. Reluctance is based on the intuition that people not related with the user, might
not accept the user’s online connection request. By considering reluctance, we could identify the nodes that have a higher probability of refusing the connection request. We address this problem by proposing an Incremental Katz Approximation (IKA) algorithm that is designed to search the top-k nodes with high accuracy and has the
ability to run on a large graph. The IKA algorithm can handle large graphs by approximating influence measure using Monte-Carlo simulation. This algorithm updates information diffusion incrementally to find the node that can maximize influence. We discuss the complexity of our algorithm and the evaluation results demonstrate the
performance and scalability of our algorithm. We also report interesting behavior of the sequential recommendation result. In summary, our algorithm is effectively recommend friends such that they can improve influence of the source user on the target user.
본 논문에서는 소셜 네트워크 상에서 영향력을 확장하고 싶은 특정 사용자가 존재할 때, 그 영향력을 최대화할 수 있는 친구를 한 명씩 추천하는 알고리즘(IKA)을 제안한다. 소셜 네트워크의 뉴스피드 등에서 우리는 직접 연결된 사용자들의 소식 뿐만이 아니라 그들이 관심 있어 공유한 다양한 글들을 접하게 된다. 이런 네트워크 상에서 특정한 사용자에게 자신의 영향력을 극대화하고 싶을 때, 자신의 정보의 전파에 도움이 되는 새로운 친구 추천이 가능하다면 다양한 이익을 가져올 수 있을 것이며 이러한 생각으로부터 연구를 시작하게 되었다. 기존의 친구 추천 알고리즘은 네트워크 구조 및 프로필의 유사도가 높은 사용자를 추천해 주지만, 특정 사용자에게 나의 영향력을 증가시키는 목적과는 무관하다. 우리가 제시한 문제를 해결하기 위해 소셜 네트워크 상에서 문제 정의를 하였다. 먼저 소셜 네트워크 상에 업로드한 게시물은 직접 연결된 친구들의 게시판에 올라가게 되고, 친구가 해당 게시글을 공유하거나 답하는 등의 행동을 통해 그의 이웃으로 전파되는 모델을 설정하고, 사용자 A가 B에 미치는 영향력은 B가 받는 모든 게시글 중 A로부터 도착한 게시글의 비율로 정의하였다. 한 사용자가 받는 게시글의 개수는 우리가 설정한 모델 내에서 Katz centrality의 정의와 부합함을 확인하였다. 영향력을 최대화하는 연결 조건에 더불어 어떤 사용자에게 친구 요청을 하였을 때 수락하지 않을 확률을 두 노드 사이의 유사도를 이용하여 모델링하였고, 추천 과정에 함께 고려하였다. 친구를 추천을 위해서는 네트워크 상에서 직접 연결되지 않은 모든 사용자들에 대해, 각각 연결되었을 때 증가하는 영향력을 계산하는 과정을 거쳐야 하는데 이 경우 불필요한 연산이 매우 많아진다. 따라서 본 논문에서는 몬테 카를로 시뮬레이션을 통하여 Katz centrality를 근사하였고 새로운 연결이 추가 될 때, 특정 사용자에게 내가 미치는 영향력를 처음부터 계산하는 대신 추가된 연결로 인해 게시글이 네트웍상에 퍼지는 부분만 따로 추가하여 알고리즘의 복잡도를 크게 개선하였다. 다양한 크기와 구조를 가진 합성 네트워크와 실제 소셜 네트워크 데이터를 통해 기존 알고리즘에 비해 제안한 알고리즘(IKA)의 속도가 월등하고, 커다란 그래프를 처리할 수 있음을 보였다. 또한 정확한 값의 영향력을 계산하였을 때와 근사 알고리즘의 결과 역시 유사함을 보였다.
