La submodularidad en la red


Grafo

Después de ser invitado por mi amigo y colega Javier Melero a participar en este blog en lo relativo a redes y medios sociales, me di cuenta de que lo que realmente estaba haciendo era iniciando una conversación. Cierto, he sido influenciado para iniciar una conversación en otro sentido. Tal vez por eso siempre que presentamos nuestra compañía mencionamos nuestra obstinada y casi surrealista vocación por las conversaciones, sus contextos, los agentes involucrados, etc., y es ahí donde surge algo que venimos haciendo de natural desde hace mucho tiempo.

He estado desarrollando diferentes proyectos basados en el ecosistema social, pero curiosamente me he deslizado inicialmente por el lado de las redes, de las propiedades matemáticas de las redes, del concepto de red y de sus algoritmos para posteriormente dedicarme también a sus vertientes sociales. Este es, sin duda, el punto de partida inicial para conocer y explicar la bondad de los medios sociales: están primero en red para luego ser sociales.

Dibujando la Red

Supongamos que nuestra red social está formada por nodos, que representan personas, miembros y por enlaces, donde un enlace entre dos nodos existe cuando hay un vínculo social entre dichos

nodos. De manera simple pero no por ello trivial, sería sencillo dibujar, por ejemplo, nuestra red

de amigos; podríamos también, con su ayuda, dibujar la red de nuestros amigos y así, de manera iterativa, podríamos dibujar la red de nuestras relaciones hasta su máximo detalle. Las redes constituyen nuestra segunda piel. Han estado siempre alrededor nuestro de diferentes maneras: están las proteínas de la sangre, en nuestras neuronas, en nuestro día a día en la oficina, en el mail, etc.

Por esto es tan importante entenderlas, pues de sus propiedades podríamos obtener un gran avance de cara a comprender la difusión de información en Internet, la evolución de las conversaciones, la evolución de las innovaciones y un gran número de otras circunstancias.

Escoger como base de argumentación un método matemático en una ciencia tan novedosa y actual como son los medios y redes sociales nos ha demostrado en la práctica ser el mejor compañero de viaje. Pero esto también nos ha llevado a necesitar de otras disciplinas de la ciencia, como los sistemas adaptativos complejos y la teoría de juegos, así como de las ciencias sociales a la hora de interpretar comportamientos, contextos y situaciones más próximas a la investigación, siempre con carácter netnográfico.

No podría elegir un ejemplo en el que la aplicación de todas estas herramientas me demostrasen la necesidad de todas ellas, pero creo que os ilustraré con un ejemplo (un problema) sobre uno de nuestros clientes.

Un caso práctico resuelto

Como no podía ser de otra forma, nuestro cliente necesitaba conocer, al menos, todo lo que se decía de él. En sentido amplio, buscaba conocer qué decían los consumidores, qué se decía de sus consejeros, qué de su responsabilidad social corporativa… para posteriormente tomar determinadas acciones.

Debíamos estar atentos a toda la información actual y pasada de la compañía, a todos los rumores, comentarios y evoluciones en la mente del consumidor.

Desde el punto de vista formal, el problema atendía a lo que se conoce como búsqueda de brotes de información, es decir, la determinación temprana de los comentarios. Para ello, a priori, habría que leer todos los blogs, los foros, las redes sociales donde existieran referencias a nuestro cliente. Este problema de outbreak detection es muy semejante al de determinar, en una red de suministro eléctrico, dónde colocar sensores que nos anticipen una sobretensión que pueda ser terrorífica para la subsistencia del suministro o también, al de la temprana alerta de contaminación terrorista por envenenamiento de la red de suministro de agua potable de una gran ciudad.

Si traducimos esta problemática al mundo de los medios sociales debíamos de determinar aquellos foros, blogs, etc. que hablasen de nuestro cliente de manera más actualizada; es decir, debíamos de leer aquellos comentarios y conversaciones más actuales, aquéllos que reflejan la mayoría de las conversaciones. Habíamos convertido el problema en una solución basada en la determinación de la mayor información actualizada de nuestros clientes.

Los blogueros publican posts y otros links referidos a comentarios y posts de otros blogueros. Cada post está perfectamente determinado con una marca horaria, con lo que podríamos observar la propagación de la información en la blogosfera. En este  entorno debíamos de seleccionar el conjunto de blogs que debíamos de leer (y de recuperar) que son más actuales, o lo que es lo mismo, capturar la mayoría de las conversaciones  que circulan por Internet relativos a nuestro cliente.

