## 5 minutes on the Complexity Theory of `almost’ everything

A simple introductory explanation to what Complexity Theory is. This wonderful world were the Newtonian view of the world fails and where large heterogenous entities create complex systems that need new mathematical tools to process and understand them. It is only 5 minutes but gets to the main points of the field.

## R and iGraph: Colouring Community Nodes by attributes

When plotting the results of community detection on networks, sometimes one is interested in more than the connections between nodes. These network relations are usually multidimensional and you might want to represent other aspects other than the network links between nodes.

Plotting node attributes in R and iGraph might be tricky as the documentation is not always clears. In this example we’ll be using the Davis Dataset from the iGraph repository. This dataset was collected by Davis et al1 in the 1930s and represents the observed attendance at 14 social events by 18 Southern women.

Let’s start by loading network data into R and also load the required igraph libraryigraph is a graph manipulation library that makes it very easy to create, load, analyse, and plot graphs in R. I’ve provided many examples of using igraph but one should really invest some time learning igraph for serious networks and graphs analysis.

```library(igraph) graph <- nexus.get("Davis") plot(graph)```

It is obvious that the plot of the graph is very bland and it isn’t easy to see any natural graph partition. It would be nice to have clusters of people in different colours and shapes. Let’s try to improve the plot by identifying communities in the graph.

## Finding communities

Let’s ignore that this graph is a bipartite graph for now, let’s just try to partition the graph into communities. Is there a natural division? A division of the graph nodes where there are more connections inside the partition than there are connections to other communities? Let’s colour the nodes according to the community they belong:

```graph.com <- fastgreedy.community(graph) V(graph)\$color <- graph.com\$membership + 1 plot(graph)```

To find the communities in the graph, we first use Clauset et al2 greedy algorithm that maximises modularity of the graph in an agglomerative hierarchical clustering. Modularity compares the density of connections inside communities with a null model where connections between graph nodes was random. Then we assign the attribute color according to the graph community membership.

## Change graph node’s shape

As we see the algorithm found 2 communities and at first inspection the division seams reasonable. In any case remember that there's another natural division that the algorithm couldn't find: the bipartite relation Event / Woman. Each node has this other property that says “Is Woman” or “Is Event”. Let's use that to characterise the graph in a different way. We have 14 Events. For these we'll change their shape.

```V(graph)[V(graph)\$type == 1]\$shape <- "square" V(graph)[V(graph)\$type == 0]\$shape <- "circle" plot(graph)```

As we can see, we change the look of the graph in R by changing attributes of the nodes or of the edges. Almost every visual aspect can be changed, from the layout of the graph, to the size of the elements of the graph. This examples illustrated the basic mechanisms to change the plotting of graphs to make them more informative.

1. Allison Davis, Burleigh Bradford Gardner, Mary R. Gardner, Deep south: a social anthropological study of caste and class, University of Chicago Press (1941).

2. A Clauset, MEJ Newman, C Moore: Finding community structure in very large networks, http://www.arxiv.org/abs/cond-mat/0408187

## A caminho da Conferência Europeia de Complexidade #ECCS11

COMEÇA SEGUNDA-FEIRA a Conferência Europeia de Complexidade em Viena.

Esta conferência, que no ano passado decorreu em Lisboa e da qual fiz parte da organização, é a maior conferência europeia (talvez mundial) da área das ciências da complexidade. Apresenta um espectro disciplinar bastante vasto e abrange comunidades empenhadas no estudo de sistemas complexos, que vão desde as ciências sociais à física, passando pela informática, matemática ou análise de redes.

O programa inclui diversos oradores e diversos temas a correr em paralelo pelo que vai ser impossível ver tudo, mas estou particularmente interessado nos temas de análise de redes sociais e computer science principalmente. A ver se consigo apanhar boas sessões.

Para além do que pretendo ver, estou também a organizar um Satellite Meeting para jovens investigadores que estejam a finalizar os seus doutoramentos. Será no dia 14, quarta feira e certamente que aqui estarei um pouco preso, mas tentarei espreitar outros que estejam por perto.

Claro que no meio disto tudo tenho que arranjar um tempinho para passear e conhecer a cidade porque ficar preso o tempo inteiro numa conferência é demais.

Tem algumas sugestões para visitar em Viena?