Teoría de Grafos para análisis de redes sociales

Las redes sociales son, fundamentalmente, grafos: nodos (usuarios) conectados por aristas (relaciones). La teoría de grafos proporciona herramientas matemáticas poderosas para entender estructura, identificar influencers, detectar comunidades y predecir comportamientos virales. En este artículo profundo, exploraremos desde fundamentos teóricos hasta implementaciones prácticas con Python y NetworkX.

Fundamentos de Teoría de Grafos

¿Qué es un Grafo?

Un grafo G = (V, E) es una estructura matemática compuesta por:

• V (Vértices/Nodos): Conjunto de entidades (usuarios, páginas, posts)
• E (Aristas/Edges): Conjunto de relaciones entre entidades (follows, likes, shares)

Ejemplo conceptual:

Twitter Network:
V = {Usuario1, Usuario2, Usuario3, Usuario4}
E = {(Usuario1 → Usuario2), (Usuario1 → Usuario3), (Usuario2 → Usuario4)}

Tipos de Grafos

1. Grafos Dirigidos vs. No Dirigidos

Grafo Dirigido (Directed Graph / Digraph):

• Las relaciones tienen dirección
• A → B no implica B → A

Ejemplos:

• Twitter follows (yo sigo a alguien ≠ me sigue)
• Instagram follows
• Citas entre papers académicos

Grafo No Dirigido (Undirected Graph):

• Las relaciones son simétricas
• A — B implica B — A

Ejemplos:

• Facebook friends (amistad es mutua)
• LinkedIn connections (hasta 2019)
• Coautoría en papers

2. Grafos Ponderados vs. No Ponderados

Grafo Ponderado (Weighted Graph):

• Cada arista tiene un peso/valor
• Representa intensidad de relación

Ejemplos:

• Número de interacciones entre usuarios
• Frecuencia de comunicación
• Similitud entre perfiles

import networkx as nx
import matplotlib.pyplot as plt

# Crear grafo ponderado
G_weighted = nx.Graph()
G_weighted.add_edge('A', 'B', weight=5)  # 5 interacciones
G_weighted.add_edge('A', 'C', weight=2)  # 2 interacciones
G_weighted.add_edge('B', 'C', weight=8)  # 8 interacciones

# Visualizar
pos = nx.spring_layout(G_weighted)
labels = nx.get_edge_attributes(G_weighted, 'weight')

nx.draw(G_weighted, pos, with_labels=True, node_color='lightblue',
        node_size=1000, font_size=16, font_weight='bold')
nx.draw_networkx_edge_labels(G_weighted, pos, edge_labels=labels)
plt.title("Grafo Ponderado: Interacciones entre Usuarios")
plt.axis('off')
plt.savefig('grafo_ponderado.png', dpi=300, bbox_inches='tight')
plt.close()

3. Grafos Bipartitos

Definición: Nodos pueden dividirse en dos conjuntos disjuntos, aristas solo conectan nodos de conjuntos diferentes.

Ejemplos:

• Usuarios ←→ Productos (reseñas, compras)
• Usuarios ←→ Hashtags
• Actores ←→ Películas

# Crear grafo bipartito
B = nx.Graph()

# Conjunto 1: Usuarios
usuarios = ['User1', 'User2', 'User3']
# Conjunto 2: Hashtags
hashtags = ['#marketing', '#data', '#ai']

# Agregar nodos con atributo bipartite
B.add_nodes_from(usuarios, bipartite=0)
B.add_nodes_from(hashtags, bipartite=1)

# Agregar relaciones (usuarios usan hashtags)
B.add_edges_from([
    ('User1', '#marketing'),
    ('User1', '#data'),
    ('User2', '#data'),
    ('User2', '#ai'),
    ('User3', '#marketing'),
    ('User3', '#ai')
])

# Verificar si es bipartito
print(f"Es bipartito: {nx.is_bipartite(B)}")

# Proyectar a red de usuarios (conectados si comparten hashtags)
usuarios_nodes = {n for n, d in B.nodes(data=True) if d['bipartite'] == 0}
G_usuarios = nx.bipartite.projected_graph(B, usuarios_nodes)

print(f"Conexiones en red de usuarios: {G_usuarios.edges()}")
# User1 y User2 conectados (comparten #data)
# User1 y User3 conectados (comparten #marketing)
# User2 y User3 conectados (comparten #ai)

Representaciones de Grafos

Matriz de Adyacencia

Definición: Matriz A donde A[i][j] = 1 si existe arista entre nodo i y j.

import numpy as np

# Crear matriz de adyacencia
nodos = ['A', 'B', 'C', 'D']
n = len(nodos)

# Matriz de adyacencia (no dirigida)
A = np.array([
    [0, 1, 1, 0],  # A conectado a B y C
    [1, 0, 1, 1],  # B conectado a A, C y D
    [1, 1, 0, 1],  # C conectado a A, B y D
    [0, 1, 1, 0]   # D conectado a B y C
])

print("Matriz de Adyacencia:")
print(pd.DataFrame(A, index=nodos, columns=nodos))

# Crear grafo desde matriz
G = nx.from_numpy_array(A)
mapping = {i: nodo for i, nodo in enumerate(nodos)}
G = nx.relabel_nodes(G, mapping)

# Obtener matriz de adyacencia desde grafo
A_from_graph = nx.adjacency_matrix(G).todense()
print("\nMatriz recuperada desde grafo:")
print(A_from_graph)

Ventajas:

• Verificación rápida de existencia de arista: O(1)
• Eficiente para grafos densos
• Operaciones matriciales (multiplicación para caminos)

Desventajas:

• Uso de memoria: O(n²)
• Ineficiente para grafos sparse (mayoría de redes sociales)

