El análisis de redes sociales mediante la teoría de grafos

El incremento en el uso de las redes sociales (Facebook, twitter, Instagram, etc.) en todos los ámbitos de la sociedad, así como la importancia que éstas tienen en la creación y distribución de información entre personas, conlleva hacer un análisis de las mismas en un entorno de Big Data y Business Intelligence con el fin de obtener información relevante para las empresas, como por ejemplo la Teoría de Grafos.

En un sentido básico, una red social se basa en establecer relaciones entre personas, que a su vez establecen relaciones entre ellas, creando un grafo de personas unidas por amistad, similar al que podemos apreciar a continuación.

En la imagen anterior cada punto (nodo) representa a una persona y cada línea (arista) establece la relación de amistad entre dos nodos. Vista esta representación de las relaciones dentro de una red social no es de extrañar que a través de la teoría de grafos se estudien los patrones seguidos, con la finalidad de incrementar la inteligencia de negocio.

¿Pero qué es esto de la teoría de grafos?

Un grafo, es una estructura matemática que permite modelar problemas de la vida cotidiana, mediante, como hemos visto, una representación gráfica formada por nodos o vértices que muestra a los actores y aristas que sirven para representar los lazos o relaciones entre los actores. Así mismo, un grafo puede representar un único tipo de relación entre los actores (simple), o más de un tipo de relación (múltiple), además cada vínculo o relación puede ser orientado.

En mayo de 2007, Mark Zuckerberg, fundador y CEO de Facebook, definió como social graph al grafo de todas las conexiones y relaciones que los usuarios de la red social han establecido y lo que cuentan de cada uno de nosotros.

La teoría de grafos es por tanto una rama de las matemáticas, muy usadas en ciencias de la computación, que estudia las propiedades de los grafos. Tiene sus fundamentes en las matemáticas discretas y las matemáticas aplicadas, y requiere por tanto englobar conceptos de diversas áreas como combinatoria, álgebra, probabilidad, geometría, aritmética, etc.

¿Por qué resulta interesante aplicar la teoría de grafos a las redes sociales?

Imaginemos por ejemplo la estrategia comercial de cualquier empresa de telecomunicaciones a la que le interesa conocer la composición de los vínculos cercanos, para conocer con quien hablamos habitualmente y así poder adaptar la estrategia comercial, ofreciendo ofertas o tarifas personalizadas.

Además, entender los grafos de las redes sociales, puede servir para mejorar los sistemas actuales y diseñar nuevas aplicaciones.

Para estudiar los grafos de redes sociales, es de uso común los algoritmos para detección de comunidades. Estos algoritmos se basan en la idea de que los nodos contenidos dentro de una misma comunidad comparten atributos, características comunes o relaciones fundamentales. Entendiendo como comunidad, aquel subgrafo en el que los vértices deben estar más relacionados entre sí que con el resto de los vértices de la red.

Así en el grafo anterior, se detectan 3 comunidades diferenciadas, en donde presuponemos que los nodos de cada una de ella tienen alguna característica o atributo en común.

Métodos para la detección de comunidades

Dentro de la teoría de grafos tenemos diferentes métodos para el análisis y detección de comunidades, los podemos agrupar en:

• Métodos Jerárquicos: Buscan los divisiones naturales en la red, basándose en la idea de que el grafo tiene una estructura jerárquica. Uno de los principales algoritmos dentro de este tipo de métodos es el de Girvan-Newman.
• Métodos modulares: Se centran en intentar encontrar la partición que maximice la modularidad (métrica que compara los enlaces internos de una comunidad frente a los enlaces que conectan la comunidad con el resto de la red).

La aplicación práctica de estos métodos y el análisis de redes sociales, lo podrá llevar a cabo el Data Scientist mediante el uso de paquetes de R como es igraph, que nos permitirá por ejemplo, calcular el coeficiente de agrupamiento, el camino mínimo entre nodos o la distribución del grafo de nodos.