## Thinking in Minimum Spanning Trees

Minimum Spanning Trees are subgraphs of a graph that are TREES and connect all vertices together such the total cost of connection is minimal. Because of that, they are interesting objects.

Minimum spanning trees have many application, from routing in movement application to traversing of databases. My favorite is to define use in game AIs, by computing cost of travel for characters according to the kind of terrain they have to travel through.

## A Background on Spanning Trees.

• First, TREES, What are they? For any two given nodes have only one path between them and all nodes have one path between them. In 1857, Cayley coined the term TREE and it stuck though many graph TREES don’t have any resemblance to real trees.
• Trees have no cycles, thus, no transitivity, no triangles, no clustering coefficient. Trees are efficient when the cost of establishing connections is high (think for example subway lines that are costly to build).
• Minimum Spanning Trees are the optimisation of the COST of trees. If the graph is unweighted the cost is unitary and all edges are equal — and one can have multiple equivalent Minimum Spanning Trees. If the graph if weighted then you’ll have a unique Minimum Spanning Tree (usually).

## MST Algorithm

An ALGORITHM to compute minimum spanning trees for a weighted undirected graph is the Prim’s Algorithm — although it was proposed 27 years earlier by a Czech mathematician called Vojtěch Jarník and the algorithm should be named after him (sometimes it is).

Here’s an example how the algorithm runs:

Spanning trees are very important because they are used in pathfinding algorithms like in the Dijkstra’s algorithm or in the A* Algorithm.

## Spanning Tree in R and igraph

In R, the igraph package implements the Prim’s algorithm when computing minimum spanning trees.

A simple example of the use of the minimum spanning tree in R follows:

```library(igraph) g <- erdos.renyi.game(20, 0.25) E(g)\$weight <- runif(length(E(g)), 0., 1.) E(g)\$width <- 3.0*E(g)\$weight   mst <- minimum.spanning.tree(g) E(mst)\$color <- 'red'   layout <- layout.kamada.kawai(mst)   plot(g, layout=layout) par(new=T) E(mst)\$width <- 3 plot(mst, layout=layout) par(new=F)```

The image that illustrates this post on minimum spanning trees is one run of the short code above. I generated a random graph with 20 nodes and a probability of connecting any two of 25%. Then I gave the edges random weights and computed the weighted Minimum Spanning Tree. The trick of how to plot a minimum spanning tree superimposed on the original graph is to do it in a two-step plot. First you plot the graph with a pre-computed layout. Then you use the same pre-computed layout to plot the second layer that holds the minimum spanning tree.

You need to set the parameter new=True so that the R plot doesn’t erase the previous one. You can compute the layout for the minimum spanning tree if you want edges not to overlap and obtain a clear planar graph. iGraph offers many different graph layouts to experiment from. Kamada Kawai usually works very well for minimum spanning trees.

## Grafo do conhecimento do Google

Cada vez mais a indústria percebe que mais importante que os directórios de informação (Yahoo), é preciso estabelecer relações entre os dados que se acumulam. As relações sob a forma de gráfos, (p.ex Q-analysis) está a revolucionar a forma como a indústria está a alterar os seus produtos. Agora o Google pretende mudar o paradigma da empresa passando de um serviço de procura para um serviço de conhecimento. Esperemos que isto não seja apenas mais um dos muitos projectos que ao fim de algum tempo é engavetado.

## Some Graph/Network libraries for Python

Either for Social Networks Analysis, for Multi-agent simulation or Text mining, networks are everywhere and everyone seems to be producing their own library. Here’s a quick collection of some popular libraries that integrate well with Python (among other things).

NetworkX (1.4) – http://networkx.lanl.gov/ Python Full python and slow for large number of nodes.

igraph (0.5.4) – http://igraph.sourceforge.net/index.html python extension module, R package, Ruby gem or as C library Finding it very useful to use with R <- integrates perfectly with other thing I do in R.

boost – http://www.boost.org/ C++

## Presidenciais 2011: Diz-me com quem votas…

Hoje, o dia posterior ao dia mais frio do ano, perdão, ao dia das eleições presidenciais, decidi meter-me a brincar com os resultados (inspirado pelo excelente trabalho do António) para o Observatorium. Assim peguei nos 308 concelhos e fui procurar quem vota similarmente a quem.

