El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Aplicacions de Grafs a les Xarxes Socials

Següent ►
►

A la lliçó anterior vas encadenar optimització, assignació i rutes per a l'operativa de Rutalia. Ara canviem de domini: les xarxes socials, probablement el consumidor més gran d'algorismes de grafs del món. La bona notícia és que gairebé no hi ha res de nou per aprendre de mecànica: el BFS de 03-02, l'union-find de 01-04, Dijkstra de 03-03 i el clustering jeràrquic de 05-05 són exactament les peces que fan servir aquests sistemes. El que és nou és el modelatge: quina pregunta de negoci ("qui és influent?", "a qui li suggereixo com a amic?") es tradueix a quina propietat del graf. Desenvoluparem una peça estrella —PageRank— i treballarem sobre una xarxa sintètica amb usuaris ficticis U-nnn, inspirada en la comunitat de repartidors i clients de Rutalia.

Contingut

  1. Una xarxa social és un graf (i les decisions de modelatge importen)
  2. Construir la xarxa sintètica: preferència d'enllaç i hubs
  3. Món petit: l'experiment dels 6 graus amb BFS
  4. Components i comunitats
  5. Centralitats: qui importa a la xarxa?
  6. PageRank: el surfista aleatori, desenvolupat
  7. Recomanació d'amistats: amics en comú i Jaccard
  8. Difusió i viralitat: BFS com a model de propagació
  9. Privacitat: el que no has de fer amb dades socials reals

Una xarxa social és un graf (i les decisions de modelatge importen)

El modelatge base és directe: cada usuari és un node i cada relació una aresta. Però la primera decisió ja té conseqüències algorísmiques:

Xarxa Relació Tipus de graf Conseqüència
Facebook, LinkedIn amistat / contacte (mútua) no dirigit "amics en comú" és simètric; components amb union-find
Twitter/X, Instagram, TikTok seguir (no mútua) dirigit grau d'entrada ≠ de sortida; influència = arestes entrants
WhatsApp / missatgeria converses amb freqüència no dirigit ponderat els pesos alimenten Dijkstra (03-03) per a la "proximitat real"
Comunitat de Rutalia repartidor atén habitualment un client bipartit aparellament (03-06) i recomanació per coocurrència

