| 한글제목(Korean Title) |
독립 연쇄 모델과 그 확장 모델들을 위한 통합 영향력 최대화 처리 알고리듬 |
| 영문제목(English Title) |
A Unified Influence Maximization Processing Algorithm for Independent Cascade Model and its Extensions |
| 저자(Author) |
김진하
유환조
Jinha Kim
Hwanjo Yu
|
| 원문수록처(Citation) |
VOL 29 NO. 02 PP. 0109 ~ 0120 (2013. 08) |
한글내용
(Korean Abstract) |
소셜 네트워크의 ?#51077;소문?효과는 근래의 마케팅에 있어 중요한 역할을 차지하고 있다. 영향력 최대화 문제는 입소문 효과를 최대화 하는 것을 목표로 하며 그 목표를 조합 최적화 문제로 정형화 한다. 영향력 최대화 문제 해결 과정의 중요한 요소로서, 영향력 측정은 다항시간 내에 해결할 수 없는 것으로 여겨지는 #P-hard 문제로 분류된다. 이에 따라, 효율적인 영향력 측정/근사 알고리듬을 고안하는 것은 매우 중요한 일이다. 본 논문에서는, 효과적인 영향력 근사 알고리듬인 Independent Path Algorithm(IPA)를 제안한다. IPA의 주된 아이디어는 영 향력 전달 경로를 영향력 측정의 최소 기준으로 삼는 것이다. 이 아이디어를 통해, IPA는 기존의 가장 효율적인 영향력 근사 알고리듬인 Prefix excluding Maximum Influence Arborescence(PMIA) 보다 10배 이상 빠르 고 더욱 정확히 영향력을 근사한다. 이와 더불어, IPA는 독립 연쇄 모델(Independent Cascade(IC) model) 뿐 아니라 그 확장 모델들에도 쉽게 적용이 가능하다. |
영문내용
(English Abstract) |
The 뱖ord-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. |
| 키워드(Keyword) |
영향력 최대화
소셜 네트워크
Influence maximization
social networks
|
| 파일첨부 |
PDF 다운로드
|
