Sponsor:

National Science Foundation (NSF)

Project Team Members:

• Alok Choudhary
• Wei-keng Liao
• Ankit Agrawal
• Mostofa Patwary
• Zhengzhang Chen
• Yu Cheng
• Dan Honbo
• Kathy Lee
• Diana Palsetia
• Yves Xie
• Kunpeng Zhang
• Bharath Pattabiraman

---

---

Understanding, Analyzing, and Retrieving Knowledge from Social Media

---

Overview

Social Media has become one of the most popular platforms to allow users to communicate, and share their interests without being at the same geographical location. With the rapid growth of Social Media sites such as Facebook, LinkedIn, Twitter, Customer reviews (e.g. Amazon, CNET) and Blogs (e.g. WSJ Blogs), there is vast amount of user-generated content. Our goal is to retrieve valuable nuggets of knowledge from this huge amount of data and help users make informed decisions. To achieve this goal, the specfic objectives of the project are as follows.

• Constructing useful information networks from raw datasets.
• Understanding and analysizing useful structures, patterns, and communities in networks.
• Analysis of temporal and special dynamics in networks.
• Analysis of social reputation, influence, and trust.
• User activity modeling, profiling, exploration, and recommendation systems.
• Developing new data mining and machine learning algorithms for social networks.
• New applications and impact of social media in other areas of research.

Our current progress on this project can be categorized in two broad categories.

Community Mining

The rapid evolution of modern social networks motivates the design and understanding of networks based on users' interest. Using popular social media such as Facebook and Twitter, we present new perspective to bring out more meaningful information about the networks. Instead of using traditional user networks of Facebook and Twitter, we deduce user interest based networks using posts, comments, and tweets. Our approach is able to closely capture relations found in static networks and also finds affiliations that are constantly evolving either due to temporal or spatial activities. Further, we develop a new approach for mining communities to understand and analyze the structure of social networks. Our user-interest based model and community extraction algorithm together can be used to identify target communities in the context of business requirements. Figure 1 shows several such focused communities that belong to categories such as Technology (c231), Consumer Merchandize (c232), Retail (c243), Travel and Leisure (c244), Food (c248) and Baby Products (c251). We got many more interesting focused communities. Note that using the existing approaches, most of these focused communities belong to one large community, which does not reflect the structure of the network.

Figure 1. Partial dendrogram showing communities in Facebook.

In addition, we also explore newer methods to extract communities from a given network. In many real networks vertices may belong to more than one group, and such groups form overlapping communities. Classical examples are social networks, where an individual usually belongs to different circles at the same time, from that of work colleagues to family, sport associations, etc. Finding such overlapping community is a challenging problem, and is not supported by traditional community detection algorithms. We devised a hierarchical pruning based heuristic algorithm for finding the maximum clique for a given graph. The details on the maximum clique algorithm and source code are available online. We are currently working on extending the clique algorithm to identify the communities for massive networks. Using this, we also devised a clique-based community detection algorithm which is capable of finding overlapping communities. Figure 2 shows some of the communities detected. We see two isolated communities, one for popular singers, and another for retail chains and products. We also see a community for news channels and politics, and a community of MSNBC and popular TV shows. The highlight of our algorithms is that it allows a node to be a member of more than one community giving an overlapping community structure. Although the "news channels and politics" and "MSNBC and tv shows" communities are not directly related and have different members, they share a common member.

Figure 2. Some Facebook communities detected by our clique-based community finder.

Text Mining

Enormous amounts of messages get published each day on social media sites. For example, Twitter processes 230 million tweets (messages that are 140 characters long) a day (twitterstats). The explosion of textual messages can cause information overload. Our goal is to design systems that can analyze and summarize social media content. The current work encompasses two main themes:

Sentiment Analysis

• The goal is to mine opinions from social media data at sentence and document level.
• Design a framework that can determine the sentiment (positive, negative, or neutral) overcoming social slang and lingos, non-textual expressions and language.

SES Framework

The Sentiment Elicitation System (SES) is a sentiment identification framework which consists of three sentiment identification algorithms. First algorithm is based on Compositional Semantic Rules. The rule set is augmented to overcome poor grammar and part-of-speech tagging and results in numeric score in the range -10 to +10. The second algorithm associates numeric score in the range -5 to +5 for textual sentiments by incorporating user star ratings in reviews along with word appear frequency. The third algorithm makes use of emoticons, negation word position and domain-specific words and characterizes the sentiment as positive, negative or neutral. A predictive model (e.g. Decision Tree, Neural Network) is trained on 3 basic features i.e. output of each of the three algorithms namely S1, S2 and S3 and two derived features: a) S1 + S2 b) S2 - S1 to predict sentiment.

Figure 3: SES Architechture.

Text classification

• The goal is to group similar text or messages that can make information more manageable.
• Employ framework that can cluster similar text belong to the same topic and several similar topics that can belong to a broad category.

Constraint Mixture Clustering Framework

The proposed framework utilizes priori information such as label signs or pairwise constraints that can easily obtained from the social media sites with very little human intervention. For example, messages on Barak Obama's Facebook page and comments made by other users on these messages are constrained to the class politics. The framework integrates pairwise constraints and labels to infer data for learning. The framework uses model-based clustering/classification in which the data is generated by a model and tries to recover the original model from the data. The model recovered defines the clusters and assignment of data points to clusters. The proposed framework shows significant improvement over baseline classifiers such as semi-supervised K-Means and Transductive SVM. For future work, the goal of the framework would be to derive the pairwise constraints automatically from auxiliary information for many real world applications.

Figure 4: The general framework of learning to clustering web text with the CML model.

Text and Network based Classification Framework



Figure 5: System Architecture.
The goal of this framework is to classify trending topics (news or event for which messages are in high volume) on Twitter into known categories such as sports, politics etc. The framework is capable of classifying topics using traditional text-based techniques as well as a novel technique which uses Twitter specific network information (network-based). In text-based approach textual data such as topic definition, tweets and pre-assigned labels form the text document. Document is transformed into word tokens along with their frequencies to infer data for learning. The framework then uses traditional classification kernels (e.g. Naive Bayes, SVM) to predict the topic class based on the previously trained examples. In the network-based approach, the topic class is predicted based on the class of topics similar to it. Similarity between two topics is defined using User Similarity metric which assumes that if there is significant overlap among influential users generating content on two topics, then there is close relationship between these two topics. Therefore, the network based model can predict the class of the target topic using the categories of its similar topics. For example, Figure 5 shows the number of common influential users that generated content regarding target topic Macbook and its similar topics. Using the common influential count and class of the similar topics, the classifier (e.g. Decision Tree) develops model to predict category for future topics. The experiments on Twitter dataset reveal higher prediction accuracy for network based classification compared to text-based classification technique. Since the network model is dependent on finding similar topics, our next step would be to integrate the two models in the framework so that text based model can be employed when the network based model cannot be employed.

Figure 6: Trending topic "macbook" and its 5 similar topics "iwork", "magic trackpad", "#landsend", "apple ipad" and "mobileme".

Publications

1. Bharath Pattabiraman, Mostofa Patwary, Assefaw Gebremedhin, Wei-keng Liao, and Alok Choudhary. Fast Algorithms for the Maximum Clique Problem on Massive Sparse Graphs. In the 10th Workshop on Algorithms and Models for the Web Graph, December 2013. (pdf) 
2. Diana Palsetia, Md Mostofa Ali Patwary, Kunpeng Zhang, Kathy Lee, Christopher Moran, Yusheng Xie, Daniel Honbo, Ankit Agrawal, Wei-keng Liao, and Alok Choudhary. User-Interest Based Community Extraction in Social Networks. In the Workshop on Social Network Mining and Analysis, held in conjunction with the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 2012. (pdf) 
3. Yu Cheng, Kunpeng Zhang, Yusheng Xie, Ankit Agrawal, Wei-keng Liao, and Alok Choudhary. Learning to Group Web Text Incorporating Prior Information. In the Workshop on Optimization Based Methods for Emerging Data Mining Problems, held in conjunction with the IEEE International Conference on Data Mining, December 2011. (pdf) 
4. Lalith Polepeddi, Ankit Agrawal, and Alok Choudhary. Poll: A Citation-Text-Based System for Identifying High-Impact Contributions of an Article. In the Workshop on Data Mining in Networks, held in conjunction with the IEEE International Conference on Data Mining, December 2011. (pdf) 
5. Kunpeng Zhang, Yu Cheng, Yusheng Xie, Ankit Agrawal, Diana Palsetia, Kathy Lee, Wei-keng Liao, and Alok Choudhary. SES: Sentiment Elicitation System for Social Media Data. In the Workshop on Sentiment Elicitation from Natural Text for Information Retrieval and Extraction, held in conjunction with the IEEE International Conference on Data Mining, December 2011. (pdf) 
6. Kathy Lee, Diana Palsetia, Md Mostofa Ali Patwary, Ankit Agrawal, Alok Choudhary, and Ramanathan Narayanan. Twitter Trending Topic Classification. In the Workshop on Optimization Based Methods for Emerging Data Mining Problems, held in conjunction with the IEEE International Conference on Data Mining, December 2011. (pdf) 
7. Kunpeng Zhang, Yu Cheng, Wei-keng Liao, and Alok Choudhary. Mining Millions of Reviews: A Technique to Rank Products Based on Importance of Reviews. In the International Conference on Electronic Commerce, August 2011. (pdf)  This paper was awarded Honourable Mention at the conference ICEC 2011, Liverpool, England.
8. Alok Choudhary, William Hendrix, Kathy Lee, Diana Palsetia, and Wei-keng Liao, Social Media Evolution of The Egyptian Revolution. Communications of the ACM, 55(5):74-80, ACM, New York, NY, USA, May 2012.  (pdf) .

Related Work

DiscKNet: Discovering Knowledge from Scientific Research Networks.

Source Code

Fast algorithms to find maximum clique in massive graphs

Sentiment Service (API)

Register for trial version of sentiment service (API)

Datasets

Facebook comments, Tweets, Amazon reviews sample datasets