Social Media Research Blog

Sphere of Influence

When we talk of Influence, the general problem setting is that of identifying a set of nodes in a social network that can be considered to be "Opinion Leaders": Individuals whose opinions can cause others around them to change their viewpoint or adopt a technology or product. 

The paper by Kempe et al. presents a technique for maximizing the spread of Influence in a social network. The algorithm presented in this paper is a greedy algorithm for selecting N best nodes which if populated with some information could spread it to a large number of nodes in the network through a simple diffusion process. Although in real world social networks it is often unclear how the diffusion process really takes place or how to determine the correct values of the thresholds wherein a node adopts an idea if enough of it's neighbors have also adopted the idea. Jure et al have presented a different approach and a solution for selecting nodes to detect outbreaks in the networks through the analysis of information cascade.

Most recently, the paper "Influentials, Networks and Public Opinion Formation" by Watts and Dodds presents a strategic shift in the way we think about influence and they help casts the problem in a different manner. Their radical shift in approach is best summarized by the following excerpt from the abstract:

..We find that large cascades of influence are driven not by influentials but by a critical mass of easily influenced individuals.

Through simulation studies they validate this intuition. According to me the major importance of this result is in highlighting the fact that a) it is perhaps the followers that are more important in the analysis and b) we need to focus on what these followers are influenced by? No opinion leader or influential nodes is arbitrarily influential just about everything and for everyone. Dailykos may be influential about politics in a particular community and Gizmodo is influential in the geek community. While Dailykos might have some influence in the political community when it comes to technology, it is quite unlikely to have a significant impact on the geek bloggers about a new device. Additionally, Popularity, Influence and Authority are talked about in a similar fashion. This can be quite problematic and I remember having a great discussion with Matt Hurst while we were at KDD last year.

Recently, I had been think about the idea that every individual in the social network has some sort of a sphere of influence around them. The sphere of Influence of a node can be described as the region around that node that is in some way affected by the node.

One way to describe it would be to identify a region/local neighborhood of the node that has more links within the neighborhood than outside of it.

The approach I was thinking of turned out to have quite a bit of similarity with the paper by Aaron Clauset on "Finding a local community structure in networks". This paper presents a greedy heuristic that starts with the initial node and grows the region around the node by adding one node at a time. Each new node to be added is selected based on a local version of a modularity score (Originally proposed by Girvan and Newman). The local modularity score is calculated as

R = I/T

Where I is the current number of edges that point within the group of nodes discovered by the algorithm thus far (or the local community). T is the set of edges that point to as yet undiscovered edges plus those edges that point within the local community. I ran the above algorithm on the classic Karate club dataset. Following graph shows the local community structures or what I call the "Spheres of Influence" around a node.

The lines in red outline the sphere of influence around the node 4 and the lines in blue represent the sphere of influence around the node 32. In order to determine the boundary or the cut-off for the nodes, I use another measure called conductance of the graph. Conductance measure of the graph is related to random walks in the network. Given a partition of the graph, a low conductance would indicate that the graph is well knit and thus the probability that a random walk starting inside the partition terminates outside it is low. Thus, as the nodes are added we can compute the conductance scores. The following graph shows the conductance values of the subgraph induced by the sphere of influence around a given node. The local minimas correspond to the two levels (one in red and other in darker shade, around node 4).

This is still a relatively simple example and it would be worth exploring the Spheres of Influence in real world social networks like the subscription graph of FriendFeed or the followers in Twitter. Some interesting questions to ponder about:

• How do topics change as you move further away from the influence of the root node.
• Is the probability of receiving "Likes" and "Comments" higher within the sphere of Influence?
• What is the role of connectors and information bridges in such spheres of influence?
• Given the timing of each post, do most cascades occur within the spheres?

Information Filters and Subscription Predictability

I read a superb blog post "Who is your Information Filter?". I think Hutch makes an important point here (text in bold is highlighted by me):

In an equal world, information shared by any of your friends will merit click-throughs and discussion. But the practical reality is that some people will be more “equal” than others in terms of driving the discussion agenda. There are two highly correlated components to that:

• Number of subscribers
• Reputation for identifying what is interesting

The sheer number of subscribers make some people Information Filters. The big power users on Twitter: Leo Laporte, Dave Winer, Robert Scoble, Jason Calacanis, etc. These guys really drive discussions around ideas, opinions and news. If you subscribe, you can’t help but be overwhelmed by the discussions they can kick off.