Lista de Adyacencia

Definición: Para cada nodo, lista de nodos adyacentes.

# Representación con diccionario
adj_list = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D'],
    'D': ['B', 'C']
}

# Crear grafo desde lista de adyacencia
G = nx.from_dict_of_lists(adj_list)

# Obtener vecinos de un nodo
vecinos_B = list(G.neighbors('B'))
print(f"Vecinos de B: {vecinos_B}")

# Iterar sobre todas las aristas
for nodo, vecinos in adj_list.items():
    for vecino in vecinos:
        print(f"{nodo} -- {vecino}")

Ventajas:

• Eficiente en espacio: O(n + m) donde m = número de aristas
• Ideal para grafos sparse
• Iteración rápida sobre vecinos

Desventajas:

• Verificar existencia de arista: O(grado del nodo)

Práctica en Redes Sociales: Usa listas de adyacencia. Las redes sociales son extremadamente sparse (un usuario promedio sigue a cientos, no millones).

NetworkX: Análisis de Grafos en Python

Instalación y Setup

pip install networkx matplotlib scipy scikit-learn pandas

Creación de Grafos

import networkx as nx
import matplotlib.pyplot as plt
import pandas as pd

# 1. Crear grafo vacío
G = nx.Graph()  # No dirigido
D = nx.DiGraph()  # Dirigido
M = nx.MultiGraph()  # Múltiples aristas entre nodos

# 2. Agregar nodos
G.add_node('Alice')
G.add_nodes_from(['Bob', 'Charlie', 'Diana'])

# Agregar nodos con atributos
G.add_node('Eve', role='influencer', followers=100000)

# 3. Agregar aristas
G.add_edge('Alice', 'Bob')
G.add_edges_from([
    ('Alice', 'Charlie'),
    ('Bob', 'Diana'),
    ('Charlie', 'Diana')
])

# Agregar aristas con atributos
G.add_edge('Bob', 'Charlie', weight=5, interaction_type='comment')

# 4. Información básica
print(f"Número de nodos: {G.number_of_nodes()}")
print(f"Número de aristas: {G.number_of_edges()}")
print(f"Nodos: {list(G.nodes())}")
print(f"Aristas: {list(G.edges())}")

# 5. Crear desde datos reales
# Dataset de ejemplo: interacciones en Twitter
data = pd.DataFrame({
    'source': ['Alice', 'Alice', 'Bob', 'Charlie', 'Diana'],
    'target': ['Bob', 'Charlie', 'Diana', 'Diana', 'Alice'],
    'interaction': ['retweet', 'reply', 'mention', 'retweet', 'reply']
})

# Crear grafo dirigido
D = nx.from_pandas_edgelist(
    data,
    source='source',
    target='target',
    edge_attr='interaction',
    create_using=nx.DiGraph()
)

print(f"\nGrafo de Twitter: {D.number_of_nodes()} usuarios, {D.number_of_edges()} interacciones")

Visualización de Grafos

def visualizar_red_social(G, titulo="Red Social", layout='spring'):
    """
    Visualiza grafo de red social con estilo atractivo
    """
    plt.figure(figsize=(12, 8))

    # Elegir layout
    if layout == 'spring':
        pos = nx.spring_layout(G, k=0.5, iterations=50)
    elif layout == 'circular':
        pos = nx.circular_layout(G)
    elif layout == 'kamada_kawai':
        pos = nx.kamada_kawai_layout(G)

    # Calcular métricas para visualización
    degrees = dict(G.degree())
    node_sizes = [v * 100 for v in degrees.values()]

    # Calcular centralidad para colores
    centrality = nx.betweenness_centrality(G)
    node_colors = [centrality[node] for node in G.nodes()]

    # Dibujar
    nx.draw_networkx_nodes(
        G, pos,
        node_size=node_sizes,
        node_color=node_colors,
        cmap='YlOrRd',
        alpha=0.8,
        edgecolors='black',
        linewidths=2
    )

    nx.draw_networkx_edges(
        G, pos,
        alpha=0.3,
        edge_color='gray',
        width=2
    )

    nx.draw_networkx_labels(
        G, pos,
        font_size=10,
        font_weight='bold',
        font_color='black'
    )

    plt.title(titulo, fontsize=16, fontweight='bold')
    plt.axis('off')
    plt.tight_layout()

    # Colorbar
    sm = plt.cm.ScalarMappable(
        cmap='YlOrRd',
        norm=plt.Normalize(vmin=min(node_colors), vmax=max(node_colors))
    )
    sm.set_array([])
    plt.colorbar(sm, label='Betweenness Centrality', shrink=0.8)

    plt.savefig(f'{titulo.replace(" ", "_").lower()}.png',
                dpi=300, bbox_inches='tight', facecolor='white')
    plt.show()

# Ejemplo: Red de Game of Thrones
G_got = nx.karate_club_graph()  # Dataset clásico para ejemplos
visualizar_red_social(G_got, "Red Social - Ejemplo")

Métricas de Centralidad

La centralidad mide la importancia de un nodo en la red. Diferentes métricas capturan diferentes aspectos de importancia.

1. Degree Centrality (Centralidad de Grado)

Definición: Número de conexiones directas de un nodo.

Interpretación:

• Alto degree = Muchas conexiones directas
• En redes sociales: Usuarios populares

Fórmulas:

• No dirigido: $C_D(v) = \frac{deg(v)}{n-1}$
• Dirigido:
  • In-degree: Número de conexiones entrantes (followers)
  • Out-degree: Número de conexiones salientes (following)

