THINK COMPLEXITY�Allen Downey�2018

​

Downey, Allen. Think Complexity: Complexity Science and Computational Modeling (Function). Kindle Edition.

https://www.allendowney.com/wp/

Complexity Science!!

• Campo interdisciplinario que se encarga de estudiar sistemas complejos. Describe componentes entrelazados entre sí y que no son separables, aunque sin tener un efecto en la totalidad que lo conforman. Múltiples partes interconectadas que interactúan de manera no lineal.
• Componentes en constantes interacción entre sí: componentes vecinos. La interacción, retroalimentación caos, autoorganización, recursividad hacen parte del entendimiento de las relaciones.
• Modelos dinámicos de segregación. Thomas Schelling
• Cambios de criterios.

​

Diferentes modelos/ diferentes propósitos

• Predictive - explanatory
• Realism - Instrumentalism
• Reductionism - Holism
• Centralized - Decentralized
• One to many - many to many
• Top down - bottom up
• Isolation - Interaction
• Design - search
• Frequentist probability - Bayesianism

​

Graphs

• systems made up of components and connections between components.
• graph is a representation of a system that contains discrete, interconnected elements. The elements are represented by nodes—also called vertices—and the interconnections are represented by edges.
• Edges have attributes like length, cost, or weight.
• Directed or undirected, depending on whether the relationships they represent are asymmetric or symmetric.
• path is a sequence of nodes with an edge between each consecutive pair.

​

Directed

Undirected

NetworkX

• Libreria de Python

​

• G = nx.DiGraph()
• G.add_node('Alice')
• G.add_node('Bob')
• G.add_node('Chuck')
• >>> list(G.nodes())
• NodeView(('Alice', 'Bob', 'Chuck'))

G.add_edge('Alice', 'Chuck')

G.add_edge('Bob', 'Alice')

G.add_edge('Bob', 'Chuck')

>> list(G.edges())

[('Alice', 'Bob'), ('Alice', 'Chuck'),

('Bob', 'Alice'), ('Bob', 'Chuck')]

​

Random grahs

• a graph with nodes and edges generated at random. Of course, there are many random processes that can generate graphs, so there are many kinds of random graphs.

​

• Erdős-Rényi graph (ER graph) is characterized by two parameters: n is the number of nodes and p is the probability that there is an edge between any two nodes. is p*=(lnn)/n, where n is the number of nodes. A random graph, G(n,p), is unlikely to be connected if p<p* and very likely to be connected if p>p*.

​

• Generating Graphs: a graph where every node is connected to every other. Here’s a generator function that takes a list of nodes and enumerates all distinct pairs.

​

Connected graphs

• Esta conectado si hay una ruta desde cada nodo a todos los demás

​

​

ER conectado

Figure 2-4. An ER graph with n=10 and p=0.3.

​

Erdős-Rényi (Probabilidad de conectividad)

• Modelo G(n,p)G
• n es el número de nodos (vértices) en el grafo.
• p es la probabilidad de que exista una arista entre dos nodos cualesquiera.
• En este modelo, se comienza con n nodos y se añade cada arista posible de manera independiente con probabilidad p.
• Modelo G(n,m)
• n es el número de nodos.
• m es el número exacto de aristas que se colocan aleatoriamente entre los nodos.
• En lugar de asignar probabilidades a cada arista, simplemente se seleccionan m aristas de manera aleatoria entre los nodos.

​

Analisis de los algoritmos

• Analiza el redimiento de los algoritmos, a partir de mirar los tiempos de ejecución a medida que aumenta el tamaño de los gráficos.

​

Small World Graphs��

• La distancia promedio entre nodos, medfida en el numero de bordes en el camino más corto, es mucho menor que lo esperado.
• Experimento de Stanlye Milgram (obediencia de las persons a la autoridad) Enviar cartas si conocia a las personas
• Watts and Strogatz. Empezaron con dos grafos: aleatorios y regulares. En el primero los nodos se conectan al azar, en el regular, cada nodo tiene el mismo número de vecinos. Tiene en cuenta la agrupación en clusteres y la longitud de la trayectoria. Crearon el coeficiente de agrupamiento que mide la probabilidad de que dos nodos que están coectados al mismo nodo, estén conectados entre sí. La longitud del camino mide la distancia media entre dos nodos.