Link Prediction Using Friends Common ++

Imagine the following scenario: You are provided a list of people in a conference, and you can see all of their Facebook friends. You want to know which people probably know each other. How can you do that in a way that is efficient? 

Idea 0: If they are FB friends, then they are probably real life friends

Right off the bat, you know that if somebody at the conference is Facebook friends with another person at the conference, then they're very likely to know each other. This is pretty quick to compute. You just build a map of conference goers to Facebook Friends, then go through all their Facebook Friends and check if they are a conference goer.

However, now that we know who probably directly knows each other based on their Facebook friends, how can we figure out who might know each other at the conference but have not added each other on Facebook?

Idea 1: Count the number of common Facebook friends

One easy way to do this would be to say, for any two people, the more Facebook friends they have in common, the more likely they know each other in real life. This would be simple to implement as well. We set some threshold N, and if two people have more than N friends in common, we say that they probably know each other. 

Our equation for whether or not two people know each other is as follows:

$N > | \Gamma(x) \cap \Gamma(y) |$

(A bit of notation, x and y are the two conference goers in question, Γ(x) denotes the set of Facebook friends of x, Γ(y) denotes the set of Facebook friends of y.)

However, what if there are folks who are serial networkers? The folks who have 500+ LinkedIn connections, 5000 Facebook friends? They could have tons of friends on common with everybody at the conference, but may not necessarily know in real life the conference goers who they have many friends in common with. 

Idea 3: Use Jaccard Similarity

Instead of simply counting the number of common Facebook friends, we can apply a very nice concept called Jaccard similarity. Jaccard similarity is where we take a look at the intersection of the two conference goers' Facebook friends divided by the union of the two conference goers' Facebook friends. The higher the Jaccard similarity, the more likely it is that the two conference goers know each other. Intuitively, you can think of it like this. Let's say that Mark Zuckerberg attended the conference, and for the sake of this scenario, he is Facebook friends with everybody in the world. Now if we use our naive algorithm where we check how many friends a random conference goer and Mark Zuckerberg have in common, we will come to the conclusion that they very likely do know each other in real life, which is probably false, but we think this because they have so many Facebook friends in common. If we use Jaccard similarity instead, the intersection of their friend groups will be the size of the random conference goer's entire friend group, but the union of their friend groups will be the size of every single Facebook user in the world. This means that a different conference goer with a smaller friend group and but a decently large friend group overlap with the first conference goer will be able to outrank a celebrity like Mark Zuckerberg in Jaccard similarity. Again, we set some threshold N, where if two people have a Jaccard similarity of more than N, we say that they probably know each other.

Our equation for whether or not two people know each other is as follows:

$N > \dfrac{| \Gamma(x) \cap \Gamma(y) |} {| \Gamma(x) \cup \Gamma(y) |}$

However, in this case we run into an issue where imagine if there are a few very popular people that almost everyone is Facebook friends with, such as Mark Zuckerberg. Being friends with these folks should be weighted to give a reduced signal. For example, if two people follow Bill Gates, Mark Zuckerberg, but one of them follows a random person named Alice and the other follows a random person named Bob, they likely do not know each other. However, if two people follow Alice, Bob, but one of them follows Mark Zuckerberg while the other follows Bill Gates, they probably do know each other. Both pairs would have the same Jaccard similarity, but it is clear that the second pair of people is more likely to know each other than the first, since the in the first pair the Facebook friends they have in common are celebrities.

Idea 3: Use Adamic/Adar Similarity

To address this, we might try something like Adamic/Adar similarity. Take each Facebook friend and determine how many conference goers have that Facebook friend. Let's call this property of a Facebook friend the "centrality". For each pair of conference goers, find the intersection of their Facebook friends (which ones they have in common) and sum inverse logs of the centralities of that intersection of their Facebook friends. This is the Adamic/Adar similarity. Again, we set some threshold N, where if two people have a Adamic/Adar similarity of more than N, we say that they probably know each other.

Our equation for whether or not two people know each other is as follows:

$N > \sum_{f \in \Gamma(x) \cap \Gamma(y)} 2^{-n} \dfrac{1} {\log C(f)}$

(A bit more notation, C(f) we denote as the centrality of Facebook friend f.)

The centrality of each Facebook friend is effectively a measure of how much of a "celebrity" the Facebook friend is. By using the inverse log of the number of neighbors each Facebook friend has, you are effectively reducing the weight of a highly friended Facebook user, such as Mark Zuckerberg, so that having a celebrity Facebook friend in common with another person is treated as less indicative of knowing that person in real life than having a non-celebrity Facebook friend in common.



There are a lot more ways to guess whether or not two people know each other, and you can read more about it in the paper The Link Prediction Problem for Social Networks by Liben-Nowell and Kleinberg. It turns out from their experimental evidence, Adamic/Adar similarity seemed to work best, but Jaccard also offers considerable improvement over a simple common neighbors approach and requires very little extra complexity. Thank you for reading!

Comments

Post a Comment

Popular posts from this blog

First-Principles Derivation of A Bank

What is a Bank? A bank borrows money from people with money but low-risk appetite, and lends money to people who need money to take potentially rewarding risks. Say we live in a toy society with $10 in circulation and 2 people (a farmer and a cook). In this society, the farmer grows vegetables and the cook processes vegetables for food – both activities essential for survival. Assume that both parties start with $5 each. The farmer sells vegetables for $1 per serving and can produce 2 servings per day. The cook prepares food for $2 per serving and also has the capacity to produce 2 servings per day. Every day, the farmer sells 2 servings of vegetables to the cook for a total of $2 . Then, the cook prepares 2 servings of food and sells 1 serving to the farmer for $2 . In this perfectly balanced society, everybody eats, and money never needs to “rest.” Let's break the above equilibrium by adding a time component. In this society, vegetables take thr...
Read more

A Play-by-play of the Mirai botnet source code - Part 1 (scanner.c)

Today I've decided to start learning something very new and unfamiliar to me, as someone who mostly works with very high-level languages like Python and Kotlin, and attempt to understand the source code behind the Mirai botnet that managed to control over 380,000 IoT devices at one point in its life. I'll likely get a lot of things wrong the first time around, and this may take quite a few blog posts to complete, but my goal is to document everything I figure out, so that in the future, someone else in a similar position will be able to use this blog as a resource to understand the C and Go that ran this ground-breaking botnet. To begin, I'll start by reading  scanner.c , which is the code that is in charge of the scanning for and infecting new IoT devices. I'll be taking my time with it, so this might take a few blog posts. scanner.c  has most of its logic in a function called  scanner_init , which is triggered either from  main.c  (which seems like how it is t...
Read more

You can control individual packets using WinDivert!

Image
WinDivert is one of the most interesting packages I've recently come across. What WinDivert allows you to do is apply a filter to grab some subset of packets that pass through your Windows computer, and then apply some logic to the packet to maybe modify, and then drop or re-inject the packet. Here's a great diagram from this website that sums it up: Using PyDivert , a WinDivert Python binding, we can specify the PROGRAM portion in the above diagram, which means that we can now capture whatever packets we want, change them however we want, and then either drop them or re-inject them to be sent out whenever we want. The big sell here is that WinDivert allows you to play with packets on Windows without writing code that modifies the core operating system components that run in the kernel! The drawback is of course speed and efficiency, but for a lot of blog-post-worthy applications, we don't need that much speed and efficiency. Stay tuned for more stuff if this piqued your ...
Read more