Social Media Research Blog

Social Network Visualization Eyecandy

Visualization of graph data is incredibly challenging, particularly when it comes to extremely large, scale-free graphs and social networks. A few simple searches on the Web and you will find some mesmerizing and very cool images. Perhaps the most cited and fascinating of these are Matt's "Mapping the Blogosphere" series.

Some of my favorite tools for graph visualization are LGL (see Twitter visualization using LGL), Prefuse, Guess and UCINet (no specific ranked order). I have also been waiting to get a chance to try out AT&T's large network visualization software. Two other promising tools that I have not played with yet are Tulip (TOTH Eytan!) and yWorks.  Following is an image I had generated a year ago (more here) using UCINet. This is a community of political blogs discovered using an implementation of Dr. Mark Newman's community detection algorithm:

One thing that I think would be exciting is visualizing evolving networks. Current tools force you to map blogs, social networks etc. into static graphs. This is a serious limitation. Their real meaning and value comes from seeing the temporal interactions between members, evolution of community structures,  changes in strength of ties over a period and detecting bursts. As far as my knowledge goes, this feature is not supported by any of the open source/freely available tools that I have explored. I would love to hear about other graph visualization tools that I may be unaware of.

Only 10 Cherry Picked? Thats not Enough!

Sixapart re-launced Blogs.com as a blog directory... yawn! (Wow! A Yawn is really contagious... via techcrunch's coverage -- the Yawn cascade initiator).

Seriously.. Sixapart? I am sure you could do a lot better than having an expensive team of editors cherry pick their favorite blogs in a handful of categories. You guys have a ton of good, high quality blogs and the interesting thing is that you can use some of the tag information to cluster these blogs into the different communities they belong to. For example blogs that talk about business are likely to use tags like marketing, advertising, finance etc. Algorithmic approaches can be effectively used to mine blog graphs to find high quality feeds.

At eBiquity, we have looked at this problem from two different approaches:

• Using readership information from Bloglines, we can cluster the blogs based on how people subscribe and categorize their feeds. Although typepad probably does not have access to subscription information it has other sources (like what tags are used by the blogger, and the number of people visiting and commenting on the blogs) to come up with a much better directory. Something on the lines of "Feeds That Matter" (see site here, bit outdated though).
• More recently, I have looked at how we can combine the graph structure and folksonomy information to identify communities in social media. This was an Idea that I first shared on this blog and subsequently submitted a paper, which I would be presenting at this year's WebKDD workshop.

The point is, I beleive that the top 10 offered by sixapart and bloglines are not really that interesting anymore. In the era of hundreds of thousands of potentially good blog (of the millions that exist), we can rely on algorithmic approaches to find (more than just 10) high quality blogs. This is also related to the "Feed Distillation Task" that TREC ran for 2007. If you are interested in feed distillation... check out CMU's submission by Elsas et al. and the follow up papers by Jon at other venues.

Another challenge is being able to find not just popular blogs but also that cool blog that probably be down there somewhere in the long tail.

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?

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]

Detecting Commmunities via Simultaneous Clustering of Graphs and Folksonomies

Great news! Our WebKDD 2008 submission titled "Detecting Commmunities via Simultaneous Clustering of Graphs and Folksonomies" was accepted. I received a number of very helpful comments and suggestions from the reviewers and I am working on updating the paper. I will make the pre-print version available on the ebiquity site as soon as it is ready. In the mean time here is the abstract for this paper:

We present a simple technique for detecting communities by utilizing both the link structure and folksonomy (or tag) information that is readily available in most social media systems. A simple way to describe our approach is by defining a community as a set of nodes in a graph that link more frequently to within this set than outside it and they share similar tags. Our technique is based on the Normalized Cut (NCut) algorithm and can be easily and efficiently implemented. We validate our method by using a real network of blogs and tag information obtained from a social bookmarking site. We also verify our results on a citation network for which we have access to ground truth cluster information. Our method, Simultaneous Cut (SimCut), has the advantage that it can group related tags and cluster the nodes simultaneously.

Interestingly, I had discussed some of the basic idea behind this paper in my earlier blog post "Clustering Tags and Links Simultaneously."

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.

The Echo Chamber Model

The blogosphere if often described as an echo chamber. Ideas, comments, controversies and discussions are all reverberate in this online space. In the paper titled "Information Diffusion in the Blogspace", Daniel Gruhl et al. studied the dynamics of topics propagate in the Blogosphere. They say that resonance is a rare phenomenon that can be described as

fascinating phenomenon in which a massive response in the community is triggered
by a minute event in the real world.

