Clusterizando meus amigos

Ontem eu fiz um experimento com alguns resultados interessantes: peguei uma lista de todos os meus amigos do Orkut e os amigos deles. Alem dos nomes, sei quem eh amigo de quem. Meus amigos do IME estao conectados nos meus amigos do IME, e meus amigos do segundo grau estao conectados nos meus amigos do segundo grau. Entao olhando, deveria ser facil perceber os clusters de amigos. Mas como fazer isso automaticamente? Nao eh uma tarefa tao trivial dado que tenho amigos da faculdade que conhecem meus amigos da escola e vice versa. Mas existem algumas arestas cruzando essas comunidades. Uma solucao que vi recentemente foi usar metodos espectrais: de forma geral voce calcula os autovalores da matriz de adjacencias e plota os amigos no plano de acordo com os coeficientes dos autovetores. Eu escrevi um blog post mais tecnico sobre isso no meu outro blog, explicando um pouco mais a intuicao por tras de metodos espectrais. O resultado foi o seguinte:

Depois que o grafico jah estava montado, eu olhei quem era cada vertice e colori da seguinte maneira: azul os meus amigos da faculdade, verde os meus amigos da escola, amarelo as pessoas da minha familia e vermelho os demais q nao se encaixavam em nenhuma das categorias anteriores (e as pessoas que usam caracteres esotericos no seu nome do Orkut que eu nao consegui parsear). O algoritmo conseguiu claramente separar os meus amigos da faculdade dos meu amigos da escola e conseguiu tambem colocar as pessoas da minha familia mais ou menos proximas (e em nenhum momento o algoritmo usou as cores, elas soh foram fornecidas depois). E tambem mostrar que elas estao mais conectadas aos meus amigos da escola do que os da faculdade.

Uma imagem maior e com os nomes nos vertices estah aqui.