%\documentclass[aps,floats,showpacs,superscriptaddress,floatfix]{revtex4}
\documentclass[11pt]{article}
\usepackage[final]{epsfig}
\usepackage[italian]{babel}
\usepackage[latin1]{inputenc}
\usepackage{amsmath, amsthm, amssymb}
\newcommand{\avg}[1]{\langle{#1}\rangle}
\newcommand{\Avg}[1]{\left\langle{#1}\right\rangle}
\newcommand{\be}{\begin{equation}}
\newcommand{\ee}{\end{equation}}
\newcommand{\beas}{\begin{eqnarray*}}
\newcommand{\eeas}{\end{eqnarray*}}
\newcommand{\bea}{\begin{eqnarray}}
\newcommand{\eea}{\end{eqnarray}}
\newcommand{\req}[1]{(\ref{#1})}
\newcommand{\wt}{\widetilde}
\newcommand{\kinnk}{K_{nn}^(in)(k_{in})}
\begin{document} 

\title{Rapporto di attività 2004/2005}
\author{Andrea Capocci}
\date{\today}
\maketitle

\section{Introduzione}

L'attività 2004/2005 è stata dedicata allo studio delle proprietà
statistiche di alcune reti complesse essenziali per la sfera della
comunicazione. Il linguaggio, l'infrastruttura fisica di Internet e
l'architettura del World Wide Web sono stati infatti l'oggetto dei
miei studi, sia dal punto di vista teorico che da quello
empirico. Ciascuno di questi oggetti di indagine, infatti, può essere
rappresentato attraverso una rete, in maniera più o meno
immediata. Inoltre, tali reti condividono proprietà statistiche
peculiari quanto ubique \cite{LinkedBarabasi}, come il grande numero
di nodi contenuti o la distribuzione statistica del numero di
connessioni $k$ possedute da ciascun nodo: essa segue una legge a
potenza del tipo $P(k) ~ k^{-\gamma}$, come in decine di altri esempi
già analizzati in letteratura con gli strumenti tipici della meccanica
statistica. Tale proprietà statistica implica un'estrema eterogeneità
dei nodi che compongono una rete complessa, rispetto ai tradizionali
modelli, come i reticoli regolari o i grafi aleatori ``possoniani''
\cite{ErdosRenyi}, in cui la distribuzione del grado dei nodi è
gaussiana o, addirittura, con varianza nulla nel caso dei reticoli
regolari. Si tratta di una proprietà di grande interesse, dal punto di
vista della meccanica statistica. Distribuzioni di questo tipo sono di
norma osservate nei fenomeni critici che si verificano nelle
transizioni di fase e in sistemi auto-organizzati 

Proprio per la loro natura e il loro impatto sul nostro
attuale habitat tecnologico, lo studio di tali reti non può limitarsi
alla descrizione quantitativa ma deve, ove possibile, fornire
strumenti di analisi dell'informazione trasmessa tra i nodi della
rete. Con questo spirito, ho studiato le reti complesse che emergono
studiando le strutture funzionali al trasferimento di informazione in
diversi ambiti.

\section{Le reti linguistiche e le comunità}

Data clustering: applicazioni alla linguistica
Algoritmi spettrali: stato dell'arte e innovazioni fatte
Applicazioni alla linguistica

Le {\em reti linguistiche} permettono di studiare le relazioni tra le
parole (i nodi di tali reti, appunto) da diversi punti di vista. Le
parole di una lingua interagiscono sia sul piano sintattico, svolgendo
funzioni diverse secondo la loro posizione all'interno delle
proposizioni e la grammatica della lingua considerata, che su quello
semantico, ovvero nel significato delle parole stesse.

Nell'anno passato, con Francesca Colaiori, Guido Caldarelli e Vito
P. Servedio, studiammo proprio una particolare rete semantica come
ideale ``palestra'' per verificare l'efficienza di algoritmi di
individuazione di comunità \cite{WordClustering}. La rete semantica
utilizzata era stata generata in diversi esperimenti psicologici in
cui i partecipanti erano invitati ad associare parole liberamente
\cite{FreeAssociationNet}: le libere associazioni raccolte possono
essere interpretate come legami diretti (cioè, direzionati dalla
parola data come stimolo verso la parola ottenuta dalla libera
associazione) e di diversa intensità o {\em peso} secondo la frequenza
di ciascuna associazione tra i nodi, i.e. le parole.

Gli algoritmi di partizione, applicati alle reti, individuano i
sotto-insiemi di nodi particolarmente interconnessi in un sistema
disordinato come una rete complessa. Ciò è utile per scomporre una
rete di grandi dimensioni in strutture più piccole dette {\em
comunità}, e permette di osservare la struttura elementare di reti
complesse, se presente, per facilitarne la comprensione. Applicati
alle reti delle libere assocazioni semantiche, tali algoritmi
permettono di associare in comunità le parole che si riferiscono ad
uno stesso argomento, ad esempio.

Lo scopo principale dello studio, tuttavia, non era l'analisi delle
reti linguistiche, ma lo sviluppo di un nuovo algoritmo ,
basato sull'analisi spettrale di funzioni semplici della {\em matrice
di adiacenza} della rete (i cui elementi di matrice corrispondono
all'intensità delle connessioni tra i nodi): l'algoritmo da noi
sviluppato, e qui sta la sua novità, permette di studiare reti dirette
e ``pesate'' anche di grandi dimensioni. I metodi spettrali
tradizionali inferiscono la struttura delle comunità di una rete dal
profilo degli autovettori delle matrici ``normale'' e ``Laplaciana''
\cite{SearsRichards}. Questi metodi sono utili solo nell'analisi di
reti non dirette e di piccole dimensioni; per questo motivo, abbiamo
introdotto nuovi problemi agli autovalori, legati comunque alla
matrice di adiacenza, che generalizzano gli algoritmi classici e ne
permettono l'applicazione in casi reali di grande interesse pratico
(ad esempio, il World Wide Web).

Le reti semantiche a nostra disposizione (con migliaia di nodi e
decine di migliaia di connessioni di diversa intensità)
rappresentarono un ottimo banco di prova tali metodi, in quanto
l'efficienza del clustering può essere osservata direttamente dalla
plausibilità delle comunità ottenute (parole di significato scorrelato
devono appartenere a comunità distinte, se il metodo funziona).

Grazie alla collaborazione, nel quadro del progetto europeo (FET)
COSIN, con Ramon Ferrer y Cancho (ricercatore nel campo delle teorie
del linguaggio) tale algoritmo ha trovato una prima applicazione
diretta nel campo della linguistica, ed è servito per analizzare la
struttura delle relazioni sintattiche tra le parole: nell'analisi
logica, le unità elementari (complementi, soggetti, predicati,
attributi) hanno relazioni interne ben note agli studiosi del
linguaggio, ma sono rari gli studi quantitativi della struttura che ne
emerge.

[...]

\section{L'importanza delle correlazioni}

Loop structure
Internet e' Markoviana, lo dicono i Loops

La complessità delle reti complesse reali non è rappresentata solo
dalla distribuzione particolare del grado dei nodi. Sin dalle prime
applicazioni interdisciplinari della meccanica statistica, fu chiaro
che anche il {\em clustering}, ovvero la densità di triangoli, è molto
più elevata rispetto al valore aspettato nel caso di una rete del
tutto aleatoria. Lo studio del 

\section{Il WWW è una rete sociale?}

Correlazioni nelle reti dirette
WWW e' una rete sociale?
La soluzione di un paradosso

\section{Wikipedia, una rete collaborativa particolare}

Wikipedia
Reti sociali collaborative
Studio di una rete sociale vera: complessita' di Wikipedia




\begin{thebibliography}{99}

\bibitem{newman01} M. E. J. Newman {\em Phys. Rev. E} {\bf 67}, 026126
  (2003).

\bibitem{vazquez03} A. V\'azques and Y. Moreno {\em Phys. Rev. E} {\bf 67}, 015101
  (2003).

\bibitem{newman02} M. E. J. Newman {\em Phys. Rev. Lett.} {\bf 89}, 208701
  (2002).

\bibitem{capocci03} A. Capocci G. Caldarelli and P. De Los Rios {\em
Phys. Rev. E} 68, 047101 (2003).

\bibitem{kleinberg00} J. M. Kleinberg, in {\em Proceedings of the 32nd
Annual ACM Symposium on Theory of Computing }

\bibitem{bianconi04} G. Bianconi, G. Caldarelli, A. Capocci,
  cond-mat/0408349, to be published in Physical Review E.

\bibitem{barabasi99} A. L. Barabási and R. Albert, 
{\em Science} {\bf 286}, 509-512 (1999).

\bibitem{newman03b} M. E. J. Newman and J. Park {\em Phys. Rev. E} {\bf 68},
036122 (2003).

\bibitem{boguna03} M. Bogu\~n\`a, R. Pastor-Satorras, {\em Physical Review E},
  {\bf 68} (3) 036112 (2003).

\bibitem{catanzaro04} M. Catanzaro, G. Caldarelli, L. Pietronero, {\em Physical
Review E}, {\bf 70} (3) 037101 (2004).

\bibitem{ramasco04} J.J. Ramasco, S.N. Dorogovtsev, R. Pastor-Satorras, cond-mat/0403438

\bibitem{bianconi01} G. Bianconi and A.-L. Barab\'asi {\em Europhys. Lett..},
{\bf 54} (4) 436 (2001)

\bibitem{pastor01} R. Pastor-Satorras, A. V\'azquez, A. Vespignani {\em
Phys. Rev. Lett.} {\bf 87}, 258701 (2001)

\end{thebibliography}

\end{document}