Sense Networks: Mining Location Data

There is an enormous amount of location data being generated by cell phones, wi-fi enabled devices, and gps devices every minute. Sense Networks, a company founded by Columbia University and MIT faculty members, is a company that mines this location data in real-time to discover behavioral patterns of mobile phone users. One simple mobile application that the company has produced is CitySense, which produces an activity "heat map" of a city, showing the user where all of the busiest locations are in real-time. "Citysense shows the overall activity level of [a] city, top activity hot spots, and places with unexpectedly high activity, all in real-time. Then it links to Yelp and Google to show what venues are operating at those locations."

At the heart of Sense Networks' technology is the MVE algorithm:

Sense Networks attributes 487,500 dimensions to every place in a city, thus identifying a unique and complex 'DNA' which describes it completely... Proprietary MVE (Minimum Volume Embedding) algorithms reduce the dimensionality of location and temporal data to 2 dimensions while retaining over 90% of the information.

The company eventually plans to produce an application that learns the movement patterns of a mobile phone user over time, subsequently providing recommendations for places to visit when the user visits a new city. For example, if you like to visit ice-cream shops in your hometown, the application will automatically learn this behavior. When you go to visit another city in another state, the application can automatically "sense" and report to you where the most popular ice-cream shops are in that city based on location data from other ice-cream lovers.

The application of this kind of technology to social networks and consumer-enriching applications is exciting, but the privacy implications can be frightening. Sense Networks has a special executive called the CPA (the "Chief Privacy Advocate") who deals with privacy concerns. Their philosophy is to give a user complete ownership over the data they choose to share, as well as a provision for the user to easily delete at any time the data they have already chosen to share.

Resolving Blog Entities

Problem: How do you determine whether a particular url is associated with a feed? For example, if another blog posted a link to datamining.blogspot.com, how would you determine the feed (http://datamininglab.blogspot.com/feeds/posts/default) associated with that url?

Solution: In our research we perform two operations to determine whether a url has an associated feed. First, we determine whether the url represents an actual feed. This can usually be determined by submitting an http request and checking the content-type header included in the response. If the content-type is "application/rss+xml", "application/atom+xml","application/rdf+xml" or "text/xml" then you are probably dealing with a feed.
Second, you need to check to see if the url is not a feed, but is associated with a feed. This would be the case in situations where a url was to the front page or a specific entry of a blog. If the content-type in the http response, as describe in step one, was not a feed, then you would parse the "link" tags found between the "head" tags. If a "link" tag has a "rel=alternate" attribute then you can check the type attribute to see if it has a value equal to "application/rss+xml" or "application/atom+xml" similar to what we did in step one. If it does, then you can parse the value of the href attribute to retrieve the feed url associated with the url. For example, on the main page of our blog, if you look at the page source, you will see link tags to both the rss and atom feeds associated with our blog.
There are certainly other ways for resolving blog entities, but this seems to work fairly consistently. Feel free to chime in if you have any ideas on how to better accomplish this task.

Google Reader API

Problem: To perform social network analysis on blog data you need consistent data over a period of time. Periodically retrieving the content directly from the blog's feed has its limitations because you can only retrieve current blog content. Thus if you decide to begin retrieving content from a specific blog, you have no way at getting at the archived blog content.

Solution: Use the unofficial Google Reader API to retrieved archived feed content. The API was first documented two years ago at Nial Kennedy's blog and its reality was confirmed by several Google employees associated with the project. Little information has been published since as to an official release of the API, but the unofficial API still works great for retrieving archived feed content.

In our research the framework we use for interacting with the API is pyrfeed. The creators or pyrfeed also did some additional documentation on the capabilities of the API. The Google Code site has two downloadable files. The Google Reader stand alone is a simple interface for interacting with the API to perform simple actions such as feed retrieval. The other file, which is the full pyrfeed release, also provides gui and command line interfaces for interacting with the API and automated blog content storage in a mysqlite3 database. An example how to interact with the Google Reader stand alone package can be seen below.
In summary, if you are looking for a simple way to retrieve archived blog content, the Google Reader API and pyrfeed framework are cheap and easy tools for doing so. The blogosphere is at your fingertips.

Social Capital?

My last post was titled Social Capital in the Blogosphere and dealt with the experiments we are conducting into the social capital found in blog networks. When you saw the title, some of you probably wondered social capital...what's that? I do not claim to be an expert on social capital, but I have a fair idea of what it is and how it is useful. Interpretations vary, but our idea of social capital has been motivated by that of Robert Putnam, author of Bowling Alone who came and spoke here at BYU last year.

In many realms who you know may matter just as what you know. The value represented by these connections in a social network is known as the social capital of that network. In our work, we compute the social capital of a blog network by using a mathematical formula that takes into account both the actual and potential bonding (connectons with similar people) and bridging (connections with dissimilar people) of blog networks. A more detailed description of this formula can be found in this paper. Matt also recently posted about other ways of measuring social capital. His findings can be found here and here. The social capital of a network can then be used to determine how much value furthering connections in that social network would have. In our example, it would tell you whether or not you should attempt to establish a place in a certain blog network. Thanks for your comments, hopefully this gives you a good intro to social capital in the context we are using it.

Social Capital in the Blogosphere

For the past year, Matt and I (Nate) have been conducting research into the social capital that can be found online in blog networks. Why should you care? Well, first off, you're reading a blog so you must have some interest in the overall blogging community. But more importantly, blogs are being used to establish the identity of people, places and products. In today's online age, the potential of blogs is tremendous. Here's a quick summary of our research.

What: Analysis has been done on the explicit connections (links, comments, friend lists) between blogs. Little work has been done regarding the implicit connections (interests, hobbies, location) that exist between blog authors. We are conducting research into methods of using both explicit and implicit connections in social network analysis.

How: We have retrieved a large archive of blog content for use in our research. An explicit social network of the content is created from the hyper links found in the blog content. Using topic extraction methods such as Latent Dirichlet Allocation, a network of implicit connections is constructed. Overlaying the implicit network on the explicit network allows for potential and actual connections or social capital to be identified. A example graphical representation of one of these networks, which we created using Cytoscape, is found below.


Why: Information about actual social communities, and the implicit similarities that exist between them, can be used to recommend potentially valuable actions that could be taken. For example, a politician could contact influential blogs and attempt to convince them to lead a grassroots campaign for his candidacy. A doctor could use social network analysis to identify and coordinate with colleagues in order to help patients with rare diseases. Companies could approach blogs that are found in the center of their customer market about participating in usability testing or marketing campaigns. Conducting social network analysis on blogging communities has valuable potential in many domains.

You can learn more of the details about our research here at our lab wiki.