Social Network Analysis Algorithm (SNA) Request
I got the task to make a social graph where, with one user in center , it shows the connections he has.
But before we can achieve that, we'll focus on how we can determine the shortest path between two users.
I found some algorithm for this, but it seems like it takes a long time and because it is about social links, we are looking for the one that is the fastest because we will need to run it on a regular basis to keep up with updates in friends.
So, do you know what is the fastest way to determine the shortest path between two users?
PS: If you know an example in PHP and MySQL, I'll give you a virtual beer (or coke).: D
a source to share
what you want is a "all pairs of shortest path" algorithm ; if you need to generate pairs globally for the graph, this is faster than running the shortest path algorithm for each pair. saving this update is another issue - note that you will have to do this every time you add a graph connection, not just every time you add a person. if it's for a production site it might be worth keeping the graph generation as a standalone task written in a language faster than php and writing its results back to db. you will probably find existing C ++ implementations.
a source to share
It seems to me that if you draw the entire graph anyway, the easiest thing would be to keep track of each person's paths as they are added to the graph. So, for a person's friends, the path is simply "main person → friend". Then, when you add each of your friends to the graph, keep the path "main person -> friend 1 -> friend 2" and so on.
If the picture in my mind is accurate, this seems like the easiest way to do it, but I am perhaps a little misunderstood.
a source to share
Diysktra's algorithm works well on weighted graphs. In a social graph, all edges have the same weight. Thus, Dijkstra's algorithm becomes BFS. However, on a dense graph, the list of nodes considered at each level will be huge. One of the optimizations you can make is to start searching at both ends (A and B).