def analizar_degree_centrality(G, top_n=10):
    """
    Analiza centralidad de grado
    """
    # Calcular degree centrality
    degree_cent = nx.degree_centrality(G)

    # Ordenar por centralidad
    sorted_nodes = sorted(degree_cent.items(), key=lambda x: x[1], reverse=True)

    print(f"{'='*60}")
    print(f"TOP {top_n} NODOS POR DEGREE CENTRALITY")
    print(f"{'='*60}")

    for i, (node, centrality) in enumerate(sorted_nodes[:top_n], 1):
        degree = G.degree(node)
        print(f"{i}. {node}")
        print(f"   Degree: {degree}")
        print(f"   Normalized Centrality: {centrality:.4f}")
        print()

    # Si es dirigido, analizar in-degree y out-degree
    if G.is_directed():
        in_degree_cent = nx.in_degree_centrality(G)
        out_degree_cent = nx.out_degree_centrality(G)

        print("\nTOP INFLUENCERS (más followers - In-Degree):")
        sorted_in = sorted(in_degree_cent.items(), key=lambda x: x[1], reverse=True)
        for node, cent in sorted_in[:5]:
            print(f"  {node}: {G.in_degree(node)} followers")

        print("\nTOP BROADCASTERS (más following - Out-Degree):")
        sorted_out = sorted(out_degree_cent.items(), key=lambda x: x[1], reverse=True)
        for node, cent in sorted_out[:5]:
            print(f"  {node}: {G.out_degree(node)} following")

    return degree_cent

# Ejemplo
G_ejemplo = nx.karate_club_graph()
degree_centrality = analizar_degree_centrality(G_ejemplo, top_n=5)

Ventajas:

• Simple e intuitiva
• Rápida de calcular: O(n)

Limitaciones:

• Solo considera conexiones directas
• No considera calidad de conexiones
• No captura posición en estructura global

2. Closeness Centrality (Centralidad de Cercanía)

Definición: Qué tan cerca está un nodo de todos los demás nodos.

Fórmula: $$C_C(v) = \frac{n-1}{\sum_{u \neq v} d(v, u)}$$

Donde $d(v, u)$ es la distancia (camino más corto) entre v y u.

Interpretación:

• Alto closeness = Puede alcanzar otros nodos rápidamente
• En redes sociales: Información se propaga rápido desde este nodo

def analizar_closeness_centrality(G, top_n=10):
    """
    Analiza centralidad de cercanía
    """
    # Nota: closeness requiere que el grafo sea conexo
    if not nx.is_connected(G):
        # Trabajar con componente conexa más grande
        largest_cc = max(nx.connected_components(G), key=len)
        G = G.subgraph(largest_cc).copy()
        print(f"Trabajando con componente conexa más grande: {len(G)} nodos\n")

    # Calcular closeness centrality
    closeness_cent = nx.closeness_centrality(G)

    # Ordenar
    sorted_nodes = sorted(closeness_cent.items(), key=lambda x: x[1], reverse=True)

    print(f"{'='*60}")
    print(f"TOP {top_n} NODOS POR CLOSENESS CENTRALITY")
    print(f"{'='*60}")

    for i, (node, centrality) in enumerate(sorted_nodes[:top_n], 1):
        # Calcular distancia promedio a otros nodos
        avg_distance = nx.average_shortest_path_length(G, weight=None)

        print(f"{i}. {node}")
        print(f"   Closeness: {centrality:.4f}")
        print(f"   Interpretación: Alcanza otros nodos {1/centrality:.1f}x más rápido que promedio")
        print()

    return closeness_cent

# Ejemplo
closeness = analizar_closeness_centrality(G_ejemplo, top_n=5)

Ventajas:

• Considera estructura global de la red
• Útil para identificar nodos estratégicos para difusión

Limitaciones:

• Requiere grafo conexo
• Costosa de calcular: O(n³) en general, O(nm) con BFS
• Menos útil en redes muy grandes

3. Betweenness Centrality (Centralidad de Intermediación)

Definición: Qué tan frecuentemente un nodo aparece en caminos más cortos entre otros nodos.

Fórmula: $$C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}$$

Donde:

• $\sigma_{st}$ = número de caminos más cortos entre s y t
• $\sigma_{st}(v)$ = número de esos caminos que pasan por v

Interpretación:

• Alto betweenness = "Puente" importante en la red
• En redes sociales: Brokers, conectores entre comunidades

def analizar_betweenness_centrality(G, top_n=10):
    """
    Analiza centralidad de intermediación
    """
    print("Calculando betweenness centrality (puede tomar tiempo)...")

    # Calcular betweenness
    betweenness_cent = nx.betweenness_centrality(G, normalized=True)

    # Ordenar
    sorted_nodes = sorted(betweenness_cent.items(), key=lambda x: x[1], reverse=True)

    print(f"\n{'='*60}")
    print(f"TOP {top_n} NODOS POR BETWEENNESS CENTRALITY")
    print(f"{'='*60}")
    print("Estos son los 'brokers' o conectores clave en la red\n")

    for i, (node, centrality) in enumerate(sorted_nodes[:top_n], 1):
        print(f"{i}. {node}")
        print(f"   Betweenness: {centrality:.4f}")
        print(f"   Rol: Controla {centrality*100:.1f}% del flujo de información")
        print()

    # Visualizar nodos con alto betweenness
    visualizar_betweenness(G, betweenness_cent, top_n)

    return betweenness_cent