While few topics reach the state where they "resonate" through out the community/blogosphere, the echo chamber is still active with millions of posts and discussions in the form of trackbacks, comments and twitter posts, etc. The blogosphere is a huge graph and the echo chamber phenomena can be easily modeled in terms of random walks in this graph. Imagine that your post is read by your immediate neighbors and their posts (in reply to yours) is read by their neighbors and so on. Now what is the probability that this sequence would terminate with a post or a comment back on your blog? This is nothing but the commute time or the round trip time for the random walk to start on a given node (say A), traverse to a node (say B) and return back to the node A.

Commute time embedding is a way to map the original graph (which lies in a high dimensional space) into a two (or any low) dimensional space in such a way that the euclidean distance in the low dimensional embedding preserves (i.e proportional to) the commute times in the original graph. Interestingly, this can be quite useful in describing how ideas or information might flow in the network. For more details about the exact method to compute the embedding please refer to the paper. It is a neat technique that can be described in terms of the eigenvectors of the graph Laplacian (and can also be related to heat diffusion in the graph).

Consider the classic Karate club example. The original graph and the corresponding embedding in a two dimensional space is shown below. Notice how the nodes 33 and 34 are very close to each other. Compare this to node 3 which is almost equidistant to the central nodes (33/34 and 1) of both the communities.

I think that this might be an interesting way to model the echo chamber of the blogosphere. In this representation, blogs that are closer to each other in Euclidean space are also closer in terms of social distance (another term used in the literature that approximately means the same thing as commute time).

Quantifying Social Capital

Since attending the talk by Dr. Tufekci on "The New Social Physics", I have been thinking about social capital and how we can quantify it.

Social Capital, is a term used to describe the intrinsic value of social networks. Robert Putnam attributes social capital to "civic engagement" and as an indicator of "communal health". Pierre Bourdieu describes how social capital explains how people find jobs through their social connections. Similarly, the strength of weak links, describes the importance of social relations in job searches.

In general social capital can be described in terms of bridging capital and bonding capital. Bridging capital is the notion that chance, long range social connections, that we build as part of our social interactions, can help us connect with heterogeneous groups. The idea of "bridges" in social relation is again similar to the notion of connectors in the book "Tipping Point" by Malcolm Gladwell. As Gladwell describes it 

"Connectors are people who link us to the world ... people with a special gift for bringing the world together"

So how can we quantify the connectors? According to the Wikipedia entry:

"There is no widely held consensus on how to measure social capital, which is one of its weaknesses."

One simple way to explain such relations is to use the analogy of bridges. These are individuals who link across the different departments in your office, they are the researchers who have worked with people from other fields and universities. We all know such people and run to them to find our link to the "other side of the planet". One measure that might be useful in quantifying bridging capital is "Edge betweenness". It is a measure that indicates the number of all pair shortest paths that flow through an edge.  In other words, if the edge is removed, many pairs of nodes need to follow a longer path to communicate with each other. Edge-betweenness is also used in some of the community detection techniques. By iteratively removing edges that are most in-between, we can identify the communities that exist in a social network.

Bridging capital is easier to conceptualize than bonding capital. Bonding capital is defined as

"the value assigned to social networks between homogeneous groups of people"

Another way of thinking about bonding capital is as follows: If you were in an urgent need for $500, which you promised to return the next day -- whom would you turn to? The person most likely to lend you the money is one with whom you share a strong bond. In my opinion, one simple way in which bonding capital can be quantified is by measuring the "strength of ties" or the number of common relations you share with another individual. If we think about business partners, it is quite likely that they share the same set of social relationships. Thus their bonding capital will be quite high. By identifying social relationships, which if removed would cause the least effect in the overall shortest path distance between other nodes, we can identify the edges that have a high bonding capital.

Here is a simple example, from the classic karate club dataset. In this graph there are 34 nodes that represent the members of a karate club. During this study the group split into two with half the members going to the founder of the club, node 34 and the rest to the instructor, node 1. Here we can find interesting examples of bridging and bonding capital. The edge between node 33 and node 34 reflect a high bonding capital.. both these nodes have several friends in common. On the other hand the link from 9 to 1 among others are examples of bridging capital.

I would also like to point out a very interesting piece of research by Dr. Tufekci on social relations in Facebook. According to her study, she found that women use Facebook as a means to establish bonding capital while men are trying to increase bridging capital. This is an excellent study on Facebook from a social science perspective and I would highly recommend reading it.

Clustering Tags and Links Simultaneously

I have a large collection of blogs that I would like to cluster. For the blogs in my collection, I have the following information:

• Text aggregated across all the posts
• A dump of the homepage of the blog
• Tags obtained from del.icio.us or "Feeds that matter"
• And finally how the blogs link to each other (aggregated across all the posts)

If we want to cluster the blogs, one can take the following approaches:

1. Cluster the blogs using only the text (Kmeans style)
2. Cluster the blogs using only the link information (By say performing NCut)
3. First cluster all the tags (so you would group "tech", "technology", "geek" etc) and then group the blogs that are categorized in each of these clusters.
4. Using a bipartite graph of the form <Blog,tag>. This is also known as co-clustering.

The problem with using the text alone is that the data can be huge (typically in Gigs) and it is almost essential to use some dimensionality reduction techniques like PCA etc. By performing NCut over the graph alone, you land up ignoring the text or the tag information that could be quite helpful. By clustering in only the tag space and then mapping the resulting clusters to the blog graph, we miss how the blogs might be interconnected. Finally, co-clustering technique too misses the fact that the blogs might link to each other and this information can be quite useful in grouping them together.

The question I was wondering about was how to cluster the blogs while using both the link and the tag information simultaneously. I think that the tags provide a reduce dimensional representation of the text. The tag space is of a much lower dimension than the complete text of the collection and it can be efficient to cluster the blogs using tags than the complete text.

Recently, I came across a very interesting piece of work that talked about "Classification Constrained Dimensionality Reduction". The idea here is that if we have a bunch of data points for which we know the true class information, we would like to classify the remaining points such that the available class information is utilized to guide the dimensionality reduction.

The above paper applied very well to our problem. One simple way to combine the two different information is to use the matrix W' shown here. C is a k*n matrix where n is the number of blogs and k is the number of tags. While W is the adjacency matrix of size n*n. I is an identity matrix of size k*k. Typically, we can get away by using only the top 200-500 most popular tags. Now, if we perform NCut using the matrix W' instead of using W alone, we can combine/fold-in the tag information with the link information. The parameter \beta controls how much importance we would like to give to the graph versus the tag information.

For example for a blog graph consisting of ~3000 blogs, I fetched the tags from del.icio.us and the link graph from the WWE/Buzzmetrics collection. Figure on the right shows 20 clusters if we use just the link information and perform NCut and the same graph using the simultaneous clustering method. Notice, how the 20 odd clusters seem nicely block diagonalized in comparison with the results using link information alone. It would be interesting to look at how these techniques compare with that using the entire text from all the blogs. I am working on this and the intuition is: we might be able to show that using just tag and link information, we can do as good (or better) than using the entire text. Afterall tags are nothing but a place holder for the "topic" of the blog.

An even more interesting extension would be to use the original paper that presented the constrained classification using dimensionality reduction and apply the same technique to our problem, such that we can perform clustering using just a small set of labeled blog and labels (matrix C).

Notes from DEBSM Workshop: Monitoring the Evolution of Interest in Blogosphere

Monitoring the evolution of interests in the blogosphere
Iraklis Varlamis (Presenter), Vasilis Vassalos, Antonis Palaios

The authors present a simple (perhaps even obvious) hypothesis that "Interests of bloggers converge around real world events".

A prototype system was built to to analyze blogs and monitor the evolution of interests. Existing search engines monitor the term popularity of words in isolation and the related terms are not clustered in any way to identify the topics. A motivating example presented was around the football world cup season, where there might be terms like "football" "round" "final" "result" "world cup" and aggregated scores for topic would be helpful rather than having to find/view the histograms for each of these terms. Also one can not know all the terms for a given topic. In many cases, multilingual content and difference in vocabulary can further make it difficult to just monitor the term popularity. Other approaches require training a topic based on a given set of training/pre-annotated document pool. This is an expensive and a semi-supervised method can be strongly effected by the selection of the initial document pool.

The goal of their paper is to build an unsupervised approach to cluster the documents and identify the evolution of interest. However, the current algorithm presented is not incremental; but they claim some recent work on an incremental version. The current version of their algorithm uses the DBScan clustering technique. Term space is clustered at the post level and their evaluation is done using inter cluster, intra cluster similarity and the utility function. They have used the BuzzMetrics dataset, however they only focus on blogs that have a post everyday, which brings the dataset down to 2500 blogs. The posts are classified into topics and then the blogs are clustered. The categories are determined by using the Cyberfiber news groups to find the topics and training documents. This is an interesting dataset that I was not aware of.

Some questions that came up were the choice of using newswire documents to learn classifiers, and also the accuracy of the classifiers. While the original hypothesis seems obvious, it can be seen as a litmus test for the efficacy of the clustering algorithms. In particular the examples presented were using the "London Bombing" Event. Any clustering algorithm that groups the related terms must at the very least pass the litmus test to show that it works.

I think that in general there are perhaps two types of events, one concerning a very specific group of individuals  ("County elections", social events, conferences etc) where online communities emerge due to offline events. The other is around real word events like "London bombings" or "Hurricane Katrina": both of which are examples of events that cut across community boundaries and which invoke reaction from almost every part of the blogosphere and almost in unison. In such cases on might see that the original community affiliation of the bloggers dont matter and tech, politics, religion and every other community might be talking about the same issue.