1. Given two users u1 and u2 can we predict they will be friends after n updates to an evolving graph like facebook
1.1. Facebook's Friend Suggestion is an implementation of a solution.
1.1.1. http://stackoverflow.com/questions/1283587/how-does-facebook-generate-suggestions
1.2. Some key terms
1.2.1. Affinity Scores
1.2.1.1. Affinity Score means how "connected" a particular user is to the Edge. For example, I'm friends with my brother on Facebook. In addition, I write frequently on his wall, and we have fifty mutual friends. So I have a very high affinity score with my brother
1.2.1.2. Source - http://edgerank.net/
1.2.2. Edges
1.2.2.1. Every action that a user takes creates an edge, and each of those edges, except for clicks, creates a potential story. So when user A adds another user B to his friend list, a new edge connects node A to node B. Even actions such as liking or commenting leads to edge creations.
1.3. Assumption
1.3.1. We become friends with someone else most of the time due to the presence of a mutual friend.
1.3.2. If say A and B are friends with a particular affinity score. Let's say that B has a friend C who is having a very similar affinity score . Then A and C are good candidates for becoming friends
1.3.2.1. This could be the case in which the three people had studied in the same college as to why the affinity scores match.
1.3.2.2. So n updates could be the time taken for the affinity scores of two users to become in the range where we could say there is something common between these 2 people.
1.3.2.2.1. In other words when the affinity score reaches a particular number , there is almost a certainity that the two users will become friends in facebook
1.4. Challenges
1.4.1. Facebook's edge rank algorithm is not in public domain and need to come up with another algorithm based on similar concepts of affinity score
1.4.2. Need to get data for training and validation purpose .
1.5. Some scientific literature found online
1.5.1. Exploiting Sentiment Homophily for Link Prediction
1.5.1.1. Researchers collect twitter data sent US 2012 election campaign . And analyze and predict how such tweets on common subject later led to 'follows' between users.
1.5.2. The Anatomy of Facebook Social graph
1.5.2.1. http://arxiv.org/pdf/1111.4503v1.pdf
2. Similarly given two users u1 and u2 , can we predict that they will be a distance K apart after N updates
2.1. 6 degrees of seperation
2.1.1. http://en.wikipedia.org/wiki/Six_degrees_of_separation
2.1.2. 6 degrees of separation was proven to exist in Facebook also
2.1.3. The Anatomy of Facebook Social graph paper confirms 6 degrees of separation in facebook.
2.2. Distance between two users
2.2.1. Distance between two nodes will be the number of edges that exist in shortest path connecting two nodes
3. predict future communities.
3.1. Formation
3.1.1. Communities are formed between
3.1.1.1. Like minded people who have similar interest
3.1.1.1.1. Eg : People who are preparing for civil service exams might be candidates for forming a community.
3.1.1.2. People who have been part of some group or institution , or a particular cause
3.1.1.2.1. Eg: People who have studied in the same class in a college might form a community
3.2. Types of communities
3.2.1. Large public communities
3.2.1.1. Eg : Those who like cricket , those who like a political party etc
3.2.1.2. These communities will have lots of members and formation of these communities are difficult to predict. All the members in community might not be necessarily be friends also.
3.2.2. Small private communities
3.2.2.1. Communities for a particular class etc will be usually small and there will be a specific factor that unites all members in such community.
3.2.2.2. Members of such community are usually friends of each other also. We can say that there will be strong edges between the nodes of such members.
3.2.2.3. I think these could be predicted. We would be able to see a lot of interaction among the members . So much so that , they would come to the conclusion that forming a community group would be a better solution .
4. predict cycles in the graph
4.1. Understanding
4.1.1. User U1 is friend of U2 , U2 is friend of U3 and U3 and U1 are also friends. There exist a cycle between nodes U1, U2 and U3
4.2. Mutual friends
4.2.1. Whenever we see mutual friends , it implies there is a cycle in the social graph.
4.2.2. So the key thing in predicting cycles is whether we can oversee the formation of mutual friends growing across the graph