The Topic-Perspective Model for Social Tagging Systems

Citation

The Topic-Perspective Model for Social Tagging Systems Caimei lu, Xiaohua Hu, Xin Chen, Jung-ran Park, TingTing He, and Zhoujun Li

Online version

http://www.pages.drexel.edu/~cl389/dataset/kdd10-lu.pdf

Summary

In this paper, authors propose LDA type(link LDA) generative model for social annotation. Usually tags associated with a particularly URL belongs to either the content of the URL or the tagger’s perspective about the content of URL. In data mining applications, we would be interested in separating tags associated with the content from tagger’s perspective. In proposed generative model model, we get probability of each tag being associated with content or tagger perspective. This model improves on previously proposed models for same task where user’s perspective is not fully taken in account. Tags associated with user perspective can help in improving personalised search.

Evaluation

They evaluate their methods by asking following 4 questions :

 - Does NF find out meaningful neighborhoods?
 - How close is Approximate NF to exact NF?
 - Can AD detect injected anomalies?
 - How much time these methods take to run on graphs of varying sizes?

Discussion

This paper poses two important social problems related to bipartite social graphs and explained how those problems can be solved efficiently using random walks.

They also claim that the neighborhoods over nodes can represent personalized clusters depending on different perspectives.

During presentation one of the audiences raised question about is anomaly detection in this paper similar to betweenness of edges defined in Kleinber's text as discussed in Class Meeting for 10-802 01/26/2010. I think they are similar. In the texbook they propose, detecting edges with high betweenness and using them to partition the graph. In this paper they first try to create neighbourhood partitions based on random walk prbabilities and which as a by product gives us nodes and edges with high betweenness value.

Related papers

There has been a lot of work on anomaly detection in graphs.

• The paper by Moonesinghe and Tan ICTAI06 finds the clusters of outlier objects by doing random walk on the weighted graph.
• The paper by Aggarwal SIGMOD 2001 proposes techniques for projecting high dimensional data on lower dimensions to detect outliers.

Study plan

• Article:Bipartite graph:[1]
• Article:Anomaly detection:[2]
• Paper:Topic sensitive pagerank:[3]
  • Paper:The PageRank Citation Ranking: Bringing Order to the Web:[4]
• Paper:Multilevel k-way Partitioning Scheme for Irregular Graphs:[5]