def visualizar_betweenness(G, betweenness, top_n=5):
    """
    Visualiza nodos con mayor betweenness
    """
    # Identificar top nodes
    top_nodes = sorted(betweenness.items(), key=lambda x: x[1], reverse=True)[:top_n]
    top_node_ids = [node for node, _ in top_nodes]

    plt.figure(figsize=(14, 8))
    pos = nx.spring_layout(G, k=0.5, iterations=50)

    # Colores: destacar top betweenness nodes
    node_colors = []
    for node in G.nodes():
        if node in top_node_ids:
            node_colors.append('red')
        else:
            node_colors.append('lightblue')

    # Tamaños basados en betweenness
    node_sizes = [betweenness[node] * 5000 + 100 for node in G.nodes()]

    nx.draw_networkx_nodes(G, pos, node_color=node_colors, node_size=node_sizes, alpha=0.8)
    nx.draw_networkx_edges(G, pos, alpha=0.2)
    nx.draw_networkx_labels(G, pos, font_size=8)

    plt.title("Nodos con Mayor Betweenness Centrality (en rojo)", fontsize=14)
    plt.axis('off')
    plt.tight_layout()
    plt.savefig('betweenness_visualization.png', dpi=300, bbox_inches='tight')
    plt.show()

# Ejemplo
betweenness = analizar_betweenness_centrality(G_ejemplo, top_n=5)

Ventajas:

• Identifica puntos de control en la red
• Crucial para entender flujo de información

Limitaciones:

• Muy costosa de calcular: O(n³) o O(nm) con algoritmo de Brandes
• Puede ser contra-intuitiva en redes complejas

4. Eigenvector Centrality (Centralidad de Vector Propio)

Definición: Un nodo es importante si está conectado a nodos importantes.

Fórmula: $$x_v = \frac{1}{\lambda} \sum_{u \in N(v)} x_u$$

Donde λ es el eigenvalor principal de la matriz de adyacencia.

Interpretación:

• Alto eigenvector centrality = Conectado a nodos influyentes
• En redes sociales: Influencia por asociación

def analizar_eigenvector_centrality(G, top_n=10):
    """
    Analiza centralidad de vector propio
    """
    try:
        # Eigenvector centrality requiere grafo conexo
        if not nx.is_connected(G):
            largest_cc = max(nx.connected_components(G), key=len)
            G = G.subgraph(largest_cc).copy()
            print(f"Usando componente conexa más grande: {len(G)} nodos\n")

        # Calcular eigenvector centrality
        eigen_cent = nx.eigenvector_centrality(G, max_iter=1000)

        # Ordenar
        sorted_nodes = sorted(eigen_cent.items(), key=lambda x: x[1], reverse=True)

        print(f"{'='*60}")
        print(f"TOP {top_n} NODOS POR EIGENVECTOR CENTRALITY")
        print(f"{'='*60}")
        print("Nodos conectados a otros nodos importantes\n")

        for i, (node, centrality) in enumerate(sorted_nodes[:top_n], 1):
            # Obtener vecinos
            neighbors = list(G.neighbors(node))
            avg_neighbor_centrality = np.mean([eigen_cent[n] for n in neighbors])

            print(f"{i}. {node}")
            print(f"   Eigenvector Centrality: {centrality:.4f}")
            print(f"   Conexiones: {len(neighbors)}")
            print(f"   Centralidad promedio de vecinos: {avg_neighbor_centrality:.4f}")
            print()

        return eigen_cent

    except nx.PowerIterationFailedConvergence:
        print("No convergió. Usando PageRank como alternativa...")
        return analizar_pagerank(G, top_n)

# Ejemplo
eigen_centrality = analizar_eigenvector_centrality(G_ejemplo, top_n=5)

Ventajas:

• Captura influencia indirecta
• Base de algoritmos como PageRank

Limitaciones:

• Puede no converger en algunos grafos
• Menos interpretable que degree centrality

5. PageRank

Definición: Versión mejorada de eigenvector centrality con damping factor.

Fórmula: $$PR(v) = \frac{1-d}{n} + d \sum_{u \in N_{in}(v)} \frac{PR(u)}{|N_{out}(u)|}$$

Donde:

• d = damping factor (típicamente 0.85)
• $N_{in}(v)$ = vecinos entrantes
• $N_{out}(u)$ = vecinos salientes de u

Interpretación:

• Simula "random surfer" que sigue enlaces con probabilidad d
• En redes sociales: Importancia considerando toda la red

def analizar_pagerank(G, top_n=10, alpha=0.85):
    """
    Analiza PageRank
    """
    # Calcular PageRank
    pagerank = nx.pagerank(G, alpha=alpha)

    # Ordenar
    sorted_nodes = sorted(pagerank.items(), key=lambda x: x[1], reverse=True)

    print(f"{'='*60}")
    print(f"TOP {top_n} NODOS POR PAGERANK")
    print(f"{'='*60}")
    print(f"Damping factor: {alpha}\n")

    # Calcular estadísticas
    pr_values = list(pagerank.values())
    pr_mean = np.mean(pr_values)
    pr_std = np.std(pr_values)

    for i, (node, pr) in enumerate(sorted_nodes[:top_n], 1):
        # Comparar con promedio
        desviaciones = (pr - pr_mean) / pr_std

        print(f"{i}. {node}")
        print(f"   PageRank: {pr:.6f}")
        print(f"   {desviaciones:.2f} desviaciones estándar sobre el promedio")

        if G.is_directed():
            print(f"   In-degree: {G.in_degree(node)}")
            print(f"   Out-degree: {G.out_degree(node)}")
        else:
            print(f"   Degree: {G.degree(node)}")
        print()

    return pagerank

# Ejemplo con grafo dirigido (simular Twitter)
D_twitter = nx.DiGraph()
D_twitter.add_edges_from([
    ('Influencer1', 'User1'), ('Influencer1', 'User2'),
    ('User1', 'User2'), ('User2', 'User3'),
    ('Influencer2', 'User1'), ('Influencer2', 'User3'),
    ('User3', 'Influencer1'),  # Ciclo de importancia
])