És la mateixa disjuntiva de representació que vas veure a 03-01 (llista vs matriu d'adjacència) elevada al nivell semàntic: abans triaves com emmagatzemar el graf; ara tries què és el graf. En aquesta lliçó farem servir un graf no dirigit (relacions mútues) excepte a PageRank, on el sentit de l'aresta és l'essència.

Construir la xarxa sintètica: preferència d'enllaç i hubs

Les xarxes socials reals no són aleatòries uniformes: uns pocs nodes acumulen moltíssimes connexions (hubs) i la majoria en té poques. El mecanisme generador clàssic és la preferència d'enllaç (preferential attachment, model de Barabási-Albert): cada usuari nou tendeix a connectar-se amb qui ja està ben connectat — "els rics es fan més rics". Ho implementem amb un truc elegant: mantenir una llista on cada node apareix una vegada per cada aresta que toca; mostrejar uniformement d'aquesta llista equival a mostrejar proporcionalment al grau.

import random
from collections import deque, defaultdict

random.seed(7)

def xarxa_preferencial(n, m=2):
    """Xarxa de n usuaris; cada usuari nou crea m enllaços
    amb probabilitat proporcional al grau (Barabási-Albert)."""
    adj = defaultdict(set)
    bossa = []                       # cada node apareix tantes vegades com el seu grau
    nodes = [f"U-{i:03d}" for i in range(1, n + 1)]
    # nucli inicial: els m+1 primers, tots connectats entre si
    for i in range(m + 1):
        for j in range(i + 1, m + 1):
            adj[nodes[i]].add(nodes[j]); adj[nodes[j]].add(nodes[i])
            bossa += [nodes[i], nodes[j]]
    for k in range(m + 1, n):
        nou = nodes[k]
        destins = set()
        while len(destins) < m:
            destins.add(random.choice(bossa))   # proporcional al grau
        for d in destins:
            adj[nou].add(d); adj[d].add(nou)
            bossa += [nou, d]
    return adj

xarxa = xarxa_preferencial(300)
graus = sorted(((len(v), u) for u, v in xarxa.items()), reverse=True)
print("Top 5 hubs:", [(u, g) for g, u in graus[:5]])
print("Grau mitjà (mediana):", sorted(len(v) for v in xarxa.values())[150])

El resultat típic: els hubs superen les 30-40 connexions mentre que l'usuari mitjà en té 2-4. Aquesta desigualtat extrema (distribució de "cua llarga") és la signatura de les xarxes socials reals, i explica per què el màrqueting busca hubs i per què una fallada en un hub (o el seu compte compromès) afecta mitja xarxa.

Món petit: l'experiment dels 6 graus amb BFS

El 1967 Milgram va demanar a persones de Nebraska fer arribar una carta a un desconegut de Boston passant-la només entre coneguts: la mediana va ser ~6 salts. Al nostre graf, "nombre de salts entre dos usuaris" és exactament la distància en arestes, i l'algorisme per calcular-la des d'un origen és el BFS de 03-02 — sense canvis, només reinterpretat.

def bfs_distancies(xarxa, origen):
    """Distàncies en salts des de l'origen (BFS de 03-02, tal qual)."""
    dist = {origen: 0}
    cua = deque([origen])
    while cua:
        u = cua.popleft()
        for v in xarxa[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                cua.append(v)
    return dist

# Distància mitjana entre 200 parelles a l'atzar
nodes = list(xarxa)
mostres = []
for _ in range(200):
    a, b = random.sample(nodes, 2)
    d = bfs_distancies(xarxa, a)
    if b in d:
        mostres.append(d[b])
print(f"Distància mitjana: {sum(mostres)/len(mostres):.2f} salts, màxima: {max(mostres)}")

Amb 300 usuaris i només 2 enllaços per usuari nou, la distància mitjana volta els 3-4 salts i gairebé mai no supera 6. Aquesta és la propietat de món petit: el diàmetre creix com O(log n), no com O(n), perquè els hubs actuen de dreceres. Conseqüència pràctica: qualsevol cosa que es propagui per la xarxa (informació, rumors, malware) pot arribar a gairebé tothom en molt pocs passos — ho quantificarem a la secció de difusió.

Components i comunitats

Components connexes — la xarxa està sencera o fragmentada? Dues eines que ja tens: BFS/DFS repetits (03-02) o union-find (01-04), que a més suporta el cas incremental (les amistats arriben com un stream d'esdeveniments i vols saber en tot moment si dos usuaris estan connectats, sense recalcular res). En xarxes amb preferència d'enllaç tot acaba en una component gegant; a les xarxes reals sol haver-hi una component gegant (~90 % d'usuaris) i pols de components minúscules.

Les comunitats són una altra cosa: grups dins de la mateixa component amb moltes arestes internes i poques cap enfora (la colla del barri, els companys de feina). Dos enfocaments amb peces del curs:

  • Aglomeratiu (de baix a dalt). És el clustering jeràrquic de 05-05 aplicat al graf: si defineixes la similitud entre usuaris com el Jaccard dels seus veïnatges (ho veurem a recomanació) i fusiones les parelles més similars, el dendrograma revela comunitats. Recorda l'equivalència que vas descobrir a 05-05: single-linkage = Kruskal (03-04); aquí el "bosc que es va fusionant" són les comunitats creixent.
  • Divisiu (de dalt a baix): la idea de Girvan-Newman. En lloc d'unir el que és similar, talla el que separa. Les arestes "pont" entre comunitats tenen una propietat mesurable: hi passen molts camins mínims (si només hi ha un pont entre dos barris, tot camí interbarri el creua). Aquesta mesura es diu betweenness (intermediació) d'aresta i es calcula amb BFS des de cada node. L'algorisme conceptual:
flowchart TD
    A[Calcular la betweenness<br>de cada aresta amb BFS] --> B[Eliminar l'aresta<br>de betweenness més alta]
    B --> C{S'ha partit el graf<br>en més components?}
    C -->|no| A
    C -->|sí| D[Cada component<br>és una comunitat candidata]
    D -->|continuar tallant<br>per a comunitats més fines| A

No l'implementarem complet (el càlcul eficient de la betweenness és delicat i O(n·m) per iteració el fa car en xarxes grans — per això en producció es fan servir mètodes més ràpids com Louvain, que optimitzen una mesura anomenada modularitat), però la intuïció és el que és transferible: comunitat = regió densa; frontera = arestes per on s'escolen tots els camins.

Centralitats: qui importa a la xarxa?

"Important" no és una sola cosa. Cada definició matemàtica de centralitat respon una pregunta de negoci diferent:

Centralitat Definició Es calcula amb Pregunta que respon
Grau nre. de connexions comptar (O(1) per node) Qui té més audiència directa?
Proximitat invers de la distància mitjana a la resta BFS des del node (03-02); Dijkstra si hi ha pesos (03-03) Qui difon una cosa més ràpid a tota la xarxa?
Intermediació fracció de camins mínims que passen pel node BFS des de tots els nodes Qui és el pont la caiguda del qual fragmenta la xarxa?
PageRank importància recursiva: t'apunten nodes importants iteració de punt fix (secció següent) Qui és influent de veritat, no només popular? 
def proximitat(xarxa, u):
    d = bfs_distancies(xarxa, u)
    assolits = [x for x in d.values() if x > 0]
    return len(assolits) / sum(assolits) if assolits else 0.0

top_grau = max(xarxa, key=lambda u: len(xarxa[u]))
top_prox = max(xarxa, key=lambda u: proximitat(xarxa, u))
print("Grau més alt:", top_grau, "| proximitat més alta:", top_prox)

En xarxes amb hubs, grau i proximitat solen coincidir al capdamunt, però se separen tan bon punt la xarxa té estructura de comunitats: un node de grau modest situat entre dues comunitats pot tenir una proximitat (i sobretot una intermediació) altíssima. Aquest matís —popular ≠ ben situat— és el que motiva la secció següent.

PageRank: el surfista aleatori, desenvolupat

El grau compta quants t'apunten; PageRank pondera qui. Va néixer per ordenar la web (una recomanació d'una pàgina important val més que cent de pàgines irrellevants) i es fa servir igual a les xarxes socials: un "segueix" d'un usuari influent pesa més que deu de comptes buits. Aquí el graf és dirigit: l'aresta u→v significa "u segueix v" (o "u enllaça v").

La idea del surfista aleatori. Imagina un usuari que navega eternament: a cada pas, amb probabilitat d (l'esmorteïment, damping, típicament 0,85) salta a un seguit/enllaç a l'atzar del node actual, i amb probabilitat 1−d es teletransporta a un node qualsevol de la xarxa (s'"avorreix" i torna a començar). El PageRank d'un node és la fracció del temps que el surfista hi passa a llarg termini. El teletransport no és un ornament: sense ell, el surfista quedaria atrapat en carrerons sense sortida i en cicles, i el procés no convergiria a res útil.

Formulació iterativa. Traduïm la història a una equació de punt fix, amb N nodes:

PR(v) = (1 - d)/N  +  d * Σ  PR(u) / sortida(u)     per a cada u que apunta a v

Cada node reparteix el seu rang a parts iguals entre les seves sortides; el terme (1−d)/N és el teletransport. S'itera des d'un repartiment uniforme fins que els valors deixen de moure's — la mateixa filosofia d'iteració fins al punt fix que vas veure a Bellman-Ford (03-03) i a k-means (05-05).

def pagerank(sortides, d=0.85, iters=100, tol=1e-10):
    """sortides: dict node -> conjunt de nodes als quals apunta."""
    nodes = set(sortides) | {v for s in sortides.values() for v in s}
    N = len(nodes)
    pr = {u: 1.0 / N for u in nodes}          # repartiment inicial uniforme
    for _ in range(iters):
        nou = {u: (1 - d) / N for u in nodes}
        for u in nodes:
            destins = sortides.get(u, set())
            if destins:
                quota = pr[u] / len(destins)      # reparteix el seu rang
                for v in destins:
                    nou[v] += d * quota
            else:
                # node sense sortides ("penjant"): reparteix a tota la xarxa,
                # com si el surfista es teletransportés sempre des d'ell
                for v in nodes:
                    nou[v] += d * pr[u] / N
        if sum(abs(nou[u] - pr[u]) for u in nodes) < tol:
            break
        pr = nou
    return pr

# Xarxa dirigida d'exemple: qui segueix qui
segueix = {
    "U-001": {"U-002"},
    "U-002": {"U-003"},
    "U-003": {"U-001"},
    "U-004": {"U-003"},
    "U-005": {"U-003"},
    "U-006": {"U-003"},
    "U-007": {"U-004"},          # segueix el que segueix el hub
}
pr = pagerank(segueix)
for u, r in sorted(pr.items(), key=lambda kv: -kv[1]):
    print(f"{u}: {r:.4f}")

Observa el resultat: U-003 guanya amb claredat (l'apunten quatre nodes), però el que és interessant és la resta. U-001 puntua més alt que U-004 tot i que a tots dos els apunta un sol node — perquè U-001 l'apunta el mateix U-003, que és important, mentre que U-004 l'apunta el perifèric U-007. Això és exactament "no compta quants t'apunten, sinó qui", i cap recompte de grau no ho captura. Detalls del codi que importen:

  • Nodes penjants (sense sortides): si no repartissin el seu rang, el sistema "perdria massa" a cada iteració. La solució estàndard és que reparteixin a tota la xarxa.
  • Convergència: garantida amb d < 1; amb d = 0,85 basten unes desenes d'iteracions. Cada iteració costa O(nodes + arestes): PageRank escala a grafs de milers de milions d'arestes (així es calculava sobre tota la web).
  • L'esmorteïment com a control: d → 1 dona més pes a l'estructura d'enllaços (i convergeix més lent); d → 0 ho aplana tot cap a l'uniforme.

Recomanació d'amistats: amics en comú i Jaccard

"Persones que potser coneixes" és, en el seu nucli, un problema de camins de longitud 2: si U-042 i U-107 no són amics però comparteixen 8 amics, probablement es coneixen. Comptar amics comuns afavoreix els hubs (comparteixen amics amb tothom); la similitud de Jaccard corregeix aquest biaix normalitzant per la mida dels veïnatges:

J(a, b) = |veins(a) ∩ veins(b)| / |veins(a) ∪ veins(b)|
def recomanacions(xarxa, u, k=5):
    """Top-k candidats a amistat per a u: no-amics a distància 2,
    ordenats per similitud de Jaccard de veïnatges."""
    candidats = set()
    for amic in xarxa[u]:
        candidats |= xarxa[amic]          # amics dels meus amics
    candidats -= xarxa[u] | {u}           # fora els que ja són amics, i jo
    puntuats = []
    for c in candidats:
        inter = len(xarxa[u] & xarxa[c])
        unio = len(xarxa[u] | xarxa[c])
        puntuats.append((inter / unio, inter, c))
    puntuats.sort(reverse=True)
    return [(c, f"J={j:.2f}", f"{n} en comú") for j, n, c in puntuats[:k]]

print(recomanacions(xarxa, "U-050"))

És la mateixa maniobra que vas fer a k-NN (05-01): definir una similitud i rankejar-hi. Canvia l'espai (veïnatges d'un graf en lloc de coordenades numèriques), no el mètode. A 06-04 reutilitzaràs exactament aquesta idea amb matrius usuari-ítem per recomanar productes.

Difusió i viralitat: BFS com a model de propagació

Què passa quan un usuari publica alguna cosa i cada contacte la comparteix amb una certa probabilitat? El model més simple és un BFS probabilístic: la informació avança per nivells (els nivells del BFS són "hores" o "rondes" de propagació), però cada aresta només la transmet amb probabilitat p.

def difusio(xarxa, origen, p=0.3, rondes=6):
    """Simula la propagació: cada contacte comparteix amb probabilitat p."""
    assolits = {origen}
    frontera = {origen}
    historia = [1]
    for _ in range(rondes):
        nova = set()
        for u in frontera:
            for v in xarxa[u]:
                if v not in assolits and random.random() < p:
                    nova.add(v)
        assolits |= nova
        frontera = nova
        historia.append(len(assolits))
        if not frontera:
            break
    return historia

print("Abast per ronda des d'un hub:      ", difusio(xarxa, graus[0][1]))
print("Abast per ronda des de la perifèria:", difusio(xarxa, graus[-1][1]))

Dos fenòmens apareixen en executar-ho diverses vegades: partir d'un hub dispara l'abast a les primeres rondes (per això les campanyes busquen nodes de PageRank alt), i existeix un llindar: amb p petita la difusió s'apaga sola; superat un cert valor, arriba a gairebé tota la component en poques rondes — la propietat de món petit treballant a favor (màrqueting) o en contra (desinformació, virus). Els models seriosos d'epidemiologia sobre xarxes (SIR i companyia) són refinaments d'aquesta mateixa simulació.

Privacitat: el que no has de fer amb dades socials reals

Tot l'anterior ho hem fet sobre usuaris ficticis U-nnn, i no és casualitat. Un graf social real és una dada personal, i de les delicades: revela relacions, hàbits i cercles d'una persona fins i tot si els seus atributs estan "anonimitzats" (l'estructura de connexions d'algú pot bastar per reidentificar-lo). Si algun dia analitzes xarxes reals —fins i tot internes d'una empresa, com la xarxa d'interaccions entre repartidors i clients—:

  • Base legal i finalitat primer: a Europa, el RGPD exigeix un fonament jurídic i una finalitat declarada abans de tocar la dada; "és que era interessant" no és una finalitat.
  • Agrega i minimitza: per a la majoria de preguntes de negoci (quantes comunitats hi ha?, quina és la distància mitjana?) basten mètriques agregades; no necessites —ni has de— mirar individus.
  • Compte amb la reidentificació: treure noms no anonimitza un graf; els patrons de connexió són empremtes dactilars.
  • Centralitats sobre persones són decisions sobre persones: fer servir PageRank intern per avaluar empleats, per exemple, entra al terreny de les decisions automatitzades amb efectes sobre individus, que requereixen transparència i supervisió humana (ho reprenem a 06-04).

Com a norma de treball: desenvolupa i valida amb dades sintètiques (com aquí), i quan passis a dades reals, fes-ho amb el marc legal i de governança de dades de la teva organització, no pel teu compte.

Errors Comuns i Consells

  • Triar malament dirigit/no dirigit. Modelar "seguir" com a amistat mútua (o viceversa) invalida totes les anàlisis posteriors: PageRank sobre un graf simetritzat degenera gairebé en el grau. La primera decisió de modelatge és la més barata de corregir al principi i la més cara després.
  • Confondre component amb comunitat. Component és un fet topològic (hi ha camí o no n'hi ha); comunitat és una qüestió de densitat relativa i sempre depèn d'un criteri. No existeix "la" partició en comunitats veritable.
  • Oblidar els nodes penjants a PageRank. Sense el repartiment especial, la suma de rangs decau a cada iteració i els resultats deixen de ser comparables. Comprova sempre que sum(pr.values()) ≈ 1.
  • Recomanar per amics comuns sense normalitzar. Sense Jaccard (o una altra normalització), recomanaràs hubs a tothom — correcte segons la mètrica, inútil per a l'usuari.
  • Treure conclusions d'una sola simulació de difusió. És un procés aleatori: reporta la mitjana i la dispersió de moltes execucions, com vas fer amb els algorismes genètics a 02-04.
  • Consell: abans de calcular res de sofisticat, imprimeix el bàsic — nre. de nodes, arestes, distribució de graus, mida de la component gegant. Cinc línies que detecten el 90 % dels errors de càrrega o modelatge.

Exercicis

  1. Robustesa de la xarxa. Sobre la xarxa de 300 usuaris, simula dos atacs: (a) eliminar els 10 nodes de grau més alt; (b) eliminar 10 nodes a l'atzar. Després de cadascun, mesura amb union-find o BFS la mida de la component gegant. Quin fragmenta més la xarxa? Què implica per protegir una infraestructura social (o per vacunar en una epidèmia)?
  2. PageRank amb compra de seguidors. Parteix de la xarxa dirigida segueix de l'exemple i afegeix 20 comptes nous U-9xx que només segueixen U-007. Recalcula PageRank. Quant puja U-007? Puja també U-004 (a qui U-007 segueix)? Explica per què aquest "atac" funciona pitjor del que l'atacant espera i quin paràmetre l'amorteix.
  3. Recomanador avaluat. Dissenya una avaluació del recomanador d'amistats: oculta aleatòriament el 10 % de les arestes de la xarxa, genera top-5 recomanacions per a cada usuari afectat i mesura quina fracció de les arestes ocultes apareix recomanada (recall). Compara "amics en comú" contra Jaccard.

Solucions

  1. L'atac dirigit als hubs és devastador: la component gegant sol perdre una fracció gran dels seus nodes o trencar-se a trossos, mentre que 10 eliminacions aleatòries gairebé no es noten (gairebé sempre cauen nodes de grau 2-3). És la doble cara de les xarxes de cua llarga: robustes davant de fallades aleatòries, fràgils davant d'atacs dirigits. En epidemiologia, la lectura és que immunitzar hubs (persones d'alt contacte) rendeix molt més que immunitzar a l'atzar.
  2. U-007 puja clarament (passa de rang mínim a rang notable: 20 comptes li transfereixen el seu (1−d)/N amplificat), i U-004 també puja — el rang flueix per l'aresta U-007→U-004 i d'allà a U-003: la inflació es propaga però diluint-se a cada salt (factor d i repartiment entre sortides). Funciona pitjor de l'esperat perquè els comptes nous només aporten el rang de teletransport (ningú no els apunta), i l'esmorteïment d limita quant de rang "fabricat" es pot acumular. És, a petita escala, la cursa de l'spam d'enllaços contra els cercadors; les defenses reals afegeixen a més detecció de patrons anòmals (classificació de 05-02!).
  3. Esquema: ocultes = mostra aleatòria del 10 % d'arestes → treu-les de xarxa → per a cada usuari amb arestes ocultes, genera el top-5 → recall = |recomanades ∩ ocultes| / |ocultes|. És l'equivalent en grafs del train/test que vas fer servir a 05-02: no avaluïs mai amb informació que el model va poder veure. Jaccard sol guanyar en xarxes amb hubs perquè "amics en comú" omple el top-5 amb els mateixos nodes populars per a tothom; si la teva xarxa sintètica és petita i densa, la diferència pot ser modesta — una altra raó per reportar mitjanes sobre diverses llavors.

Conclusió

Has analitzat una xarxa social de cap a cap gairebé sense aprendre cap algorisme nou: el BFS (03-02) et va donar distàncies, món petit, proximitat i el model de difusió; l'union-find (01-04), les components; el clustering jeràrquic (05-05) i la idea de Girvan-Newman, les comunitats; i l'única peça desenvolupada des de zero —PageRank— va resultar ser una altra iteració de punt fix de la família que ja coneixies de Bellman-Ford i k-means. La lliçó de fons del cas d'estudi: en un domini nou, la feina és mapar preguntes de negoci a propietats del graf, triar la definició correcta (dirigit?, quina centralitat?, quina normalització?) i respectar els límits ètics i legals de la dada. A la propera lliçó el repte canvia de forma: no és l'estructura del problema sinó la seva mida — què passa amb la cerca i l'ordenació quan els 200 milions de registres històrics de Rutalia no caben a la memòria de cap màquina.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats