Notes on Graph theory — Part 1
A series of easy to grasp notes on graph theory for curious learners
Why am I creating this notes?
As a curious learner, I find myself consuming an important quantity of material in order to stay updated in my favorite fields or build a solid base to enter new ones. This large quantity of material after being understood needs to be stored in order to be used in the future.
That’s why I've launched a personal project (hope I can finish this one …) called the Brain Box which is a collection of easy to read, small and compact notes that will help me and the interested community fresh in up with informative and important material without the need to waste hours reading long papers or watching infinite YouTube playlist.
This collection of notes will be short and direct, with examples to help you understand.
Let's start with graph theory!
Why do you need to study graph theory?
Two months ago I was reading about Graph neural networks being the trend in the machine learning field. I understood that data needed as input for every ml model can’ t always be expressed in a euclidean space (vectors, matrix …) but can be more than simple values, a collection of features with connections that have meaning, for example: molecules, social networks, and others form of networks, and so we need a type of model that is compatible with this datatype input.
Graph neural networks can be the solution to analyze and process this type of data but working with them needs a pre-study of graphs: its mathematics and anatomy.
Studying graph theory will not just give you a getting started to understand GNN but will help you discover a new world: the network's world where I personally enjoyed projecting its concepts as centrality or diffusion on real-world applications as local roads network near my city or my favorite series cast relations.
Graph-theory: overview
In this first article, I 'll try to introduce graphs as an object by giving its definition and its mathematical representation since we will need it for later.
- Graphs definition
Graphs are everywhere it's a well-suited tool to present data where connections and links are important for us to understand it. Like molecules structure that presents a collection of basic atoms which are linked to other, forming complex structure where each atom's connection in this collection means something's in terms of the usage or the characteristics of this molecule, in fact, changing one of this connection can give you a totally different molecule.
This example will help us understand the basic anatomy of a graph that is generated by a bunch of nodes that are connected by edges. Basic anatomy? Yes, but keep adding these nodes and edges and you can create some complex networks that ever existed. Take the example of Facebook where nodes are users and edges are friendships or follows.
- Graph mathematical presentation
As said, graphs can build up to become a complex structure, take the Facebook social network. Thus, it will be hard to study it just by observing it visually, so for that, we need to build mathematical tools that will help us understand or analyze our graph structure.
We start with the graph definition as a mathematical object. A graph is defined by its set of nodes and set of edges so it's trivial that a graph G will be defined as :
N denotes the set of nodes in our graph and E is the set of edges we also define the norm of our graph as the number of nodes
- Adjacency matrix
As I said earlier we can't just use the geometrical shape of graphs to analyze them, but we need some sort of tools that encapsulate the information in our graphs and also easy to do mathematical analysis on it.
For this, we define the adjacency matrix as binary 2d array n*n where n denotes the number of nodes. Each value can be either 1 if the two nodes are linked else it will be 0. And as you see in the example the adjacency matrix is symmetric for the undirected graph (a type of graph structures) we will see more about this in the next stories.
Conclusion
As you might see I used this article to introduce an interesting project that I'm working on and I hope you'll use this as motivation to start on your personal notes. I didn't want it to be just about the project but I wanted to start as soon as possible with the informative content.
Graphs are very interesting especially with its structure and its many applications and projection on real-life.and this story was just the beginning of a series on graph theory where we will understand more about its structure and how to analyze it.
PS:
Each story I'm using one of the hand-style notes (first media in this story) that summarize the content of the article feel free to keep it since it will be easy for you to freshen up each time you take a look at it as I said previously once you understand the content, an easy to go note will do the work.
Sources :
- Materials
- Sketching tool
