Discussion on Algorithm Improvement for Bidirectional Friend Recommendations

[Akshay02022]

Hey @juninhokaponne ,

I hope you're doing well. I was going through the project, and I must say it's quite interesting. I've reviewed the functional requirement document and noticed that your algorithm currently focuses on unidirectional recommendations.

To clarify, in the current setup, if 'A is a friend of B, A is a friend of C, B is a friend of D, C is a friend of D and E,' and we ask for a recommendation for A, the output will be D and E. However, for entities B, C, D, and E, there would be no recommendations, resulting in an empty response.

My question is whether we are intentionally focusing on implementing unidirectional relationships, or if we have the flexibility to enhance the algorithm to consider bidirectional relationships as well. In other words, if A is a friend of B, it implies that B is also a friend of A.

I hope this clarifies the objective I wanted to discuss. Looking forward to your insights on this matter.

[juninhokaponne]

Excellent point @Akshay02022, I'm glad you liked the algorithm, I really appreciate your question and even more so for taking the time to read the requirements document even though it hasn't been translated into English yet. PS: I'm sorry about that, I'll fix that too

As for the main question, initially, the algorithm was proposed to be a unidirectional recommendation system, thus respecting the limits of recommendations and resulting in the point where you highlighted entities B, C, D, and E not having recommendations.

However, I would like to add this two-way flexibility to the algorithm, allowing it to provide recommendations not only for the originating user but also for the connections of the user. This would make the system more comprehensive and useful for all the users involved.

I'm open to suggestions and contributions for this enhancement. If you have ideas or insights on how to effectively implement this functionality, I would greatly appreciate hearing them and working together to make the algorithm even better. Let's collaborate to make this project more robust and useful for all users. Thank you again for your interest and contribution!

[Akshay02022]

Hey @juninhokaponne , I've considered two approaches for achieving bidirectional relationships, and the first one is as follows: Approach 1: When we create a relationship by posting data with the body { cpf1: 'cpf1', cpf2: 'cpf2' } and push it into the relationship array, we can simultaneously add another object with { cpf1: 'cpf2', cpf2: 'cpf1' } to establish the bidirectional link.

Here's a code snippet:

However, there are downsides to this approach, one being that it makes us store the same information twice, essentially doubling the amount of data we need to save.

Approach 2: When recommending friends of friends for a given user (userCPF), we can check for cpf1=usercpf or cpf2 = usercpf in relationship array to find friend and similar to find friendofFriend. Here's a pseudo code snippet that concentrates on the underlying logic: In controller/RelactionshipController.js

Please note that this code may look messy for now because it's primarily focused on the logic.

I hope you've grasped the concept and approach I'm trying to convey. I've tested both of these logic segments, and they function as anticipated.

If you have any alternative approaches in mind, I'd appreciate it if you could share them. Collaboratively, we can work towards enhancing the algorithm further.

[juninhokaponne]

Both approaches are very interesting, I took a look at the pseudocode and both really work. The first example I found to be very robust and with an easy level of applicability for the code as it is a simple and quick solution, despite storing some duplicate items, it is a leaner and more favorable approach for the maturity of the current project.

I believe that the second option would be the most ideal because it will have to scan the relationship matrix to find the desired data, which can also be slower in large volumes of data.

Another point is that the logic can be more complex, especially when finding friends of friends efficiently.

My suggestion is, we can do it in the second way, taking some points into consideration.

1. Data Storage: When creating a relationship, we can add just a single record in the relationship matrix. This will save storage space and avoid duplication.

2. Time Complexity: The time complexity of this approach to finding friends of friends will be O(n), where "n" is the total number of relationships. If the number of relationships is large, we will have to consider optimizing this operation.

3. Cache: For frequently executed operations and the number of relationships is very large, we can consider using a cache system to temporarily store the results and avoid frequent queries/operations to the relationship matrix.

let me know your opinion and feedback.

[Akshay02022]

To achieve the points you've mentioned, I can only think of using a graph data structure to achieve the desired time complexity. Here's how the algorithm works:

• Data Structure Setup: Create a new data structure called RelationshipIndex, which is essentially an adjacency list. It uses each person's CPF as the key and their connections (friends) as the value in an array.

• Building Relationship Index: Populate the RelationshipIndex by iterating through the relationships array and adding connections for each person.

• Recommendation Algorithm: When you input a userCpf to get recommendations: Step 1: You retrieve the list of friends of the userCpf from the RelationshipIndex. Step 2: For each friend in the user's friends list, you get their list of friends (friends of friends) using the RelationshipIndex. Step 3: You check for each friend of a friend's CPF if it's not equal to the userCpf and if the user's friends list doesn't include that friend of a friend's CPF. Step 4: If the conditions are met, you add the friend of a friend to the friendOfFriends object and recommend them in sorted decreasing order.

I hope you have grasped the algorithm, which I believe is currently the most optimized solution I can come up with. I've tested it, and it performs as expected.

Regarding the cache system, I plan to implement it shortly, but I'd like to hear your validation and opinion on this approach first.

Additionally, I've made some changes in the createRelationship section, and I have a few questions about the usage of the validateCPF middleware. Should I create a new issue or discussion thread to discuss these matters in more detail?

[juninhokaponne]

Perfect approach, it seems to me that it is well designed, I confess that it is an exciting feature, I analyzed the code and it really looks good that way. This way it will be possible to scale the algorithm for bidirectional recommendations, which is great.

Good job, you can send me the PR when it's ready and I can give the code a final review and merge it to release another release with this new functionality added to other new ones I've been working on on the project and other contributors.

Regarding middleware, take a look at this issue, perhaps it is the problem you reported, if it is the same, there is a collaborator working on the refactoring.

https://github.com/juninhokaponne/friendRecommendation/issues/6

If not, feel free to open a new issue.

[juninhokaponne]

Your PR was merged! Thanks for the contribution again.