독립 연쇄 모델과 그 확장 모델들을 위한 통합 영향력 최대화 프레임워크 = A Unified Influence Maximization Processing Framework for Independent Cascade Model and Its Extensions

국문 초록 (Abstract)

소셜 네트워크의 “입소문” 효과는 근래의 마케팅에 있어 중요한 역할을 차지하고 있다. 영향력 최대화 문제는입소문 효과를 최대화 하는 것을 목표로 하며 그 목표를 조합 최적화 문제로 정형화 한다. 영향력 최대화 문제해결 과정의 중요한 요소로서, 영향력 측정은 다항시간 내에 해결할 수 없는 것으로 여겨지는 #P-hard 문제로분류된다. 이에 따라, 효율적인 영향력 측정/근사 알고리듬을 고안하는 것은 매우 중요한 일이다. 본 논문에서는,효과적인 영향력 근사 알고리듬인 Independent Path Algorithm(IPA)를 제안한다. IPA의 주된 아이디어는 영향력 전달 경로를 영향력 측정의 최소 기준으로 삼는 것이다. 이 아이디어를 통해, IPA는 기존의 가장 효율적인영향력 근사 알고리듬인 Prefix excluding Maximum Influence Arborescence(PMIA) 보다 10배 이상 빠르고 더욱 정확히 영향력을 근사한다. 이와 더불어, IPA는 독립 연쇄 모델(Independent Cascade(IC) model) 뿐아니라 그 확장 모델들에도 쉽게 적용이 가능하다.

다국어 초록 (Multilingual Abstract)

The “word-of-mouth” effect on social networks – opinion propagation– nowadays plays an important role in marketing. The influence maximization problem aims at maximizing the word-of-mouth effect and formulates such goal as a combinatorial optimization problem. As an important process of the influence maximization problem, evaluating influence is #P-hard which cannot be affordable in a polynomial time. Accordingly, devising a fast influence evaluation/approximation algorithm is crucial. We propose a scalable influence approximation algorithm called IPA. The main idea of IPA is considering an influence path as an independent influence evaluation unit. Using that idea, IPA approximates influence an order of magnitude faster and more accurately than PMIA, the current state of the art approximation algorithm. In addition,IPA is applicable to independent cascading(IC) model and its extensions.

참고문헌 (Reference)

1 W. Chen, "Scalable influence maximization in social networks under the linear threshold model" IEEE Computer Society 88-97, 2010

2 W. Chen, "Scalable influence maximization for prevalent viral marketing in large-scale social networks" ACM 1029-1038, 2010

3 L. Dagum, "Openmp: An industry-standard api for shared-memory programming" 5 : 46-55, 1998

4 D. Kempe, "Maximizing the spread of influence through a social network" ACM 137-146, 2003

5 M. Kimura, "Knowledge Discovery in Databases: PKDD 2006, volume 4213 of Lecture Notes in Computer Science,, In Knowledge Discovery in Databases: PKDD 2006, volume 4213 of Lecture Notes in Computer Science" Springer 259-271, 2006

6 D. Kempe, "Influential nodes in a diffusion model for social networks, In ICALP, volume 3580 of Lecture Notes in Computer Science" Springer 1127-1138, 2005

7 W. Chen, "Influence maximization in social networks when negative opinions may emerge and propagate" 379-390, 2011

8 W. Lee, "Influence maximization for time-considering independent cascade model" IEEE Computer Society 960-965, 2012

9 W. Chen, "Efficient influence maximization in social networks" ACM 199-208, 2009

10 J. Leskovec, "Cost-effective outbreak detection in networks" ACM 420-429, 2007

11 Y. Wang, "Community-based greedy algorithm for mining top-k influential nodes in mobile social networks" ACM 1039-1048, 2010