Per Bak and Kim Sneppen Model

The Per Bak and Kim Sneppen evolution model is one of the most simple and at the same time more elegant ways to show self-organised criticality.

The above demo is part of a vaster set of animations illustrating complex systems that I’m in the process of coding in javascript and P5. I had coded a Bak-Sneppen model a long time ago in Java, but this is nicer.

If you would like to see a particular example coded, or want to contribute, head on to github and either fork the dave.complexity or make your suggestions in the issues.

Traversing News with Second Order Swarm Intelligence

David MS Rodrigues Reading the News Through its Structure New Hybrid Connectivity Based Approaches

Figure – Two simplicies a and b connected by the 2-dimensional face, the triangle {1;2;3}. In the analysis of the time-line of The Guardian newspaper (link) the system used feature vectors based on frequency of words and them computed similarity between documents based on those feature vectors. This is a purely statistical approach that requires great computational power and that is difficult for problems that have large feature vectors and many documents. Feature vectors with 100,000 or more items are common and computing similarities between these documents becomes cumbersome. Instead of computing distance (or similarity) matrices between documents from feature vectors, the present approach explores the possibility of inferring the distance between documents from the Q-analysis description. Q-analysis is a very natural notion of connectivity between the simplicies of the structure and in the relation studied, documents are connected to each other through shared sets of tags entered by the journalists. Also in this framework, eccentricity is defined as a measure of the relatedness of one simplex in relation to another [7].

David M.S. Rodrigues and Vitorino Ramos, “Traversing News with Ant Colony Optimisation and Negative Pheromones” [PDF], accepted as preprint for oral presentation at the European Conference on Complex SystemsECCS14 in Lucca, Sept. 22-26, 2014, Italy.

Abstract: The past decade has seen the rapid development of the online newsroom. News published online are the main outlet of news surpassing traditional printed newspapers. This poses challenges to the production and to the consumption of those news. With those many sources of information available it is important to find ways to cluster and organise the documents if one wants to understand this new system. Traditional approaches to the problem of clustering documents usually embed the documents in a suitable similarity space. Previous studies have reported on the impact of the similarity measures used for clustering of textual corpora [1]. These similarity measures usually are calculated for bag of words representations of the documents. This makes the final document-word matrix high dimensional. Feature vectors with more than 10,000 dimensions are common and algorithms have severe problems with the high dimensionality of the data. A novel bio inspired approach to the problem of traversing the news is presented. It finds Hamiltonian cycles over documents published by the newspaper The Guardian. A Second Order Swarm Intelligence algorithm based on Ant Colony Optimisation was developed [2, 3] that uses a negative pheromone to mark unrewarding paths with a “no-entry” signal. This approach follows recent findings of negative pheromone usage in real ants [4].

In this case study the corpus of data is represented as a bipartite relation between documents and keywords entered by the journalists to characterise the news. A new similarity measure between documents is presented based on the Q-analysis description [5, 6, 7] of the simplicial complex formed between documents and keywords. The eccentricity between documents (two simplicies) is then used as a novel measure of similarity between documents. The results prove that the Second Order Swarm Intelligence algorithm performs better in benchmark problems of the travelling salesman problem, with faster convergence and optimal results. The addition of the negative pheromone as a non-entry signal improves the quality of the results. The application of the algorithm to the corpus of news of The Guardian creates a coherent navigation system among the news. This allows the users to navigate the news published during a certain period of time in a semantic sequence instead of a time sequence. This work as broader application as it can be applied to many cases where the data is mapped to bipartite relations (e.g. protein expressions in cells, sentiment analysis, brand awareness in social media, routing problems), as it highlights the connectivity of the underlying complex system.

Keywords: Self-Organization, Stigmergy, Co-Evolution, Swarm Intelligence, Dynamic Optimization, Foraging, Cooperative Learning, Hamiltonian cycles, Text Mining, Textual Corpora, Information Retrieval, Knowledge Discovery, Sentiment Analysis, Q-Analysis, Data Mining, Journalism, The Guardian.

References:

[1] Alexander Strehl, Joydeep Ghosh, and Raymond Mooney. Impact of similarity measures on web-page clustering. In Workshop on Artifcial Intelligence for Web Search (AAAI 2000), pages 58-64, 2000.

[2] David M. S. Rodrigues, Jorge Louçã, and Vitorino Ramos. From standard to second-order Swarm Intelligence phase-space maps. In Stefan Thurner, editor, 8th European Conference on Complex Systems, Vienna, Austria, 9 2011.

