Identificacion de Nodos Influyentes mediante Colonia de Hormigas

Vista previa del material en texto

Identificación de Nodos Influyentes
mediante Colonia de Hormigas
Autor: Elvis Suarez Beltran
Director: Ariel Monteserin
Facultad de Ciencias Exactas - UNICEN
Tesis de Grado
Ingeniería de Sistemas
Tandil, Mayo 2022
Dedicatoria
A mis amigos, a mi mamá, mi papá y mi hermana, por bancarme incondicionalmente en
cada proceso de la carrera, en cada momento compartido a lo largo del trayecto que me
permitió llegar hasta hoy..
Agradecimientos
Para Ariel Monteserin, que me tuvo paciencia en todo el proceso y me guió hasta el final, y
a cada persona que dedicó un poco de su tiempo a explicar conceptos que desconocía.
Agradezco a la universidad de UNICEN, por la posibilidad de tener semejante carrera y las
posibilidades que brinda para que podamos ser parte de esta.
Resumen
La elección de los usuarios influyentes es un factor clave para garantizar el éxito y
conseguir los objetivos empresariales, dentro de la planificación de la estrategia comercial.
Es necesario saber identificar aquellos influencers que por sus valores, estilo, se asemeja al
negocio que se quiere que representen. En la actualidad, los influencers implican la
traslación, la nueva versión de los líderes de opinión aplicado al medio online,
aprovechando el enorme potencial demostrado por las redes sociales. Los influencers son
personas que poseen cierta credibilidad sobre un tema concreto y que su presencia e
influencia en las redes sociales hacen que se conviertan en un prescriptor idóneo.
Nos encontramos ante el marketing de influencia, en el que se fusionan las redes
sociales como espacios publicitarios con el recurso a los usuarios, como los líderes de
opinión o los personajes famosos como prescriptores e influencers, a los que las marcas
dirigen sus esfuerzos comunicativos. La idea detrás del marketing viral es que, al dirigirnos
a un conjunto de usuarios influyentes de la red, podemos activar una reacción en cadena de
la influencia impulsada por el boca a boca, de tal manera que con un costo de marketing
muy pequeño podemos alcanzar una porción muy grande de la red mediante la selección de
usuarios claves.
Goyal en [2] desarrolla un nuevo modelo denominado Credit Distribution, construido
sobre trazas de propagación reales que nos permite predecir directamente la dispersión de
influencia de un conjuntos de nodos, sin necesidad de aprender probabilidades de borde o
realizar simulaciones de Montecarlo. Proponen un enfoque diferente, tomando una
perspectiva “u-céntrica” asignando “créditos” a los posibles influenciadores de un nodo u
siempre que u realiza una acción. Mostraron también que la maximización de la influencia
bajo este modelo es NP-Hard, y que, la función de propagación de la influencia es
monótona y submodular. En consecuencia la implementación del algoritmo Greedy
proporciona una aproximación de (1-1/e) a la solución óptima, aunque por sí mismo no
garantiza eficiencia.
Para permitir una mejora adicional en la calidad de las soluciones, la investigación
en este campo en las últimas décadas ha centrado su atención en el diseño de técnicas de
propósito general para guiar la construcción de soluciones o la búsqueda local en las
distintas heurísticas. Estas técnicas se llaman comúnmente metaheurísticas y consisten en
conceptos generales empleados para definir métodos heurísticos. Las metaheurísticas son
métodos que emplean heurísticas para producir soluciones de mejor calidad. Estas están
inspiradas en diversos campos como la genética, la biología, la física, etc.
La metaheurística basada en colonia de hormigas (ACO) se desarrolló a partir de
observar como ciertas especies de hormigas con capacidades visuales muy limitadas logran
alcanzar su alimento realizando muy buenos recorridos. La idea general del algoritmo se
basa en abstraer ese comportamiento y representarlo artificialmente. Por un lado, el
sendero de las hormigas con un grafo, y por otro lado, las hormigas son agentes
computacionales independientes unos de otros que construyen soluciones tomando
decisiones en cada intersección. Cada hormiga representa una solución completa del
problema.
Índice general
Introducción.………………………………………………………………………………………... 9
Motivación………………...………………...………………...………………...………………….10
Objetivos………………...………………...………………...………………...…………………... 11
Marco Teórico………………...………………...………………...………………...…………….. 12
Redes sociales………………...………………...………………...………………...…………… 12
Influence Maximization and propagation………………...………………...………………... 13
Campo aleatorio de Markov………………...………………...………………...……………… 14
The Independent Cascade y Linear Threshold………………...………………...…………. 18
Credit Distribution………………...………………...………………...………………...………. 21
Ant Colony………………...………………...………………...………………...………………... 25
Proceso………………...………………...………………...………………...………………... 25
Metaheurística de Optimización Basada en Colonias de Hormigas……………………... 26
Sistema de Hormigas………………...………………...………………...…………………… 29
Sistema de Colonia de Hormigas………………...………………...………………...……... 31
Sistema de Hormigas Max-Min………………...………………...………………………….. 32
Sistema de Hormigas con Ordenación………………...………………...…………………. 33
Herramientas similares………………...………………...………………...…………………… 35
Klout………………...………………...………………...………………...……………………. 35
Kred………………...………………...………………...………………...……………………. 36
Twitanalyzer………………...………………...………………...………………...…………… 37
Propuesta………………...………………...………………...………………...…………………. 38
Implementación………………...………………...………………...………………...………….. 42
Arquitectura………………...………………...………………...………………...……………… 42
Python………………...………………...………………...………………...…………………. 42
Bibliotecas utilizadas………………...………………...………………...…………………… 42
Herramientas………………...………………...………………...………………...…………. 44
Diseño………………...………………...………………...………………...…………………. 45
Base de datos………………...………………...………………...………………...………… 47
Estrategias utilizadas………………...………………...………………...…………………… 48
Evaluación Experimental………………...………………...………………...…………………. 49
Objetivo………………...………………...………………...…………………………………... 49
Datos………………...………………...………………...………………...…………………… 49
Procedimientos………………...………………...………………...…………………………. 50
Resultados………………...………………...………………...………………………………. 51
Heurística 1………………...………………...………………...…………………………. 52
Heurística 2………………...………………...………………...…………………………. 53
Heurística 3………………...………………...………………...…………………………. 54
Heurística 4………………...………………...………………...…………………………. 55
Heurística 5………………...………………...………………...…………………………. 57
Heurística 6………………...………………...………………...…………………………. 58
Heurística 7………………...………………...………………...………………………….. 59
Análisis de resultados………………...………………...………………...………………….. 60
Comparación de seed sets entre ACO y Greedy………………...………………………… 63
Grafo de 200 nodos………………...………………...………………...…………………….. 67
Cantidad de hormigas………………...………………...………………...…………………... 69
Conclusiones………………...………………...………………...………………...……………... 70
Resumen………………...………………...………………...………………...…………………... 70
Ventajas………………...………………...………………...………………...……………………. 70
Limitaciones………………...………………...………………...………………...………………. 71
Trabajos futuros………………...………………...………………...……………………………. 71
Experimentación con varios dataset………………...………………...…………………….. 71
Implementación del proyecto en otro lenguaje………………...…………………………… 72
Nodos sin recorrer………………...………………...………………...………………………. 72
Profundizar en las alternativas dentro de ACO………………...…………………………... 72
Índice de figuras
2.1 Demostración de rastros de feromonas en una bifurcación ……………………. 26
2.2 Algoritmo ACO ………………………………………………………………………. 28
4.1 Diagrama de clases del proyecto ………………………………………………….. 46
5.1 Resultados de cada heurística destacando el mejor resultado para cada grafo
en un seed set de 10 nodos …………………………………………………………….. 61
5.2 Resultados de cada heurística destacando el mejor resultado para cada grafo
en un seed set de 30 nodos …………………………………………………………….. 62
5.3 Resultados de cada heurística destacando el mejor resultado para cada grafo
en un seed set de 50 nodos…………………………………………………………….. 63
Índice de tablas
5.1 Ejemplo de los datos que se encuentran en Ratings.timed.cs…………………….. 49
5.2 Ejemplo de los datos que se encuentran en el archivo links.csv ………………….. 50
5.3 Resultados de la heurística 1 para un seed set de 10 nodos ……………………… 52
5.4 Resultados de la heurística 1 para un seed set de 30 nodos ……………………… 52
5.5: Resultados de la heurística 1 para un seed set de 50 nodos ……………………... 52
5.6 Resultados de la heurística 2 para un seed set de 10 nodos ……………………… 53
5.7 Resultados de la heurística 2 para un seed set de 30 nodos ……………………… 53
5.8 Resultados de la heurística 2 para un seed set de 50 nodos ……………………… 54
5.9 Resultados de la heurística 3 para un seed set de 10 nodos ……………………… 54
5.10 Resultados de la heurística 3 para un seed set de 30 nodos …………………….. 55
5.11: Resultados de la heurística 3 para un seed set de 50 nodos ……………………. 55
5.12 Resultados de la heurística 4 para un seed set de 10 nodos …………………….. 55
5.13 Resultados de la heurística 4 para un seed set de 30 nodos …………………….. 56
5.14 Resultados de la heurística 4 para un seed set de 50 nodos …………………….. 56
5.15 Resultados de la heurística 5 para un seed set de 10 nodos …………………….. 57
5.16 Resultados de la heurística 5 para un seed set de 30 nodos …………………….. 57
5.17 Resultados de la heurística 5 para un seed set de 50 nodos …………………….. 57
5.18 Resultados de la heurística 6 para un seed set de 10 nodos …………………….. 58
5.19 Resultados de la heurística 6 para un seed set de 30 nodos …………………….. 58
5.20 Resultados de la heurística 6 para un seed set de 50 nodos …………………….. 58
5.21 Resultados de la heurística 7 para un seed set de 10 nodos …………………….. 59
5.22 Resultados de la heurística 7 para un seed set de 30 nodos …………………….. 59
5.23 Resultados de la heurística 7 para un seed set de 50 nodos …………………….. 60
5.24 Comparativa de Seed set entre Greedy y Ant Colony en un seed set de 10
nodos en un grafo de 30 usuarios ………………………………………………………….
64
5.25 Comparativa de Seed set entre Greedy y Ant Colony en un seed set de 30 65
nodos en un grafo de 50 usuarios ………………………………………………………….
5.26 Comparativa de Seed set entre Greedy y Ant Colony en un seed set de 50
nodos en un grafo de 200 usuarios ………………………………………………………..
66
Capítulo I
En el presente capítulo se hará una presentación formal del proyecto final, una
introducción, nuestra motivación y los objetivos que nos planteamos.
Introducción
El consumidor se encuentra expuesto en su actividad diaria a multitud de mensajes
publicitarios a través de diversos canales y plataformas. Entre todos esos canales la opinión
de un amigo, conocido, familiar, colega, ocupa un puesto primordial a la hora de tomar
decisiones en la elección de compra.
Una referencia positiva hacia un producto o un servicio por parte de una persona
aparentemente desinteresada puede suponer esa motivación última que a un potencial
cliente le falta para tomar la decisión de llevar a cabo una compra. Si a eso le añadimos el
alcance online que puede llegar a tener la recomendación de una persona de gran
influencia en este medio, nos encontramos ante un recurso con un éxito prácticamente
asegurado.
En la actualidad, los influencers implican la traslación, la nueva versión de líderes de
opinión aplicado al medio online, aprovechando el enorme potencial demostrado por las
redes sociales. La elección de los influencers, es un factor clave para garantizar el éxito y
conseguir los objetivos empresariales, dentro de la planificación de la estrategia comercial,
al mismo tiempo, los usuarios valoran cada vez en mayor medida las opiniones de los
influencers por lo que aquellos perfiles con grandes comunidades ganan poder de
persuasión.
La maximización de la influencia es el problema de encontrar un conjunto de
usuarios en una red social, de modo que al apuntar a este conjunto, uno maximiza la
dispersión esperada de influencia en la red. Kempe en [11] formalizó esto como el problema
de maximización de la influencia, de la siguiente forma:
● “encontrar k nodos ‘semilla’ en la red, para un número k dado, de modo que
al activarlos podamos maximizar la propagación de influencia esperada”.
Motivación
Con el éxito de las redes sociales en línea y los microblogs como Facebook, Flickr y
Twitter, el fenómeno de la influencia ejercida por los usuarios de dichas plataformas sobre
otros usuarios, y cómo se propaga en la red, ha atraído el interés de los informáticos,
tecnólogos en información y especialistas en marketing. Uno de los principales problemas
en esta área, es la identificación de usuarios influyentes, apuntando a quienes pueden
lograr ciertos resultados de marketing deseables. Aquí, la orientación podría significar dar
muestras gratuitas (o con precios reducidos) de un producto y el resultado deseado puede
ser conseguir que la mayor cantidad posible de clientes compren el producto [1].
La idea detrás del marketing viral es que, al dirigirnos a los usuarios más influyentes
de la red, podemos activar una reacción en cadena de la influencia impulsada por el boca a
boca, de tal manera que con un costo de marketing muy pequeño podemos alcanzar una
porción muy grande de la red. La selección de estos usuarios claves en un grafo, es una
tarea de aprendizaje interesante que ha recibido mucha atención en los últimos años.
Para determinar cuáles son los usuarios más influyentes de una red es necesario
analizar la propagación de la influencia en las redes sociales, para esto, es importante
definir qué es considerado influencia en las redes sociales. La respuesta básica es que
cuando los usuarios ven a sus contactos de la red realizar una acción, ellos deciden llevarla
a cabo también. Si observamos que un usuario v realiza una acción a en un tiempo t, y un
usuario u (que tiene una relación con v) realiza la misma acción en un plazo corto de
tiempo, entonces podemos pensar que la acción a se propagó de v a u. En caso de
observar que esto sucede frecuentemente para diferentes acciones, entonces podemos
concluir que el usuario v está ejerciendo influencia sobre el usuario u.
Los primeros en considerar la propagación de influencia y el problema de
identificación de usuarios influyentes por una perspectiva de minería de datos, fueron
Domingos y Richardson [10]. Kempe [11], por otro lado, centró su trabajo en dos modelos
de propagación denominados, Threshold Model (LT) e Independent Cascade Model (IC).
Bajo estos modelos de propagación, IC y LT, el problema se vuelve NP-Hard. Sin
embargo, Kempe, demostró que la función es monótona y submodular. Gracias a estas dos
propiedades, el problema de maximización de influencia puede aproximarse con un factor
de con el algoritmo Greedy. Sin embargo, en ambos casos, dicho algoritmo no(1 − 1/𝑒)
garantiza eficiencia en sí mismo, ya que requiere determinar las ganancias marginales de
un nodo candidato respecto al actual conjunto de semillas, y lo realiza con costosas
simulaciones de Montecarlo [1] [2].
En estos modelos descritos, se asignan probabilidades a los enlaces entre los nodos
siguiendo distintos criterios (como por ejemplo igual valor a los enlaces entre los nodos). Sin
embargo, nosotros vamos hacer énfasis en un modelo que permite aprender a partir de
propagaciones anteriores que fueron registradas. El modelo Credit Distribution, aprovecha
directamente los rastros de propagación disponibles para aprender cómo fluye la influencia
en la red y lo utiliza para estimar la propagación de influencia esperada. Sin embargo, se
demostró en [2] que la maximización de la influencia bajo este modelo es NP-hard. Debido a
estas desventajas presentes, y resaltando que Borodin en [3] señaló que para ciertos
modelos de difusión, particularmente aquellos que investigan la influencia competitiva en las
redes sociales, pueden no ser monótonos o submodulares, por lo tanto, el algoritmo Greedy
no puede usarse. Se propone entonces, complementar CD con Ant Colony Optimization
(ACO).
ACO inicialmente propuesto por Dorigo [9], es un metaheurístico desarrollado para
componer soluciones aproximadas. ACO está inspirado en las observaciones del
comportamiento colectivo dealimentación en colonias de hormigas reales y representa
problemas como grafos, con soluciones construidas dentro de un proceso iterativo
estocástico al agregar componentes de solución a soluciones parciales.
Objetivos
Planteado el contexto anteriormente mencionado, se propone el desafío de proveer
una herramienta que permita identificar un conjunto de usuarios dentro de una red social,
para el cual maximice la influencia sobre toda dicha red a través de distintas heurísticas
buscando minimizar dicho costo computacional para lograr obtener mejores resultados.
Se buscará comprobar si la combinación de un modelo, Credit Distribution [2] y un
algoritmo, Ant Colony Optimization, ya expuestos en el tema, permiten lograr solucionar el
problema propuesto. Como objetivo secundario se buscará mejorar los resultados que
podrían obtenerse utilizando el modelo CD con el algoritmo Greedy. El modelo Credit
Distribution, como se dijo anteriormente, aprovecha directamente los rastros de propagación
disponibles para aprender cómo fluye la influencia en la red y lo utiliza para estimar la
propagación de influencia esperada, es decir, permite aprender las probabilidades a partir
de propagaciones anteriores que fueron registradas. Por otro lado, la inspiración para ACO
es el comportamiento de búsqueda de hormigas reales [6]. Al buscar comida, las hormigas
inicialmente exploran el área que rodea su nido de manera aleatoria. Tan pronto como una
hormiga encuentra una fuente de alimento, evalúa la cantidad y la calidad del alimento y lo
lleva de vuelta al nido. Durante el viaje de regreso, la hormiga deposita un rastro químico de
feromonas en el suelo. La cantidad de feromona depositada depende de la cantidad y
calidad de los alimentos, y esto guiará a otras hormigas a la fuente de alimentos.
La comunicación indirecta entre las hormigas a través de senderos de feromonas les
permite encontrar los caminos más cortos entre su nido y las fuentes de alimentos.
Diferentes estudios han demostrado que la comunicación de las hormigas a través de
caminos con feromonas les permite encontrar las rutas más cortas entre su nido y las
fuentes de alimentos [9]. Esta característica es ampliamente utilizada para la solución de
problemas de optimización que necesitan mejorar sustancialmente los tiempos de cómputo
para la solución de una aplicación específica [7].
Para nuestro caso, las hormigas artificiales, recorren el grafo buscando los mejores
caminos, estas van a ser quienes nos guíen y generen distintas soluciones al problema, ya
que, como se mencionó anteriormente, cada hormiga genera una solución propia y distinta,
pero tal como sucede en estos seres vivos, dichas hormigas van dejando feromonas, un
valor numérico, que sirven de guía para las demás hormigas a la hora de tomar la decisión
en una bifurcación, una medida de la deseabilidad al momento de elegir dicho camino.
Capítulo II
Marco Teórico
En este capítulo se mostrará un conjunto de enfoques teóricos propuestos,
investigaciones y conceptos importantes, significativos para entender el dominio de la
herramienta y comprender su alcance.
Redes sociales
Ya no existe la sociedad sin internet. No realizar búsquedas en Google o no
mantener contacto con tus amigos y familiares durante tu día es prácticamente impensado.
El dominio de internet y su influencia en nuestras vidas es gigante, principalmente con el
marketing digital y la transformación digital tan presentes. Actualmente más de 3.800
millones de personas en todo el mundo están conectadas al mundo virtual, de los cuales
existen aproximadamente 3 mil millones de usuarios activos en las redes sociales. Y este
número tiende a crecer cada vez más, con la dinámica de mejoras constantes de estas
plataformas y el surgimiento de nuevas.
Las redes sociales son plataformas digitales formadas por comunidades de
individuos con intereses, actividades o relaciones en común (como amistad, parentesco,
trabajo, etc). Las redes sociales permiten el contacto entre personas y funcionan como un
medio para comunicarse e intercambiar información. Los individuos no necesariamente se
tienen que conocer antes de entrar en contacto a través de una red social, sino que pueden
hacerlo a través de ella, y ese es uno de los mayores beneficios de las comunidades
virtuales. Las redes sociales [29], se pueden clasificar en dos tipos:
● Redes sociales horizontales o genéricas: Son aquellas redes sociales que
no poseen una temática determinada, sino que apuntan a todo tipo de
usuarios. Estas redes funcionan como medios de comunicación, información
o entretenimiento. Son muy numerosas y populares, por ejemplo: Facebook o
Twitter.
● Redes sociales verticales: Son aquellas redes sociales que relacionan
personas con intereses específicos en común, como música, hobbies,
deportes. Por ejemplo: Flickr, red social cuya temática es la fotografía.
Flixster, cuya red social permitía encontrar personas con los mismos gustos
sobre películas. Dentro de estas redes se encuentran las redes verticales
profesionales, como LinkedIn, que involucra individuos que comparten el
ámbito laboral o que buscan ampliar sus fronteras laborales.
La década del noventa se caracterizó por la aparición de la web, las redes sociales
no tardaron en llegar teniendo su origen en la segunda mitad de los noventa. Classmates
[30] es considerada la primera red social. Fue creada en 1995 por el estadounidense Randy
Conrads. Buscaba conectar de manera virtual a ex compañeros de colegio y universidad.
Como el proyecto fue exitoso, comenzaron a aparecer nuevas redes cuyo fin era reunir
amigos y conocidos.
En 1997 se creó SixDegrees, una red que permitía contactar a otros miembros de la
red, crear un perfil, armar listas de amigos, etc. SixDegrees se basó en la teoría de “seis
grados de separación”, que afirma que todas las personas se encuentran a seis personas
de distancia de cualquier otra persona del planeta. Esta red social estuvo activa hasta 2001.
En 2003 surgió Friendster, una red que permitía contactar a otros miembros y compartir
contenido online con ellos (fotos, videos, links). Estuvo activa con gran presencia de
usuarios hasta 2015. En 2003 también se creó LinkedIn, red social laboral para buscar,
recomendar u ofrecer un trabajo. Como respuesta ante la popularidad de Friendster surgió,
en 2003, MySpace. Creada por una agencia de marketing; esta red se dedicaba
especialmente a la música y a la tecnología. Para 2009, MySpace era la red social con
mayor tráfico de usuarios. Más tarde MySpace perdió la pulseada con la llegada y el auge
de Facebook, que surgió en 2004 y tuvo gran popularidad debido a su plataforma, al
creciente desarrollo de Internet y a la aparición de dispositivos móviles con conexión a la
red. De hecho, en la primera década del siglo XXI, surgieron algunas de las redes sociales
con mayor cantidad de usuarios.
Flixster [20] es un sitio de cine que permitía a los usuarios compartir listado de
películas, aprender sobre el cine y conocer a otras personas con gustos similares en las
películas. El sitio permite a los usuarios ver trailers de películas, así como aprender acerca
de las películas nuevas y próximos estrenos en taquilla. El sitio fue fundado por Joe
Greenstein y Chari Saran en el 2007. Luego Flixster fue adquirida por Warner Bros el 4 de
mayo de 2011. Flixster desarrolló aplicaciones para varios sitios de redes sociales. Estas
aplicaciones tenían muchas de las mismas características que el sitio principal de Flixster,
tales como valoraciones, comentarios, creados por los usuarios. Además, cada aplicación y
cada sitio de redes sociales o aplicaciones móviles eran totalmente gratuitas, permitiendo a
más usuarios descargar dicha aplicación.
Uno de los últimos sucesos en las redes sociales es Tik-Tok, una plataforma de
origen chino que permite crear y compartir vídeos. En 2018 se fusionó con Musical.ly y es
una de las redes con el mayor flujo de usuarios jóvenes, disponible en 39 idiomas.
Influence Maximization and propagation
La idea detrás del marketingviral es que, al dirigirnos a los usuarios más influyentes
de la red, podemos activar una reacción en cadena de tal manera que con un costo de
marketing muy pequeño podamos alcanzar una porción muy grande de la red. Uno de los
principales problemas en esta área, es la identificación de los usuarios influyentes. La
elección de estos, es un factor clave para garantizar el éxito y conseguir los objetivos
empresariales, dentro de la planificación de la estrategia comercial.
Para determinar cuáles son los usuarios más influyentes de una red, es necesario
analizar la propagación de la influencia en las redes sociales; Para esto, en primer lugar es
necesario definir qué es considerado influencia. La influencia es la acción de influir, es decir,
de ejercer predominio o fuerza moral o condicionar el comportamiento ajeno. Pero, en las
redes sociales, ¿cuál es el concepto de influencia? La respuesta básica es que cuando los
usuarios ven a sus contactos de la red realizar una acción, ellos deciden llevarla a cabo
también. Si observamos que un usuario v realiza una acción a en un tiempo t, y un usuario u
(que tiene una relación con v) realiza la misma acción en un plazo corto de tiempo,
entonces podemos pensar que la acción a se propagó de v a u. En caso de observar que
esto sucede frecuentemente para diferentes acciones, entonces podemos concluir que el
usuario v está ejerciendo influencia sobre el usuario u.
Para trasladar este contexto, supongamos que tenemos una red social, que es un
grafo, donde los nodos son usuarios, y los links son las relaciones entre estos usuarios.
Supongamos a su vez, que tenemos una estimación de la influencia recíproca entre estos
usuarios, y que deseamos insertar un producto en la red. El problema de la maximización
de la influencia es encontrar un conjunto inicial de usuarios donde su influencia alcance al
mayor número posible de usuarios en la red.
Kempe [11] formalizó esto como el problema de maximización de influencia:
“encontrar k nodos ‘semilla’ en la red, para un número k dado, de modo que al
activarlos podamos maximizar la propagación de influencia esperada”
El modelo de propagación determina cómo se difunde o propaga la influencia a
través de la red.
Kempe [11] centró su trabajo en dos modelos de propagación denominados,
Independent Cascade Model (IC) y Threshold Model (LT). En ambos modelos, en un tiempo
dado, cada nodo está activo o inactivo, y la tendencia de cada nodo a activarse aumenta de
forma monotónica a medida que sus vecinos se vuelven activos. Un nodo activo nunca
vuelve a estar inactivo. El tiempo se desarrolla de manera determinista en pasos discretos y
a medida que pasa el tiempo, más y más vecinos de un nodo inactivo se vuelven activos, lo
que eventualmente hace que se vuelva activo, y su decisión puede a su vez desencadenar
decisiones adicionales por parte de los nodos a los que está conectado. Bajo estos modelos
de propagación, IC y LT, el problema se vuelve NP-Hard. Sin embargo, Kempe, demostró
que la función es monótona y submodular. Gracias a estas dos propiedades, el problema de
maximización de influencia puede aproximarse con un factor de (1 − 1/e) con el algoritmo
Greedy.
Campo aleatorio de Markov
Domingos y Richardson en [10], modelaron el problema de propagación de
influencia e identificación de usuarios influyentes mediante campos aleatorios de Markov y
proporcionaron heurísticas para elegir a los usuarios a los que apuntar [1] [2] . Adoptaron el
contexto de la propagación de influencia al modelar solo el estado final de la red en
convergencia como un gran conjunto global de variables aleatorias interdependientes.
Un campo aleatorio de Markov es un conjunto de variables aleatorias que tienen una
propiedad de Markov descrito por un grafo no dirigido. En otras palabras, un campo
aleatorio se dice que es un campo aleatorio Markov, si satisface las propiedades de Markov.
Es un modelo de grafo no dirigido que representa la distribución conjunta sobre un conjunto
de variables aleatorias, donde los vértices son variables y los bordes representan
dependencias entre variables.
Consideraron un conjunto de n clientes potenciales y tomando como una variable𝑋𝑖
lógica que toma el valor 1 si el cliente compra el producto que se comercializa, y 0 en caso𝑖
contrario. Se considera que los vecinos de son los clientes que influyen directamente.𝑋𝑖
Además, es la variable que represente la acción de marketing que se toma para el𝑀𝑖
cliente . Entonces, para todo ,𝑖, (𝑀 = {𝑀
1
,..., 𝑀
𝑛
}) 𝑋
𝑖
∉ 𝑋𝑘
𝑃(𝑋𝑖 |𝑋 𝑘, 𝑌, 𝑀)
=
𝐶(𝑁
𝐼
𝑈)
∑ 𝑃(𝑋
𝑖
, 𝑁
𝑖
𝑢, |𝑋𝑘, 𝑌, 𝑀)
=
𝐶(𝑁
𝐼
𝑈)
∑ 𝑃(𝑋
𝑖
|𝑁
𝑖
𝑢, 𝑋𝑘, 𝑌, 𝑀)𝑃(𝑁
𝑖
𝑢|𝑋𝑘, 𝑌, 𝑀)
=
𝐶(𝑁
𝐼
𝑈)
∑ 𝑃(𝑋
𝑖
|𝑁
𝑖
, 𝑌, 𝑀)𝑃(𝑁
𝑖
𝑢|𝑋𝑘, 𝑌, 𝑀)
Ecuación 2.1
Donde es el conjunto de todas las configuraciones posibles de los vecinos𝐶(𝑁
𝑖
𝑢)
desconocidos de . Aproximando por su estimación de entropía máxima𝑋
𝑖
𝑃(𝑁
𝑖
𝑢|𝑋𝑘, 𝑌, 𝑀)
dados los marginales para todo .𝑃(𝑋
𝑗
|𝑋𝑘, 𝑌, 𝑀) 𝑋
𝑗
 ∈ 𝑁
