Influencia maximization bajo distribución justa del presupuesto en redes sociales en línea
Autores: Nguyen, Bich-Ngan T.; Pham, Phuong N. H.; Le, Van-Vang; Snáel, Václav
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Influencia maximization bajo distribución justa del presupuesto en redes sociales en línea
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Maximización de influencia
Distribución justa de presupuesto
Conjunto de semillas
Redes sociales
Marketing viral
Algoritmos
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 31
Citaciones: Sin citaciones
En el análisis de influencia social, marketing viral y otros campos, el problema de maximización de influencia es fundamental con aplicaciones críticas y ha atraído a muchos investigadores en las últimas décadas. Este problema busca encontrar un conjunto de semillas de tamaño -size con el mayor tamaño de propagación de influencia esperado. Nuestro documento estudia el problema de la distribución justa del presupuesto en la maximización de la influencia, con el objetivo de encontrar un conjunto de semillas de tamaño distribuido de manera justa en las comunidades objetivo. Cada comunidad tiene ciertos presupuestos limitados inferiores y superiores, y se selecciona un número de elementos de cada comunidad en un conjunto de semillas que cumple con estos límites. Sin embargo, resolver este problema se enfrenta a dos desafíos principales: los conjuntos de semillas fuertemente influyentes pueden no cumplir con la restricción de equidad, y es un problema NP-duro. Para abordar estas deficiencias, proponemos tres algoritmos (, y ). Estos algoritmos combinan una estrategia codiciosa mejorada para seleccionar semillas para garantizar una cobertura máxima con las restricciones de equidad mediante la generación de muestreos a través de un marco de muestreo de influencia inversa. Nuestros algoritmos proporcionan una -aproximación de la solución óptima, y requieren , , y complejidad, respectivamente. Realizamos experimentos en redes sociales reales. El resultado muestra que nuestros algoritmos propuestos son altamente escalables al tiempo que satisfacen garantías teóricas, y que las ratios de cobertura con respecto a las comunidades objetivo son mayores que las de las alternativas de vanguardia; hay incluso casos en los que nuestros algoritmos alcanzan cobertura con respecto a las comunidades objetivo. Además, nuestros algoritmos son factibles y efectivos incluso en casos que involucran grandes volúmenes de datos; en particular, los resultados de los algoritmos garantizan las restricciones de equidad.
Descripción
En el análisis de influencia social, marketing viral y otros campos, el problema de maximización de influencia es fundamental con aplicaciones críticas y ha atraído a muchos investigadores en las últimas décadas. Este problema busca encontrar un conjunto de semillas de tamaño -size con el mayor tamaño de propagación de influencia esperado. Nuestro documento estudia el problema de la distribución justa del presupuesto en la maximización de la influencia, con el objetivo de encontrar un conjunto de semillas de tamaño distribuido de manera justa en las comunidades objetivo. Cada comunidad tiene ciertos presupuestos limitados inferiores y superiores, y se selecciona un número de elementos de cada comunidad en un conjunto de semillas que cumple con estos límites. Sin embargo, resolver este problema se enfrenta a dos desafíos principales: los conjuntos de semillas fuertemente influyentes pueden no cumplir con la restricción de equidad, y es un problema NP-duro. Para abordar estas deficiencias, proponemos tres algoritmos (, y ). Estos algoritmos combinan una estrategia codiciosa mejorada para seleccionar semillas para garantizar una cobertura máxima con las restricciones de equidad mediante la generación de muestreos a través de un marco de muestreo de influencia inversa. Nuestros algoritmos proporcionan una -aproximación de la solución óptima, y requieren , , y complejidad, respectivamente. Realizamos experimentos en redes sociales reales. El resultado muestra que nuestros algoritmos propuestos son altamente escalables al tiempo que satisfacen garantías teóricas, y que las ratios de cobertura con respecto a las comunidades objetivo son mayores que las de las alternativas de vanguardia; hay incluso casos en los que nuestros algoritmos alcanzan cobertura con respecto a las comunidades objetivo. Además, nuestros algoritmos son factibles y efectivos incluso en casos que involucran grandes volúmenes de datos; en particular, los resultados de los algoritmos garantizan las restricciones de equidad.