pagerank_scores = analizar_pagerank(D_twitter, top_n=5)

Ventajas:

• Funciona bien en grafos dirigidos
• Maneja nodos sin out-links (dangling nodes)
• Escalable a grafos masivos

Limitaciones:

• Requiere iteración para convergencia
• Parámetro alpha afecta resultados

Comparación de Métricas de Centralidad

def comparar_metricas_centralidad(G):
    """
    Compara todas las métricas de centralidad
    """
    # Calcular todas las métricas
    degree = nx.degree_centrality(G)

    # Closeness (solo si es conexo)
    if nx.is_connected(G):
        closeness = nx.closeness_centrality(G)
    else:
        largest_cc = max(nx.connected_components(G), key=len)
        G_cc = G.subgraph(largest_cc).copy()
        closeness = nx.closeness_centrality(G_cc)

    betweenness = nx.betweenness_centrality(G)

    try:
        eigenvector = nx.eigenvector_centrality(G, max_iter=1000)
    except:
        eigenvector = {node: 0 for node in G.nodes()}

    pagerank = nx.pagerank(G)

    # Crear DataFrame
    df = pd.DataFrame({
        'Degree': degree,
        'Closeness': closeness,
        'Betweenness': betweenness,
        'Eigenvector': eigenvector,
        'PageRank': pagerank
    })

    # Normalizar para comparación
    df_norm = (df - df.mean()) / df.std()

    # Ordenar por promedio de métricas normalizadas
    df['Avg_Centrality'] = df_norm.mean(axis=1)
    df = df.sort_values('Avg_Centrality', ascending=False)

    print("\nTOP 10 NODOS - Comparación de Métricas de Centralidad")
    print("="*80)
    print(df.head(10).to_string())

    # Visualizar correlaciones
    plt.figure(figsize=(10, 8))
    import seaborn as sns

    corr = df[['Degree', 'Closeness', 'Betweenness', 'Eigenvector', 'PageRank']].corr()

    sns.heatmap(corr, annot=True, cmap='coolwarm', center=0,
                square=True, linewidths=1, cbar_kws={"shrink": 0.8})
    plt.title('Correlación entre Métricas de Centralidad', fontsize=14)
    plt.tight_layout()
    plt.savefig('centrality_correlation.png', dpi=300, bbox_inches='tight')
    plt.show()

    return df

# Ejemplo
df_centrality = comparar_metricas_centralidad(G_ejemplo)

Detección de Comunidades

Las comunidades son grupos de nodos densamente conectados entre sí pero sparsely conectados con otros grupos.

¿Por qué detectar comunidades?

Aplicaciones:

• Segmentación de usuarios con intereses similares
• Identificación de echo chambers
• Targeting de marketing por grupos
• Detección de comportamiento coordinado (bots)
• Análisis de polarización

Algoritmos de Detección de Comunidades

1. Louvain Method

Características:

• Optimiza modularidad
• Rápido y escalable
• Jerárquico (detecta comunidades en múltiples niveles)

import community.community_louvain as community_louvain

def detectar_comunidades_louvain(G):
    """
    Detecta comunidades usando algoritmo de Louvain
    """
    # Detectar comunidades
    partition = community_louvain.best_partition(G)

    # Calcular modularidad
    modularity = community_louvain.modularity(partition, G)

    print(f"{'='*60}")
    print("DETECCIÓN DE COMUNIDADES - Algoritmo de Louvain")
    print(f"{'='*60}")
    print(f"Modularidad: {modularity:.4f}")
    print(f"Número de comunidades: {len(set(partition.values()))}")

    # Analizar tamaño de comunidades
    community_sizes = {}
    for node, comm_id in partition.items():
        community_sizes[comm_id] = community_sizes.get(comm_id, 0) + 1

    print("\nTamaño de comunidades:")
    for comm_id, size in sorted(community_sizes.items(), key=lambda x: x[1], reverse=True):
        print(f"  Comunidad {comm_id}: {size} nodos ({size/len(G)*100:.1f}%)")

    # Visualizar
    visualizar_comunidades(G, partition)

    return partition

def visualizar_comunidades(G, partition):
    """
    Visualiza grafo con comunidades coloreadas
    """
    plt.figure(figsize=(14, 10))

    # Layout
    pos = nx.spring_layout(G, k=0.5, iterations=50)

    # Colores por comunidad
    cmap = plt.cm.get_cmap('tab20', len(set(partition.values())))
    node_colors = [partition[node] for node in G.nodes()]

    # Dibujar
    nx.draw_networkx_nodes(
        G, pos,
        node_color=node_colors,
        cmap=cmap,
        node_size=300,
        alpha=0.8
    )

    nx.draw_networkx_edges(G, pos, alpha=0.2)
    nx.draw_networkx_labels(G, pos, font_size=8)

    plt.title("Detección de Comunidades - Louvain Method", fontsize=16)
    plt.axis('off')
    plt.tight_layout()
    plt.savefig('comunidades_louvain.png', dpi=300, bbox_inches='tight')
    plt.show()

# Ejemplo
partition = detectar_comunidades_louvain(G_ejemplo)

2. Girvan-Newman Algorithm

Características:

• Basado en edge betweenness
• Remueve iterativamente aristas con alto betweenness
• Produce dendrograma jerárquico

from networkx.algorithms import community as nx_community