[3] Vitorino Ramos, David M. S. Rodrigues, and Jorge Louçã. Second order Swarm Intelligence. In Jeng-Shyang Pan, Marios M. Polycarpou, Michael Wozniak, André C.P.L.F. Carvalho, Hector Quintian, and Emilio Corchado, editors, HAIS’13. 8th International Conference on Hybrid Artificial Intelligence Systems, volume 8073 of Lecture Notes in Computer Science, pages 411-420. Springer Berlin Heidelberg, Salamanca, Spain, 9 2013.

[4] Elva J.H. Robinson, Duncan Jackson, Mike Holcombe, and Francis L.W. Ratnieks. No entry signal in ant foraging (hymenoptera: Formicidae): new insights from an agent-based model. Myrmecological News, 10(120), 2007.

[5] Ronald Harry Atkin. Mathematical Structure in Human Affairs. Heinemann Educational Publishers, 48 Charles Street, London, 1 edition, 1974.

[6] J. H. Johnson. A survey of Q-analysis, part 1: The past and present. In Proceedings of the Seminar on Q-analysis and the Social Sciences, Universty of Leeds, 9 1983.

[7] David M. S. Rodrigues. Identifying news clusters using Q-analysis and modularity. In Albert Diaz-Guilera, Alex Arenas, and Alvaro Corral, editors, Proceedings of the European Conference on Complex Systems 2013, Barcelona, 9 2013.

Atravessando a Europa por causa da ECCS13

In Barcelona for ECCS13

Após uma viagem muito divertida atravessando Espanha, finalmente chegamos a Barcelona. Cansados, com um GPS que tinha deixado de cooperar (NDrive nunca mais, onde anda o meu velhinho TomTom?) e indicava uma distância para o Hotel de 34Km, mesmo quando já estávamos dentro do mesmo. Ainda assim, e fugindo a uns pingos de chuva lá fomos até à Rambla para procurar comida (com a nossa sorte ainda teríamos que acabar abrindo uma garrafa de Vinho Verde e o presunto de Salamanca que estavam no carro).

A conferência europeia de sistema complexos (a finalidade para a qual esta viagem foi feita) bateu todas as expectativas. Mais de 1000 participantes estiveram no World Trade Center de Barcelona (porto de abrigo do muitos paquetes e cruzeiros que se realizam no mediterrâneo). O sucesso da conferência para os próximos anos parece assegurada (Lucca em Itália será perfeita) mas torna difícil selecionar com critério o que ver, tantas que são as sessões paralelas. Para além disso o último dia foi mais fraco, até porque muitos (como eu) se fizeram à estrada.

O caminho de volta à ilha levou-me para Norte, por Girona e FIgueres do lado espanhol e por Beziers, Millau (onde atravessei o fantástico viaduto Millau do Norman Foster) para terminar em Clermont-ferrand.

O dia seguinte levou-me ainda mais para norte onde atravessei a mancha no comboio de automóveis (Já viram a beleza que viajou comigo?)

No total de foram mais de 30h a conduzir (13 de Lisboa para Barcelona, 7 de Barcelona para Clermond-ferrand e 12 de Clermond-ferrand para Milton Keynes). No fim desta viagem penso que já não direi mal da Easyjet quando me trouxer de regresso a Lisboa.

Social Network Analysis em R e algum arrumar de casa

A área de Social Network Analysis está cada vez na actualidade científica e não só. Em 2010 leccionei numa Winter School uma cadeira sobre sobre Software para Análise de Redes Sociais no qual dei uma achega à utilização do R1 para análise de redes. O R não é só útil para análise de redes sociais, servindo para produção de documentos com gráficos de forma automática e reprodutível, análise estatística variada, manipulação de big data de forma rápida, etc… Na verdade o R é uma verdadeira mula de trabalho que se presta a diversas fases da manipulação e análise de dados.

Na área da Social Network Analysis (SNA) o R apresenta alguns packages que merecem ser analisados. Um deles é o package igraph que é possui muitas das funcionalidades necessárias para o estudo de redes, desde a produção de grafos segundo determinados modelos, análise de propriedades, detecção de comunidades… O próprio site do igraph tem um livro online sobre o igraph que pode ajudar quem se inicia neste package. Quem estiver a estudar SNA pela primeira vez pode ver também os tutoriais de Hanneman, embora em alguns casos não seja utilizado o R, mas outros softwares como o Ucinet ou o Pajek.

Para quem se estiver a iniciar no R no entanto há outros tutorias ou apresentações que ajudarão a entrar na linguagem. Se precisam de uma introdução em português vejam estes pdfs produzidos no IST aqui e aqui.

Duncan Watts promovendo Obvious*

Duncan Watts continua a promoção do seu Everything Is Obvious: Once You Know the Answer. O livro não é o melhor livro alguma vez escrito sobre influência social, não é sequer muito original e não será certamente uma obra fundamental, mas dá uma visão global dos desafios que as ciências sociais (e não só a sociologia) estão a atravessar na era em que se fala de Big Data.