讲座主题：
Sampling Large Networks:Algorithms and Applications
主讲人姓名及介绍：
John C.S. Lui现任香港中文大学计算机科学与工程系卓明教授。他目前的研究兴趣是网络系统的在线学习和机器学习、量子网络、网络经济学、网络/系统安全、大规模分布式系统和性能评估理论。约翰获得了多个部门教学奖和中大校长模范教学奖，以及中大工程研究学院卓越奖（2011-2012）。他是IFIP WG 7.3 Performance 2005、IEEE/IFIP NOMS 2006和SIMPLEX'14最佳论文奖、ACM RecSys '17最佳论文奖和ACM Mobihoc'18和ASONAM'17最佳论文亚军的共同获得者。他是IFIP WG 7.3，ACM，IEEE研究员，Croucher Foundation高级研究员，香港学院工程与科学研究员和HK RGC高级研究员，IEEE研究员。他的个人兴趣包括电影和阅读。
报告摘要：
通常，大型网络可以表示为图形。例如，互联网拓扑可以表示为无向图，而大型逻辑网络（例如Facebook、Twitter等）可以表示为有向图或无向图。对于这些图，表征节点对关系对于在线社交网络(OSN)中的好友推荐和兴趣定位等应用很重要。由于此类网络的大规模性质，枚举所有用户对是不可行的，因此使用采样。在本次演讲中，我们表明，即使对于OSN服务提供商而言，当他们拥有完整的图拓扑时，表征用户对关系也是一个巨大的挑战。原因是当采样技术（即均匀顶点采样和随机游走）被天真地应用时，它们会引入很大的偏差，特别是在估计用户对的相似性分布时，例如存在相互邻居。在没有完整的拓扑信息的情况下，估计用户对的统计数据更具挑战性，因为通常不允许使用无偏采样技术，例如统一顶点采样，并且探索OSN图拓扑的成本很高。为了应对这些挑战，我们提出了渐近无偏采样方法来表征用户对属性。我们还展示了潜在的应用并讨论了未来的研究工作。
