InnovationInspiration

Graph Theory: Who Knows Who?

Next to no one reads this blog, so I decided to brain dump some thinking I’ve been doing recently about social networks and graph theory. I’m working on a product called The Shared Web - which is all about content curation leveraging the power of social networks. While thinking about this, my economics background led me to the following question:

Assume that I have limited time and therefore I can only have a limited number of friends. If this is the case for everyone, then given this constraint, who should I be friends with , and who should everyone else be friends with, in order to maximize the value derived from the friendships in the social network overall (i.e. independent of my personal interest of whether that person is someone I actually want to be friends with). 

This means that we have a graph G,  comprised of the following sets: nodes [people] N,  potential edges L [potential friendships], and actually selected edges S [selected friendships]. The sum of the value v(S) = (v(s1) + … + v(sn)) of the S selected friendships is the actualized value of the friendships in the network. So the problem works out to something along the lines of:

Choose a subset of edges S, such that we maximize v(S), where S is a subset of the edges L [potential friendships], subject to the constraints that no Node may have more than 5 edges adjacent to it (which means no more than 5 edges in S can share a vertex).

In the simplest case, each potential edge has a constant value, v(ei) = ci, regardless of what other edges are selected in the final graph. In the more complicated case, the value of the edges themselves depends on which other selections are made. So, for example, if I have a friend Adam, who knows lots and lots of awesome people, the value of that edge may be worth more to me than another edge that I could have.  However, overall, perhaps my personal optimum of friending Adam doesn’t translate into the global optimum because of what other edges end up being selected. If it was a turn-based friendship making model, it could make for an interesting game-theory question as well (see end of post). 

In the case where who my friends’ friends are, factors into the value of the edge, the problem of deciding what edges to select to maximize the distribution of edges becomes substantially harder. I need to consider the impact of selecting an edge on the value of all other edges. I was just wondering if this type of problem is well known in the Graph Theory field, and what kind of algorithms exist to solve it. I decided to just post in case it’s interesting for anyone.

Why The Problem Is Interesting To Think About

People say it’s all about who you know, and quickly in the start-up world you realize that very much is the truth. At the same time, strong friendships are far more valuable than weak friendship. So who should know who in order to maximize the effectiveness of our economy. Those connections between people may matter far far far more than other economic considerations such as  a microscopic change in the interest rate, or the printing of money. This idea is closely related to the idea of social capital.

Now, in the business world we can talk about the value of those types of connections, but beyond that, the friendships that actually matter much of the time have nothing to do with business connections, but instead with friends that inspire you to transcend to even higher levels of achievement, that inspire you to live beautifully - or whatever may be the case. 

I recently watched a movie called Beautiful Losers, which was all about a sort of minature renaissance in art that occurred when a bunch of twenty somethings got together and shared a space in New York. At the time, they were not prominent artists, but by virtue of their friendship, and the environment they were in, many of them excelled in their field. We see those sort of clusters of genius spring up all over the place, and it’s interesting to ask if there was a way to determine that such clusters are occurring based on the edges in the network - or if we could even encourage them to occur somehow (I don’t actually think this should be done, it just is an interesting thing to imagine). 

In any case, Beautiful Losers also made me draw a conclusion that is out of the realm of this problem (though most things are out of the realm of abstract economic problems). It’s not all about the actual edges, and the friendships that exist, it’s also about the environment that is somehow created of safety and encouragement - safety to explore their shared passion unrestrained, and encouragement to act as beacons of confidence for each other. I think it was also important that not all of them were exploring the same field, or the same style, so that there was diversity of influence, that allowed for the cross-polination, and abundance of possibility to thrive. But perhaps all these things could be inferred from the graph’s value function as well.

(Sidebar: I could see this type of thinking making for a good science fiction book - a world where everyone’s friendships are pre-decided based on the social optimum that some machine calculates. Kind of like pre-arranged marriages of the future, but not just marriages are pre-arranged: friendships and business connections as well). “It was ‘fate’ that we met”.

Posible Variations Of The Graph Problem

The more friends you have, the weaker the friendships 

- This means we can change the size of S, i.e. the number of edges in S,  (e.g. without any restraint on it, or perhaps with the restraint that each person can have at 4 most friendships). 

Some friendships are bad

- They can have negative values to edges if people are harmful to you to know them - e.g. the reverse of Genius clusters.

Frienships Can Change Over Time (Game-Theory Variant)

Starting with a given distribution at time t1, if we can make ‘1’ new friendship over time, or there are some other constaints on how edges can change from turn to turn, which moves should be made to maximize the sum of the edges selected over all the time snapshots: t1, t2, … tn. Over time, given the graph shifts, which connection should be made this time around (e.g. if we were to analyze a slice of time, what would be the optimal movement of connections, across time, in order to maximize).

If we introduce personal calculations of the utitlity of ‘changing friends’, this becomes the game theory problem I was mentioning before, where we can solve to see if the social optimum calculated algorithmically without ‘local/personal’ based solving would reach the same solution, or would have a higher value summing over all the t1, t2… tn.

You can think of this as everyone has a chance to make a friend, and if not then they go to the other person (both people have to accept friendhsip, or something) - we could simulate this with a facebook like system where people can only have 50 connections - sort of similar to what Path is doing, and see what happens, it’s optimal for them to be friends sooner rather than later, scores decrease over time probably because of expected life time value of the friendship - depends on whether the edges are temporal or not. 

Who you know determines who else you can know

This is making the set of remaining possible edges a function of the edges Sselected so far:

L(Sselected so far) 

(Final thought: There’s no good way to write math in tumblogs - that’s too bad - good opportunity lost).