𝑖
𝑢
Provocando:
𝑃(𝑋
𝑖
|𝑋𝑘, 𝑌, 𝑀)
=
𝐶(𝑁
𝐼
𝑈)
∑ 𝑃(𝑋
𝑖
|𝑁
𝑖
, 𝑌, 𝑀) 
𝑋𝑗∈𝑁
𝑖
𝑢
∏ 𝑃(𝑋
𝑗
|𝑋𝑘, 𝑌, 𝑀)
Ecuación 2.2
El conjunto de variables con probabilidad conjunta condicionada por , y𝑋𝑢 𝑋𝑘 𝑌 𝑀
descritas por la ecuación anterior, es una instancia de un campo aleatorio de Markov.
Debido a que expresa las probabilidades en función de sí mismas, se puede𝑃(𝑋
𝑖
|𝑋𝑘, 𝑌, 𝑀)
aplicar de forma iterativa para encontrarlas, comenzando por una asignación inicial
adecuada. Este procedimiento se conoce como etiquetado de relajación y se garantiza que
converge a valores localmente consistentes siempre que la asignación inicial esté lo
suficientemente cerca de ellos. Una opción natural para la inicialización es usar las
probabilidades sin red .𝑃(𝑋
𝑖
|𝑌, 𝑀)
Observe que el número de términos en la ecuación 2.2 es exponencial en el número
de vecinos desconocidos de . Si este número es pequeño, esto no debería ser un𝑋𝑖
problema; de lo contrario, se necesita una solución aproximada. Un método estándar para
este propósito es el muestreo de Gibbs. Se propone una alternativa basada en un algoritmo
eficiente de k-ruta más corta en Chakrabarti.
Dado y debe ser independiente de las acciones de marketing para los demás𝑁
𝑖
𝑌, 𝑋
𝑖
clientes. Suponiendo un modelo de Bayes para en función de , y :𝑋
𝑖
𝑁
𝑖
𝑌
1
, ..., 𝑌
𝑛
𝑀
𝑖
𝑃(𝑋
𝑖
|𝑁
𝑖
, 𝑌, 𝑀)
= 𝑃(𝑋
𝑖
|𝑁
𝑖
, 𝑌, 𝑀
𝑖
)
= 𝑃(𝑋
𝑖
) 𝑃(𝑁
𝑖
, 𝑌, 𝑀
𝑖
|𝑋
𝑖
) / 𝑃(𝑁
𝑖
, 𝑌, 𝑀)
= [𝑃(𝑋
𝑖
) 𝑃(𝑁
𝑖
|𝑋
𝑖
)𝑃(𝑀
𝑖
|𝑋
𝑖
) / 𝑃(𝑁
𝑖
, 𝑌, 𝑀)] 
𝑘=1
𝑚
∏ 𝑃(𝑌
𝑘
|𝑋
𝑖
)
= [𝑃(𝑋
𝑖
|𝑁
𝑖
) 𝑃(𝑀
𝑖
|𝑋
𝑖
) / 𝑃(𝑌, 𝑀
𝑖
|𝑁
𝑖
)] 
𝑘=1
𝑚
∏ 𝑃(𝑌
𝑘
|𝑋
𝑖
)
Ecuación 2.3
Donde:
𝑃(𝑌, 𝑀
𝑖
|𝑁
𝑖
) = 𝑃(𝑌, 𝑀
𝑖
|𝑋
𝑖
= 1)𝑃(𝑋
𝑖
= 1|𝑁
𝑖
) + 𝑃(𝑌, 𝑀
𝑖
|𝑋
𝑖
= 0)𝑃(𝑋
𝑖
= 0|𝑁
𝑖
)
Ecuación 2.4
Las correspondientes probabilidades sin red son:
𝑃(𝑋
𝑖
|𝑌, 𝑀) = 𝑃(𝑋
𝑖
)𝑃(𝑀
𝑖
|𝑋
𝑖
) 
𝑘=1
𝑚
∏ 𝑃(𝑌
𝑘
|𝑋
𝑖
)/𝑃(𝑌, 𝑀
𝑖
)
Ecuación 2.5
Por simplicidad, suponga que M es un vector booleano (es decir, solo se está
considerando un tipo de acción de marketing, como ofrecer al cliente un descuento
determinado). Supongamos que c es el costo de comercialización para un cliente (se
supone constante), es el ingreso por vender el producto al cliente si no se realiza ninguna𝑟
0
acción de comercialización, y es el ingreso si se realiza la comercialización, serán𝑟
1
𝑟
0
 𝑦 𝑟
