AR - Lecture Notes Summary

Lecture Info

Analisi di Reti

• Esempio 1: Stabilità

• Esempio 2: Influenza

• Rappresentare una Rete

Esperimenti Sociali

• Componente Gigante (Leskovec e Hrovitz)

• Gradi di Separazione (Milgram)

Grafi Aleatori

• Modello di Erdős-Rényi

  • Grado Medio

Rich get Richer

• Scelta parametro \(p\)

Componenti Connesse \(G_{n,p}\)

Esercizio: \(1 - x \leq e^{-x}\)

• Proof 1

• Proof 2

Lecture Info

Modello Strong/Weak Ties

• Strength of Weak Ties

• Descrizione Modello

• Coefficiente di Clustering

• Esempio

• Strong Triadic Closure Property

• Bridges

• S/W Edges and LB

Modello Rilassato

• Neighborhood Overlap

• Neighborhood Overlap as LB

Capitale Sociale

Lecture Info

Gruppi Coesi (Zachary)

Teoria della Complessità

• Problemi Decisionali

• P vs NP

• NP-Completezza

Comunità

• Web-Community (WC)

• Cut-Community (CC)

• Connessione tra WC e CC

• Esempio: CC senza WC

Lecture Info

WCP Problem

• 3-Sat \(\preceq\) WCP

  • Variable Gadget

  • Nodi T e F

  • Clause Gadget

  • Ultimo Ritocco

  • Dimostrazione

(Edge)-Betweenness

• Calcolo di \(b(u, v)\)

• Girvan-Newman Algorithm

  • Example

Lecture Info

Omofilia

Reti Segnate (complete)

• Stabilità in Reti Segnate

• Strutturalmente Bilanciato

• Quasi Strutturalmente Bilanciato

Reti Segnate (non-complete)

Lecture Info

Reti Approssimatamente Bilanciate

• Caratterizzazione

• Dimostrazione

  • Parte 1: Trovare Nodo \(u_0\)

  • Parte 2: Costruzione partizione (X, Y)

  • Parte 3: Calcolo di \(a^-_X, a_Y^-, a_{XY}^+\)

  • Parte 4: Dimostrazione casi

Lecture Info

World Wide Web

• Struttura del Web

• Ricerca nel Web

Hubs and Authorities

• Notazione Matriciale

• Teorema di Convergenza

• Condizione per Autovalori Positivi

Lecture Info

Page Rank

• Prima Formulazione (PR)

• Seconda Formulazione (SPR)

• Teorema di Perron-Frobenius

• Convergenza di SPR

• PR come Random Walk

Modern Web Search

Lecture Info

Regola di Bayes

• Esempio (spam e-mail)

Effetto Herding

• Esperimento Sociale

• Formalizzazione Esperimento

Lecture Info

Effetto Herding

• Primo Individuo

• Sequenza di Segnali

• Probabilità Innesco Cascata

Lecture Info

Modelli Rich Get Richer

• Modello Erdős-Rényi

  • Teorema del Limite Centrale

  • Secondo Chernoff Bound

• Power Laws

• Modello Copia

  • Dimostrazione Power Law

Amazon e la Lunga Coda

Lecture Info

Diffusione delle Innovazioni

Network Coordination Game

• Esempio Diffusione

• Problemi di Interesse

Clusters e Cascate

• Osservazioni Finali

Azione Collettiva

• Esempi

Lecture Info

Turning Point

Capacità di Cascata

• Diffusione nel Cammino

• Diffusione nella Griglia

• Capacità di Cascata Massima

Lecture Info

Bilinguismo

Capacità nella Catena con Bilinguismo

Lecture Info

Teoria del Mondo Piccolo

• Numero di Shortest Paths

• Ricerca Decentralizzata

Modelli Mondo Piccolo

• Modello di Watts-Strogatz

• Modello per Ricerca Decentralizzata

  • Perché \(q=2\) è ottimo nel piano?

Lecture Info

Ricerca Miope

Analisi Anello

• Caso Ottimo \(q=1\)

• Caso \(q \neq 1\)

Analisi Griglia

Lecture Info

Modello Matematico di Voto

• Voto Tramite Ranking

• Voto Tramite Ordinamento

• Equivalenza dei Metodi di Voto

Esempi di Sistemi di Voto

• Voto a Maggioranza

  • Esempio (Paradosso di Condorcet)

• Voto Posizionale

  • Esempio (Alternative Irrilevanti)

Lecture Info

Principi per Sistemi di Voto

• PIIA - Indipendenza Alternative Irrilevanti

• PU - Principio di Unanimità

Teorema di Arrow

• Dimostrazione Teorema Arrow

  • Costruzione Profili \(P_i\)

  • Individuazione del ditattore

  • Il votante \(j\) è il ditattore - parte 1: \(y, z \in N - \{x\}\)

  • Il votante \(j\) è il dittatore - parte 2: \(y \in N - \{x\}, z=x\)

  • Il votante \(j\) è il dittatore - parte 3: \(l=j\)

Teorema del Votante Mediano

• Esempio

Lecture Info

Sistemi di Voto per Aggregare Informazioni

• Esperimento delle Urne

• Esperimento della Giuria

Teorema della Giuria di Condorcet