November 5, 2018 at 9:29 am #238
Learn how to compute degree of connection on LinkedIn using BFS in this guest post by Devangini Patel, the author of Hands-On Artificial Intelligence for Search.
LinkedIn is a social network and users are connected to each other through first or second-degree connections. In order to better understand this concept, use the following diagram as a reference:
Suppose Dev wants to find an acquaintance named Jill and connect with her. When he goes to her profile, he finds that she is a second-degree connection, which means that they have a mutual colleague. To understand how this degree is computed you’ll first have to create a connection tree:
1. Start with the profile node, Dev, and add it to the connection tree:
2. Now, find Dev’s colleagues and add them beneath Dev’s node: Ali and Tom
3. Now, for both Ali and Tom, find their colleagues and add them beneath their nodes. So, under Ali, add Dev, Seth, and Ram, and under Tom, add Dev, Seth, Kai, and Jill:
4. Now, for each of these nodes, find their connections and add those as well:
In the above diagram, the connections to Dev have been added (due to space constraints, this is not shown). For Seth, find his connections (Ali, Tom, and Harry) and add them underneath his name. For Ram, add Ali and Jill.
Similarly, due to space constraints, the connections for Dev and Seth haven’t been shown here, as they are already shown in the diagram. Under Kai, add his connection, Tom. Finally, when you come to the node for Jill (to add her connections), you find that this node has the goal state, so you end your search here.
You may have noticed that Jill appears as a connection to Ram at the bottom of the tree, but if you consider the bottom node, then the connection degree is 3, which is not the least value.
However, because a BFS search processes the search tree level by level, you can find the least path solution. You can also see that there are people that appear multiple times in this connection tree. For example, Dev, Ali, and Tom appear three times each, while Seth and Jill each appear twice.
So, keep the first entry of the node in the connection tree and remove the other instances; the following diagram shows how the search tree should look:
When you add the node to the search tree, you should check whether it already exists in the search tree.
The State class indicates the condition of the search process and has to be changed for every application, even though the search algorithm is the same. It’s time now to look at the State class for this application.
First, you need a property to track the condition of the search. In this case, the property is the person under consideration. Then, you’ll need four methods:
Take a look at each of these three ingredients in detail. To find the initial state, you should ask yourself the question, where do I start searching from? In this application, you start searching from Dev’s profile. To find the successor function, you should ask yourself, how do I explore from the current state?
In this application, the function should return the people connected to the person under consideration. So, for Ali, it should return all of his colleagues. Finally, to find the goal function, you should ask the question, how will I know when I’ve found the solution? The goal function should return true if the person is Jill.
Now take a look at the State class code:
... from GraphData import * class State: ''' This class retrieves state information for social connection feature ''' def __init__(self, name = None): if name == None: #create initial state self.name = self.getInitialState() else: self.name = name def getInitialState(self): """ This method returns me. """ initialState = "Dev" return initialState def successorFunction(self): """ This is the successor function. It finds all the persons connected to the current person """ return connections[self.name] ...
As shown in the above code, in the
State.pymodule, you’re importing all of the variables from GraphData. The purpose of GraphData will be explained in the Graph data structure section. In the constructor, the name argument is passed. If the argument name is None, then the initial state is created, and if the name is provided, that name is assigned to the name property.
initialStateproperty holds the value Dev, and the
successorFunctionmethod returns all of the people connected to the current person. To get the people connected to the person, use connections from GraphData:
` def checkGoalState(self):
This method checks whether the person is Jill.
#check if the person’s name is Jill
return self.name == “Jill”`
checkGoalStatefunction returns true if the current person’s name is Jill.
Hope you’ve understood how the degree of connection is computed. If you found this article interesting and want to learn more about AI for search, you can explore Hands-On Artificial Intelligence for Search. Packed with step-by-step instructions and working examples, the book takes you through the different search methods in a comprehensive manner, and is a must-read for developers keen on getting started with AI and building practical AI-based applications.
You must be logged in to reply to this topic.