题 目：大规模图的采样理论(Sampling Theory of Large Graphs)
日 期: 5.13, 2013 (星期一)
时 间:上午10:30 – 11:30地 点:北京航空航天大学，主楼213会议室报告人：John C.S. Lui教授，香港中文大学，计算机科学与工程系邀请人：刘红英副教授
Characterizing user pair relationships is important for applications such as friend recommendation and interest targeting in online social networks (OSNs). Due to the large scale nature of such networks, it is infeasible to enumerate all user pairs and so sampling is used. In this talk, we show that it is a great challenge even for OSN service providers to characterize user pair relationships even when they posses the complete graph topology.
The reason is that when sampling techniques (i.e., uniform vertex sampling (UVS) and random walk (RW)) are naively applied, they can introduce large biases, in particular, for estimating similarity distribution of user pairs with constraints such as existence of mutual neighbors, which is important for applications such as identifying network homophily. Estimating statistics of user pairs is more challenging in the absence of the complete topology information, since an unbiased sampling technique such as UVS is usually not allowed, and exploring the OSN graph topology is expensive. To address these challenges, we present asymptotically unbiased sampling methods to characterize user pair properties based on UVS and RW techniques respectively.
John C.S. Lui was born in Hong Kong and is currently a full professor in the Department of Computer Science & Engineering at The Chinese University of Hong Kong. He received his Ph.D. in Computer Science from UCLA. When he was a Ph.D student at UCLA, he worked as a research intern in the IBM T. J. Watson Research Laboratory. After his graduation, he joined the IBM Almaden Research Laboratory/San Jose Laboratory and participated in various research and development projects on file systems and parallel I/O architectures.
He later joined the Department of Computer Science and Engineering at The Chinese University of Hong Kong. His current research interests are in Internet, network sciences with large data implications (e.g., online social networks, large scale data analytics,..etc), network/system security (e.g., cloud security, mobile security, ...etc), network economics, large scale distributed systems and performance evaluation theory. John served as the chairman of the CSE Department from 2005-2011. He received various departmental teaching awards and the CUHK Vice-Chancellor's Exemplary Teaching Award. John also received the CUHK Faculty of Engineering Research Excellence Award (2011-2012). John is a co-recipient of the IFIP WG 7.3 Performance 2005 and IEEE/IFIP NOMS 2006 Best Student Paper Awards. He is an elected member of the IFIP WG 7.3, Fellow of ACM, Fellow of IEEE, Senior Research Fellow of the Croucher Foundation and is currently the chair of the ACM SIGMETRICS. His personal interests include films and general reading.