1
igual a menos que la acción de marketing ofrezca un descuento.
Sea el resultado de establecer a 1 y dejar el resto de sin cambios y𝑓
𝑖
1(𝑀) 𝑀
𝑖
 𝑀 
similar a . El aumento esperado de las ganancias de marketing para el cliente𝑓
𝑖
0(𝑀) 𝑖
ignorando su efecto sobre otros clientes, es:
𝐸𝐿𝑃
𝑖
(𝑋𝑘, 𝑌, 𝑀) =
𝑟
1
𝑃(𝑋
𝑖
= 1|𝑋𝑘, 𝑌, 𝑓
𝑖
1(𝑀))
− 𝑟
0
𝑃(𝑋
𝑖
= 1|𝑋𝑘, 𝑌, 𝑓
𝑖
0(𝑀)) − 𝑐
Ecuación 2.6
Donde es el vector nulo (todosceros). El aumento global en las ganancias que𝑀
0
resulta de una elección particular M de clientes para comercializar es entonces:
𝐸𝐿𝑃
𝑖
(𝑋𝑘, 𝑌, 𝑀) =
𝑖=1
𝑛
∑ 𝑟
1
𝑃(𝑋
𝑖
= 1|𝑋𝑘, 𝑌, 𝑀)
− 𝑟
0
 
