Why the search intent is more complex to classify

Analysing and modeling the user search intent goes beyond the simplistic categorisation of informational, navigationals, transactional and commercial. Users are quite complex and the purpose of their search can’t be easily inserted into the four boxes of categorisation that is common in most search platforms, articles and commentaries.

The search intent is usually conceived as the purpose behind a search. Keyword search data on third party software tools, Google Search Console and Google Keyword planner are a goldmine for data-centric marketers. The user intent should focus on the purpose, motivations and reasoning behind a search. There are user stories, prompts and triggers around the public and private  keyword data. Reducing use intent to general actions that suit us as marketers deprives us from gaining deeper insights as to why users are searching in the first instance.  

Continue reading

A simplified analysis of the 0-1 knapsack problem

In our previous article, we touched on the Travelling Salesman problem and highlighted how it belongs to the subfield of combinatorial optimisation. The topic of combinatorial optimisation seeks to discover the most efficient object from a finite set of items.  The three main combinatorial optimisation problems are Travelling Salesman Problem (TSP), Knapsack problem and Minimum Spanning Tree (MST). Our focus will be on the Knapsack problem in this article. A subsequent piece will touch on MST. 

Diving  into the Knapsack Problem

Let’s now assume a deeper look into the logic of the Knapsack Problem. The decision version of the Knapsack problem is considered NP-Complete. Firstly, we will briefly examine the problem statement. Providing a set of objects with attributable value and weights (Vi, Wi), what is the maximum value that can be attained when the sum of the subsets of these objects are selected to be within the knapsack capacity.

Continue reading

Exploring the Traveling Salesman Problem (TSP)

Graph theory seeks to address different situations or problems in business application or organisational setups. TSP (Traveling Salesman Problem) is usually considered NP-hard (nondeterministic polynomial time) in solving decision problems. This is because there are more than one possible action or directions when deciding to traverse through every city or vertex in a given graph with the goal or returning to the original. Taking some journey down the historical lane, the TSP problem was formulated in1800s by an Irish mathematician W.R Hamiltion and his British counterpart Thomas Kirkman. 

Continue reading

Understanding Articulation Points in a graph with examples

Graphs can be directed or undirected in nature. Articulation points are quite important in a graph as they signal possible vulnerabilities in a given network. Removing a node from a connected undirected graph is likely to split the network into different components of an undirected graph. 

A simple illustration of articulation points 

The undirected graph below contains seven nodes and there are two articulation or critical points. Node B is very important to the network as it directly connects with five nodes. Removing node B will break this graph into three disconnected components. The three disconnected graphs after removing node B will be (A) , (C and D) and (E, F and G). The second articulation point on this graph is node C. A decision to remove node C will lead to two disconnected components which are nodes (A, B, E, F, G) and (D). This clearly shows that node B and C are the two articulation points with B being slightly more critical. Node B is the most critical because if removed it renders the remaining graphs into three disconnected components. On the other hand, removing vertex C splits the graph into two disconnected components.

Continue reading

A practical understanding of topological sorting and ordering 

The shortest path problem is pivotal in graph theory. It aims at discovering the “most efficient’ or ‘best’ way of moving from x to y, where x and y are both nodes in a given graph. The most efficient or best in this context is evaluated by the lowest sum of edge weights between the path of both vertices. The shortest or quickest path is arrived at by summing the lengths of the individual edges. A best-case scenario is a graph with edges having positive weights. There is also the concept of single-source shortest path problem with s as the source node. For clarity, the source node initiates the transversal within the graph.

Continue reading

Exploring Breadth First Search and Depth First Search in a graph

You might have encountered the words, breadth and depth in real-world scenarios. Breadth implies the complete range of knowledge of any given subject or topic. On the other hand, depth in terms of learning touches on the degree to which a particular subject is magnified or explored. Let’s begin with the breadth first search or the BFS of a given graph. Now BFS does not refer to Best Friends from school but Breadth-First Search. 