Curiosamente, las conversaciones en Internet se propagan formando diferentes cascadas. En cada avance de la conversación, esta llega a un blog diferente. Se trataba por tanto de examinar y leer los blogs que tienen mayor numero de conversaciones relativas a nuestro cliente. Pero, ¿cómo seleccionar estos blogs? Una vez más, aparece una propiedad matemática para ayudarnos en esto: la submodularidad.

Y por fin, la submodularidad

Sin entrar en demasiados detalles, la submodularidad es una propiedad que se observa en los grafos (y por ende, en las redes de cualquier tipo) por la que determinadas propiedades que se observan a pequeña escala nos garantizan que se observarán en toda la red. Es una manera muy elegante de obtener resultados sobre toda la red sin necesidad de examinarla en su totalidad, pero que permite afirmar propiedades de carácter general. Dicho en un lenguaje más próximo: propiedades de carácter local pueden extenderse a propiedades de propósito general.

Volviendo al problema sería coherente pensar que deberíamos de elegir la lectura y el examen de los blogs y foros más grandes para resolver eficazmente el problema de nuestro cliente. Pero debido a la submodularidad, es mucho más eficiente y efectivo leer los pequeños blogs y foros que citan a nuestro cliente. Nos ha pasado muchas veces que después de leer un blog grande al respecto de una noticia, pasamos a leer otro blog y el incremento de la información aportada es nulo: prácticamente lo que leímos en el primero esta tambien en el segundo. Además, como es un blog grande, tendrá muchos enlaces y mucha publicidad, con lo que será “costoso” de leer.

Apoyándonos en la submodularidad, comenzamos por leer pequeños blogs y foros, de manera paralela. La lectura fue muy eficiente y a cada paso, fuimos incrementando considerablemente el flujo de conversaciones de nuestro cliente sin recurrir a los foros grandes.

Finalmente, esta es solo una aplicación matemática al mundo de las redes sociales, de la difusión y de la influencia. Vendrán más comentarios a este respecto, pero no debemos de olvidarnos que las redes, dentro y fuera de nosotros, han llegado hace mucho para quedarse.

Por Enrique Hortalá.

