# Leonhard Euler and the seven bridges of Konigsberg: The beginning of Graph Theory

Standard

Today is the 306th birthday of Leonhard Euler, a great mathematician who developed different insights not only in mathematics, but also in Physics disciplines like mechanics, optics and astronomy. He developed a lot of work in mathematics among which he stated the bases of Graph Theory and Topology.

It was solving a problem related with a circuit formed by seven bridges in Königsberg, city of Prussia (Now Kaliningrad Russia). This city was situated at the border of the Pregel River. As is showed in the figure below, inside the city there was a circuit of the river. This position made this city very important for commerce. In order to connect the city, the habitants built seven bridges that connect all the points of the city and allowed them to cross from one landmass to the other.

The problem started when in 1736 the mayor Carl L. Gottlieb wanted to have a circuit using the bridges such a way that starting from one point it be possible to cross for all the bridges only once. As in the Village they didn’t found a solution, the mayor asked Euler for help to found a solution.

Although Euler at the beginning didn’t accept to solve this problem, may be because he found this so trivial, he started to work in this because it seems to be related with some work in geometry that Leibniz had discussed in one of his publications and that called `geometria situs` i.e., “geometry of position”. This geometry of position derived in what we know now as Graph Theory.

Developing the mathematics needed to solve the problem, in 1735, Euler presented his paper called “Solutio problematis ad geometriam situs pertinetis“ in which he exposed the mathematical bases of Graph Theory.
In that paper he stated the general question to the problem: Can one find out whether or not it is possible to cross each bridge exactly once?
After his analysis and develop of this new mathematics, he found that this problem does not have solution, in fact he conclude that:
• If there are more than two landmasses with an odd number of bridges, then such path is impossible.
• If there are exactly two landmasses and the number of bridges is odd, then the path exists if it starts in one of the two odd numbered landmasses.
• If there are no regions with an odd number of landmasses then the path can be accomplished starting in any region.
In this paper Euler worked with vertices and edges as now a day are used in Graph Theory and Network Theory. That is why when a path in a graph use each edge of the graph once and only once, is called an Eulerian path.
Due the nature of the problem, and the simplicity of the solution using nodes and edges, this is a very important problem and initial point to start learning Graph Theory and Network Theory.

# Network Structure

Standard

The importance of the networks is being extended to the technological and economic systems, which are becoming in real complex networks. This complexity and the instability of the behaviour of these systems put them in a high risk of turning localized breakdowns that evolve into cascading failures and or financial crisis.
A network analysis of these systems could help us to know what these points of potential breakdown are, and how we can help to solve the conflict. That is why is important to know how the networks looks like, visualizing these systems and making a network analysis of their networks we may found key information that make possible a prediction of the problem, and with time develop solutions that help us to prevent this potential problems.

Most of the measures in networks have their origin in Graph Theory. Graph theory, help us to study the shape of any network (topology of the network) and analyze it mathematically.
Then, there are taken from graph theory different tools to make possible this analysis.

Fig. 1 Weighted and directed Network of the dataset of the characters1 in the novel “Les Miserables” from Victor Hugo.

Figure 1, shows the network formed from the relationships that exists among the characters in the novel of Victor Hugo “Les Miserables”. This is the aspect of a network. This network has been made using Gephi, and it will be useful to explain the different elements that constituted a network.
We can find two essential elements in figure 1: nodes and links. Then the figure shows a collection of elements that in this case are the characters of the novel and that are represented by the color circles. The size of the circle represents the importance of this character. Each circle is called “node” in graph theory and network analysis. By other hand, the lines that connect the circles are called the links. The links represents the relationships that exist among two characters. i.e., if there exist a relation among the characters, then one line will be depicted linking them, if not, there not exists this line. The link thickness represents how strong this relation is.

(1) D.E. Knuth, The Standford GraphBase: A platform for combinatorial Computing, Addison-Wesley. Reading, MA (1993).

