Invited Talk: Reachability Query, Shortest Distance Query, and Graph Pattern Matching over Large Graphs

There are numerous applications that need to deal with a large graph, including bioinformatics, social science, link analysis, citation analysis, and collaborative networks. A fundamental query is to query whether a node is reachable from another node in a large graph, which we call a reachability query. Another fundamental query is to query the shortest distance between two nodes in a large graph, which we call a shortest distance query. It is well known to be inefficient to answer such queries on demand or to precompute and maintain all answers on disk. The former requests high computational cost and the latter requests high storage cost. In this talk, we first discuss on computing a graph labeling, called 2-hop, for a large directed graph efficiently, in order to process reachability queries and shortest distance queries online. In addition, we discuss graph pattern matching which is to find all patterns in a large graph that match a user-given graph pattern based on reachability.

Speaker
Dr Jeffrey Xu Yu is a Professor in the Department of Systems Engineering and Engineering Management at the Chinese University of Hong Kong. His current main research interests include graph mining, graph query processing, graph pattern matching, and keywords search in relational databases. Dr. Yu served/serves in over 200 organisation committees and programme committees in international conferences/workshops. Dr. Yu also served as an associate editor of IEEE Transactions on Knowledge and Data Engineering (2004-2008), and serves in VLDB Journal editorial board and ACM SIGMOD executive committee. He has published over 200 papers including papers published in reputed journals and major international conferences.

Industry Talk: Advertising for Product Adoption through Social Networks

Online social networks offer opportunities to analyze user behavior and social connectivity, and leverage resulting insights for effective online advertising. We study the adoption of a paid product by members of a large and well-connected Instant Messenger (IM) network. We find that adoption by highly connected individuals is correlated with their social connections (friends) adopting after them.

However, there is little evidence of social influence by these high degree individuals. At the same time, we observe strong evidence of peer pressure wherein future adoption by an individual is more likely if the product has been widely adopted by the individual's friends.

Using these insights we build predictive models to identify individuals most suited for two types of marketing campaigns - direct marketing and social neighborhood marketing. We identify the most desirable features for predicting future adoption which can in turn be leveraged to effectively promote its adoption. Offline analysis shows that building predictive models for direct marketing and social neighborhood marketing outperforms several widely accepted marketing heuristics. Further, these models are able to effectively combine user features and social features to predict adoption better than using either user features or social features in isolation.

Speaker
Vineet Chaoji is a Senior Associate Scientist in the Advertising Sciences group at Yahoo! Labs Bangalore. His research interests include large scale graph mining, social network analysis and applied machine learning. Prior to joining Yahoo! Labs he got his PhD in Computer Science from Rensselaer Polytechnic Institute under the supervision of Prof. Mohammed Zaki. He has served on the program committee for KDD, ECML/PKDD and PAKDD conferences.

Research Presentations

Trust Mining - A Discovery of Rules and Behaviors

Social networks contain social links carrying different degrees of trust. In this research, we will give an overview of some ongoing trust mining research projects within the School of Information Systems of Singapore Management University. In trust link prediction, we propose a trust antecedent framework for determining relevant user behaviorial attributes for training prediction models. We further examine trust reciprocity user behaviorial attributes that allow reciprocal trust prediction to be performed accurately. Finally, we demonstrate that trust links are generally formed using some rules and such rules can be discovered using our proposed link formation rule mining methodology and algorithms. These research efforts were conducted on real social network data giving us an valuable insights into the user-level behaviorial knowledge.

Speakers
Ee-Peng Lim is a professor at the School of Information Systems of the Singapore Management University (SMU). His research interests include social network/web mining, information integration, and digital libraries. He is currently an Associate Editor of the ACM Transactions on Information Systems (TOIS), Social Network Analysis and Mining Journal, IEEE Intelligent Systems, and other journals. He is a member of the ACM Publications Board. He is on the Steering Committee of the International Conference on Asian Digital Libraries (ICADL) and the Pacific Asia Conference on Knowledge Discovery and Data Mining (PAKDD).

Cane Leung is a postdoctoral researcher in the School of Information Systems at the Singapore Management University. She is a member of the Social Network Mining Research Group led by Professor Ee-Peng Lim. Cane obtained her Ph.D. in Computer Science from The Hong Kong Polytechnic University in 2009. Her research interests include data and text mining in social network and user-generated content.

Understanding the Psychological Motives Behind Microblogging

This research aims to understand the psychological motives behind microblogging. We conducted two studies to investigate if social exclusion and existential anxiety would lead to a high tendency to microblog. Our results showed that participants did not use microblogging to satisfy their needs for social connection and affiliation, but highly extraverted participants did use it to relieve their existential anxiety.

Speaker
Qiu Lin is an assistant professor at the School of Humanities and Social Sciences of Nanyang Technological University. His main research interests are human-computer interaction and engineering psychology. He studies the impact of technology on human cognitive and social behaviors, and incorporates the results of empirical studies to the design of innovative technologies. His previous work has contributed to US National Science Foundation-funded projects in the area of knowledge management, interactive learning, and educational critiquing. He has received research grants from Microsoft Research, Hewlett-Packard, and NSF to design the next generation digital sketch-based user interfaces and study their impact on teaching and learning.  Dr. Qiu has been invited to deliver workshops to IT professionals and provide consultation to technology companies on interaction design and usability engineering.

Mining Diversity on Social Media Networks

The fast development of multimedia technology and increasing availability of network bandwidth has given rise to an abundance of network data as a result of all the ever-booming social media and social websites in recent years, e.g., Flickr, Youtube, MySpace, Facebook, etc..   Social network analysis has therefore become a critical problem attracting enthusiasm from both academia and industry. However, an important measure that captures a participant's diversity in the network has been largely neglected in previous studies. Namely, diversity characterizes how diverse a given node connects with its peers. In this paper, we give a comprehensive study of this concept. We first lay out two criteria that capture the semantic meaning of diversity, and then propose a compliant definition which is simple enough to embed the idea. Based on the approach, we can measure not only a user's sociality and interest diversity but also a social media's user diversity. An efficient top-k diversity ranking algorithm is developed for computation on dynamic networks. Experiments on both synthetic and real social media datasets give interesting results, where individual nodes identified with high diversities are intuitive.

Speaker
Feida Zhu is currently an Assistant Professor at the School of Information Systems in Singapore Management University. His research interests are data mining, web mining, algorithms and complexity analysis for data mining and database problems. He got his Ph.D. in Computer Science from University of Illinois at Urbana-Champaign under the supervision of Prof. Jiawei Han and Prof. Jeff Erickson in 2009.  During his Ph.D. study, he has won two Best Student Paper Awards from ICDE (International Conference on Data Engineering Conference) 2007 and PAKDD (The Pacific-Asia Conference on Knowledge Discovery and Data Mining) 2007 respectively.