def detectar_comunidades_girvan_newman(G, k=None):
    """
    Detecta comunidades usando Girvan-Newman
    k: número de comunidades deseado (None = automático)
    """
    print("Ejecutando Girvan-Newman (puede tomar tiempo)...")

    # Generar dendrograma
    communities_generator = nx_community.girvan_newman(G)

    # Si k no especificado, probar diferentes números de comunidades
    if k is None:
        modularidades = []
        particiones = []

        for communities in communities_generator:
            partition_dict = {}
            for comm_id, comm_nodes in enumerate(communities):
                for node in comm_nodes:
                    partition_dict[node] = comm_id

            # Calcular modularidad
            mod = nx_community.modularity(G, communities)
            modularidades.append(mod)
            particiones.append(partition_dict)

            if len(communities) > 10:  # Limitar búsqueda
                break

        # Elegir partición con mayor modularidad
        best_idx = np.argmax(modularidades)
        best_partition = particiones[best_idx]
        best_modularity = modularidades[best_idx]

        print(f"\nMejor modularidad: {best_modularity:.4f}")
        print(f"Número óptimo de comunidades: {len(set(best_partition.values()))}")

    else:
        # Avanzar hasta tener k comunidades
        for communities in communities_generator:
            if len(communities) == k:
                best_partition = {}
                for comm_id, comm_nodes in enumerate(communities):
                    for node in comm_nodes:
                        best_partition[node] = comm_id
                break

        best_modularity = nx_community.modularity(
            G,
            [{node for node, c in best_partition.items() if c == i}
             for i in set(best_partition.values())]
        )

        print(f"\nModularidad con {k} comunidades: {best_modularity:.4f}")

    return best_partition

# Ejemplo
partition_gn = detectar_comunidades_girvan_newman(G_ejemplo, k=3)

3. Label Propagation

Características:

• Muy rápido
• Cada nodo adopta la etiqueta más común entre sus vecinos
• No determinístico

def detectar_comunidades_label_propagation(G):
    """
    Detecta comunidades usando Label Propagation
    """
    # Detectar comunidades
    communities_generator = nx_community.label_propagation_communities(G)
    communities = list(communities_generator)

    # Convertir a formato partition
    partition = {}
    for comm_id, comm_nodes in enumerate(communities):
        for node in comm_nodes:
            partition[node] = comm_id

    # Calcular modularidad
    modularity = nx_community.modularity(G, communities)

    print(f"{'='*60}")
    print("DETECCIÓN DE COMUNIDADES - Label Propagation")
    print(f"{'='*60}")
    print(f"Modularidad: {modularity:.4f}")
    print(f"Número de comunidades: {len(communities)}")

    return partition

# Ejemplo
partition_lp = detectar_comunidades_label_propagation(G_ejemplo)

Análisis de Comunidades

def analizar_comunidades(G, partition):
    """
    Análisis profundo de comunidades detectadas
    """
    # Organizar nodos por comunidad
    communities = {}
    for node, comm_id in partition.items():
        if comm_id not in communities:
            communities[comm_id] = []
        communities[comm_id].append(node)

    print(f"{'='*60}")
    print("ANÁLISIS DETALLADO DE COMUNIDADES")
    print(f"{'='*60}\n")

    for comm_id, nodes in sorted(communities.items(), key=lambda x: len(x[1]), reverse=True):
        subgraph = G.subgraph(nodes)

        # Métricas de la comunidad
        density = nx.density(subgraph)
        avg_degree = np.mean([d for n, d in subgraph.degree()])

        # Identificar miembros centrales
        if len(nodes) > 0:
            degree_cent = nx.degree_centrality(subgraph)
            top_members = sorted(degree_cent.items(), key=lambda x: x[1], reverse=True)[:3]

        # Conexiones externas
        external_edges = 0
        for node in nodes:
            for neighbor in G.neighbors(node):
                if partition[neighbor] != comm_id:
                    external_edges += 1

        internal_edges = subgraph.number_of_edges()

        print(f"Comunidad {comm_id}:")
        print(f"  Tamaño: {len(nodes)} nodos")
        print(f"  Densidad: {density:.3f}")
        print(f"  Grado promedio: {avg_degree:.2f}")
        print(f"  Aristas internas: {internal_edges}")
        print(f"  Aristas externas: {external_edges}")
        print(f"  Ratio interno/externo: {internal_edges/(external_edges+1):.2f}")

        if len(nodes) > 0:
            print(f"  Miembros principales:")
            for member, centrality in top_members:
                print(f"    - {member} (centralidad: {centrality:.3f})")

        print()

    return communities

# Ejemplo
communities = analizar_comunidades(G_ejemplo, partition)

Análisis de Influencia y Difusión

Modelos de Difusión

1. Independent Cascade Model

Funcionamiento:

• Nodos infectados tienen una probabilidad p de infectar a vecinos
• Cada arista intenta "activarse" una sola vez
• Simula difusión de información/innovaciones