Subscribing to somebody's feed is like a commitment. On social network sites, your actions often speak for themselves. The posts one comments on or likes are quite predictive of who you subscribe to. This is what I found from the analysis of the "likes" in FriendFeed. The following graph shows the probability that a user A subscribes to a user B, given that User A "likes" k or more posts by user B. Typically, if a user has 'liked; more than 3 posts of another users there is over 80% probability of a subscription.

On one hand, this is because users are more exposed to posts from those whom they subscribe to. On the other hand, as the number of such actions between two users increases, so does the probability that there will be a continued commitment in terms of a subscription. Similar trends are observable from the "comments" graph.

The way I see it, an important implication of this is ensuring that the social network makes it possible for users to find and "try out" feeds they might "like". Findability and explorability of social networks allows users to initially explore posts from others and then decide which of these users they would like to pick as their "Information Filters".

Locality of Reference in FriendFeed Interactions

While I was having a discussion about my previous FriendFeed posts, I had mentioned that it would be interesting to see the split up of likes w.r.t the directed, shortest path distance. Following graph shows the number of likes that are received from people you directly subscribe to, or subscribe to 2 hops away, 3 hops away and so on...

Both from this graph and the earlier post, we can see that almost 45% of the likes are from people you directly subscribe to. But what is really interesting is that almost 90% of the remaining likes are accounted by friends who are just two or three steps away. FriendFeeders sure are a close bunch!

This type of locality of reference is also related to what sociologists have called the triangle closing. Partly, this is also due to the fact that FriendFeed tries to make it easier to attain "closing of triangles" by displaying the updates from friends who are just one step away. It would be worth looking into how this network's evolution takes place by recrawling FriendFeed subscription graph and observing how it changes. I suspect that through the likes and comments users find new friends and subscribe to their feeds: Your Friend's Friends who like you may be quite likable themselves!

I believe that models of Web graphs (small world, preferential attachment) are getting even more sophisticated in such social settings. The act of linking is not just creating a new hyperlink anymore -- but it is fragmented into actions such as "I subscribe to someone", "I comment on someones posts", "I like someones post". Such actions are not limited to FriendFeed alone. You can draw similar analogies in Youtube (watching, rating, commenting...), Flickr etc. As we explore these datasets through our empirical analysis, it might bring in a better understanding and intuition to build newer models for Social Graphs.

This data was generated using the 200,000 likes and the graph consisting of subscription information of over 75,000 users. The actual shortest path calculation was done using the Boost Graph Libraries (BGL). This is an amazing and extensive tool for graph analysis and quite frankly, I am a bit surprised that I hadn't used it before! I had used the MATLAB bridge but for very large graphs it is best to run the algorithms using BGL. But, more on that later!

Services That Attract Most Comments on FriendFeed

Indexing about 400,000 posts and over 650,000 comments from about 70,000 users on FriendFeed gives some interesting data. There are about 45 different services that FriendFeed connects to at this point of time. First, I wanted to see what were the absolute volume of posts were from each of these services:

Next, I pulled up the number of comments that every service draws during the time period of my index (which was built by fetching the most recent posts and comments from the API).

Note that this is not normalized for multiple updates by the same user. A few interesting points:

• Large volumes of updates are from URL sharing and bookmarking tools like del.icio.us, Google Reader and StumbleUpon
• Most Comments are attracted by posts that were made directly via FriendFeed.
• del.icio.us does attract an equally large volume of comments.
• While Twitter is not far behind and receives a significant share.

Finally, for the services that attract the most comments, I have calculated the average number of comments per post:

The above chart says something important. On an average, original content like what one would find on blogs, still attracts the most comments. Followed by conversation focussed services like FriendFeed and Twitter. Finally, images posted on Flickr get a lot of attention too. Bookmark sharing sites are now lower in the ladder. See some trend here?

The attention and appeal one receives in social networks is a function of the original content you produce and the value, insights you bring to the table when you share new stuff.

DERI/NUI boards.ie SIOC Data Competition

Following Announcement is Via Dr. John Breslin spotted on W3C's Semantic Web Mailing List:

The Digital Enterprise Research Institute (DERI) at NUI Galway is running a unique competition from 1st August to 30th September 2008 in conjunction with
boards.ie, Ireland’s largest discussion forum site. The competition is an open contest in which entrants can win over €4000 in Amazon.com vouchers by submitting an interesting creation based on an RDF data set of discussion posts from boards.ie over the past ten years:

* The first prize is an Amazon voucher for $4000 (~€2500)
* The second prize is a voucher for $2000 (~€1250)
* The third prize is a voucher for $1000 (~€625)

Read the rules and find out more information on the contest at:

http://data.sioc-project.org/

The data set (approximately 9 million documents) has been represented in the Semantically-Interlinked Online Communities (SIOC) RDF format developed by DERI, NUI Galway for expressing the information contained in social websites (forums, mailing lists, blogs, etc.). Entrants may create whatever they feel is interesting based on this data: it could be a novel web application that makes use of the data set, a report on analyses performed on the data, a tool that allows one to visualise or browse the semantic structure, or whatever else the imagination can come up with!

This event is duly noted in the Social Media Events Calendar.

Ranking FriendFeed Users

I read this interesting approach being used to rank FriendFeed users. The ranking is based on Google's search results page and is therefore a mix of FriendFeed linking and webpage links. I had been running a small crawl of FriendFeed users for the past couple of days. I started at Bret Taylor, one of the founders and followed all the users he subscribes to and went from there to discover more users, based only on the subscriptions. The crawl hasnt finished yet and there are roughly 22,000 user's subscriptions that I have fetched (so far).  Nevertheless, the graph that I found so far can be used to compute the PageRank of users based on who subscribes to whom. Following are the top 10 users based on PageRank from the subscription graph.

1. Thomas Hawk
2. Stefan Hayden
3. Duncan Riley
4. Robert Scoble
5. Jason Calacanis
6. Andrew Baron
7. Mrsth
8. Julio Medina
9. Marco
10. Czar D.J. Peterman

Take these results with a grain of salt. Firstly, because the crawl is incomplete and secondly because I think that rather than subscriptions the comment network says more interesting things. That said, what really surprised me about the top users is that I would have expected it to be dominated by the regular Blogosphere rockstars (aka A-Listers), but there are new faces up there -- more evidence that A-List is dead! People care more about interesting stuff and not the celebrity status of a handful and FriendFeed is a perfect place for finding and surfacing new stuff.

I am collecting "comments" and "likes" statistics from the crawl. We can similarly compute the PageRank over the comments graph. This is a fantastic dataset and has some wonderful properties, rating (ie likes) and temporal data.

As and when the crawl finishes, I will try to crunch it and post a few interesting nuggets.

Clustering Triples from Social Data

By far, the most prevalent data available in social media is tagging information. For example, in del.icio.us a user may tag a URL or in Flickr she may tag an image. One of the questions that comes up is how to then cluster social data that is rich in tags. Some techniques available ignore the user information and use only a bipartite graph consisting of tags and URLs. Another method is to represent two pieces of evidence (user-tag;tag-blog) in a tripartite graph (where nodes are of three different types: users, tags and urls). However, even this type of structure actually  misses the higher order relation between the three nodes. Note that the information available is really in triples of the type <user, tag, url>. This information is not captured by the tripartite graph model. In particular, two users may be connected via a common tag even if the actual URL they bookmarked is vastly different.

There are some techniques using Tensor Matrix Factorization that can handle such data. However, the question of how to deal with triple (or higher) information from social data is quite interesting. Moreover, being able to do so efficiently and in an online fashion would also be important. I believe that this topic may be of significant interest in the upcoming social media and data mining conferences. The implications of these techniques would be in building better recommendation systems and personalization algorithms.

[Thanks Vlad Korolev for some of the discussions related to this post]

Community Detection via Matrix Factorization

One form of matrix factorization is Singular Valued Decomposition (SVD). This is a powerful technique and it has several applications in information retrieval and graph analysis.

Another matrix factorization technique I had mentioned recently was Non Negative Matrix Factorization (NNMF). The advantage of NNMF over SVD is that it is easier to compute and is generally much easier to interpret due to the strict positivity constraint.

Matrix factorization can be achieved via optimization methods. Suppose a matrix A (shown in the figure on the left) of size 20*20 was to be factorized into two matrices X of size 20*4 and W' of size 4*20, the following objective function can be minimized:

J = || A - XW'||_f 

The cost function minimizes the Frobenius norm between the original matrix A an XW', i.e. the error in approximating A as a product of two matrices. This can be solved using conjugate gradient methods and MATLAB's optimization toolbox (fminunc; tutorial) is one way to implement this. Following is the MATLAB code as an example:

test = ones(5,5);
B = blkdiag(test,test,test,test);
M = rand(40,4);

