Seminars on 30th June 2014 by Hanghang Tong et al.
9:00 – 9:45 Hanghang Tong (City U. of New York, USA): Optimal Dissemination on Graphs: Theory and Algorithms
9:45 – 10:30 Jingrui He (Stevens Inst. of Tech., USA): Heterogeneous Learning
10:30 – 11:15 Tea break, and poster presentations by students of the UCAS InfoVis class (chaired by Lei Shi of Inst. of Software, CAS)
11:15 – 12:00 Jie Tang (Tsinghua U., China): Mining Structural Hole Spanners Through Information Diffusion in Social Networks
Venue: Lecture Hall, Level 4, Building 5, Institute of Software, Chinese Academy of Sciences
Abstracts and biographies:
Title: Optimal Dissemination on Graphs: Theory and Algorithms
Abstract: Big graphs are prevalent and are becoming a popular platform for the dissemination of a variety of information (e.g., viruses, memes, opinions, rumors, etc). In this talk, we focus on the problem of optimally affecting the outcome of dissemination by manipulating the underlying graph structure. We aim to answer two questions: (1) what are the key graph parameters for the so-called tipping point? and (2) how can we design effective algorithms to optimize such parameters in a desired way? We show that for a large family of dissemination models, the problem becomes optimizing the leading eigen-value of an appropriately defined system matrix associated with the underlying graph. We then present two algorithms as the instantiations of such an optimization problem – one to minimize the leading eigen-value (e.g., stopping virus propagation) and the other to maximize the eigen-value (e.g., promoting product adoption). If time allowed, I will also introduce our other work on analyzing big graphs.
Bio: Hanghang Tong is currently an assistant professor at Computer Science Department, City College, City University of New York. Before that, he was a research staff member at IBM T.J. Watson Research Center and a Post-doctoral fellow in Carnegie Mellon University. He received his M.Sc and Ph.D. degree from Carnegie Mellon University in 2008 and 2009, both majored in Machine Learning. His research interest is in large scale data mining for graphs and multimedia. His research has been funded by NSF, DARPA and ARL. He has received several awards, including best paper award in CIKM 2012, best paper award in SDM 2008 and best research paper award in ICDM 2006. He has published over 80 referred articles and more than 20 patents. He has served as a program committee member in top data mining, databases and artificial intelligence venues (e.g., SIGKDD, SIGMOD, AAAI, WWW, CIKM, etc).
Title: Heterogeneous Learning
Abstract: Real-world applications exhibit rich heterogeneity, such as medical informatics, manufacturing, document classification, image classification/retrieval. In the past, researchers have mainly focused on modeling a single type of heterogeneity, such as task/view/instance/oracle heterogeneity. More recently, researchers have started to jointly model more than one type of heterogeneity, which has shown improved performance in the aforementioned applications. In this talk, I will introduce these techniques under the umbrella ‘Heterogeneous Learning’, which aims to address the rich heterogeneous properties in a target application. I will also discuss the application of these techniques in multiple domains, as well as future directions and key challenges.
Bio: Dr. Jingrui He is currently an assistant professor in Computer Science Department at Stevens Institute of Technology. She received her M.Sc and Ph.D degree from Carnegie Mellon University in 2008 and 2010 respectively, both majored in Machine Learning. Her research interests include heterogeneous machine learning, rare category analysis, active learning and semi-supervised learning, with applications in social network analysis, semiconductor manufacturing, traffic analysis, etc. She has published over 40 referred articles and served as the organization committee member of ICML, KDD, etc.
Title: Mining Structural Hole Spanners Through Information Diffusion in Social Networks
Abstract: The theory of structural holes suggests that individuals would benefit from filling the “holes” (called as structural hole spanners) between people or groups that are otherwise disconnected. The fundamental challenge we want to address is to detect users who span structural holes in social networks and how the structural hole spanners influence the information diffusion? We explore the problem of mining top-k structural hole spanners through information diffusion in social networks. We formally define the objective function and provide two instantiation models (HIS and MaxD) to deal with the problem. Optimization of the problem is proved to be NP-hard, and efficient algorithms with provable approximation guarantees have been developed. We test the proposed models on three different networks: Coauthor, Twitter, and Inventor. Our study provides evidence for the theory of structural holes, e.g., 1% of Twitter users who span structural holes control 25% of the information diffusion on Twitter.
Bio: Jie Tang is an associate professor at the Department of Computer Science and Technology of Tsinghua University. He has been visiting at Cornell University, HKUST, and CUHK. His research interests include social network analysis, data mining, and machine learning. He has published more than 100 journal/conference papers and held 10 patents. He has developed a notable system Arnetminer.org for academic social network analysis and mining. The system has already attracted 432 independent IP accesses from 220 countries/regions. He was honored with the CCF Young Scientist Award, NSFC Excellent Young Scholar, IBM Innovation Faculty Award, and the New Star of Beijing Science & Technology. He also served as Workshop Co-Chair of SIGKDD’13, Local Chair of SIGKDD’12, Publication Co-Chair of SIGKDD’11, Program Co-Chairs of ADMA’11, SocInfo’12 and WSDM’15, and also serves as the PC member of more than 50 international conferences.