𝑖=1
𝑛
∑ 𝑃(𝑋
𝑖
= 1|𝑋𝑘, 𝑌, 𝑀
0
) − |𝑀|𝑐
Ecuación 2.7
Donde:
● si𝑟
𝑖
= 𝑟
1
𝑀
𝑖
= 1
● si𝑟
𝑖
= 𝑟
0
𝑀
𝑖
= 0
● es el número de 1 en|𝑀| 𝑀
El objetivo es encontrar la asignación de valores a M que maximice ELP. En general,
encontrar la M óptima requiere probar todas las combinaciones posibles de asignaciones a
sus componentes. Como esto es imposible, proponen utilizar uno de los siguientes métodos
aproximados:
● Single pass
● Greedy search
● Hill-climbing search
Cada método es computacionalmente más costoso que el anterior, pero
potencialmente conduce a una mejor solución para M (es decir, produce un ELP más alto).
Supongamos ahora que podemos aumentar la probabilidad de compra de un cliente al
aumentar la cantidad gastada en marketing para ella, y que podemos estimar cuánto se
necesita gastar para producir un aumento dado en la probabilidad de compra. El costo
óptimo de adquisición del cliente para el cliente es entonces el valor de que maximiza su𝑖 𝐶
𝑖
valor total con reemplazado por en la𝐸𝐿𝑃(𝑋𝑘, 𝑌, 𝑓
𝑖
1(𝑀)) − 𝐸𝐿𝑃(𝑋𝑘, 𝑌, 𝑓
𝑖
0(𝑀)) |𝑀|𝑐
𝑖=1
𝑛
∑ 𝐶
𝑖
 