# The information as a network structure

Standard

How the information is diffused in the actuality is a very important deal in which many companies have been focused in the last years.
The importance of the spread of the information in the digital world may be seeing as a course in which the winners are the people that have more tools to spread their information faster and to the right people. Also, the objective is not only to increment the amount of target persons if not incrementing the interest of these persons over the information that is being transmitted.
The traffic of this information, the target actors (people), the source of the information, the other important people that may be interacting with this information and that may bloc it, and how all these elements are connected may be visualized as a network. The network visualization allows us to analyze all these factors and to have enough information to plan and make decisions if the objective is to improve this spread of information.
Then, understanding any one of the elements that integer this network we are going to gain understanding over the dynamics of the community to which we are linked and to which we want to send information.

Standard

# Networks

Today is a time of connectedness. Modern society is facing a great spectrum of forms to express their ideas and connect with people into the whole world. This connectedness may develop different sources of information. In fact, the connectedness is a source of information. From all the social networks that in this moment exist in the web, we can extract a lot of tendencies, modes and data thhat allow us to know about what is going on in different sectors of the society. And, it could be helpful to know more about this tendencies and modes. Analyse what people want at this moment and to predict what people could want in the future may be an advantage.
A tool that we may use to visualize and analyze this data is the Network Theory. A network is a pattern of interconnections among a set of things. We may find networks at home, at the office, at the market, etc. In all these networks the essential element is the communication, or information transferring. Then in each discussion, or commentary in which we found an interchanging of ideas among different actors, we found a network.
In society we found a diversity of networks that by its nature may be constituted by strong or weak ties. We found the basic network that is the family which in fact constitutes the unit of the society (strong ties), after this, we found the friend’s network that may contain strong and weak ties. These networks have become more complicated and complex with the technologic advances since at this moment we can share information and have more contact among all the elements (persons) that constitute the networks.
The technological advances like the facility of distant travel, the global communication and the digital interaction in fact may be considered like another parallel network that interact and helps to develop our social network.
So, the network’s study has become more fascinating with the pass of time and has acquired a lot of importance in our lives. That is why their knowledge, characterisation and study is becoming more important in this blog.

# SES’s Sustainability

Standard

As it was mentioned, both social systems and ecological systems are considered as complex system due its emergency and the interaction among their agents. But also the system composed from the imperative relation among them is indeed a complex system. More precisely a Complex Adaptive System. Actually, this relation has a great importance due to the increasing threaten from the human systems towards the ecosystems. This system has been named as Social-Ecological-System (SES).

The SESs have a hierarchical base, and the sustainability depends on the interactions of this hierachical structure.  Then before an assessment of the sustainability could be made, is necesary to understand how this system is composed. This means that the definition of the interacting agents in both, the social system and the ecosystem, is needed.

The sustainability of each natural resource is a function of the interactions among the internal and external factors. The internal factors may be social, political, ecological, or economic; while the external factors include foreing debt, structural poverty, gobal environmental problems, and social/political/economic conflicts. For all internal factors have been assigned indicators of sustainability and for the external ones have been identified a set of attributes (1).

All of this interactions among internal and external factors increments the complexity of the SES’s sustainability.

(1) Holling, C.S., “Understanding the Complexity of Economic, Ecological, and Social Systems” Ecosystems (2001) 4:390-405.

Standard

CAS may be viewed as systems composed of interacting agents which behaviour is described in terms of rules. Each of these agents that form part of the system has its own behaviour that adapt by changing their rules as experience accumulates. The problem is that considering this adaptability in each part of the system, the CAS’s behaviour  abound in  nonlinearities. This problem is at the same time the beauty of the system because from this, the system reach the adaptation, and “adaptation is the sine qua non of CAS” (1)