def simular_independent_cascade(G, seeds, p=0.1, num_simulaciones=100):
    """
    Simula difusión usando Independent Cascade Model
    """
    resultados = []

    for sim in range(num_simulaciones):
        # Inicializar
        active = set(seeds)  # Nodos activos iniciales
        newly_active = set(seeds)
        attempted = set()  # Pares (u,v) ya intentados

        # Simular difusión
        while newly_active:
            next_active = set()

            for node in newly_active:
                for neighbor in G.neighbors(node):
                    if neighbor not in active and (node, neighbor) not in attempted:
                        attempted.add((node, neighbor))

                        # Intentar activar con probabilidad p
                        if np.random.random() < p:
                            next_active.add(neighbor)

            # Actualizar
            active.update(next_active)
            newly_active = next_active

        resultados.append(len(active))

    # Estadísticas
    alcance_promedio = np.mean(resultados)
    alcance_std = np.std(resultados)

    print(f"{'='*60}")
    print("SIMULACIÓN DE DIFUSIÓN - Independent Cascade")
    print(f"{'='*60}")
    print(f"Seeds iniciales: {seeds}")
    print(f"Probabilidad de contagio: {p}")
    print(f"Número de simulaciones: {num_simulaciones}")
    print(f"\nAlcance promedio: {alcance_promedio:.1f} nodos")
    print(f"Desviación estándar: {alcance_std:.1f}")
    print(f"Alcance mínimo: {min(resultados)}")
    print(f"Alcance máximo: {max(resultados)}")
    print(f"Alcance como % de red: {alcance_promedio/len(G)*100:.1f}%")

    # Visualizar distribución
    plt.figure(figsize=(10, 6))
    plt.hist(resultados, bins=20, edgecolor='black', alpha=0.7)
    plt.axvline(alcance_promedio, color='red', linestyle='--',
                label=f'Promedio: {alcance_promedio:.1f}')
    plt.xlabel('Alcance (número de nodos activados)')
    plt.ylabel('Frecuencia')
    plt.title(f'Distribución de Alcance - Seeds: {seeds}')
    plt.legend()
    plt.tight_layout()
    plt.savefig('difusion_alcance.png', dpi=300, bbox_inches='tight')
    plt.show()

    return alcance_promedio, resultados

# Ejemplo: Comparar diferentes seeds
G_ejemplo = nx.karate_club_graph()

# Probar con nodo de alta centralidad
high_central_node = max(nx.degree_centrality(G_ejemplo), key=nx.degree_centrality(G_ejemplo).get)
alcance_central, _ = simular_independent_cascade(G_ejemplo, [high_central_node], p=0.2)

# Probar con nodo de alto betweenness
high_between_node = max(nx.betweenness_centrality(G_ejemplo), key=nx.betweenness_centrality(G_ejemplo).get)
alcance_between, _ = simular_independent_cascade(G_ejemplo, [high_between_node], p=0.2)

print(f"\nComparación:")
print(f"Nodo con mayor degree centrality: alcance = {alcance_central:.1f}")
print(f"Nodo con mayor betweenness: alcance = {alcance_between:.1f}")

2. Linear Threshold Model

Funcionamiento:

• Cada nodo tiene un threshold θ
• Se activa cuando fracción de vecinos activos supera θ
• Modela adopción basada en presión social

def simular_linear_threshold(G, seeds, thresholds=None, num_simulaciones=100):
    """
    Simula difusión usando Linear Threshold Model
    """
    if thresholds is None:
        # Thresholds aleatorios uniformes
        thresholds = {node: np.random.uniform(0.1, 0.5) for node in G.nodes()}

    resultados = []

    for sim in range(num_simulaciones):
        # Inicializar
        active = set(seeds)

        # Iterar hasta convergencia
        changed = True
        while changed:
            changed = False
            newly_active = set()

            for node in G.nodes():
                if node not in active:
                    # Calcular fracción de vecinos activos
                    neighbors = list(G.neighbors(node))
                    if neighbors:
                        active_neighbors = sum(1 for n in neighbors if n in active)
                        fraction = active_neighbors / len(neighbors)

                        # Activar si supera threshold
                        if fraction >= thresholds[node]:
                            newly_active.add(node)
                            changed = True

            active.update(newly_active)

        resultados.append(len(active))

    # Estadísticas
    alcance_promedio = np.mean(resultados)

    print(f"{'='*60}")
    print("SIMULACIÓN DE DIFUSIÓN - Linear Threshold")
    print(f"{'='*60}")
    print(f"Seeds iniciales: {seeds}")
    print(f"Threshold promedio: {np.mean(list(thresholds.values())):.2f}")
    print(f"\nAlcance promedio: {alcance_promedio:.1f} nodos ({alcance_promedio/len(G)*100:.1f}%)")

    return alcance_promedio, resultados

# Ejemplo
alcance_lt, _ = simular_linear_threshold(G_ejemplo, [high_central_node])

Influence Maximization Problem

Problema: Dado un presupuesto k, ¿qué k nodos seleccionar como seeds para maximizar alcance?

def influence_maximization_greedy(G, k, p=0.1, num_simulaciones=50):
    """
    Encuentra k seeds óptimos usando algoritmo greedy
    """
    seeds = []

    print(f"Buscando {k} seeds óptimos...")

    for i in range(k):
        print(f"\nSeleccionando seed {i+1}/{k}...")

        best_node = None
        best_gain = -1

        # Probar cada nodo candidato
        candidatos = [n for n in G.nodes() if n not in seeds]

        for node in candidatos:
            # Simular con seeds actuales + este nodo
            alcance, _ = simular_independent_cascade(
                G, seeds + [node], p=p, num_simulaciones=num_simulaciones
            )

            # Calcular ganancia marginal
            if seeds:
                alcance_sin_node, _ = simular_independent_cascade(
                    G, seeds, p=p, num_simulaciones=num_simulaciones
                )
                gain = alcance - alcance_sin_node
            else:
                gain = alcance

            if gain > best_gain:
                best_gain = gain
                best_node = node

        seeds.append(best_node)
        print(f"  Seleccionado: {best_node} (ganancia marginal: {best_gain:.1f})")

    # Evaluar seeds finales
    alcance_final, _ = simular_independent_cascade(
        G, seeds, p=p, num_simulaciones=100
    )

    print(f"\n{'='*60}")
    print("INFLUENCE MAXIMIZATION - Resultados")
    print(f"{'='*60}")
    print(f"Seeds seleccionados: {seeds}")
    print(f"Alcance esperado: {alcance_final:.1f} nodos ({alcance_final/len(G)*100:.1f}%)")

    return seeds

# Ejemplo
optimal_seeds = influence_maximization_greedy(G_ejemplo, k=3, p=0.2)

Caso de Estudio: Análisis de Red de Twitter

