You are currently browsing the tag archive for the ‘graph theory’ tag.

Video – “Be the one” track on Moby‘s Destroyed album. Destroyed is the tenth studio album by the American electronic artist Moby. It was released on 2011 by Mute Records. Network video animation by Taras Gesh.

From time to time some colleagues, students and friends do ask me what is a good introductory paper into Complex Networks. Indeed there are several, including some general books, but over the years I tend to point into “The Shortest Path to Complex Networks” by J.F.F. Mendes (thorough my life I met him several times now) and S.N. Dorogovtsev, released in 2004. For those who are beginners on the field, and do want to play or indeed program several concepts in the area, like clustering, small-worlds, edge condensation, cliques and communities as well as the preferential attachment (point 20.) among others, this is a rather simple and quick (besides is 25 pages) straightforward paper, well organized around 51 different entries, topics and concepts. Not all of them are here of course, like, among others, the age node issue which for several reasons tends to interest me. Point 1 starts with the birth of network science and it’s simple as : […] In 1735, in St Petersburg, Leonhard Euler solved the so-called Konigsberg bridge problem – walks on a simple small graph. This solution (actually, a proof) is usually considered as a starting point of the science of networks […]. The full paper is available through arXiv.org. Here is the link. Do enjoy. Like Moby says… be the one. The full reference list is also a must.

Caption – 1st page of Erdös, P.; Rényi, A. (1960). “On The Evolution of Random Graphs“. Magyar Tud. Akad. Mat. Kutató Int. Közl. 5: 17 [PDF].

Documentary film – “N is a Number: A Portrait of Paul Erdös” directed by George Csicsery | 1993 | 57 min. (9 parts)

There are three signs of senility. The first sign is that a man forgets his theorems. The second sign is that he forgets to zip up. The third sign is that he forgets to zip down“, Paul Erdös.

Paul Erdös was an immensely prolific and notably eccentric Hungarian mathematician. Erdös published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory. He wrote around 1,475 mathematical articles in his lifetime, mostly with co-authors. He strongly believed in and practised mathematics as a social activity, having 511 different collaborators in his lifetime (source).

Having no home, while globe trotting the world from place to place, living mostly for short periods in friend’s and colleagues houses, almost as if he was travelling from one set of mathematics, to another, it was not only the quantity of his work which was tremendous, but mainly the quality and impact of his works. It was not rare, that a single paper, produced a entire brand new field of research. One of my favourite examples, it’s his paper with Rényi on random graphs (image caption above): Erdös, P.; Rényi, A. (1960). “On The Evolution of Random Graphs“. Magyar Tud. Akad. Mat. Kutató Int. Közl. 5: 17 [PDF]. Alone, this single 5 pages paper emerged a  new science branch, critical in our times: Complex Networks. The work is now being cited +2500 times.

Fig. – Erdös and Rényi (1959, 1960, 1961) were the first to introduce the concept of random graphs in 1959. The simple model of a network involves taking some number of vertices, N and connecting nodes by selecting edges from the N(N-1)/2 possible edges at random  (Albert and Barabási 2002; Newman 2003). Figure shows three random graphs where the probability of an edge being selected is p=0, p=0.1 and p=0.2. (a) Initially 20 nodes are isolated. (b) Pairs of nodes are connected with a probability of p of selecting an edge. In this case (b) p=0.1 , (c) p=0.2, notice how the nodes become quickly connected. The Erdös and Rényi random graph studies explore how the expected topology of the random graph changes as a function of the number of links. It has been shown that when the number of links is below 1/N, the graph is fragmented into small isolated clusters. Above this threshold the network becomes connected as one single cluster or giant component. We now know, that at the threshold the behaviour is indeterminate  (Strogatz 2001). Random graphs also show the emergence of subgraphs (below). Erdös and Rényi explored the emergence of these structures, which form patterns such as trees, cycles and loops. Like the giant component, these subgraphs have distinct thresholds where they forming different patterns (below).

Fig. – Different subgraphs appear at varying threshold probabilities in a random graph (Albert and Barabási 2002)

[...] People should learn how to play Lego with their minds. Concepts are building bricks [...] V. Ramos, 2002.

@ViRAms on Twitter

Archives

Blog Stats

  • 254,863 hits