Eleições Presidenciais: Quem votou com quem? (clique para ver em grande)

Cada concelho tem o resultado representado por um vector de 6 componentes (os candidatos). Entre todos os pares (a,b) de concelhos é calculada a similaridade de votação através do co-seno do ângulo formado entre a e b (cos(a^b))

cos(a^b)=a.b/(|a||b|)

onde a.b é o produto interno e || representa a norma do vector.

Depois a partir da matriz de similaridade foram estabelecidas apenas as ligações com valor de cos(a^b)>0,9995 e removidos todos os concelhos que tinham grau zero (zero ligações) para facilitar a leitura da rede e aí temos, os concelhos que votam da mesma forma que outros.

É curiosa a formação de alguns clusters inesperados, mas a análise política deixo para outros.

Já agora os dois municípios mais antagónicos do país? Vale de Cambra e Santa Cruz

Vale de Cambra Cavaco Silva    61.76% Manuel Alegre    15.15% Fernando Nobre    14.54% José Coelho    4.39% Francisco Lopes    2.95% Defensor Moura    1.21%

Santa Cruz José Coelho    47.78% Cavaco Silva    36.32% Fernando Nobre    7.36% Manuel Alegre    6.13% Francisco Lopes    1.67% Defensor Moura    0.75%

## Análise de Redes Sociais – Lista de Software

A winter school do ciências da complexidade do ISCTE vai decorrer entre 11 e 15 de Janeiro. Este ano é dedicada a representações formais para a representação e análise de estruturas de redes sociais.

Já aqui fiz uma lista de software para análise de redes sociais, mas a verdade é que há sempre algo novo, algo que permite mais alguma coisa. Últimamente tenho olhado para dois softwares em particular: Um é o networkX, escrito em Python e que permite manipular programaticamente o mundo dos gráfos. O outro é o R, o pacote para tratamento estatístico de dados open source que juntamente com o algumas bibliotecas o tornam muito interessante para manipulação de redes.

E com isto tudo a lista que estava algures aqui está um pouco desactualizada pelo que é preciso adicionar algumas coisas:

R Statnet – Uma meta-biblioteca com dependências de uma variedade de outras bibliotecas do R e que torna muito fácil instalar tudo o que é preciso para trabalhar com redes no R.

## Desenhar grafos em Python

O python facilita muito a vida para desenvolvimento rápido de grafos e redes, principalmente quando estas tem que ser construídas a partir de ficheiros externos de dados. Normalmente uma combinação de python e awk pode resolver todos os problemas numa fracção do tempo das outras linguagens.

No entanto para trabalhar e desenhar redes há dois pacotes que decidi serem importantes:

### networkx

está excelente desde que se utilize a versão SVN. As versões normais para download tem 1 bug muito importante que é não ser possível exportar os grafos para um formato que se possa utilizar posteriormente. Na versão do SVN esse problema parece já estar corrigido e portanto pode-se utilizar o pacote para exportar o grafo no formato GML. Update: Nas últimas versões do networkx está tudo ok. Altamente recomendado para desenhar grafos/redes. A programação é muito pythonesca o que ajuda quem estiver embrenhado em python. Permite prototipar rapidamente ideias.

### pyNetConv

O pyNetConv é basicamente um conversor de formatos de grafos. Este software pode ser integrado como módulo mas tem também uma GUI para fazer conversões entre formatos de redes. A minha utilização serve para converter o formato GML para Pajek (.net) uma vez que algum software que utilizo não conhece o GML. Não é actualizado há mais de 10 anos, pelo que pode nem sempre funcionar.

### igraph para python

O igraph tornou-se nos últimos tempos a minha ferramenta de eleição para trabalhar com grafos, logo seguida de networkx. O igraph possui a vantagem de poder ser utilizado tanto em python, como R. Para além disso permite manter uma consistência de nomenclatura nas várias plataformas.

Com estes pacotes é possível utilizar python para estudar teoria dos grafos de forma simples. Todos apresentam imensos exemplos de como gerar e plotar os grafos.