[xnew,fval] = fminunc(@obj_fun1,M,options,B,20);

function [fun,Grad] = obj_fun1(Z,A,nodes)
    [m,n] = size(Z);
   
    X = Z(1:nodes,:);
    W = Z(nodes+1:end,:);
   
   % Objective Function
   fun = norm(A-X*W','fro')^2+norm(W,'fro')^2;
  
    if nargout > 1  
      Grad1 = 2*(X*(W'*W)-A*W); 
      Grad2 = 2*(W*(X'*X)-A'*X)+W;
      Grad = [Grad1; Grad2];
    end

Once we minimize the objective function, we can obtain the solution for X as
  82.5664   -1.1484   79.4176  -39.0137
   82.5664   -1.1482   79.4176  -39.0137
   82.5666   -1.1485   79.4176  -39.0139
   82.5666   -1.1485   79.4176  -39.0139
   82.5667   -1.1472   79.4173  -39.0141
   -6.3391  -18.4040   68.2625   88.6399
   -6.3389  -18.4039   68.2623   88.6397
   -6.3389  -18.4039   68.2624   88.6398
   -6.3388  -18.4037   68.2622   88.6396
   -6.3386  -18.4036   68.2621   88.6395
   75.9984   13.2685  -57.4890   70.8761
   75.9989   13.2680  -57.4891   70.8759
   75.9985   13.2681  -57.4889   70.8761
   75.9985   13.2687  -57.4891   70.8760
   75.9989   13.2681  -57.4890   70.8758
  -17.6262  112.9716   27.4847   14.5483
  -17.6257  112.9713   27.4844   14.5482
  -17.6263  112.9716   27.4847   14.5483
  -17.6259  112.9715   27.4844   14.5484
  -17.6255  112.9708   27.4844   14.5482

From this essentially the community structure can be easily determined (observe the rows can be grouped to reflect the original communities). However, a much faster and efficient (in terms of implementation) way to accomplish this goal is using something like Singular Valued Decomposition (SVD).

The above code is just a simple illustrative example. However, for me it was a worthwhile experiment to try out and to understand how matrix factorization via optimization can be useful in community detection.

Some recent, interesting papers that use different Matrix Factorizations:

• Algorithms for Non Negative Matrix Factorization Daniel D. Lee, Sebastian Seung [Link]
  
• Structural and temporal analysis of the blogosphere through community factorization Yun Chi, Shenghuo Zhu, Xiaodan Song, Jun'ichi Tatemura, Belle L. Tseng [Link]
• Combining content and link for classification using matrix factorization Shenghuo Zhu, Kai Yu, Yun Chi, Yihong Gong [Link]
•  Learning from Incomplete Ratings Using Non-negative Matrix  Sheng Zhang, Weihong Wang, James Ford, Fillia Makedon [Link]
• Solving Consensus and Semi-supervised Clustering Problems Using Nonnegative Matrix Factorization Tao Li, Ding, C., Jordan, M.I. [link]
• NMF Software by  Chih-Jen Lin
• I believe the statistics toolbox now supports NMF too.
• NMFPack from HIIT

I would appreciate if anyone has pointers to other interesting references/tutorials/software and could please leave me a comment.

Email Interview: Nihaar Gupta, Youlicit

Nihaar Gupta, VP of Product development at Youlicit has kindly obliged to have an email interview with SocialMedia Research Blog. Following are the responses to some of the questions I had for him:

1) Please describe Youlicit to us?

Youlicit at its core is a discovery engine (http://blog.youlicit.com/?p=23). We want to connect you to the most relevant and recommended information as effortlessly as possible. As of now, we are building a technology that allows a user to find the most recommended sites (recommended by people around the web) related to a given URL. We believe that people are the best judges of content and more often than not, the information you are looking for has been found by someone before. Our goal is to aggregate that information and allow the user to access it with the click of a button.

2) Tell Us about your background, the team behind Youlicit and how started it?

Youlicit came about as a result of trying to solve our own frustrations with trying to find information on the web. With the enormous amount of user-generated content and annotations on the web, we saw a huge amount of valuable data that was inaccessible and fragmented. For the sake of brevity, the team bios & background are here http://blog.youlicit.com/?page_id=6

3) Please give us a brief overview of the technology behind Youlicit?

Youlicit aggregates user annotations of websites and other user generated content and analyzes it to create a URL-URL mapping of websites based on relevance and quality. Using this mapping we are able to deliver related and recommended sites to a user with a click of a button.

4) While using Youlicit plugin, I felt that one of the challenges is the coverage -- how do you plan to address this and build your current index?

We are constantly working on improving our coverage. There are two metrics we strive to maximize for our results, quality and relevance. In regards to quality, we’re always looking to increase our database of “quality sites” by tapping into the various kinds of user annotations (denoting quality content) that exist on the web (bookmarks, tags, votes, comments). In regards to relevance, we’re always researching novel ways to extrapolate connections between websites and map URL’s back to our database of “quality sites”.

5) How do you ranking the 'Enhanced Links' in the plugin? Do you also take into account how many users actually click through the suggested links?

