Before jumping to the graph let's see first, what are data structures ?
It is the structure of organizing data using which some functions or operations could be performed efficiently.
Basically, there are two types of data structures :
1. Linear Data Structure — Array, Queue, Stack, Linked List, etc…
2. Non-linear Data Structure — Trees, Graphs, etc…
In this blog, we are going to focus on Graph Data Structure. So let's start…
Contents:
1. Definition of Graph
2. Types of Graphs
3. Real-Life Applications of Graphs
1. Definition of Graph
A Graph is a non-linear data structure that consists of nodes (vertices) and edges joining vertices. Data in the node depends upon the use of graphs.
In our daily life routines, we use graphs for finding the shortest possible route to someplace using GPS, to get suggestions of nearest restaurants, cinema theatres, etc. You also get some friend suggestions on Facebook, Twitter, and LinkedIn which also uses a graph data structure for implementing such super cool features. Ok! so that’s enough talk about the uses of the graph data structure, now let’s dive deeper into it…
2. Types of Graphs
I. Directed Graphs:
It has some particular direction of edge and A->B will not be equal to B->A here.
For Example, When you travel from some location to some other location, it is mandatory that the graph should start from the starting position of the journey and should end at the destination address. These graphs are also known as digraphs.
II. Undirected Graphs:
Here the direction of the edge is not mandatory, which means A->B will be equal to B->A. Here all the edges are bidirectional.
For Example, (In Chemistry) When there is covalent bond formation in two elements, it is very crucial that they should share the electrons or pair of electrons and not donate it.
It’s like the associativity of two Facebook users after connecting as a friend, both users can share photos and comments with each other.
III. Weighted Graphs:
Graphs whose edges have some values and these values have different types depending on the application of the graph.
For Example, Length, Cost, Weight, etc…
Some uses of weighted graphs are :
● GPS uses traffic and distance to calculate the fastest route.
● LinkedIn recommends people with more weight matching to your profile and connections.
IV. Complete Graphs:
In this type, each vertex of the graph is joined with every other vertex of the graph. So this type is a subset of Regular Graphs. The number of edges associated with each vertex is equal to one less than the total number of nodes.
V. Connected & Disconnected Graphs:
In the Connected type of graph, all the nodes or vertices are connected and no discontinuity is there.
In the Disconnected type of graph, there is some discontinuity and that’s why they are known as disconnected graphs. That means there is no edge between some nodes or some part of the graph.
VI. Bipartite Graphs:
In this type of graph, we can divide the graph into multiple parts. Let’s say a graph is divided into A, B, and C subparts as shown. There is no connection between the nodes in subgraph A, B, and C but there are connections between subgraph A, subgraph B, and subgraph C.
VII. Cyclic & Acyclic Graphs:
If there are some cycles inside the graph or the entire graph is cyclic such that when you start from a point in the cycle you can end at the same point. So, this is a cyclic type of graph.
In acyclic type, there are no cycles inside the graph, and traversing it from one point to another will surely not end at the same point.
An example of acyclic graphs is Tree Data Structures.
VIII. Planar Graphs:
As the name suggests this graph is strictly planar, which means there will be no intersections of any edges. The diagram is given below with both the cases.
3) Real-World Applications of Graphs
1. Google Maps
Have you ever wondered, how exactly the map services work ? What is the theory behind it ? How we can find the shortest possible route from one destination to another with the help of google maps ?
To find the shortest path, map services use graph theory. Consider an example that we have ‘A’ as the starting node and ’N’ as the destination node. Then all the other places between the start and destination node can also be assumed as nodes. These nodes will be connected horizontally and vertically with weighted edges. Here, weighted edges represent paths. Thus, all these nodes and edges represent a network of roads as a directed graph.
2. Social Networks
How many friends do you have on Facebook? How many friends do your friends have? And their friends? Facebook can answer this question with surprising accuracy. They store on their servers an internal graph representation of the human social network.
A digitized social network describes each user as a graph vertex and each friendship relation as an edge between two users. The hundreds of billions of friendship relations in the Facebook social network together build a graph data structure of a massive scale.
Each time you use Facebook Graph Search, Facebook runs an algorithm on this graph data structure.
Each time a Facebook user wants to learn about who is an influencer in a certain field, they run a graph algorithm (simple or complex). Such a graph algorithm can determine your position in the network. It can use the graph structure to predict the flow of information.
The important application scenario for graphs is social network analysis.
3. The World Wide Web
The web is a huge collection of documents pointing to each other via hyperlinks. In other words, the web is another massive graph data set.
You can model the web as a graph by treating each web page as a graph vertex and each hyperlink as a graph edge.
Many business models of large companies (such as Google) revolve around analyzing the massive web graph.
Think about it: what does the Google search really do? Given your information need, Google needs to present you with the most relevant piece of content from this huge web graph. If they do a good job (they do), they satisfy your information need. Being satisfied with the service causes you to reuse it again and again.
The problem is that it’s still difficult for machines to differentiate between good and bad content. 99% of the content on the web you would consider as trash. How does Google bot know which content has high quality?
This idea is the basis of Google’s famous PageRank algorithm. It is an iterative graph algorithm that determines the rank of a web page (higher is better) based on the summed ranks of web pages linking to them. To know their rank we look into the summed ranks of web pages linking to them. As you can see, this is an iterative procedure that refines the ranks of all the web pages one step at a time. After converging, the PageRank algorithm gives a pretty accurate measure of how trustworthy and renowned a web page is.
Ok, let’s go back to the question: what are application scenarios use cases of graphs in computer science? The business models of the largest companies in the world, with billions of dollars yearly profits, center around efficient processing and information retrieval from large graphs.
4. Product Recommendation Graphs
know about how the company owned by the richest man on the earth (Jeff Bezos’ net worth is 141 Billion US-$ in 2018) uses graphs to boost its revenue. Amazon. If you buy a product, Amazon recommends you buying similar products. These recommended products are based on what other users have already bought. For example, you buy a book about Python; Amazon recommends you to buy a book about Scrum.
Amazon knows for each user, which products he has bought (and liked). It’s a bipartite graph. On the left side are all the users. On the right side are all the products. If a user has bought (and liked) a product, there is a connection from the user to the product. The graph is bipartite as there can not be a connection between two users or two products. (Neither can a user by another user nor can a product buy another product.)
So the graph problem which Amazon solves is the following. Given the existing user-product graph. What are some likely edges from users and products? We can do this by clustering users together that bought the same products.
It is likely that users will buy similar products in the future as well. Those are the recommendations provided by Amazon. While the algorithms are much more sophisticated, this remains the main idea.
5. Circuit and Computer Chip Placement
Graph algorithms are also important in many other domains and use cases. For instance, the field of computer chip design relies on resource-efficient ways to place signals on a single chip. The numerous signals must be embedded onto the two-dimensional plane.
6. Knowledge Graphs
The knowledge of the world is inherently graph-structured. Information A is connected to information B if A stands in relation to B in some specific way.
Few people know that it’s possible to access this knowledge graph gathered by Google. Google provides an API that you can easily use and play around with.
Think about the opportunities for massive knowledge graphs that are shared among devices all over the world! The emerging collective intelligence makes applications smarter — even without high computing power.
So in this way Graphs are used in various day-to-day life applications. And I hope that from this blog you got to know how graphs help in doing so…