6 comments

  1. Siempre se presupone la bondad en los medios sociales?.Curiosa teoría,la submodularidad, se podría aplicar a cualquier ámbito?. Cómo se conjugan la submodularidad y las conversaciones?
    Gracias.

  2. En 2008, la revista TIME le preguntó: “¿Cuantos blogs serían necesarios para cubrir las necesidades del mundo? “, alegando que ya había demasiados y su número solamente iba a incrementarse de manera exponencial.
    La blogosfera ha crecido a gran velocidad, con decenas de millones de bitácoras activas generadoras de cientos de millones de intercambios, de mensajes y envíos al año. Esta actividad conduce a una gran sobrecarga de información. Por ello, esto nos ha conducido a buscar algoritmos para optimizar la detección de nuevos brotes de información, de nuevos mensajes, de nuevas conversaciones. Si sólo tiene 10 minutos al día para gastar en la blogosfera, ¿cuáles son los blogs que deben ser leídos para hacer un seguimiento correcto de las conversaciones, de las tendencias, de las innovaciones, de la influencia? Para entender la forma de abordar esta cuestión hemos de tener en cuanta de manera cuidadosa, cómo la información se propaga a través de la blogosfera.
    En una cascada de propagación, un artículo publicado en algún blog se pueden rescatar (y vincular) a otros blogs, y desde allí, éstos pueden estar relacionados con más blogs, y así sucesivamente. Esta difusión de información en los foros de la blogosfera es lo que llamamos una cascada de información. Un buen blog es el que capta grandes historias (es decir, genera grandes cascadas) de manera temprana y con liderazgo (es decir, lo más cercanamente posible a la fuente inicial, la que genera la “novedad”).
    Al principio, el problema de la captura de las cascadas de la información, de la submodularidad, de los problemas de suministro eléctrico, parece muy diferente de las otras tareas que hemos discutido hasta el momento. En realidad, sin embargo, la propagación de contaminantes a través de sistemas de distribución de agua es muy similar a la propagación de información a través de la blogosfera. Y, lo más importante es que todas estas tareas pueden ser formuladas como un problema de optimización submodular que pueden ser abordados por los algoritmos que se han descrito hasta ahora.
    Los posts son ricos en metadata, incluyendo timestamps, que nos permite extraer las cascadas de información, es decir, los subgrafos inducidos pueden ser reconocidos, creándose un flujo temporal que se corresponde perfectamente con el flujo habitual de una conversación entre dos personas. Aquí, sin embargo, estamos “participando” de múltiples y diversas conversaciones al tiempo, como si estuviéramos en el patio de un colegio hablando con todos los alumnos en el recreo. La posterior clasificación de los temas, de los tópicos y de los agentes de la conversación nos permite agrupar las conversaciones, monitorizarlas e incluso, participar en ella.
    Piensa ahora, Gabriela, en la puesta en marcha de una campaña online de una gran marca a nivel mundial. ¿Cuántas opiniones generara? ¿Cuántas por minuto? Bien, todas ellas han quedado recogidas. Al final, cada cascada de conversaciones tiene un punto de partida único y otros muchos más puestos de forma recursiva al unirse y vincularse los puntos dentro de la cascada, por lo que los vínculos obedecen a una perfecta ordenación en el tiempo.
    En el ejemplo que os mencione, detectamos cascadas en primer lugar (la identificación de partida) y luego su puesto en los siguientes enlaces. Descubrimos 346.209 cascadas no triviales con al menos dos nodos. El conjunto de datos final fue de 17.589 cascadas donde cada uno de los blogs participaba en diferentes cascadas en un número de 9,4 en promedio.
    Como fácilmente entenderás, disponer de un algoritmo capaz de todo esto con la seguridad de que lo que sucede a nivel a nivel submodular puede extenderse a todo la red extendida, nos asegura de que el camino para entender las redes y todo lo que en red esta, pasa sin duda por poder extrapolar lo que es calculable y suficiente y no pensar más en necesitar navegar todo el grafo para tener un resultado concluyente.
    Sobre la certeza de las opiniones y conversaciones alrededor de un tema hablaremos próximamente. Por favor, mantén abierta la conversación.

  3. Estás de acuerdo Enrique con el algoritmo Cascades? y que un sensor a una red pequeña tiene mucha más repercusión que añadir un sensor a una macro red?.
    Siempre se presupone la bondad en los medios sociales?

  4. Excelente. Acabamos de elevar el listón para situarnos al nivel de mi maestro y amigo Jure Leskovec.
    Sin duda alguna, el algoritmo Cascades tuvo una gran repercusión en su momento (aquello partió de una competición patrocinada entre la comunidad científica americana para encontrar puntos vulnerables a un posible atentado terrorista en una red de suministro). Por aquel entonces, Carnegie Mellon dio con la solución en un equipo de trabajo donde el de menor edad era Jure. Ahora está enseñado en Stanford y te diré que merece mucho la pena seguir sus trabajos (su tesis doctoral esta en videolectures).
    La solución que Jure y sus colegas dieron iba más allá del algoritmo. Su portentoso avance fue el poder determinar la computabilidad del mismo. Su excelente y elegante manera de navegar a través de las cascadas de mensajes les permitió al tiempo poder ir agregándolas. Puedes leer su brillante exposición en la tesis doctoral de Jure. Puedes pedírmela si no la tienes.
    Para mí, y habiendo vivido el espíritu universitario americano, ha sido más la fusión ordenada de todos los conocimientos involucrados, desde sociología, matemáticas, computación para disponer de un amplio campo de trabajo sobre el que pensar la siguiente iteración. Ayuda mucho, incluso entre clientes y prospectos conocer que las teorías que manejamos tienen un garante académico. Ya no es más el consultor que con un conejo y una chistera ofrece su última opinión. Esto es primera división y creo que sabes bien de qué te hablo.
    Te diré que Duncan J. Watts, con su trabajo previo a Cascades sobre difusión y evolución en cascadas de la información y de las innovaciones fue uno de los más beneficiados por el descubrimiento del algoritmo. Sus trabajos en sociología habían requerido de esta modelo computable para significar lo que significan hoy. Casi todo lo que hacemos escuchando redes de carácter general es encontrar cascadas y clasificarlas: los mensajes son parte de ellas.
    Más aún, partiendo de Watts, los mecanismos de influencia en redes sociales se desarrollaron de manera vertiginosa. En breve hablaremos de ello. Hay un trabajo reciente muy interesante de Papagelis, Bansal, y Koudas al respecto de lo último en la blogosfera sobre cascadas.
    Creo que ha quedado demostrado mi convencimiento y devoción por estos magos de la excelencia y el trabajo bien hecho.

    1. Francamente te agradecería que me enviaras la tesis doctoral de Jure.
      Qué opinas del término “milenario Guanxi”, término que puede ser utilizado para describir una red de contactos a los que un individuo puede recurrir cuando precisa realizar o poner en práctica algo, y mediante el cual él puede ejercer influencia en beneficio de un tercero.
      Significa esto que estamos trabajando sobre algo que lejos de parecer una innovación es simplemente una ampliación de conceptos milenarios?.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s