Algoritmos de Procesamiento en Línea para la Maximización de la Influencia

La maximización de la influencia es un problema clásico y ampliamente estudiado con importantes aplicaciones en el marketing viral. Sin embargo, los algoritmos existentes para la maximización de la influencia se centran principalmente en el procesamiento offline, en el sentido de que no proporcionan ninguna salida al usuario hasta que se derive la respuesta final, y que no se permite al usuario terminar el algoritmo anticipadamente para intercambiar la calidad de la solución por eficiencia. Esta falta de interactividad y flexibilidad conduce a una mala experiencia del usuario, especialmente cuando el algoritmo incurre en un tiempo de ejecución largo. Para abordar el problema anterior, este documento estudia algoritmos para el procesamiento en línea de la maximización de la influencia (OPIM), donde el usuario puede pausar el algoritmo en cualquier momento y pedir una solución (al problema de maximización de la influencia) y su garantía de aproximación, y puede reanudar el algoritmo para permitir que mejore la calidad de la solución dándole más tiempo para ejecutar. (Este paradigma interactivo es similar en espíritu al procesamiento de consultas en línea en sistemas de bases de datos). Mostramos que el único algoritmo existente para OPIM es en gran medida ineficaz en la práctica, y que adoptar métodos existentes de maximización de la influencia para OPIM da como resultado resultados insatisfactorios. Motivados por esto, proponemos un nuevo algoritmo para OPIM con una efectividad empírica superior y fuertes garantías teóricas, y mostramos que también se puede extender para manejar la maximización de la influencia convencional. Experimentos extensivos con datos reales demuestran que nuestras soluciones superan el estado del arte tanto para OPIM como para la maximización de la influencia convencional.