Open Access System for Information Sharing

Login Library

 

Thesis
Cited 0 time in webofscience Cited 0 time in scopus
Metadata Downloads

Realistic Influence Diffusion Model and Scalable Influence Evaluation Method for Influence Maximization Problem

Title
Realistic Influence Diffusion Model and Scalable Influence Evaluation Method for Influence Maximization Problem
Authors
김진하
Date Issued
2014
Publisher
포항공과대학교
Abstract
As social network services connect people across the world, influence maximization, i.e., finding the most influential nodes (or individuals) in the network, is being actively researched with applications to viral marketing. In this paper, two crucial challenges of the influence maximization problem are addressed – (1) realistic influence diffusion model and (2) efficient influence evaluation algorithm. Underlying influence diffusion models affect influence maximizing nodes because they focus on difference aspect of influence diffusion. Nevertheless, existing diffusion models overlook two important aspects of real-world marketing - continuous trials and time restriction. This paper proposes a new realistic influence diffusion model called Continuously activated and Time-restricted IC (CT-IC) model which generalizes the IC model by embedding the above two aspects. Another crucial challenge in scalable influence maximization processing is evaluating influence, which is #P-hard and thus hard to solve in polynomial time. In this paper, a scalable influence approximation algorithms, Independent Path Algorithms (IPAs) are proposed for Independent Cascade (IC) diffusion model and its two variants – IPA-N for IC-N model and CT-IPA for CT-IC model. IPA efficiently approximates influence by considering an independent influence path as an influence evaluation unit. IPA is also easily parallelized by simply adding a few lines of OpenMP meta-programming expressions. Also, overhead of maintaining influence paths in memory is relieved by safely throwing away insignificant influence paths. IPA is seamlessly extended to IPA-N and CT-IPA by simply modifying the influence propagation probability of an influence path. Extensive experiments conducted on large-scale real social networks show that IPA is an order of magnitude faster and uses less memory than the state of the art algorithms. Our experimental results also show that parallel versions of IPA speeds up further as the number of CPU cores increases, and more speed-up is achieved for larger datasets. IPA-N and CT-IPA also show the same characteristics to IPA. Moreover, CT-IC model provides different seed nodes of higher influence spread than IC model.
온라인 소셜 네트워크 서비스들이 전세계의 사람들을 이어줌에 따라, 소셜 네트 워크 상에서 가장 영향력이 높은 사용자를 찾아내는 영향력 최대화 문제는 바이럴 최근 활발히 연구 되고 있다. 본 논문에서는 영향력 최대화 문제가 해결해야할 주요한 도전 과제들중 현실적인 영향력 전달 문제와 효율적인 영향력 측정 방법에 대한 연구를 다루고자 한다. 각 영향력 전달모델은 현실 세계의 영향력 전달 양상 중 특정한 특징만을 반영하게 되므로 영향력 전달모델은 영향력 최대화 문제의 결과에 큰 영향을 치니다. 그럼에도 불구하고, 현재까지 존재하는 영향력 전달 문제들은 현실 세계의 마케팅이 고려하고 있는 (1) 지속적인 영향력 전달 시도와 (2) 마케팅의 종료시점을 간과하고 있다. 본 논문은 위의 두가지 영향력 전달 양상을 반영한 Continuously activated and Time-restricted IC (CT-IC) 영향력 전달모델을 제안한다. 현실적 영향력 전달 모델과 더불어 영향력 최대화 문제가 직면한 또 하나의 과제는 효율적인 영향력 측정 방법이다. 정확한 영향력 측정은 #P-Hard 문제 집합에 속하며 다항시간내에 수행 할수 없다. 따라서, 본 논문은 Independent Cascade (IC) 영향력 전달 모델과 그 확장 모델인 IC model with negative opinion (IC-N) 모델과 CT-IC 모델에서의 효율적인 영향력 근사 방법인 Independent Path Algorithm (IPA)를 제안한다. IPA는 영향력 경로를 영향력 전달의 기본 단위로 삼아 영향력 근사를 효율적으로 수행한다. 계산과정에서 의존관계가 없는 IPA는 10라인 이내의 OpenMP 구문을 이용하여 쉽게 병렬화가 가능하다. 또한 메인 메모리에 과도한 영향력 경로를 저장하는 IPA의 과제는 중요하지 않은 영향력 경로를 버림으로써 해결할 수 있다. IC 모델을 위한 IPA 는 영향력 패스가 가지는 영향력 값을 재정의 함으로써 원활하게 IC-N 모델을 위한 IPA-N, CT-IC 모델을 위한 CT-IPA로 확장 가능하다. 제안한 영향력 전달 모델과 영향력 근사 방법의 효과성과 효율성을 보이기 위해 현실 세계 그래프를 사용하여 실험을 하였다. 실험으로부터 IPA는 최신 영향력 근사 방법보다 10배 빠른 수행속도를 보였으며 더욱 적은 메모리를 사용하였다. 또한 병렬화된 IPA 는 프로세서의 수가 늘어남에 따라 더욱 높은 속도 향상을 보여주었으며, 동일 프로세서 수에서 대용량의 데이터에서 더욱 높은 속도 향상을 보여주었다. IPA-N 과 CT-IPA에 대한 실험또한 IPA와 동일한 결과를 보였다. 더불어, CT-IC 모델은 영향력 최대와 문제에서 IC 모델과 다른 최대 영향 사용자들을 보여주었으며 동일 조건에서 더욱 높은 영향력 수치를 보여주었다.
URI
http://postech.dcollection.net/jsp/common/DcLoOrgPer.jsp?sItemId=000001677713
http://oasis.postech.ac.kr/handle/2014.oak/2211
Article Type
Thesis
Files in This Item:
There are no files associated with this item.

qr_code

  • mendeley

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Views & Downloads

Browse