Social Media Research Blog

Geolocating blogs

A quick note:

Clay Finkand colleagues from UMBC have a new paper on "Geolocating Blogs From Their Textual Content". From the abstract:

"Mashups showing the geographic location of the authors of social media content are popular. They generally depend on the authors reporting their own location. For blogs, auto-mated geolocation strategies using IP address and domain name are not adequate for determining an author’s location. Instead, we detail textual geolocation techniques suitable for tagging social media data, facilitating development of geo-graphic mashups and spatial reasoning tools."

As noted in this paper, trying to geolocate blogs from IP addresses or domain names does not work well due to many blogs mapping to various hosting services. To locate the named entities that refer to a potential location, the authors use GeoNames (This is a really great, free resource for those working with geographical analysis). The location of the blogger is disambiguated by clustering occurances of different geographical named entities in a region. From the paper:

For example, if “Maryland” has already been disambiguated as the U.S. state of Maryland, then the text “Laurel, Maryland” leads us to disambiguate “Laurel” as Laurel, Maryland.

Location is an important element in social media analysis and any results (for example, sentiment analysis or trends) that could be pivoted on this dimension are especially useful in providing an insight into what people in different regions think about a particular topic.

In context of this work, there are a few more related papers (in addition to references in this paper) one might want to check out. Although these papers dont address the same issue, they are interesting from the perspective of location analysis:

• Recent study of "Iran's online public" by Harvard researchers.
• "Spatial variation in search queries" by Backstrom et al.
• A study of blog commentsof persian bloggers by Noor Ali Hasan
• In our work with twitter analysis, we did some basic mapping of location names mentioned in user profiles to lat/long coordinates using Yahoo API.

Exploring the Impact of Profile Injection Attacks in Social Tagging Systems

Live blogging from WebKDD 08:

Exploring the Impact of Profile Injection Attacks in Social Tagging Systems
Maryam Ramezani, J.J. Sandvig, Runa Bhaumik, Robin Burke, and Bamshad Mobasher

Explores how folksonomies can be used for social navigation and protect it from 'self-promotion tags'. in profile injection attacks, users create number of identities and add 'tag spam' for malicious intent. Spurl.net is an example of a social tagging system that was inundated with spam and had to shut down.With various entities (resource, tag and users) the profile injection attacks can effect each of the 'navigation contexts' like: related resources, co-occurring tags, recent items etc. The paper goes in depth into the various classes of such attacks. The paper uses del.icio.us crawls for this study that were split into three partitions: low freq, med freq, high freq.

Two main types of attacks discussed:

• attacks on popular tags
• Piggyback attack: force association of a particular resource with another resource to make it look similar.
• Overload attack: associate popular tags with a target URL.
• Focused overload attack: for a specific target users (say those, using the tag coffee) associate the target URL with those tagged as coffee

One interesting point is that piggyback attack is a problem mostly in the Low and medium freq partitions and just 3-5% of fake user profiles injected (using relatively few number of tags) can cause considerable problems in social tagging systems. The authors present various results based on number of tags, number of profiles etc.

I think as tagging systems become more main stream dealing with spam in such environments is quite important. 

Structure of Information Pathways in Social Networks

One of the papers I am looking forward to at KDD 2008 is "The Structure of Information Pathways in a Social Communication Network"  by Kossinets, Kleinberg and Watts (PDF). This paper analyzes the communication graph of an email network. The authors present two important and novel concepts to social networks research: Temporal distance and Network backbone. They beautifully incorporate a rather Operating Systems textbook technique of vector clocks into the analysis of social networks. Following is an excerpt from the abstract:

....We formulate a temporal notion of “distance” in the underlying social network by measuring the minimum time required for information to spread from one node to another — a concept that draws on the notion of vector-clocks from the study of distributed computing systems. We find that such temporal measures provide structural insights that are not apparent from analyses of the pure social network topology. In particular, we define the network backbone to be the subgraph consisting of edges on which information has the potential to flow the quickest. We find that the backbone is a sparse graph with a concentration of both highly embedded edges and long-range bridges—a finding that sheds new light on the relationship between tie strength and connectivity in social networks.

The authors use vector clocks to determine the nodes that are up-to date with respect to each other and describe a network backbone as

the subset of edges in the social network that are not bypassed by a faster alternate path.

Thus a network backbone is the set of edges that are critical in ensuring the flow of information within the network and thereby responsible for keeping the nodes 'in sync' with respect to each other. The idea of a backbone is not new and many real world networks like the internet are known to have some such equivalent. Traditionally, in social networks most of the attention so far has been on the "strength of weak links".  In this paper, the authors not only validate this phenomena, but also show that these links are critical in the network backbone structure. This is a paper that offers some deep insights and fundamentally advances our knowledge of how information flows in social networks.

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."