Measuring Social Influence

Measuring social influence is going to be increasingly more important as we begin to quantify & measure social media campaigns (can you hear those whispers..."ROI, ROI..."). The other day in my office I scribbled all over the whiteboard a terrible looking graph which I labeled "Network Influence Potential," which, in theory, would be a predictive value for determining best targets within a social network. Two of the most obvious markers of NIP were Direct Influence (#of "friends"), Connectivity (number of friends to number of networks). An obvious lacking piece is exponential value of the direct influence and connectivity (the whole beauty of the marketing multiplicity effect that makes social technologies so appealing to marketers). While I've been hammering at some of these pieces from a marketing perspective, I came across 20bits Graph Theory Part III (Facebook) and just about died. First and foremost 20bits is for computer science and mathematics folks, but I love that in this particular post they say at the beginning "lets look at the graph and think like a marketer would" (yes!). So, being that these guys are total quants and much smarter than I--I'll let these guys take over from here. Below is a an excerpt from the Graph Theory III post:


What Can Be Done With a Social Graph

Let's step back and think like a marketer for a second. Facebook, thanks to the newsfeed, is essentially a word-of-mouth engine. Everything I do, from installing applications to commenting on photos, is broadcast to all my friends via the newsfeed. Intuitively, however, we know that some people are just more influential than others.

If my cool friend writes a note about an awesome new shop he found in the Lower Haight I'm probably going to pay more attention. People like this, who are influential and highly connected, are a marketers dream. If I can identify and target these people, "infecting" them with my marketing, I'll get ten times my return than I would going after random people in my target demographic.

Facebook is almost certainly doing something like this already with respect to the newsfeed. They process billions of newsfeed items per day. How do they know which messages are most important to me? Well, it stands to reason that the messages that are most important to me are the ones from the people who are most important to me. So, as Facebook, I want to be able to calculate the relative level of importance of a person's friends and use that measurement to weight whether their newsfeed items get displayed for their friends.

There are several problems. Can we come up with a good measure of social importance or influence? Are there multiple measures, and if so, what are their relative merits?

Measurements of Social Influence
Let's start simple. One way to measure influence is connectivity. People who have lots of friends tend to have more influence (indeed, it's possible they have more friends precisely because they are influential). Recall from the first part that the degree of a node in a graph is the number of other nodes to which it is connected. For a graph where "is friends with" is the edge relationship then the degree corresponds to the number of friends.

Degree Centrality
Let's call this influence function Id ("d" for degree). Thus, if p is a person then Id(p) is the measure of their influence. Mathematically we get:




The main advantage of this is that it's dead-simple to calculate. If you represent your graph as an adjacency matrix, as in the second part of this series, then the influence of a node is just the row-sum of the corresponding row — an operation which is very fast and easily paralleizable.

The downside of this is that its naive. Consider the following graphs.


Single person with high degree


Single person low degree but high connectivity


Using Id as a measure of influence the first person, p1, has a higher measure of influence because they are directly connected to eight people. The second person, p2, however, has the potential to influence up to 9 people. This happens in the real world, too. Consider a corporate hierarchy in a large company. The CEO only has direct relationships with his board, the VPs, and maybe a few other employees. He is undeniably more influential than an administrative assistant to the deputy regional director of sales for Southern Montana and yet might have fewer direct connections.

and there's more...