소셜 네트워크에서 잘못된 정보 확산 제한

본 연구에서는 소셜 네트워크에서 경쟁하는 캠페인 개념을 연구하고 "나쁜" 캠페인이 네트워크의 특정 노드에서 전파되기 시작할 때의 영향 제한 문제를 다룹니다. 정보 오염의 효과를 상쇄하기 위해 제한 캠페인 개념을 사용합니다. 이 문제는 경쟁하는(또는 "좋은") 캠페인을 채택하도록 설득해야 하는 개인 집합을 식별하여 두 전파 과정 종료 시 "나쁜" 캠페인을 채택하는 사람 수를 최소화하는 것으로 요약할 수 있습니다. 이 최적화 문제가 NP-어려움임을 보이고, 이를 서브모듈러임을 증명하여 다양한 문제 정의에 대한 탐욕적 해법의 근사 보장을 제공합니다. 탐욕적 방법과 여러 휴리스틱 방법의 성능을 실험적으로 비교했습니다. 대개 차수 중심성과 같은 비용이 적게 드는 휴리스틱이 탐욕적 접근과 비교해 좋은 결과를 나타냄을 실험이 보여줍니다. 또한 네트워크 노드의 현재 상태가 확률적으로만 알려져 있는 결측 상황에서 영향 제한 문제를 연구하며, 이 설정에서 예측 문제가 초서브모듈러 문제임을 보입니다. 무작위 스패닝 트리 생성을 기반으로 한 예측 알고리즘을 제안하고 성능을 평가했습니다. 실험 결과 예측 알고리즘을 사용하면 약 90%의 결측 데이터까지 성능 저하 없이 견딜 수 있고, 많은 결측 데이터가 있어도 완전한 데이터 사용 시 성능의 75% 수준으로만 감소한다는 것을 확인했습니다.