Graph Theory: The Solution for Your Complex Relationship.

A Not-too-Brief Introduction of Graph Theory to Network Analysis.

Quick Journey to the Begining of the Graph!

Let’s start our journey with time-traveling to 18th century — or 1736 to be specific!

Figure 1. The Map of Königsberg, Prussia. (source)

It’s 1736, there was a genius yet curious man named Leonhard Euler lived in Königsberg, Prussia. He was — presumably — sitting at his desk, with a dilemma. At that time, Kongsberg (modern day Kaliningrad, Russia) was divided by the Pregel River into four sections which were connected by seven bridges. And he asked a simple question — yet it will turn out to be a beginning of a great theory.

“Can we take a walk through the city that would cross each of the seven bridges only once?”

Figure 2. The clear illustration of Konigsberg Bridge (source)

With his abstract way of thinking, he ultimately found a solution to this problem — and this will be the foundation of the Graph Theory.

Maybe you are now curious how his abstract way of thinking. He just made a simple drawing of several nodes and lines that connects between nodes. He realized that it wasn’t the land masses themselves that were important, but rather the bridges that connected them.

Figure 3. Graph representation of Konigsberg Brigde (source)

He demonstrated the each land mass as an abstract vertex called node and connecting each other with the abstract line called edge. Soon, this drawing will be known as a graph. From this abstract drawing, Euler could show that there is no answer for his question. There’s no way we can travel to each land mass without crossing the bridge at least twice.

While the initial effort may not have seemed worthwhile, the use of graphs to model and analyze data has proven to be valuable. In addition to the inherent value of the data itself, the connections and relationships between data can provide even more insights. By creating or inferring connections between records, significant insights can be gained from a dataset.

Your Social Life — But make it as a graph!

Maybe the bridge example above is too hard to be understood for you. Don’t worry, we got you! Maybe we can look another example that is very close to you — and also to me or everyone else.

Um, I don’t usually stick my nose to one’s business, but let’s look it up in you social life!

Let’s say, you are married to a woman named Omega. You have four close friends: Amanda, Bob, Charlie, and Daniel. And your wife has three close friends: Alpha, Beta, and Gamma. Your friend, Amanda is working for Unikloh, a retail store. And, so does your wife’s friend, Beta. Maybe it’s a little bit complicated if you read the paragraph above, but let’s make it a simple explanation with A GRAPH!

Figure 4. The sketch of graph of your social life.

Every single person or object in your social network is represented as a vertex or in the graph theory it is called as node, and the interaction or relation is represented with an arrow called edge. You can see that the arrow can represent from which to which the relation is and every edge is labeled with the interaction or relationship status. Actually, you can complete the graph with the properties of each person so it can represent a complete information of your social life with the abstract way. Additionally, you can add a weight for the edge. Like the closeness rating between you and your friends or anything else. It’s totally up to you!

Figure 5. Sam is also working for Unikloh. How likely Sam knows both of you?

Let’s say, Sam is also working for Unikloh too. Based on the size of the company and the type of relationship and interaction, we can infer that Sam also knows Amanda and Beta. But the question is, how likely Sam knows both of you — you and your wife, Omega? This question can be answered with a graph — or to be specific, with a network analysis.

A.M. Chiesi, in the International Encyclopedia of the Social & Behavioral Sciences, stated that “Network Analysis (NA) is a collection of methods used to represent the relationships between actors and to study the social structures that arise from the repetition of these relationships. The fundamental belief is that a better understanding of social phenomena can be gained by analyzing the connections between individuals or entities.”

Fun fact!

According to six-degree separation theory, you are on average six or fewer social connections away from Jisoo Blackpink. Go contact your friends and friends of your friends now!

Transactional Dataset + Network Analysis = Valuable Insight!

Things are getting serious now. How can network analysis help you dig the valuable insight from your dataset? Well, let’s take a deep look how it can help you to get the valuable insight from your data.

• It helps you to determine most important entity with centrality analytics. Imagine, you create a graph for tweet analysis. Every time someone retweets a tweet (node), it will make an outflow arrow to show the connection from the tweet to the account that retweeted it (edge). At a glance, you can see that the most hit tweet will be the tweet that has number of outflow edges the most — and you can conclude that this tweet is the most important among the others. You also may count the degree of centrality — ratio of a total actual neighbor of a node compared to a total possible neighbor of a node —to make you be more confidence with your analysis. This analytics can help you to find the key entities such as finding the most influential people in the social network or finding the hub in the transportation.

Figure 6. A hit tweet can be determined with the centrality degree of a tweet.

• It helps you to find the path with connectivity analytics. Ever get lost of something? Well, network analysis can help you to find the right way! In centrality analytics, the focus is on identifying important nodes, while in connectivity analytics, the focus is on understanding the unique characteristics of a node’s connections, such as the difference between incoming and outgoing edges. This analytics can help you to detect fraudulent users and to whom they interact with (and also its pattern)!

Figure 7. Ever get lost when trying to watch Dark serial? Well, Network Analysis can help you! (source)

• It helps you to find a group of people that can create a ‘community’. Imagine a TikTok video of a cute cat purring and we represent it as a node and the edge is the like sent from the user. We can discover “the cat lover” community from this node because they send like to this cute cat purring video. Mapping connections between entities can reveal the communities within the network, which can be used to generate recommendations.

Figure 8. Cat lovers community can be found through the interaction of this image (if this image has like button) (source)

• It helps you to find shortest path. It is mainly used in weighted graph. You can figure out how to reach the most efficient way to travel from two cities with this weighted graph. The weight itself can represent the cost or maybe the time needed to travel. There is Djikstra’s algorithm to tackle this problem.

Figure 9. Need to go somewhere to accomplish a mission? You can find the shortest path from the map above with Network Analysis!

Conclusion — It’s not a Goodbye!

Well, it’s not a goodbye. Now you know that this over-a-century-years-old concept of mathematics is actually can be used and such a powerful thing in this modern day. In the end, it’s important to have a good understanding of your data and to try out different ways of representing it in a network or graph!

In the next post, we will deep dive to the python script for graph modeling and we will get into machine learning. So, stay tuned! Cheers.