En numerosas redes sociales, determinar la relación existente entre los usuarios no es un problema sencillo, especialmente cuando se habla de redes grandes. Por eso, es necesario realizar ciertas simplificaciones que permitan resolver el problema de forma analítica.
Una de esas técnicas es el análsis espectral, muy empleada para la detección de comunidades en distintos ámbitos, pero que tiene una limitación importante: requiere que las relaciones entre los miembros de la comunidas sean siempre positivas. Este cálculo es la base de, por ejemplo, el algoritmo de PageRank de Google.
Por este motivo, muchos de los servicios que se basan en la detección de grupos de usuarios con características similares y trabajan con comunidades de millones de usuarios emplean estas mismas técnicas. Por ejemplo, Facebook solo permite etiquetar los comentarios de forma positiva o el reciente botón de Google de +1 tiene el mismo efecto en una página web: incrementar la utlidad relativa de ese enlace para un usuario. Otros servicios se basan en el mismo mecanismo, aunque no sea tan evidente. Por ejemplo, los servicios de geolocalización, donde al hacer check-in en determinadas localizaciones estamos valorándolas positivamente. Aunque en este caso no es un norma y dependerá de las connotaciones del comentario asociado.
Sin embargo hay muchos otros servicios en los que existen valoraciones positivas y negativas: como en eBay (tras el proceso de compra), Amazon e iTunes (donde un número bajo de estrellas indica opinión baja), Menéame y Diggit (con la votación/valoración de karma de los usuarios). En general, la mayoría de los servicios basados en recomendación o en mecanismos de reputación. Otro problema al que se puede aplicar es la detección de vandalismos en la wikipedia y, con un componente adicional que sea capaz de extraer la semántica de los mensajes, a redes en Twitter o comentarios en blogs.
Desde el punto de vista matemático, a este tipo de problemas se les conoce como problemas de coherencia, donde hay una red donde los enlaces están valorados entre -1 y 1 y el objetivo es encontrar una partición óptima en dos grupos coherentes, de forma que todos los miembros de un grupo estén relacionados entre sí de forma positiva y a la vez estén relacionados con el otro grupo de forma negativa.
En general, este tipo de problemas es muy costoso de resolver y hace que sea impracticable conseguir la solución óptima y sea necesario contentarse con aproximaciones. La mayoría de ellas están basadas en sistemas de satisfacción de restriciones o incluso en redes neuronales. Pero siguen siendo demasiado costosas, por lo que no resultan útiles en redes grandes. En términos de ciencas de la computación, se habla de soluciones problemas exponenciales, como puedes ser el ajedrez.
Sin embargo, existe un método que permitiría identificar las comunidades existentes. incluso incluyendo relaciones negativas, con un coste razonable (polinómico): las redes de consenso. En ellas, la red de usuarios trata de ponerse de acuerdo en un valor que indicará a qué grupo pertenece. La separación en comunidades se consigue por el sigo de ese valor, de forma que todos los usuarios que tengan un coste positivo pertenecen a un grupo y los que tengan un valor negativo al otro. El objetivo de esta comunicación es explicar el funcionamiento de este método y de cómo permite la clasificación de los usuarios en grupos, incluso para comunidades grandes.
