Finding influential users in a social network is essential for viral marketing and social media marketing. Influence maximization problem is defined as finding a node set S of given
size K in a social network to maximize their influence spread - the expected total number of activated nodes under a certain diffusion process initiated from the set S. In this work, we propose a novel scalable and memory-efficient Influence Rank Influence Estimation (IRIE) algorithm for the influence maximization problem under the popular independent cascade (IC) model and its extension Independent Cascade model with Negative Opinions (IC-N) model. The IRIE algorithm incorporates fast influence ranking algorithm (IR) with a fast influence estimation (IE) method to achieve scalability while maintaining good Influence coverage. Through extensive experiments, we demonstrate that IRIE matches the
influence coverage of other algorithms while scales much better than all other algorithms: it runs up to two orders of magnitude faster than the state-of-the-art algorithms such as PMIA for large networks with tens of millions of nodes and edges, while using only a fraction of memory comparing with PMIA. To show the wide applicability of our IRIE framework, we also suggest a variant of IRIE to the IC-N model that incorporates negative opinion propagations, which is called as IRIE-N. Our simulation results show that IRIE-N has better influence coverage with less running time that the known state-of-the-art MIA-N heuristic.
소셜 네트워크 내 영향력 있는 사용자를 찾아내는 것은 입소문 마케팅이나 소셜 미디어 마케팅에서 매우 중요하다. 영향력 최대화 문제는 소셜 네트워크 내에서 영향력 확산 - 특정 정보 확산 모델 하에서 어떤 노드 집합 S 로 부터 확산 과정이 시발되었을 때 영향을 받는 총 노드 개수의 기대값 - 을 최대화 하기 위해 주어진 크기 K 의 노드 집합 S 를 찾는 것으로 정의된다. 본 연구는 많은 연구에 적용되는 Independent Cascade (IC) 모델과 일반화된 Independent Cascade model with Negative Opinions (IC-N) 모델 하에서 영향력 최대화 문제를 해결하는 매우 빠르고 메모리 효율적이며 정확한 Influence Rank Influence Estimation (IRIE) 알고리즘을 제안한다. IRIE 알고리즘은 우수한 정확성과 scalability 를 얻기 위해 influence ranking (IR) 과 influence estimation (IE) 의 두 부분으로 구성된다. 광범위한 실험을 통해서 우리는 IRIE 알고리즘이 다른 알고리즘에 비해 훨씬 빠르고 scalable 하면서 유사한 정확성을 얻는 것을 보인다: IRIE 알고리즘은 알려진 가장 우수한 휴리스틱 알고리즘인 PMIA 알고리즘과 비교할 때 수천만 개의 노드와 에지를 가지는 대규모 네트워크에서 훨씬 적은 메모리를 사용하면서 100배 가량의 실행 속도 개선을 보인다. 나아가 우리는 부정적 의견 확산을 모델링하도록 일반화된 IC-N 모델 하에서의 영향력 최대화 문제를 위한 IRIE-N 알고리즘을 제안한다. 실험 결과에서 IRIE-N 알고리즘이 알려진 MIA-N 알고리즘보다 빠르고 정확함을 보인다.