Exploring Breadth First Search or Breadth First Traversal 

BFS is an algorithm that is designed to search for a graph or tree data formation. It usually travels in a breadthward motion and utilises a queue as a prompt to identify the next vertex to commence a traversal. If a roadblock is encountered or no adjacent node is found, the tree root or the source node is removed for the queue. The traversal of the graph usually begins with a ‘search key’ or the initialising node. Imagine a hotel with so many floors and rooms as nodes, a breadth-first traversal algorithm is like a cleaning staff that will clean rooms floor by floor. All neighbouring nodes at the current depth or floor with the example above will be visited to clean before moving to the vertices or rooms on the next floor. No node is expected to be revisited as one would not expect hotel staff to clean the same room twice in the same period. Once a room is cleaned, it is ticked on a sheet as a visited while with BFS, the neighbouring reversed node is enqueued or marked as visited, 

Continue reading

Finding the mother vertex in a graph 

Networks or graphs are pivotal in so many real-world applications such as fraud prevention systems. search engines, recommendation systems, social networks and a lot more. The search for the mother vertex of a graph aids in understanding the accessibility of a given vertex or collection of vertices. 

What is the meaning of the mother vertex in a given graph?

In a given graph G = (V, E), a mother vertex v has a pathway for all other vertices in the specified graph to enable the connection. All other vertices in the graph can be accessed via the mother vertex. A mother vertex is quite common in directed graphs but is also applicable in undirected networks. We will briefly explore mother vertices in different network examples

Continue reading

The role of the betweenness centrality measure in networks 

Ever wondered how to detect the most influential individual, station, motorway or node in a network? It is not a normal popularity test but a mathematical way for determining a node with the most impact in the flow of information within a network. A very good way of determining nodes that are great connectors for moving from one point of a graph to another. In a real-world situation, when these nodes are removed, the movement to other nodes in the graph becomes quite challenging. With betweenness centrality, the number of paths a node is a part of is also revealed. In a connected graph, the Betweenness Centrality algorithm calculates the shortest path between nodes in the given network. The weight between nodes is quite important in determining the shortest path as factors such as frequency, capacity, time, flow and influence determine these weights. 

Continue reading

Exploring Dijkstra’s shortest path algorithm

Several graph algorithms can help reveal hidden patterns in connected data. These algorithms can be classified into several categories such as approximations (e.g clustering), assortativity (e,g average neighbour degree), communities (e.g K-Clique) and centrality (e.g shortest path). In this blog, we will be looking at one of the most popular shortest path algorithms known as the Dijkstra’s algorithm. We will look at an example table and code implementation for this algorithm. Shortest path algorithm can be relevant in a traffic network situation a user desires to discover the fastest way to move from a source to a destination. It is an iterative algorithm that provides us with the shortest path from an origin node to all other nodes in the graph. This algorithm can work in weighted and unweighted graph scenarios. 

Continue reading

The impact of bridges in a graph 

In graph theory, a bridge is an edge whose removal leads to the disconnection of the network. It is usually found in undirected graphs and can also be viewed within the context of disconnected undirected graphs. In these disconnected undirected graphs, removing a bridge leads to a further separation of the subgraphs. Let’s explore some examples below. 

Bridge in an undirected connected graph:

The below graph is undirected but it is connected. There are 9 nodes and 10 edges in this graph. You can determine that one edge is in red and the rest are in grey/black. The edge in red is the bridge and removal will lead to a disconnection of node [L] from the rest of the graph. Assuming all of these nodes were train stations and the edges are London tube lines.  A rail track maintenance work, shortage of control room staff or a broken train on the track are some of the reasons that can cause a train line that connects node [H] to node[L] to become disconnected or temporarily removed from the train network or graph. When this occurs, people living close to the station [L] will become stranded or short of transportation options. This is a connected graph because the disconnected unit is not a sub-graph on its own but a single node stranded and possibly struggling in the network.  

Continue reading