ecuación 2.7.
The Independent Cascade y Linear Threshold
Los primeros en considerar la propagación de la influencia y el problema de la
obtención de usuarios influyentes en una red, fueron Domingos y Richardson [10] [17]. Ellos
modelaron el problema mediante campos aleatorios de Markov y proporcionaron heurísticas
para elegir a los usuarios a los que apuntar.
Kempe, por otro lado, en [11] hizo foco en dos modelos de propagación, “The
Independent Cascade” (IC) y “Linear Threshold” (LT). En ambos modelos un nodo está
activo o inactivo, en un tiempo dado. El tiempo se desarrolla en pasos discretos. La
tendencia de un nodo a activarse aumenta a medida que sus vecinos se activan, y un nodo
activo, nunca vuelve a estar inactivo.
Bajo los modelos de propagación, IC y LT, se demostró que el problema es NP-Hard.
Sin embargo, Kempe mostró que la función ) es monótona y submodular. Una funciónσ
𝑚
(𝑆
de un conjunto de reales, es monótona si donde . Una función es𝑓 𝑓(𝑠) ≤ 𝑓(𝑡) 𝑆 ⊆ 𝑇
submodular si siempre que La𝑓(𝑆 + 𝑤) − 𝑓(𝑆) ≥ 𝑓(𝑇 + 𝑤) − 𝑓(𝑇) 𝑆 ⊆ 𝑇.
submodularidad dice intuitivamente que la probabilidad de un nodo activo, de activar algún
nodo inactivo no aumenta si más nodos ya han intentado activarlo. Esto también se llama
"la ley de rendimientos decrecientes". Para cualquier función submodular monótona con𝑓
, el problema de encontrar un conjunto S de tamaño k tal que sea máximo,𝑓 (ϕ) = 0 𝑓(𝑆)
puede aproximarse a un factor de (1−1 / e) por un algoritmo Greedy, un resultado que se
traslada directamente a el problema de maximización de influencia.
En el modelo IC, cuando un nodo se activa por primera vez, digamos en el tiempo𝑣
, se considera contagioso. Tiene una posibilidad de influir en cada vecino inactivo con𝑡 𝑢
probabilidad , independientemente de la historia hasta el momento. Si la tentativa tiene𝑝
𝑣,𝑢
éxito, se activa en el tiempo . La probabilidad puede considerarse como la fuerza𝑢 𝑡 + 1 𝑝
𝑣,𝑢
de la influencia de sobre𝑣 𝑢.
En el modelo LT, por otro lado, cada nodo está influenciado por cada vecino de𝑢 𝑣
acuerdo con un peso de modo que la suma de los pesos entrantes a no es mayor que𝑝
𝑣,𝑢
𝑢
1. Cada nodo elige un umbral uniformemente al azar entre [0 , 1]. En cualquier marca𝑢 θ
𝑢
de tiempo , si el peso total de los vecinos activos de un nodo inactivo es al menos ,𝑡 𝑢 θ
𝑢
entonces se activa en la marca de tiempo𝑢 𝑡 + 1.
Para fundamentar esto, Kempe en [11] considera un punto en el proceso del
algoritmo cuando el nodo se activa e intenta activar a su vecino , teniendo éxito con un𝑣 𝑤
probabilidad . Podemos ver el resultado de este evento aleatorio como determinado al𝑝
𝑣,𝑤
lanzar una moneda de sesgo . Desde el punto de vista del proceso, claramente no𝑝
𝑣,𝑤
importa si la moneda fue lanzada en el momento en que se activó, o si fue lanzada al𝑣
comienzo de todo el proceso y solo se está revelando ahora. Continuando con ese
razonamiento, supone que, para cada par de vecinos en el grafo, se lanza una(𝑣, 𝑤)
moneda de sesgo al comienzo del proceso (independientemente de las monedas para𝑝
𝑣,𝑤
todos los demás pares de vecinos), y el resultado se almacena para que luego pueda
verificarse en caso de que se active mientras todavía está inactivo.𝑣 𝑤
Con todas las monedas lanzadas por adelantado, el proceso se puede ver de la
siguiente manera. Las aristas en para los cuales el lanzamiento de la moneda indica que𝐺
una activación será exitosa se declaran vivos; Las aristas restantes se declaran bloqueadas.
Si arreglamos los resultados de los lanzamientos de monedas y luego activamos
inicialmente un conjunto , queda claro cómo determinar el conjunto completo de nodos𝐴
activos al final del proceso en cascada:
Teniendo en cuenta que,
“un nodo termina activo si y sólo si, hay un camino desde algún nodo en a que𝑥 𝐴 𝑥
consiste completamente en bordes vivos. (Llamaremos a este camino un camino de borde
vivo)”
Aclaración 2.1
Si se considera el espacio de probabilidades en el que cada punto muestral
especifica un posible conjunto de resultados, para todos los lanzamientos de moneda en los
bordes. Sea X un punto muestral en este espacio, y se define como el número total deσ
𝑥
(𝐴)
nodos activados por el proceso cuando es el conjunto objetivo inicialmente y X es el𝐴
conjunto de resultados de todos los lanzamientos de monedas en los bordes. Como se fijó
una opción para que es de hecho una cantidad determinista y existe una forma𝑋, σ
𝑥
(𝐴)
natural de expresar su valor, como sigue. Sea el conjunto de todos los nodos a los𝑅(𝑣, 𝑋)
que se puede llegar desde v, en una ruta que consta completamente de bordes vivos.
Según la aclaración 2.1, es el número de nodos que se pueden alcanzar en las rutasσ
𝑥
(𝐴)
de borde vivo desde cualquier nodo en , por lo que es igual a la cardinalidad de la unión𝐴
.𝑈
𝑣∈𝐴
𝑅(𝑣, 𝑋)
Para probar que IC es submodular, en [11] se afirma que para cada resultado fijo ,𝑋
la función es submodular. Para ver esto, propone que y sean dos conjuntos deσ
𝑥
(·) 𝑆 𝑇
nodos tales que , y considera la cantidad . Este es el número de𝑆 ⊆ 𝑇 σ
𝑥
(𝑆 ∪ {𝑣}) − σ
𝑥
(𝑆)
elementos en que aún no están en la unión ; es al menos tan grande𝑅(𝑣, 𝑋) 𝑈
𝑢∈𝑆
𝑅(𝑢, 𝑋)
como el número de elementos en que no están en la unión (más grande)𝑅(𝑣, 𝑋) 𝑈
𝑢∈𝑆
𝑅(𝑢, 𝑋)
. Se deduce que σX (S ∪ {v}) - σX (S) ≥ σX (T ∪ {v}) - σX (T), que es la desigualdad
definitoria para la submodularidad.
En el análisis para el modelo de LT, cada nodo tiene un peso de influencia𝑣 𝑏
𝑣,𝑤
≥ 0
de cada uno de sus vecinos , sujeto a la restricción de que . (Podemos extender𝑤
𝑤
∑ 𝑏
𝑣,𝑤
≤ 1
esta notación escribiendo cuando no es un vecino de ).𝑏
𝑣,𝑤
= 0 𝑤 𝑣
Supongamos que selecciona al menos una de sus aristas al azar, seleccionando la𝑣
arista con probabilidad y no seleccionando la arista con probabilidad . El𝑤 𝑏
𝑣,𝑤
1 −
𝑤
∑ 𝑏
𝑣,𝑤
borde seleccionado se declara como "en vivo", y todos los demás bordes se declaran como
"bloqueados".
Se necesita demostrar que la accesibilidad bajo la elección aleatoria de bordes vivos
y bloqueados define un proceso equivalente al del Modelo LT. Para obtener una intuición
sobre esta equivalencia, es útil analizar primero el caso especial en el que el grafo
subyacente es dirigido y acíclico. En este caso, podemos arreglar un orden topológico de𝐺
los nodos (para que todos los bordes pasen de nodos anteriores a nodos𝑣
1
, 𝑣
2
,..., 𝑣
𝑛
posteriores en el orden) y desarrolle la distribución de conjuntos activos siguiendo ese
orden. Para cada nodo , supongamos que ya hemos determinado la distribución en𝑣
𝑖
subconjuntosactivos de sus vecinos. Luego, bajo el proceso de LT, la probabilidad de que 𝑣
𝑖
se active, dado que un subconjunto de sus vecinos está activo, es . Esta es𝑆
𝑖
𝑤∈𝑆
𝑖
∑ 𝑏
𝑣
𝑖
,𝑤
precisamente la probabilidad de que el borde entrante en vivo seleccionado por se𝑣
𝑖
encuentre en , por lo que inductivamente vemos que los dos procesos definen la misma𝑆
𝑖
distribución sobre conjuntos activos.
Para probar la aclaración, considere un grafo que no sea acíclico. Se vuelve más𝐺
complicado mostrar la equivalencia, porque no hay un orden natural de los nodos sobre los
cuales realizar la inducción. En cambio, discutimos por inducción sobre las iteraciones del
proceso de LT. Definimos como el conjunto de nodos activos al final de la iteración , para𝐴
𝑡
𝑡
(teniendo en cuenta que es el conjunto inicialmente dirigido). Si el nodo no𝑡 = 0, 1, 2,... 𝐴
0
𝑣
se ha activado al final de la iteración , entonces la probabilidad de que se active en la𝑡
iteración es igual a la posibilidad de que los pesos de influencia en lo empujen𝑡 + 1 𝐴
𝑡
/𝐴
𝑡−1
por encima de su umbral, dado que su el umbral no fue excedido ya; esta probabilidad es
(
𝑢∈𝐴
𝑡
\𝐴
𝑡−1
∑ 𝑏
𝑣,𝑤
)/(1 − 
𝑢∈𝐴
𝑡−1
∑ 𝑏
𝑣,𝑤
)
Ecuación 2.21
Por otro lado, podemos ejecutar el proceso de borde vivo revelando las identidades
de los bordes vivos gradualmente de la siguiente manera. Comenzamos con el conjunto
objetivo . Para cada nodo con al menos un borde del conjunto , determinamos si el𝐴 𝑣 𝐴
borde activo de proviene de . Si es así, entonces es accesible; pero si no, mantenemos𝑣 𝐴 𝑣
desconocido el origen del borde vivo de , sujeto a la condición de que provenga del𝑣
exterior . Después de haber expuesto un nuevo conjunto de nodos accesibles en la𝐴
primera etapa, procedemos a identificar otros nodos accesibles mediante realizando el𝐴
1
'
mismo proceso en las aristas de , y de esta manera produce conjuntos Si no se𝐴
1
' 𝐴
2
' , 𝐴
3
' ,...
ha determinado que el nodo es alcanzable al final de la etapa , entonces la probabilidad𝑣 𝑡
de que se determine que se puede alcanzar en la etapa es igual a la probabilidad de𝑡 + 1
que su borde vivo provenga de , dado que su ventaja en vivo no proviene de ninguno𝐴
𝑡
\𝐴
𝑡−1
de los conjuntos anteriores. Pero esta es la fórmula:
(
𝑢∈𝐴
𝑡
\𝐴
𝑡−1
∑ 𝑏
𝑣,𝑤
)/(1 − 
𝑢∈𝐴
𝑡−1
∑ 𝑏
𝑣,𝑤
)
Ecuación 2.22
que es igual que en el proceso de LT del párrafo anterior. Por lo tanto, por inducción
sobre estas etapas, vemos que el proceso de borde vivo produce la misma distribución
sobre conjuntos activos que el proceso umbral lineal.
Credit Distribution
Goyal en [2] adopta una perspectiva diferente sobre la definición del alcance
esperado, al tratar el problema de maximización de la influencia. Teniendo en cuenta que
los modelos IC y LT discutidos anteriormente son de naturaleza probabilística. En el modelo
IC, los lanzamientos de monedas deciden si un nodo activo logrará activar sus pares. En el
modelo LT, es el umbral de nodo elegido uniformemente al azar, junto con los pesos de
influencia de los vecinos activos, lo que decide si un nodo se vuelve activo. Bajo ambos
modelos, podemos pensar en una traza de propagación el resultado de un conjunto de
elecciones probabilísticas.
Dado un modelo de propagación y un grafo dirigido y ponderado , donde 𝐺 = (𝑉, 𝐸, 𝑝)
denota el conjunto de todos los mundos posibles. Independientemente del modelo𝐺 𝑚
elegido, la extensión esperada se puede escribir como:σ
𝑚
(𝑆)
σ
𝑚
(𝑆) =
𝑥∈𝐺
∑ 𝑃𝑟[𝑋] · σ
𝑚
𝑥 (𝑆)
Ecuación 2.23
donde es el número de nodos alcanzables desde en el posible mundo . El númeroσ
𝑚
𝑥 (𝑆) 𝑆 𝑋
de mundos posibles es claramente exponencial, por lo tanto, el enfoque estándar
(simulaciones Montecarlo) es muestrear un mundo posible X ∈ G, calcular y repetirσ
𝑚
𝑥 (𝑆)
hasta que el número de mundos muestreados sean lo suficientemente grandes.
Mientras que el enfoque estándar muestra mundos posibles desde la perspectiva de
la ecuación 2.23, Goyal en [2] observa que las trazas de propagaciones reales son similares
a los mundos posibles, excepto que son "mundos reales disponibles", es decir, estima
directamente utilizando las trazas de propagación disponibles en el𝑃𝑟[𝑝𝑎𝑡ℎ(𝑆, 𝑢) = 1]
registro de propagación.
Para estimar utilizando trazas de propagación disponibles, es𝑃𝑟[𝑝𝑎𝑡ℎ(𝑆, 𝑢) = 1] 
natural interpretar tal cantidad como la fracción de las acciones iniciadas por que se𝑆
propagaron a , dado que es el conjunto de semillas. Más precisamente, podríamos𝑢 𝑆
estimar esta probabilidad como:
|{𝑎 ∈ 𝐴|𝑖𝑛𝑖𝑡𝑖𝑎𝑡𝑒(𝑎, 𝑆)&∃𝑡: (𝑢, 𝑎, 𝑡) ∈ 𝐿}| / |{𝑎 ∈ 𝐴|𝑖𝑛𝑖𝑡𝑖𝑎𝑡𝑒(𝑎, 𝑆)}|
Ecuación 2.24
donde denota el registro de propagación y es verdadero si es precisamente𝐿 𝑖𝑛𝑖𝑡𝑖𝑎𝑡𝑒(𝑎, 𝑆) 𝑆
el conjunto de iniciadores de acción . Desafortunadamente, este enfoque sufre un𝑎
problema de escasez que es intrínseco al problema de maximización de influencia.
Considere, por ejemplo, un nodo que es un usuario muy influyente para la mitad de𝑥
la red, y otro nodo que es un usuario muy influyente para la otra mitad de la red. Es𝑦
probable que su unión sea un conjunto de semillas muy bueno, pero no podemos{𝑥, 𝑦}
estimar su propagación utilizando la fracción de las acciones que contienen , porque es{𝑥, 𝑦}
posible que no tengamos propagación en los datos con como el conjunto de semillas{𝑥, 𝑦}
real.
Resumiendo, si necesitamos estimar para cualquier conjunto y𝑃𝑟[𝑝𝑎𝑡ℎ(𝑆, 𝑢) = 1] 𝑆
nodo , necesitaremos una enorme cantidad de trazas de propagación correspondientes a𝑢
varias combinaciones, donde cada traza tiene como su conjunto iniciador precisamente el
conjunto de nodos requerido . Es claramente poco práctico encontrar un registro de acción𝑆
del mundo real donde esto se pueda realizar (a menos que alguien establezca un
experimento a gran escala basado en humanos, donde se inicien muchas propagaciones
con los conjuntos de semillas deseados).
Para superar este obstáculo, los autores sugieren una perspectiva "u-centrica" para
la estimación de : escanean el registro de propagación y cada vez que𝑃𝑟[𝑝𝑎𝑡ℎ(𝑆, 𝑢) = 1] 𝑢
realiza una acción se distribuyen "créditos" a los posibles influenciadores del nodo ,𝑢
retrocediendo la red de propagación. Este modelo se denomina Credit Distribution.
Tenemos un grafo donde , con nodos correspondientes a los usuarios y𝐺 = (𝑉, 𝐸) 𝑉
bordes dirigidos (no ponderados) correspondientes a los lazos sociales entre los usuarios,𝐸
y un registro de acciones, es decir, una relación donde una tupla𝐿(𝑈𝑠𝑒𝑟, 𝐴𝑐𝑡𝑖𝑜𝑛, 𝑇𝑖𝑚𝑒)
indica que un usuario realizó la acción en el tiempo . Contiene una tupla(𝑢, 𝑎, 𝑡) ∈ 𝐿 𝑢 𝑎 𝑡
para cada acción realizada por cada usuario del sistema. Además se asume que la
proyección de en la primera columna está contenida en el conjunto de nodos del grafo𝐿 𝑉 𝐺
. denota el universo de acciones, es decir, la proyección de en la segunda columna.𝐴 𝐿
Además, suponemos que un usuario realiza una acción como máximo una vez, y definimos
la función para devolver el tiempo cuando el usuario realizó la acción (el valor𝑡(𝑢, 𝑎) 𝑢 𝑎
no está definido si nunca se realizó , y es falso siempre que𝑡(𝑢, 𝑎) 𝑎 𝑡(𝑢, 𝑎) < 𝑡(𝑣, 𝑎)
cualquier no esté definido).𝑡(𝑢, 𝑎), 𝑡(𝑣, 𝑎)
Decimos que se propaga del nodo a si y sólo si, están socialmente vinculados,𝑎 𝑢 𝑣
y realiza una acción antes que (también decimos que influye sobre por ). Esto𝑢 𝑎 𝑣 𝑢 𝑣 𝑎
define un grafo de propagación de cómo un grafo dirigido con𝑎 𝐺(𝑎) = (𝑉(𝑎), 𝐸(𝑎))
y . Tenga en cuenta𝑉(𝑎) = {𝑣 ∈ 𝑉|∃ι : (𝑣, 𝑎, 𝑡) ∈ 𝐿} 𝐸(𝑎) = {(𝑢, 𝑣) ∈ 𝐸 | 𝑡(𝑢, 𝑎) < 𝑡(𝑣, 𝑎)}
que el grafo de propagación de una acción es la representación gráfica de la traza de𝑎
propagación de , y siempre es un DAG: está dirigido, cada nodo puede tener cero o más𝑎
padres, y los ciclos son imposibles debido a la restricción de tiempo . El registro de acciones
es, por lo tanto, un conjunto de estos DAG querepresentan trazas de propagación a𝐿
través del grafo. Denotamos el conjunto de potenciales𝑁
𝑖𝑛
(𝑢, 𝑎) = {𝑣|(𝑣, 𝑢) ∈ 𝐸(𝑎)}
influyentes de para la acción y ser el grado de para la acción .𝑢 𝑎 𝑑
𝑖𝑛
(𝑢, 𝑎) = |𝑁
𝑖𝑛
(𝑢, 𝑎)| 𝑢 𝑎
Finalmente, llamamos a un usuario un iniciador de la acción si y ,𝑢 𝑎 𝑢 ∈ 𝑉(𝑎) 𝑑
𝑖𝑛
(𝑢, 𝑎) = 0
es decir, realizó la acción pero ninguno de sus vecinos la realizó antes que .𝑢 𝑎 𝑢
Cuando un usuario realiza una acción , deseamos otorgar crédito de influencia𝑢 𝑎
directa, denotado por , para todo , es decir, todos los vecinos de queγ
𝑣,𝑢
(𝑎) 𝑣 ∈ 𝑁
𝑖𝑛
(𝑢, 𝑎) 𝑢
realizaron la misma acción antes de . Restringimos la suma de los créditos directos𝑎 𝑢
otorgados por un usuario a sus vecinos para que no sea mayor que 1. Podemos tener
varias formas de asignar crédito directo: para facilitar la explicación, asumimos por el
momento dar créditos iguales a cada vecino de , es decir, para todo𝑣 𝑢 γ
𝑣,𝑢
(𝑎) = 1/𝑑
𝑖𝑛
(𝑢, 𝑎)
. Más adelante se comentará un método más sofisticado para asignar crédito𝑣 ∈ 𝑁
𝑖𝑛
(𝑢, 𝑎)
directo.
Intuitivamente, también queremos distribuir el crédito de influencia de forma
transitiva hacia atrás en el grafo de propagación , de modo que no solo otorgue𝐺(𝑎) 𝑢
crédito a los usuarios , sino que a su vez transfieran el crédito a sus𝑣 ∈ 𝑁
𝑖𝑛
(𝑢, 𝑎)
predecesores en y así sucesivamente. Esto sugiere la siguiente definición de crédito𝐺(𝑎)
total otorgado a un usuario por influir en en la acción , correspondiente a múltiples𝑣 𝑢 𝑎
rutas de propagación:
Γ
𝑣,𝑢
(𝑎) =
𝑤∈𝑁
𝑖𝑛
(𝑢,𝑎)
∑ Γ
𝑣,𝑤
(𝑎) · γ
𝑤,𝑢
(𝑎)
Ecuación 2.25
donde la base de la recursión es . A veces, cuando la acción es clara desde elΓ
𝑣,𝑣
(𝑎) = 1
contexto, podemos omitir y simplemente escribir y . De ahora en más, como ejemplo,γ
𝑣,𝑢
Γ
𝑣,𝑢
consideramos el grafo de la figura 1 como el grafo de propagación con los bordes𝐺(𝑎)
etiquetados con crédito directo . Por ejemplo:γ
𝑣,𝑢
(𝑎) = 1/𝑑
𝑖𝑛
(𝑢, 𝑎)
Γ
𝑣,𝑢
= Γ
𝑣,𝑣
· γ
𝑣,𝑢
+ Γ
𝑣,𝑡
· γ
𝑡,𝑢
+ Γ
𝑣,𝑤
· γ
𝑤,𝑢
 + Γ
𝑣,𝑧
· γ
𝑧,𝑢
 = 1 · 0. 25 + 0. 5 · 0. 25 + 1 · 0. 25 + 0. 5 · 0. 25 = 0. 75
Ecuación 2.26
Luego definimos el crédito total otorgado a un conjunto de nodos por influir𝑆 ⊆ 𝑉(𝑎)
al usuario en la acción de la siguiente manera:𝑢 𝑎
Si 𝑣 ∈ 𝑆:
Γ
𝑆,𝑢
=
𝑤∈𝑁
𝑖𝑛
(𝑢,𝑎)
∑ Γ
𝑠,𝑤
(𝑎) · γ
𝑤,𝑢
(𝑎)
⎰
⎱
⎱
⎰
Ecuación 2.27
Sino:
1
Considere nuevamente el grafo de propagación en la Figura 1. Sea𝐺(𝑎) 𝑆 = {𝑣, 𝑧}
Entonces, es la fracción de flujo que llega a que fluye desde o :Γ
𝑆,𝑢
𝑢 𝑣 𝑧
Γ
𝑆,𝑢
= Γ
𝑆,𝑤
· γ
𝑤,𝑢
+ Γ
𝑆,𝑣
· γ
𝑣,𝑢
+ Γ
𝑆,𝑡
· γ
𝑡,𝑢
 + Γ
𝑆,𝑧
· γ
𝑧,𝑢
 = 1 · 0. 25 + 1 · 0. 25 + 0. 5 · 0. 25 + 1 · 0. 25 = 0. 875
Ecuación 2.28
La siguiente pregunta es cómo agregar el crédito de influencia sobre todo el registro
de acciones . Considere dos nodos y : el crédito de influencia total otorgado a por𝐿 𝑣 𝑢 𝑣 𝑢
para todas las acciones en , se obtiene simplemente tomando el crédito total sobre todas𝐴
las acciones y normalizando por el número de acciones realizadas por (denotado ). Esto𝑢 𝐴
𝑢
se justifica por el hecho de que los créditos son asignados por hacia atrás a sus posibles𝑢
influenciadores. Entonces definimos:
𝐾
𝑣,𝑢
= 1/𝐴
𝑢
𝑎∈𝐴
∑ Γ
𝑣,𝑢
(𝑎)
Ecuación 2.29
Intuitivamente, denota el crédito promedio otorgado a por influir en , sobre todas𝑣 𝑢
las acciones que realiza. Del mismo modo, para el caso de un conjunto de nodos ,𝑢 𝑆 ⊆ 𝑉
podemos definir el crédito de influencia total para todas las acciones en como:𝐴
𝐾
𝑆,𝑢
= 1/𝐴
𝑢
𝑎∈𝐴
∑ Γ
𝑆,𝑢
(𝑎)
Ecuación 2.30
Luego se analizó definir el crédito directo dado por un nodo a un vecinoγ
𝑣,𝑢
(𝑎) 𝑢 𝑣
para la acción . Se observó que la influencia decae con el tiempo de manera exponencial y𝑎
que algunos usuarios son más influyentes que otros. Motivado por estas ideas, propusieron
la asignación de crédito directo como:
γ
𝑣,𝑢
(𝑎) = (𝑖𝑛𝑓𝑙𝑢(𝑢)/𝑁
𝑖𝑛
(𝑢, 𝑎)) · 𝑒𝑥𝑝(− [(𝑡(𝑢, 𝑎) − 𝑡(𝑣, 𝑎))/𝑡
𝑣,𝑢
])
Ecuación 2.31
Aquí es el tiempo promedio necesario para que las acciones se propaguen del𝑡
𝑣,𝑢
usuario al usuario . El término exponencial en la ecuación logra el efecto deseado que𝑣 𝑢
influye en las desintegraciones con el tiempo. Además, denota la capacidad de𝑖𝑛𝑓𝑙𝑢(𝑢)
influencia del usuario, es decir, qué tan propenso es al usuario a influir en el contexto𝑢
social. Precisamente, se define como la fracción de acciones que realiza bajo la𝑖𝑛𝑓𝑙𝑢(𝑢) 𝑢
influencia de al menos uno de sus vecinos, digamos ; es decir, realiza la acción, digamos𝑣 𝑢
, Normalizado por para garantizar que la suma de los𝑎 𝑡(𝑢, 𝑎) − 𝑡(𝑣, 𝑎) ≤ τ
𝑣,𝑢
; 𝑁
𝑖𝑛
(𝑢, 𝑎)
créditos directos asignados a los vecinos de debido a la acción sea como máximo uno.𝑢 𝑎
Hay que tener en cuenta que tanto y se aprende de .𝑖𝑛𝑓𝑙𝑢(𝑢) 𝑡
.𝑢
𝐿
Ant Colony
Las hormigas son unos insectos hipersociales que suelen vivir en comunidades
organizadas bajo tierra, en túmulos a nivel del suelo o en árboles, la mayoría de las
especies están completamente ciegas. Pero pueden encontrar comida (en un grupo) con la
ayuda de un tipo especial de químico denominado “Feromona”. Ésta desempeña un papel
importante en la toma de decisiones cuando las hormigas mueven la comida al nido, la
hormiga realiza un comportamiento de búsqueda en el que las hormigas (siempre en una
cola) depositan feromonas en un camino durante la búsqueda de alimentos y forman un
rastro. Si no se encuentra ningún rastro de feromona, las hormigas se mueven de manera
básicamente aleatoria, pero cuando existe feromona depositada, tienen mayor tendencia a
seguir el rastro.
La elección entre distintos caminos toma lugar cuando varios caminos se cruzan.
Entonces, las hormigas eligen el camino a seguir con una decisión probabilística sesgada
por la cantidad de feromona, cuanto más fuerte es el rastro de feromona, mayor es la
probabilidad de elegirlo. Puesto que las hormigas depositan feromona en el camino que
siguen, este comportamiento lleva a un proceso de auto-refuerzo que concluye con la
formación de rastros señalados por una concentración de feromona elevada. Este
comportamiento permite además a las hormigas encontrar los caminos más cortos entre su
hormiguero y la fuente del alimento [26].
Proceso
Inicialmente no existe ningún rastro de feromona en el camino y, cuando una
hormiga llega a una intersección y debe elegir entre dos caminos, elige de manera aleatoria
uno de los caminos. Según transcurre el tiempo y mientras que las hormigas están
recorriendo los caminos, estos van recibiendo una cantidad superior de feromona. Esto
ocurre gracias a que al ser los caminos más cortos, las hormigas que los siguen consiguen
encontrar la comida más rápidamente, por lo que comienzan su viaje de retorno antes.
Entonces, en el camino más corto habrá un rastro de feromona ligeramente superior y, por
lo tanto, las decisiones de las siguientes hormigas estarán dirigidas en mayor medida a
dicho camino. Además, este camino recibirá una proporción mayor de feromona por las
hormigas que vuelven por él que por las que vuelven por el camino más largo. Este proceso
finaliza haciendo que la probabilidad de que una hormiga escoja el camino más corto
aumente progresivamente y que al final el recorrido de la colonia converja al más corto de
todos los caminos posibles.
Figura 2.1: Demostración de rastros de feromonas en una bifurcación.
Esta convergencia se complementa con la acción del entorno natural que provoca
que la feromona se evapore transcurrido un cierto tiempo. Así, los caminos menos
prometedores pierden progresivamente feromonas porque son visitados cada vez por
menos hormigas. Sin embargo, algunos estudios biológicos han demostrado que los rastros
de feromona son muy persistentes, la feromona puede permanecer desde unas pocas horas
hasta varios meses dependiendo de variosaspectos distintos, como la especie de las
hormigas, el tipo de suelo, etc [27]. Esto último provoca una menor influencia del efecto de
la evaporación en el proceso de búsqueda del camino más corto [7].
Metaheurística de Optimización Basada en Colonias de
Hormigas
Los algoritmos de Optimización basada en colonia de hormigas (ACO por sus siglas
en inglés), se inspiran directamente en el comportamiento de las colonias de hormigas
naturales. Los algoritmos de ACO, son por esencia, algoritmos constructivos, estos
algoritmos se basan en ir generando paso a paso una solución completa a un problema
eligiendo elementos de una lista de candidatos, análogamente, cada hormiga construye una
solución parcial al problema recorriendo el grafo. Cada arista del grafo, que representa un
posible movimiento de la hormiga, posee información de dos tipos:
1. Información heurística, que mide la preferencia heurística de moverse desde el
nodo hasta el nodo , o sea, de recorrer la arista .𝑟 𝑠 𝑎
𝑟𝑠
2. Información de los rastros de feromona artificiales, que mide la “deseabilidad
aprendida” del movimiento de a . Imita a la feromona real que depositan las𝑟 𝑠
hormigas naturales.
El modo de operación básico de un algoritmo de ACO es como sigue: las m
hormigas (artificiales) de la colonia se mueven, concurrentemente y de manera asíncrona, a
través de los estados adyacentes del grafo. Este movimiento se realiza siguiendo una regla
de transición que está basada en la información local, es decir, los nodos. Esta información
incluye la información heurística y memorística (rastros de feromona) para guiar la
búsqueda. Al moverse por el grafo, las hormigas construyen incrementalmente soluciones.
Opcionalmente, las hormigas pueden depositar feromona cada vez que crucen por una
arista mientras construyen la solución (actualización en línea paso a paso de los rastros de
feromona). Una vez que cada hormiga ha generado una solución se evalúa ésta y puede
depositar una cantidad de feromona que es función de la calidad de su solución. Esta
información guiará la búsqueda de las otras hormigas de la colonia en el futuro.
Además, el modo de operación genérico de un algoritmo de ACO incluye dos
procedimientos adicionales, la evaporación de los rastros de feromona y las acciones del
demonio. La evaporación de feromona la lleva a cabo el entorno y se usa como un
mecanismo que evita el estancamiento en la búsqueda y permite que las hormigas busquen
y exploren nuevas regiones del espacio. Las acciones del demonio son acciones opcionales
para implementar tareas desde una perspectiva global que no pueden llevar a cabo las
hormigas por la perspectiva local que ofrecen. Ejemplos son observar la calidad de todas
las soluciones generadas y depositar una nueva cantidad de feromona adicional sólo en las
transiciones/componentes asociadas a algunas soluciones, o aplicar un procedimiento de
búsqueda local a las soluciones generadas por las hormigas antes de actualizar los rastros
de feromona. En ambos casos, el demonio reemplaza la actualización en línea a posteriori
de feromona y el proceso pasa a llamarse actualización fuera de línea de rastros de
feromona.
Figura 2.2: algoritmo ACO.
El primer paso incluye la inicialización de los valores de los parámetros que se
tienen en consideración en el algoritmo. Entre otros, se deben fijar el rastro inicial de
feromona asociado a cada transición, , que es un valor positivo pequeño, normalmente el𝑡
0
mismo para todas las componentes/conexiones, el número de hormigas en la colonia, , y𝑚
los pesos que definen la proporción en la que afectarán la información heurística y
memorística en la regla de transición probabilística.
Varios componentes son o bien opcionales, como las acciones del demonio, o bien
dependientes estrictamente del algoritmo de ACO específico, por ejemplo cuándo y cómo
se deposita la feromona. Generalmente, la actualización en línea paso a paso de los rastros
de feromona y la actualización en línea a posteriori de los rastros de feromona son
mutuamente excluyentes y no suelen estar presentes a la vez ni faltar ambas al mismo
tiempo (si las dos faltan, el demonio suele actualizar los rastros de feromona).
Por otro lado, hay que remarcar que el procedimiento actualiza_memoria_hormiga()
se encarga de especificar el estado inicial desde el que la hormiga comienza su camino y,
además almacenar la componente correspondiente en la memoria de la hormiga L. La
decisión sobre cuál será dicho nodo depende del algoritmo específico (puede ser una
elección aleatoria o una fija para toda la colonia, o una elección aleatoria o fija para cada
hormiga, etc.).
Por último, los procedimientos calcular_probabilidades_de_transición() y
aplicar_política_decisión() tienen en consideración el estado actual de la hormiga, los
valores actuales de la feromona visibles en dicho nodo y las restricciones del problema W
para establecer el proceso de transición probabilístico hacia otros estados válidos. En
cualquier caso, la metaheurística ACO no es lo suficientemente general como para cubrir la
familia completa de algoritmos de hormigas, que pueden definirse como métodos
aproximados para solucionar problemas combinatorios basados en características del
comportamiento genérico de las hormigas naturales.
En la literatura se han propuesto diversos algoritmos que siguen la metaheurística
ACO. Entre los algoritmos de ACO disponibles para problemas de optimización
combinatoria NP-hard, se encuentran el Sistema de Hormigas (SH o Ant System (AS)), el
Sistema de Colonia de Hormigas (SCH o Ant Colony System (ACS)), el Sistema de
Hormigas Max-Min (SHMM, Max-Min Ant System), el SH con ordenación (Rank-Based Ant
System) y el Sistema de la Mejor-Peor Hormiga (SMPH o Best-Worst Ant System). En lo
que sigue, presentaremos una pequeña descripción de algunos de estos algoritmos.
Sistema de Hormigas
El SH [33], fue el primer algoritmo de ACO. Inicialmente se presentaron tres
variantes:
● SH-densidad
● SH-cantidad
● SH-ciclo
En los dos primeros la hormiga depositaban feromonas mientras que construían
soluciones con la diferencia que la cantidad de feromona depositada en el SH-densidad es
constante, mientras que en el SH-cantidad depende directamente de la deseabilidad
heurística de la transición . Por último, en SH-ciclo, la inserción de feromona se lleva a𝑛
𝑟𝑠
cabo una vez que la solución está completa.
Las soluciones en el SH se construyen de la siguiente manera. En cada paso de
construcción, una hormiga escoge ir al siguiente nodo con una probabilidad:𝑘
Si 𝑠 ∈ 𝑁
𝑘
(𝑟)
𝑃
𝑟𝑠
𝑘 =
τ
𝑟𝑠
⎡
⎢
⎣
⎤
⎥
⎦
α. η
𝑟𝑠[ ] β
𝑢∈𝑁
𝑟
𝑘
∑ τ
𝑟𝑠
⎡
⎢
⎣
⎤
⎥
⎦
α. η
𝑟𝑠[ ] β
⎧
⎪
⎨⎪
⎩
⎫
⎪
⎬⎪
⎭
En otro caso
0
Ecuación 2.8
Donde es el vecindario alcanzable por la hormiga cuando se encuentra en el𝑁
𝑘
(𝑟) 𝑘
nodo y son dos parámetros que ponderan la importancia relativa de los rastros𝑟 α, β ∈ 𝑅
de feromona y la información heurística. Cada hormiga almacena la secuencia que ha𝑘
seguido hasta el momento y su memoria , tal como se explicó antes, se utiliza para𝐿
𝑘
determinar en cada paso de construcción.𝑁
𝑘
(𝑟)
Volviendo a los parámetros y , su función es la que sigue: si , aquellosα β α = 0
nodos con una preferencia heurística mejor tienen una mayor probabilidad de ser
escogidos, haciendo el algoritmo muy similar a un algoritmo voraz probabilístico clásico. Sin
embargo, si , solo se tienen en cuenta los rastros de feromonas para guiar el procesoβ = 0
constructivo, lo que puede causar un rápido estancamiento, esto es, una situación en la que
los rastros de feromona asociados a una solución son ligeramente superiores que el resto,
provocando por tanto que las hormigas siempre construyan las mismas soluciones,
normalmente óptimos locales. Por lo tanto hay que ser preciso establecer una adecuada
proporción entre la información heurística y la información de los rastros de feromonas.
Como se mencionó, la disposición de feromona se realiza una vez que todas las
hormigas han acabado de construirsus soluciones. Primero, los rastros de feromona
asociados a cada arco se evaporan reduciendo su valor en un factor constante:
τ
𝑟𝑠
← (1 − ρ) · τ
𝑟𝑠
Ecuación 2.9
Donde es la tasa de evaporación. El siguiente paso de cada hormiga esρ ∈ (0, 1]
recorrer de nuevo el camino ha seguido y deposita una cantidad de feromona en cada∆τ
𝑟𝑠
𝑘
arista por la que ha viajado:
τ
𝑟𝑠
← τ
𝑟𝑠
+ ∆τ
𝑟𝑠
𝑘 , ∨ 𝑎
𝑟𝑠
∈ 𝑆
𝑘
Ecuación 2.10
Donde , es decir, la cantidad de feromona que se deposita depende∆τ
𝑟𝑠
𝑘 = 𝑓(𝐶(𝑆
𝑘
))
de la cantidad de la solución construida para la hormiga .𝐶(𝑆
𝑘
) 𝑆
𝑘
𝑘
Sistema de Colonia de Hormigas
El SCH es uno de los primeros sucesores del SH, el cual introduce tres
modificaciones importantes con respecto a dicho algoritmo de ACO:
1. El SCH usa una regla de transición distinta, denominada regla proporcional
pseudo-aleatoria. Sea una hormiga situada en el nodo un parámetro y un𝑘 𝑟, 𝑞
0
∈ [0, 1] 𝑞
valor aleatorio en [0,1], el siguiente nodo se elige aleatoriamente mediante la siguiente𝑠
distribución de probabilidad:
Si, 𝑞 ≤ 𝑞
0
:
𝑃
𝑟𝑠
𝑘 = 1, 𝑠𝑖 𝑠 = 𝑎𝑟𝑔 𝑚𝑎𝑥
𝑢∈𝑁
𝑘
(𝑟)
{τ
𝑟𝑢
· η
𝑟𝑢
β } ; 0 𝑒𝑛 𝑜𝑡𝑟𝑜 𝑐𝑎𝑠𝑜
⎰
⎱
⎱
⎰
Ecuación 1.11
Si, 𝑞 > 𝑞
0
:
𝑃
𝑟𝑠
𝑘 =
τ
𝑟𝑠
⎡
⎢
⎣
⎤
⎥
⎦
α. η
𝑟𝑠[ ] β
𝑢∈𝑁
𝑟
𝑘
∑ τ
𝑟𝑠
⎡
⎢
⎣
⎤
⎥
⎦
α. η
𝑟𝑠[ ] β
 ; 0 𝑒𝑛 𝑜𝑡𝑟𝑜 𝑐𝑎𝑠𝑜
⎧
⎪
⎨⎪
⎩
⎫
⎪
⎬⎪
⎭
Ecuación 2.12
Como se observa, la regla tiene una doble intención: cuando explota el𝑞 ≤ 𝑞
0
conocimiento disponible, eligiendo la mejor opción con respecto a la información heurística y
los rastros de feromona. Sin embargo, si se aplica una exploración controlada, tal𝑞 > 𝑞
0
como se hacía en el SH. En resumen, la regla establece un compromiso entre la
exploración de nuevas conexiones y la explotación de la información disponible en ese
momento.
2. Sólo el demonio (y no las hormigas individualmente) actualiza la feromona, es decir, se
realiza una actualización de feromona fuera de línea de los rastros. Para llevarla a cabo, el
SCH sólo considera una hormiga concreta, la que generó la mejor solución global.
La actualización de la feromona se hace evaporando primero los rastros de
feromona en todas las conexiones utilizadas por la mejor hormiga global (es importante
recalcar que, en el SCH, la evaporación de feromona sólo se aplica a las conexiones de la
solución, que es también la usada para depositar feromona) tal como sigue:
τ
𝑟𝑠
← (1 − ρ) · τ
𝑟𝑠
, ∀α
𝑟𝑠
∈ 𝑆
𝑚𝑒𝑗𝑜𝑟−𝑔𝑙𝑜𝑏𝑎𝑙
Ecuación 2.13
Luego, el demonio deposita feromonas usando la regla:
τ
𝑟𝑠
← τ
𝑟𝑠
+ ρ · 𝑓(𝐶(𝑆
𝑚𝑒𝑗𝑜𝑟−𝑔𝑙𝑜𝑏𝑎𝑙
)) , ∀α
𝑟𝑠
∈ 𝑆
𝑚𝑒𝑗𝑜𝑟−𝑔𝑙𝑜𝑏𝑎𝑙
Ecuación 2.14
Opcionalmente, el demonio puede aplicar un algoritmo de búsqueda local para
mejorar las soluciones de las hormigas antes de actualizar los rastros de feromona.
3. Las hormigas aplican una actualización en línea paso a paso de los rastros de feromona
que favorece la generación de soluciones distintas a las ya encontradas. Cada vez que una
hormiga viaja por una arista , aplica la regla:𝑎
𝑟𝑠
τ
𝑟𝑠
← (1 − φ) · τ
𝑟𝑠
+ φ · τ
0
Ecuación 2.15
donde es un segundo parámetro de decremento de feromona. Como puedeφ ∈ (0, 1]
verse, la regla de actualización en línea paso a paso incluye tanto la evaporación de
feromona como la deposición de la misma. Ya que la cantidad de feromona depositada es
muy pequeña (de hecho, es el valor del rastro de feromona inicial y se escogiese de talι
0
manera que, en la práctica, se corresponda con el límite menor de rastro de feromona, esto
es, con la elección de las reglas de actualización de feromona del SCH ningún rastro de
feromona puede caer por debajo de ), la aplicación de esta regla hace que los rastros deι
0
feromona entre las conexiones recorridas por las hormigas disminuyan. Así, esto lleva a una
técnica de exploración adicional del SCH ya que las conexiones atravesadas por un gran
número de hormigas son cada vez menos atractivas para el resto de hormigas que las
recorren en la iteración actual, lo que ayuda claramente a que no todas las hormigas sigan
el mismo camino. Este es el algoritmo a utilizar en nuestro desarrollo para complementar
con el modelo Credit Distribution, que fué explicado anteriormente.
Sistema de Hormigas Max-Min
El SHMM [34] es una de las extensiones del SH que mejor rendimiento muestran.
Extiende el SH en los siguientes aspectos:
1. Se aplica una actualización de los rastros de feromona fuera de línea, de manera similar
a como se hace en el SCH. Después de que todas las hormigas hayan construido su
solución cada rastro de feromona sufre una evaporación:
τ
𝑟𝑠
= (1 − ρ) · τ
𝑟𝑠
Ecuación 2.16
y a continuación la feromona se deposita siguiendo la siguiente fórmula:
τ
𝑟𝑠
= τ
𝑟𝑠
+ 𝑓(𝐶(𝑆
𝑚𝑒𝑗𝑜𝑟
)), ∀ 𝑎
𝑟𝑠
 ∈ ∀ 𝑆
𝑚𝑒𝑗𝑜𝑟
Ecuación 2.17
La mejor hormiga a la que se le permite añadir feromona puede ser, la que tiene la
mejor solución de la iteración o la mejor solución global. Los resultados experimentales
demuestran que el mejor rendimiento se obtiene incrementando gradualmente la frecuencia
de escoger la mejor global para la actualización de feromona.
2. Los valores posibles para los rastros de feromona están limitados al rango .[𝑡
𝑚𝑖𝑛
, 𝑡
𝑚𝑎𝑥
]
Por lo tanto, la probabilidad de un estancamiento del algoritmo disminuye al darle a cada
conexión existente una probabilidad, aunque bastante pequeña, de ser escogida. En la
práctica, existen heurísticas para fijar los valores de y . Se puede ver que, a causa𝑡
𝑚𝑖𝑛
𝑡
𝑚𝑎𝑥
de la evaporación de la feromona, el nivel máximo de feromona en los rastros está limitado
a donde es la solución óptima. Basándonos en este resultado, la𝑡
𝑚𝑎𝑥
* = 1/(ρ · 𝐶(𝑆*)) 𝑆*
mejor solución global puede usarse para estimar sustituyendo por en la𝑡
𝑚𝑎𝑥
𝑆* 𝑆
𝑚𝑒𝑗𝑜𝑟−𝑔𝑙𝑜𝑏𝑎𝑙
ecuación de . Para , normalmente sólo es necesario escoger su valor de tal manera𝑡
𝑚𝑎𝑥
* 𝑡
𝑚𝑖𝑛
que sea un factor constante menor que .𝑡
𝑚𝑎𝑥
3. En vez de inicializar los rastros de feromona a una cantidad pequeña, el SHMM los
inicializa a una estimación del máximo permitido para un rastro (la estimación puede
obtenerse generando una solución S´ con una heurística voraz y reemplazando dicha
solución en la ecuación de ). Esto lleva un componente adicional de diversificación en𝑆' 𝑡
𝑚𝑎𝑥
*
el algoritmo, ya que al comienzo las diferencias relativas entre los rastros de feromona no
serán muy acusadas, lo que no ocurre cuando los rastros de feromona se inicializan a un
valor muy pequeño.
Sistema de Hormigas con Ordenación
El Sistema de Hormigas con Ordenación es otra extensión del SH [35] incorpora la
idea de ordenar las hormigas para realizar la actualización de feromona, que el demonio
realiza, de nuevo, fuera de línea, tal como se muestra a continuación:
1. Las m hormigas se ordenan de mejor a peor según la calidad de sus soluciones:
, siendo la mejor solución construida en la iteración actual.(𝑆
1
' ,..., 𝑆
𝑚
' ) 𝑆
1
'
2. El demonio deposita feromona en las conexiones por las que han pasado las σ − 1
mejores hormigas (hormigas elitistas). La cantidad de feromona depositada depende
directamente del orden de la hormiga y de la calidad de su solución.
3. Las conexiones por las que ha pasado la mejor hormiga global reciben una cantidad
adicional de feromona que depende únicamente de la calidad de dicha solución. Esta
deposición de feromona se considera la más importante, de hecho, recibe un peso de .σ
Esta metodología de operación tiene efecto al utilizar la siguiente regla de
actualización de feromona, la cual se aplica a cada arista una vez que todos los rastros de
feromona han sido evaporados:
τ
𝑟𝑠
← τ
𝑟𝑠
+ σ · ∆τ
𝑟𝑠
𝑚𝑔 + ∆τ
𝑟𝑠
𝑜𝑟𝑑𝑒𝑛
Ecuación 2.18
donde,
Si 𝑎
𝑟𝑠
∈ 𝑆
𝑚𝑒𝑗𝑜𝑟−𝑔𝑙𝑜𝑏𝑎𝑙
∆τ
𝑟𝑠
𝑚𝑔 = 𝑓(𝐶(𝑆
𝑚𝑒𝑗𝑜𝑟−𝑔𝑙𝑜𝑏𝑎𝑙
))
En otro caso
0
Ecuación 2.19
Si 𝑎
𝑟𝑠
∈ 𝑆
µ
'
∆τ
𝑟𝑠
𝑜𝑟𝑑𝑒𝑛 =
µ=1
σ−1
∑ (σ − µ) ·𝑓(𝐶(𝑆
µ
' ))
Ecuación 2.20
En otro caso
0
Herramientas similares
En este capítulo se mostrarán varias herramientas relacionadas con nuestro enfoque
propuesto, similitudes, diferencias y un breve análisis.
Klout
Klout [22] era una de las herramientas más populares, que medía la influencia social
de una persona a través de las redes sociales. Esta influencia se veía reflejada en un
puntaje, basado en diversos factores medidos por esta aplicación. Para conocer este
puntaje, el sitio web de Klout permitía crear un perfil para cada uno de sus usuarios. En este
perfil era posible ver este puntaje y conocer cómo evolucionaba día a día. Además era
posible ver otro tipo de estadísticas, muchas de las cuales son útiles para quienes usan las
redes sociales con fines comerciales o comunicacionales.
Entre las principales y más populares redes sociales donde se desenvolvía Klout
eran Twitter, Facebook, Google+, LinkedIn, Instagram, YouTube, Tumblr, Last.fm, Flickr,
Blogger y Wordpress.
Klout analizaba a diario más de 400 ítems de diferentes redes sociales para
actualizar la puntuación de cada cuenta. La mayoría de estas señales sociales son la
proporción de reacciones que genera la persona en comparación con la cantidad de
contenido que comparte. Hay en tres apartados fundamentales:
Alcance: Número de personas a las que llega el usuario con su contenido u opinión. Aquí
se incluyen a los seguidores, amigos, gente que comparte grupos, amigos de los amigos.
Amplificación: Mide el grado en el que los contenidos son compartidos por otros usuarios.
Publicar muchas veces y obtener cero respuestas no es ser influyente, pero publicar una
vez y conseguir mil respuestas o compartidos si puntúa mucho en Klout.
Red: Klout analiza también el tipo de personas que siguen al usuario y su influencia en las
redes. Tener o interactuar con seguidores influyentes es un signo positivo.
Klout era una herramienta excelente y de gran ayuda para determinar qué tan
influyente es una persona en las redes sociales, de hecho en EEUU llegó a ser un
parámetro a la hora de obtener un empleo. Pero un detalle no menor, es que Klout medía
las interacciones de distintos usuarios sobre nuestras acciones en las redes, pero lo que no
medía es la propagación de ese accionar nuestro y de la influencia que provocaba en las
redes. Esto último puede deberse no solo al algoritmo proporcionado en sí, si no al
comportamiento de las redes y su comportamiento. Klout, dejó de existir en 2018 y fue una
característica faltante para ser no sólo la más popular sino la más completa.
Kred
Similar a Klout, en el sentido en que genera un puntaje, Kred [23] presume de una
total transparencia en la forma en que se otorgan puntos y es el único servicio de medición
de influencia que publica abiertamente su algoritmo.
Kred proporciona dos mediciones:
● Influence (Influencia): la habilidad de inspirar acciones de otros, es decir, mide el
hecho de que alguien reaccione a tus posts y se basa en una escala de 1 a 1000. En
Twitter mide la frecuencia en la que eres retuiteado, la frecuencia en la que te
contestan y te mencionan y que recibes nuevos seguidores, mientras que en
Facebook obtienes puntos cuando tus contactos interactúan con tus posts en tu
muro o con tus posts en los muros de otros (a condición de que también tengan
registrado su Facebook en Kred). En el caso de Facebook las interacciones que
cuentan son los posts, las menciones, los likes, las veces que alguien comparte tu
contenido y las invitaciones a eventos.
● Outreach (Alcance): la tendencia que tienes a compartir lo que recibes de otros,
esta medida puede crecer pero nunca baja. ¿La razón? Ellos creen que la capacidad
de tu generosidad es infinita y así esperan que siempre siga creciendo. En junio de
2012 el mayor nivel alcanzado fue de 12. Midiendo Twitter, obtienes 10 puntos cada
vez que haces acciones para otros, como responderles, mencionarlos o retuitear su
contenido, mientras que el hecho de empezar a seguir a alguien cuenta como un
punto. En Facebook, las acciones por las que Kred otorga puntos son menciones a
la persona, comentar un post y hacer likes a posts o comentarios.
Además del Kred Global, que es el puntaje total, podremos obtener puntajes
relativos en función de las comunidades en las que Kred considera que somos influyentes.
Por ejemplo, podemos tener un Kred Global alto pero en determinado grupo de interés el
Kred no puede ser el mismo, dependiendo de la autoridad en el tema que tengamos. Otras
formas de ganar puntos es cuando otros usuarios te los otorgan directamente (+Kred),
porque consideran que eres una referencia en determinado tema. Si das un +Kred, el
usuario recibe 70 puntos y tú 30 como forma de agradecimiento a tu acción.
Se puede observar como Kred es el claro sucesor de Klout, mejora sobre todo en su
visión sobre la propagación de la influencia al considerar quienes son los que responden un
tweet, lo comparten o quien te citan si son o no amigos por ejemplo. Pero una desventaja es
lo dicho en el párrafo anterior. Se pueden donar puntos de influencia, además de que se
suman puntos si interactúas en la red, algo que podría hacer un influencer pero no
necesariamente significa que eres uno de ellos. Así mismo el parámetro de medición del
alcance, no es 100% significativo para determinar la influencia, aún así, son puntajes que se
suman.
Twitanalyzer
Twitalyzer [24] es otra herramienta para conocer la influencia ejercida sobre Twitter.
Nos proporciona un número entre 0 y 100, para medir la influencia general que tenemos a lo
largo de los últimos 30 días. Además nos ofrece los resultados de las puntuaciones de Klout
y Peenrindex [25], con lo que podemos comparar los resultados de las 3 herramientas. Esta
influencia se puede medir por diferentes indicadores: número de followers y followings,
número de RTs, número de clics en los tweets con enlace, etc. Independientemente de
estos indicadores podemos sacar en un solo número toda la influencia de un usuario
haciéndonos una idea general. Otras métricas que proporciona Twitalyzer son:
Engagement: Proporciona una medida de la relación entre las personas
referenciadas por el usuario y el número de personas que le han referenciado a él.
Velocity: Es una indicación de la frecuencia relativa con la que el usuario publica
actualizaciones en Twitter.
Influence: Indica la probabilidad de que se retuitee o se referencie algo escrito por el
usuario.
Signal: Ratio de tweets que contienen enlaces (http://), menciones, hashtag o algún
indicio de que el tweet hace referencia a un tweet previo de otro usuario.
Impact : Finalmente el impacto, en el que se tienen en cuenta una combinación de
los siguientes factores:
● Número de seguidores de un usuario.
● Número de referencias únicas y menciones del usuario en Twitter.
● Frecuencia con la que el usuario es retuiteado de manera única.
● Frecuencia con la que el usuario hace retweets a otras personas de manera
única.
● Frecuencia relativa con la que el usuario publica actualizaciones.
Al igual que las anteriores herramientas mencionadas, esta sobresale al hacer una
comparativa con otras herramientas, salvando este detalle mencionado las herramientas
son similares entre sí, implementan métricas similares. Una métrica interesante es
“engagement”, la cual hace referencia al seguimiento entre las personas en sí, no es lo
mismo alguien que interactúe con vos siendo un “amigo” a un desconocido. Algunas con
mejoras sobre otras pero todas recaen en una aparente influencia, como por ejemplo el
mero hecho de seguir mucha gente, o de realizar muchas acciones no necesariamente
recae en ser un influencer. Nosotros nos centraremos en las acciones y cómo estas influyen
y se propagan a través del tiempo y de los usuarios dentro de una misma red social.
Capítulo III
Propuesta
Con la popularidad de las redes sociales, como Twitter, Facebook, Instagram,
incluso YouTube, surgen los conocidos influencers. Pero, ¿Quiénes son? ¿Qué determina
quienes son influencers? Según Endor en su artículo