Due the interconnectivity between all the agents that compose the CAS, each of them exerts an influence over the others. It has as consequence that all change in the behaviour of one of the agents affect the behaviour of the total system. Considering that the agents are in constant change because the continuum process of learning-adapting, then the CAS shows a temporal adaptation that is coherent  with the change of all of its parts.

Among the CAS’s examples that exist in the nature is important o mention the economic, ecological and social systems. The social problems, and the ecological ones are considered to be complex because their emergency. Both of them have been studied from a complex system perspective introducing methods of statistical physics and has been considered like CAS (2).

(1) Holland, J.H. “Hidden Order How Adaptation Builds Complexity” 1996 Perseus Books Cambridge Massachusetts.

(2) Pascual, M., and Dunne, J.A. 2006 “From Small to Large Ecological Networks in a Dynamic World.” In Ecological Networks Linking Structure to Dynamics in Food Webs, ed. by M. Pascual, J.A. Dunne Santa Fe Institute Studies in the Sciences of Complexity 3-24 Oxford University Press.

# The social-ecological relationship from a network perspective

Standard

Like the social problems, the ecological ones are considered to be complex because their emergency. Both of them have been studied from a complex system perspective introducing methods of statistical physics and has been considered like Complex Adaptive Systems (CAS) (1). Now, the relation between them has more importance due to the increasing threaten from the human systems towards the ecosystems. Then, a new concept of system has been created, and from any years it has been developed, the Social-Ecological-Systems (SESs).

The sustainability of these systems is an important theme now a day. Scientist have been developed many theoretical approaches that may help in the assessment of the sustainability of these systems. There are many case of study, but the problem is that all of them are very particular. Most of them, may be the oldest, are located in the fishery, some of them in the forestry, but there are not a general model that may be applied over more global circumstances. Now is imperative to develop a method that enclose more systems or at least, that its parameters may be evaluated and discriminated in agree with the problem that is wanted to be analysed.

Considering that this is a complex system that have many variables and parameters and that all of them are interconnected and, more over, exists an interdependency among them, result a great idea to apply Network Theory (NT) to the study of these systems. And as these are complex systems, in consequence, the network must be a Complex Network (CN).

(1) Pascual, M., and Dunne, J.A. 2006 “From Small to Large Ecological Networks in a Dynamic World.” In Ecological Networks Linking Structure to Dynamics in Food Webs, ed. by M. Pascual, J.A. Dunne Santa Fe Institute Studies in the Sciences of Complexity 3-24 Oxford University Press.

# Statistical Physics, complex systems and social problems

Standard

The concepts of Statistical Physics have been applied in several ways to the study of the economic and social problems. This has generated divers approximations and models that may be applied under different circumstances and with different objectives.

One of them is the study of the social hierarchies considered in the Bonabeau model. The emergent collective behaviour of the elements integrating the social systems has been the primordial characteristic to consider the application of the statistical physics concepts in their analysis.

The model of social hierarchies of Bonabeau is based in the creation of artificial societies that follow certain group of rules. (1) This model is able to describe the transition of societies from egaletarian to more hierarchical ones. The artificial agents that appear in the results of this approach may be substituted by animals, individuals, communities, countries, etc., depending the problem that is being analyzed.

However, despite the simplicity of the model, it has showed not be so close to reality. In order to improuve the model it has been modified, over all in the rules that follow the agents, giving approaches more realistics and with extended applicability (2).

Due to the complexity of the system, and the idea of introducing a ”lattice with dynamical distribution of attractive sites coupled with the agent distribution”(2), and in order to improuve the analysis, may be good propose the use of a dynamical network that helps to link the agents and the sites by means of dynamic links and dynamics sites, in such a form that each agent may have a memory of their movements but also a knowledge of the movements of the other agents.

(1) E. Bonabeau, G. Theraulaz, J.L. Deneubourg, Physica A 217 (1995) 1157.

(2) G.G. Naumis, M. del Castillo-Mussot, L.A. Perez, G.J.Vazquez, Physica A 369 (2006) 789-798