Social Search

Overview: When you search for a route to reach a person in a social network, there are frequently thousands of paths to the target. Most networks return a list of paths ranked by degrees of separation, which is not necessarily useful. In our work, we show that paths can be usefully ordered by path strength, as opposed to path length. To compute path strength, we first automatically infer a weight to each edge in the network, which loosely correlates with the influence the source of the edge has over the destination, and therefore the probability that the destination will forward a message from the source towards its eventual target.

We model the influence a person has on another based on interaction volume. Intuitively, if A sends a high fraction of his messages to B, them B has high mindshare with A, and correspondingly high influence. The influence model is asymmetric, i.e. one person may pay attention to another, but the latter may not reciprocate. We study two large real-world networks, DBLP (a computer science bibliography network) and a network formed by one month of Twitter retweet data. Our experiments show that for these social networks, the best paths according to our influence metric are not necessarily the shortest paths: a longer path is better in 68% of searches in Twitter RT and 45% of searches in DBLP. Furthermore, even when the best and shortest path lengths are equal, we find that the best path is often better than a random shortest path of the same length by a significant margin.

Papers:
All Friends are not Equal: Using Weights in Social Graphs to Improve Search [PDF]
Sudheendra Hangal, Diana MacLean, Monica S. Lam, Jeffrey Heer
SNAKDD '10: Proceedings of the SIGKDD Workshop on Social Network Mining and Analysis, 2010.

Factoids:
We define the overall influence of a person to be simply the sum of the influences he or she exercises over his or her direct connections. Can you guess the most influential individuals in these two networks, as computed by our metric of overall influence of a person ?

Here are the results for the Twitter retweet network (1 month's tweets) and for the DBLP co-authorship network.
(Warning: this is a fun experiment, and not meant to reflect actual influence in the real world.)