3 ms·

I'm sort of surprised that Facebook's "friends of" is a directed graph, when the actual social graph is undirected. I guess they use enough directed edges for o

by mcintyre1994 13y ago

I'm sort of surprised that Facebook's "friends of" is a directed graph, when the actual social graph is undirected. I guess they use enough directed edges for other things in that graph, but I'm sort of surprised their social graph isn't undirected and ridiculously optimised as its own separate thing.

seiji 13y ago
For surveillance it's of great importance to know the difference between me being friends with Iranian nuclear scientists, them being friends with me, or us having mutual hugs going on.
Scaevolus 13y ago
An undirected graph is equivalent to a directed graph with doubled edges. The only efficient way to implement an undirected graph is as a directed graph with doubled edges. You want to list friends of Alice. Directed: query all friend(Alice, X). Undirected: query all friend(Alice, X) OR friend(X, Alice). Finding all friend(X, Alice) will be very slow without an index of all friend relationships with Alice in the second position. Storing this is harder than just storing friend(Alice, X) and friend(X, Alice).
- mcintyre1994 13y ago
  Oh of course, I see what you mean, thanks for the explanation.
  - random_coder 13y ago
    More generally, in Facebook's social graph, connections can be of different types. For e.g., for a user, 'likes' can be one type of an edge and 'followers'(people he follows) is of a different type, 'followed by'(people who follow him) is yet another type, so on. Many of these types can only be uni directional(e.g., all the above three examples). So, the social graph is a directed graph. Of course, the well known 'friends' connection is a bi-directional type of edge.
    - mcintyre1994 13y ago
      I assumed, I think incorrectly with hindsight, that the 'friends' connection dwarfed all others and would be separately optimised. I think you're right though - 'likes' and 'friends' probably don't dwarf each other at a guess, and as Scaevolus pointed out it wouldn't be fundamentally different anyway.

seiji 13y ago

For surveillance it's of great importance to know the difference between me being friends with Iranian nuclear scientists, them being friends with me, or us having mutual hugs going on.

Scaevolus 13y ago

An undirected graph is equivalent to a directed graph with doubled edges. The only efficient way to implement an undirected graph is as a directed graph with doubled edges. You want to list friends of Alice. Directed: query all friend(Alice, X). Undirected: query all friend(Alice, X) OR friend(X, Alice). Finding all friend(X, Alice) will be very slow without an index of all friend relationships with Alice in the second position. Storing this is harder than just storing friend(Alice, X) and friend(X, Alice).

mcintyre1994 13y ago
Oh of course, I see what you mean, thanks for the explanation.
- random_coder 13y ago
  More generally, in Facebook's social graph, connections can be of different types. For e.g., for a user, 'likes' can be one type of an edge and 'followers'(people he follows) is of a different type, 'followed by'(people who follow him) is yet another type, so on. Many of these types can only be uni directional(e.g., all the above three examples). So, the social graph is a directed graph. Of course, the well known 'friends' connection is a bi-directional type of edge.
  - mcintyre1994 13y ago
    I assumed, I think incorrectly with hindsight, that the 'friends' connection dwarfed all others and would be separately optimised. I think you're right though - 'likes' and 'friends' probably don't dwarf each other at a guess, and as Scaevolus pointed out it wouldn't be fundamentally different anyway.