Introduction to Graph Theory and Complex Network Analysis#
Context#
The start of the journey#
(1735) - Koinsber Bridge’s problem:
The city of Koinsber had 7 bridges connecting different parts of the city.
People wondered if it was possible to cross each bridge exactly once and end up back where they started.
Leonard Euler simplified the problem by representing land areas as circles (nodes) and bridges as lines.
He discovered that for such a path to exist, every area should have an even number of bridges connected to it.
Continental area had an odd number of bridges, making it impossible to find the desired path.
Euler’s solution was a breakthrough in discrete mathematics, specifically Graph Theory.
It helped analyze and solve problems involving networks and connections.
This problem is famous and considered the birth of graph theory.
Traditional social networks#
(1930) Jacob Moreno’s Sociograms:
People were represeted as nodes and their relations by edges that connect them.
Jacob Moreno defines this concept of “Sociograms”. Herem people are presented by vertices or nodes, and their relationships by lines that connect them (which we also call links).
This figure, for example, corresponds shows the affection between people. Symbol (+) and (-) mean good and bad vibes , respectively. The absence of a link implies “neutrality”\(^{(1)}\).
What do we gain by representing a problem in this way?
Why using graphs to represent a problem? All the problems? What type of problems?
Opportunities#
What are the benefits of representing a social problem in this way?
It allows to represent the structure of relations of people.
We can quantify different features from this representation.
What does it mean if one person is connected ti many others?
\(\rightarrow\) proxy of “importance” or “influence” of one person given a network of people.
Relations between people can represent many things (e.g. similar features/interests, affection). Additionally, we can quantify these conections.
We can analyse the structure of the social network and compare different networks (See sub-chapter 4 for details).
We can detect clusters or communities of people based on their interactions and connections.
We can analyse different definitions of “centrality” or “importance” for each person based on their location in the social network (See sub-chapter 5 for details).
We can study how a social network evolves across time (See sub-chapter 6 for details).
A long etc.!!
When to use it?
Whenever the relationship(s) between entities in a dataset are important, then it makes sense to model it as a (di)graph.
In sub-chapter 3, we will see different graph structures that allow us to have assign a value to each connection, and also directions.
Applications#
Due to their large number of applications of graph theory in complex systems, here I will mention some of the many studies that use or are based on graph theory.
Natural Language Processing#
The first application is related to text processing analysis. Rousseau F. and Vazirgiannis M. propose a Graph-of-Words approach to represent a text\(^{(2,3)}\).
There are language processing techniques that often use this “bag-of-word “ representation (which corresponds to an unordered set of term-frequency (TF) pairs; with the assumption that each term is independent of the others).
Here, they propose this concept of “graph-of-word”; The idea is to use a representation that captures the relationships between terms, and that challenges this assumption of independent terms.
In terms of semantics, word order and dependency between words matter (e.g. “Mary is faster than Peter” versus “Peter is faster than Mary” are clearly two different sentences).
In particular, they use a binary directed graph, where the links are the co-occurrences between terms in a fixed time window and the direction of the link represents the order of each term.
Here, the words are connected because there are relationships between words. How are they connected? by the order in which they appear in the phrase or sentence. Therefore, this can be considered a way to “encode”, in our graph-like model, the context in which each word appears.
Computational Neuroscience#
Finally, from this review by De Vico Fallani et al. (2014) called “Graph analysis of functional brain networks”\(^{(6)}\).
They describe what can be done in neuroscience studies with this approach from the study of networks. For example, the nodes of our network can be related to sensors or electrodes that we can use to measure the neuronal activity in people (e.g. Electroencephalogram).
Then, the links that connect these nodes can be defined in multiple ways depending on the research question. Then, we can connect nodes (or sensors) and create a graph, based on neural activity. We can study it statistically or topologically, and then perform studies to find different things.
For example, we can see that maybe the neural responses allow us to correlate variables. Maybe, we can detect when the individual was performing a motor task versus just resting, or distinguish whether an individual suffers from a neurological disease or not, etc.
References#
Maarten van Steen (2010). Graph Theory and Complex Networks. An Introduction (Book).
Rousseau F. & Vazirgiannis M. (2013; ACM Conference). “Graph-of-word and TW-IDF: New Approach to Ad Hoc IR”. Source: https://frncsrss.github.io/papers/rousseau-cikm2013.pdf.
Rousseau F., et al. (2015; Computational Linguistics). “Text Categorization as a Graph Classification Problem”. Source: https://aclanthology.org/P15-1164.pdf.
Batty, M. (2013). The new science of cities. MIT press.
Sotomayor-Gómez, B., & Samaniego, H. (2020). City limits in the age of smartphones and urban scaling. Computers, Environment and Urban Systems, 79, 101423. (Article, https://www.sciencedirect.com/science/article/pii/S0198971519301814)
De Vico Fallani F., et a.l (2014). “Graph analysis of functional brain networks: practical issues in translational neuroscience”. Source: https://royalsocietypublishing.org/doi/epdf/10.1098/rstb.2013.0521.
Social/Urban Computing#
Here, this Batty suggests that cities begin to be studied as complex systems, as a “something” that changes over time and that actually requires people (its inhabitants) to be understood. Specifically, he says that cities fulfill a series of characteristics where people come together to live, and that this necessarily implies a people-places or spaces type of relationship in this city.
With that in mind, we can apply some ideas from graph theory because they talk connections between entities. Connections between people and city spaces.
Defining cities from the trajectories of people (“Eigencities”)
In this study\(^{(5)}\), we can use phone data (internet usage) to know the traces that people from different cities describe in their daily basis. Due to phones are synchronizing data very often, it is possible to have an approximation of the the trajectories of people from different cities in Chile.
Then, we can create a network of connected places based on the number of people who include them in their daily trajectories. By utilizing eigen-vector centrality, a network centrality metric, we can identify the relevance of nodes (i.e., places) are in the network (i.e. city). The objective of this paper is to establish a definition of a city, in terms of geographic boundaries, for urban planning, using this novel approach of interconnected places and non-conventional data.