def analisis_completo_red_twitter(tweets_df):
    """
    Análisis end-to-end de red de Twitter
    tweets_df: DataFrame con columnas [user_id, mentioned_user_id, retweet_user_id]
    """
    print("="*80)
    print("ANÁLISIS COMPLETO DE RED DE TWITTER")
    print("="*80)

    # 1. Construir grafo
    print("\n1. CONSTRUCCIÓN DEL GRAFO")
    print("-"*80)

    G = nx.DiGraph()

    # Agregar menciones
    for _, row in tweets_df[['user_id', 'mentioned_user_id']].dropna().iterrows():
        G.add_edge(row['user_id'], row['mentioned_user_id'], type='mention')

    # Agregar retweets
    for _, row in tweets_df[['user_id', 'retweet_user_id']].dropna().iterrows():
        if G.has_edge(row['user_id'], row['retweet_user_id']):
            G[row['user_id']][row['retweet_user_id']]['weight'] = \
                G[row['user_id']][row['retweet_user_id']].get('weight', 1) + 1
        else:
            G.add_edge(row['user_id'], row['retweet_user_id'], type='retweet', weight=1)

    print(f"Nodos (usuarios): {G.number_of_nodes():,}")
    print(f"Aristas (interacciones): {G.number_of_edges():,}")
    print(f"Densidad: {nx.density(G):.6f}")

    # 2. Análisis de centralidad
    print("\n2. IDENTIFICACIÓN DE INFLUENCERS")
    print("-"*80)

    # PageRank
    pagerank = nx.pagerank(G, alpha=0.85)
    top_influencers = sorted(pagerank.items(), key=lambda x: x[1], reverse=True)[:10]

    print("\nTop 10 Influencers (PageRank):")
    for i, (user, score) in enumerate(top_influencers, 1):
        in_deg = G.in_degree(user)
        out_deg = G.out_degree(user)
        print(f"{i:2d}. {user}")
        print(f"     PageRank: {score:.6f} | Followers: {in_deg} | Following: {out_deg}")

    # 3. Detección de comunidades
    print("\n3. DETECCIÓN DE COMUNIDADES")
    print("-"*80)

    # Convertir a no dirigido para detección de comunidades
    G_undirected = G.to_undirected()

    # Louvain
    partition = community_louvain.best_partition(G_undirected)
    modularity = community_louvain.modularity(partition, G_undirected)

    num_communities = len(set(partition.values()))
    print(f"Comunidades detectadas: {num_communities}")
    print(f"Modularidad: {modularity:.4f}")

    # Analizar comunidades
    community_sizes = {}
    for user, comm_id in partition.items():
        community_sizes[comm_id] = community_sizes.get(comm_id, 0) + 1

    print("\nTamaño de principales comunidades:")
    for comm_id, size in sorted(community_sizes.items(), key=lambda x: x[1], reverse=True)[:5]:
        print(f"  Comunidad {comm_id}: {size} usuarios ({size/len(G)*100:.1f}%)")

    # 4. Análisis de difusión
    print("\n4. SIMULACIÓN DE DIFUSIÓN VIRAL")
    print("-"*80)

    # Seleccionar top 3 influencers como seeds
    top_3_seeds = [user for user, _ in top_influencers[:3]]

    alcance, _ = simular_independent_cascade(G, top_3_seeds, p=0.15, num_simulaciones=100)

    print(f"Seeds: {top_3_seeds}")
    print(f"Alcance esperado: {alcance:.0f} usuarios ({alcance/len(G)*100:.1f}% de la red)")

    # 5. Visualización
    print("\n5. GENERANDO VISUALIZACIONES...")
    print("-"*80)

    # Visualizar solo subgrafo de top usuarios
    top_users = [user for user, _ in top_influencers[:50]]
    G_top = G.subgraph(top_users).copy()

    visualizar_red_social(G_top, titulo="Red de Twitter - Top 50 Influencers", layout='kamada_kawai')

    print("\nAnálisis completado. Visualizaciones guardadas.")

    return {
        'grafo': G,
        'pagerank': pagerank,
        'comunidades': partition,
        'modularity': modularity
    }

# Ejemplo de uso (con datos simulados)
# En práctica real, obtener datos de Twitter API
tweets_simulados = pd.DataFrame({
    'user_id': np.random.choice(['User'+str(i) for i in range(100)], 1000),
    'mentioned_user_id': np.random.choice(['User'+str(i) for i in range(100)], 1000),
    'retweet_user_id': np.random.choice(['User'+str(i) for i in range(100)], 1000)
})

# resultados = analisis_completo_red_twitter(tweets_simulados)

Próximos Pasos

Para dominar análisis de redes sociales:

1. Practica con datos reales:

   • Twitter Academic API
   • Reddit API
   • Datasets públicos (SNAP, Kaggle)

2. Explora temas avanzados:

   • Temporal Networks (redes que evolucionan)
   • Multilayer Networks (múltiples tipos de relaciones)
   • Hypergraphs (relaciones entre más de 2 nodos)

3. Profundiza en algoritmos:

   • Community detection avanzado (Infomap, Leiden)
   • Link prediction
   • Network embedding (Node2Vec, DeepWalk)

4. Herramientas complementarias:

   • Gephi para visualización interactiva
   • graph-tool (más rápido que NetworkX para redes grandes)
   • Neo4j para grafos persistentes

5. Aplicaciones específicas:

   • Detección de fake news
   • Identificación de bots
   • Análisis de polarización política
   • Recomendación basada en grafos

La teoría de grafos es fundamental para entender el tejido de las redes sociales. Dominar estas técnicas te permite extraer insights que son imposibles de ver con análisis tradicional.