Each result in the Youlicit More widget (and on Youlicit’s site) has a score based on the metrics above, quality of the site and relevance to the item being queried. We are looking into ways of scoring the results from implicit/explicit feedback that we get from users (clicks, recommends).

6) How do you ensure that the Enhanced links feature is non-intrusive?

The current version has manifested itself after a few weeks of alpha testing with a handful of bloggers. That said, we are still looking for feedback on the user interface and would love to hear opinions on how to make it more useful and less intrusive for bloggers/blog readers.

7) How would you compare the plugin to sphere's related blog posts?

While Sphere focuses related & recent blogosphere content, we, at Youlicit, are trying to provide the blog reader with more seminal information related to the blogger’s topic of conversation. For instance, if you are reading a blog entry on global warming, you are more likely to receive the most recommended articles (blogs, sites, essays) on Global warming from around the web rather than  recent blog entries on that topic.

8) What are the other features on Youlicit?

Youlicit’s primary product is a Firefox extension to access that allows a user to access our results during his/her browsing experience. We are in the process of redesigning our website and streamlining the current offering to focus on this button. Down the road we would like to be able to deliver personalized recommendations for users as well as connect users to people based on transient and long-terms interests (ideally using a person’s interests to enhance his/her social graph).

9) Would the plugin be adverting supported?

We do see advertising as a very possible source of monetization. Given the fact that we are providing contextually relevant information, the search model of advertising applies nicely. We are also exploring other possible means of monetization but as of right now the priority is to build something that people find useful.

10) What are the next things to look out for at Youlicit?

As I mentioned above, we are stripping down Youlicit to bring the focus back to its core; the Youlicit More functionality via the Firefox extension and blog widget. We expect to release a new designed website very soon. And as always, we love to hear feedback on what you think so far and how we can improve.

Youlicit: Search Less and Find More!

Youlicit is a new tool that helps you "Search less and find more". Often we forget that search is only one means to find what we are looking for. Even search by itself is not the endpoint of an information need or a query. This tool reminds me of the "berry picking model" of Information Retrieval that I had read about first in my IR Class. The model basically says that:

Information need is not satisfied by a single set of documents but by bits and pieces found along the way.

The paper  titled "The Design of Browsing and Berrypciking Technique for Online Search Interface" describes a searcher as

Moving through many actions towards a general goal of satisfactory completion of research related to an information need.

What Youlicit does is provide this ability implicitly, without the reader (or more generally a searcher) having to go through the trouble of navigating and mentally processing through hyperlinks or firing search queries to find related content. Youlicit takes care of all that on your behalf. By providing a simple plugin, the Youlicit widget automatically highlights some of the related, relevant links and provides useful suggestions -- all without your audience ever leaving your blog. I love the idea and the neat implementation that these guys have built. (The very same need was what lead me to hack this Wikipedia related widget a few weeks earlier.)

On the Youlicit site, you have lots more interesting tools. You can discover new content that is relevant to your interests, find related users and share links with them or follow their interests. Youlicit is paving the way for social browsing tools and is a neat concept that is well implemented. Their index does not seem to be very large at the moment and I feel that it would get better as they start to seriously scale up. In the interim, I feel that there might be stopgap solutions that they could be employ -- for example the Alexa related URLs for the links that are not currently in Youlicit's index.

In relation to this plugin, one tool that is similar is the  Sphere plugin that shows related blog posts. I feel that sphere serves a complementary need. From what I understand Youlicit aims to find the interesting blogs and Web URLs one might want to look into in relation to a given hyperlink.

Another plugin is the Snap plugin -- which shows a screenshot of the outlink. However, in my opinion snap does not really serve much purpose and is a bad tool from a usability perspective.

Youlicit is non-intrusive and you are gonna enjoy the serendipity of finding interesting new links! Give it a spin!