My main research interests include social and information networks, online learning, algorithmic game theory, Internet economics, distributed computing, and fault tolerance. I have been serving on the PCs or Senior PCs of the top data mining and database conferences, such as KDD, WSDM, WWW, SDM, SIGMOD, ICDE, etc. I am a member of the Big Data Task Force of Chinese Computer Federation.
I am also an Adjunct Professor in the Institute of Interdisciplinary Information Sciences, Tsinghua University and Adjunct Researcher in the Institute of Computing Technology, Chinese Academy of Sciences. In IIIS Tsinghua, I teach a Distributed Computing course to undergraduate students in the Tsinghua Xuetang Special Pilot CS Class adminstrated by the Institute of Interdisciplinary Information Science, headed by Turing Award Winner Prof. Andrew Yao. I also coordinate between MSRA and IIIS on student curriculum, research practices, and co-supervise graduate students of IIIS.
I obtained my bachelor and master degrees from the Department of Computer Science and Technology, Tsinghua University, and my Ph.D degree from the Department of Computer Science, Cornell University. I worked for Oracle Corporation before joining MSRA.
I served as the captain of Tsinghua University Varsity soccer team, which won Beijing Inter-collegiate Championship twice in 1992 and 1993. I also served as the captain of the “Tsinghua Veterans” soccer team in North America, which won the championship title of the Annual North America Chinese Soccer Tournament twice in 1996 and 1997. I am now a team member of Tsinghua Ling Pao alumni soccer team, which won the Championship of 2012 Tsinghua Alumni Cup and the Championship of 2013 Beijing Intercollegiate Alumni Cup.
Professional association committees
- Member of Task Force on Big Data, China Computer Federation (CCF TFBD), 2012 –
- Organizer of the International Workshop on Computational Aspects of Social and Information Networks (CASIN’2011), July 20-22, 2011, Beijing, China.
- Organizer of Microsoft Research Asia Theory Workshop, April 2008
Editorial boards/Journal guest editors
- Member of the editorial board of Big Data Research, China Posts and Telecom Press.
- Member of the associate editorial board of Computational Social Networks, SpringerOpen.
- Guest co-editor for the special issue on Computational Aspects of Social and Information Networks (CASIN) at ACM Transactions on Knowledge Discovery in Data (CASIN-TKDD)
Conference program committees, journal reviewers
- PC co-chair for the 26th International World Wide Web Conference (WWW’17) Poster Track, 2017.
- Program committee member for the 26th International World Wide Web Conference (WWW’17), 2017.
- Program committee member for the SIAM Data Mining conference (SDM’17), 2017.
- Program committee member for the 30th Annual Conference on Neural Information Processing Systems (NIPS’16), 2016.
- Program committee member for the 2016 IEEE International Conference on Big Data (BigData’16), 2016.
- Program committee member for the 22nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD’16), 2016.
- Program committee member for the 25th International World Wide Web Conference (WWW’16), 2016.
- Program committee member for the SIAM Data Mining conference (SDM’16), 2016.
- Senior program committee member for the 9th International Conference on Web Search and Data Mining (WSDM’16), 2016
- Program committee member for the Social Influence Analysis Workshop (SocInf’15) at IJCAI, 2015.
- Program committee member for the 2015 European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECMLPKDD), 2015.
- Program committee member for the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM’15), 2015.
- Program committee member for the 11th Ad Auction Workshop (AdAuction’15), 2015.
- Program committee member for the 21st ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD’15), 2015.
- Program committee member for the 24th International World Wide Web Conference (WWW’15), 2015.
- Program committee member for the SIAM Data Mining conference (SDM’15), 2015.
- Senior program committee member for the 8th International Conference on Web Search and Data Mining (WSDM’15), 2015.
- Program committee member for the 20th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD’14), 2014.
- Program committee member for the 23rd International World Wide Web Conference (WWW’14), 2014.
- Program committee member for ACM SIGMOD International Conference on Management of Data (SIGMOD’14), 2014.
- Program committee member for the 30th IEEE International Conference on Data Engineering (ICDE’14), 2014.
- Program committee member for the first IEEE International Conference on Bid Data (BigData’13), 2013.
- Program committee member for the 19th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD’13), 2013.
- Program committee member for the 22nd International World Wide Web Conference (WWW’13), 2013.
- Program committee member for the 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO’13), 2013.
- Program committee member for the 19th Annual International Computing and Combinatorics Conference (COCOON’13), 2013.
- Programm committee member for the 10th Annual Conference on Theory and Applications of Models of Computation (TAMC’2013), 2013.
- Program committee member for the 6th International Conference on Web Search and Data Mining (WSDM’13), 2013.
- Program committee member for the 8th International Conference on Advanced Data Mining and Applications (ADMA’12), 2012.
- Program committee member for the 6th International AAAI Conference on Weblogs and Social Media, 2012 (ICWSM’12), 2012.
- Program committee member for the 9th Annual Conference on Theory and Applications of Models of Computation (TAMC’12), 2012.
- Program committee member for the 32nd IEEE International Conference on Distributed Computing Systems (ICDCS’12), 2010.
- Vice program committee co-chair of the 7th International Conference on Advanced Data Mining and Applications (ADMA’11), 2011.
- Program committee member for the Joint Conference of the 5th International Frontiers of Algorithmics Workshop and the 7th International Conference on Algorithmic Aspects of Information and Management (FAW-AAIM’11), 2011.
- Program committee member for the 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO’11), 2011.
- Program committee member for the 12th International Conference On Distributed Computing and Networking (ICDCN’11), 2011.
- Program committee member for the 14th International Conference On Principle Of Distributed Systems (OPODIS’11), 2010.
- Program committee member for the 29th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2010 (PODC’10)
- Program committee member for the 30th IEEE International Conference on Distributed Computing Systems, 2010 (ICDCS’10)
- Program committee member for the 7th Annual Conference on Theory and Applications of Models of Computation, 2010 (TAMC’10)
- Program committee member for the 13th International Conference On Principle Of Distributed Systems, 2009 (OPODIS’09)
- Program committee member for the 20th International Symposium on Algorithms and Computation, 2009 (ISAAC’09)
- Program committee member for the 3rd International Frontiers of Algorithmics Workshop, 2009 (FAW’09)
- Program committee member for the 2nd ACM Workshopon Social Network Systems, 2009 (SNS’09)
- Program committee member for the 39th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, 2009 (DSN’09)
- Program committee member for the 29th IEEE International Conference on Distributed Computing Systems, 2009 (ICDCS’09)
- Program committee member for the 10th International Symposium on Stabilization, Safety, and Security of Distributed Systems, 2008 (SSS’08)
- Program committee member for the 27th IEEE International Symposium on Reliable Distributed Systems, 2008 (SRDS’08)
- Program committee member for the 28th IEEE International Conference on Distributed Computing Systems, 2008 (ICDCS’08)
- Program committee member for the 4th International Conference on Algorithmic Aspects in Information and Management, 2008 (AAIM’08)
- Program committee member for the 26th IEEE International Symposium on Reliable Distributed Systems, 2007 (SRDS’07)
- Program committee member for the first ACM Workshop on Scalable Trusted Computing, 2006 (STC’06)
- Program committee member for the 12th Pacific Rim International Symposium on Dependable Computing, 2006 (PRDC’06)
- Program committee member for the International Conference on Dependable Systems and Networks, 2006 (DSN’06)
- Program committee member for the International Workshop on Applications and Economics of Peer to Peer Systems, 2005 (AEPP’05)
- Program committee member for the 11th Pacific Rim International Symposium on Dependable Computing, 2005 (PRDC’05)
- Program committee member for the 25th International Conference on Distributed Computing Systems (ICDCS’05)
- Ad hoc referee for ACM Transactions on the Web, ACM Transactions on Intelligent Systems and Technology, IEEE Transactions on Knowledge and Data Engineering, IEEE Transactions on Parallel and Distributed Systems, IEEE Transactions on Software Engineering, Data Mining and Knowledge Discovery Journal, Distributed Computing, Journal of Parallel and Distributed Computing, IEEE International Conference on Dependable Systems and Networks, IEEE International Symposium on Reliable and Distributed Systems, International Symposium on Distribute Computing, Theoretical Computer Science, Information Processing Letters, Parallel Processing Letters, Journal of Combinatorial Optimizations, etc.
- Expert reviewers for National Science Foundation of China
Talks and Tutorials
Tutorial and Guest Lectures
- Guest lecture at Peking University: Information diffusion in social networks. Nov. 18, 2015. Also given at Tsinghua University.
- Guest lecture at Tsinghua University: Online learning. June 9, 2015.
- KDD 2012 Tutorial: Infomation and influence spread in social networks, with Carlos Castillo and Laks V. S. Lakshamanan. Beijing, China, Aug. 12, 2012.
Research Keynotes and Talks
- WWW’2017 talk: Interplay between social influence and network centrality: A comparative study of Shapley centrality and single-node-influence centrality. Perth, Australia, April 6, 2017
- Chinese National Computer Conference (CNCC) 2016 invited talk in the Online Algorithm Forum: Combinatorial Online Learning. Taiyuan, China, October 21, 2016.
- KDD’2016 talk: Robust influence maximization. San Francisco, U.S.A., August 15, 2016.
- Keynote speech at IJCAI’15 Social Influence Analysis Workshop: Computational Social Influence. Buenos Aires, Argentina, July 27, 2015.
- WWW’2015 talk: A game theoretic model for the formation of navigable small-world networks. Florence, Italy, May 21, 2015.
- Talk at CS Department, University of British Columbia: Combinatorial learning for combinatorial optimization — A trilogy. Vancouver, Canada, March 27, 2015.
- NIPS’2014 Full Oral Presentation: Combinatorial pure exploration in multi-armed bandits. Montreal, Canada, Dec. 10, 2014.
- Invited talk at the Institute of Mathematics and System Sciences, Chinese Academy of Sciences:Influence maximization: The new frontier — non-submodular optimizations. Beijing, China, Sept. 15, 2014.
- Keynote speech at the 10th Chinese National Mathematical Programming Conference: Influence diffusion modeling and optimizations in social networks. Luoyang, China, May 11, 2014.
- ACM EC’2013 talk: Sybil-proof mechanisms in query incentive networks. Atlanta, U.S.A., June 20, 2013.
- ICML’2013 talk (revised): Combinatorial multi-armed bandit: General framework, results, and applications. Philadelphia, U.S.A., June 18, 2013.
- Chinese National Computer Conference (CNCC) 2012 invited talk: Influence diffusion dynamics and influence maximization in complex social networks. Dalian, China, Oct. 18, 2012.
- Talk at EconCS Group of Harvard University.: Influence diffusion dynamics and influence maximization in complex social networks. Cambridge, MA. U.S.A, Oct. 18, 2011.
- CASIN 2011 talk: Influence maximization when negative opinions may emerge and propagate. Beijing, China, July 20, 2011.
- ICDM 2010 talk: Scalable influence maximization in social networks under the linear threshold model. Sydney, Australia, Dec. 15, 2010.
- KDD 2010 talk: Scalable influence maximization for prevalent viral marketing in large-scale social networks. Washington D.C, U.S.A., July 27, 2010.
Influence diffusion dynamics and influence maximization in social networks
– Monograph summarizing research results on modeling, optimization, and learning of information and influence diffusions: “Information and Influence Propagation in Social Networks, Morgan and Claypool, 2013“.
– Robust influence maximization [KDD’16, arXiv:1601.06551]: We address the issue of robust optimization when parameters for the influence maximization are not accurate. We propose a new algorithm to achieve robust influence maximization with a guarantee, and investigate sampling methods to effectively improve parameter accuracy for the robust influence maximization task.
– Influence diffusion model covering the spectrum from competition to complementarity [VLDB’16, arXiv:1507.00317]: We propose an extension to the classical independent cascade model to cover the entire spectrum from competition to complementarity for two propagating items in a social network. We study the properties of the model and two variants of optimization problems for the mutually complementary regime. The paper also proposes a general sandwich approximation and a general condition for applying reverse reachable set approach to any diffusion model.
– Amphibious influence maximization [EC’15, arXiv:1507.03328]: we propose the model of combining traditional media marketing with viral marketing by selecting seed content providers to initiate cascades and selecting seed consumers to propagate the cascades in the social network. We prove hard-to-approximate result of the problem for general graphs, and propose an approximation algorithm for a certain class of restricted bipartite graph between content providers and consumers.
– Seed minimization with probabilistic coverage guarantee [KDD’14, arXiv: 1402.5516]: We look into the optimization problem of minimizing the seed set to ensure a probabilistic influence coverage guarantee. The main difficulty is that the objective function is not submodular. We provide theoretical analysis on the approximation guarantee of this problem and experimental study on the effectiveness of our algorithm.
– Active friending in social networks [KDD’13, arXiv: 1302.7025]: Active friending provides a new perspective on using social influence in social networks. Instead of finding seed nodes to maximize influence, it needs to find influence pathways to maximize influence. We provide efficient algorithms for finding intermediate nodes so as to increase the probability of a target node accepting the friending request.
– Scalable influence maximization: We study new algorithms and heuristics to improve the speed of finding influential nodes in a social network for viral marketing.
- MixedGreedy and DegreeDiscount [KDD’09]: improve the greedy algorithm by edge sampling, and propose DegreeDiscount for uniform independent cascade model.
- PMIA [KDD’10, DAMI’12]: scalable heuristic for the independent cascade model, using local tree structures to speed up influence computation for 3 orders of magnitude.
- LDAG [ICDM’10, MSR-TR-2010-133]: scalable heuristic for the linear threshold model, using local directed acyclic graph structures to speed up influence computation for 3 orders of magnitude.
- IRIE [ICDM’12, arXiv:1111.4795]: even faster scalable heuristic combining efficient influence ranking with influence estimation method, achieving up to 2 orders of magintude faster than PMIA in the independent cascade model.
- Dataset used: [data for two collaboration graphs NetHEPT and NetPHY][DBLP graph data]
- Code is available upon request by email
– Influence diffusion modeling and maximization for complex social interactions: We model complex social interactions including negative opinions due to product defects, competitive influence diffusion, and friend/foe relationships, and study influence maximization problem in these contexts.
- IC-N model and MIA-N algorithm [SDM’11, MSR-TR-2010-137]: We extend the independent cascade model to incorporate the emergence and propagation of negative opinions due to product defects, and study the influence maximization problem in this new model.
- Competitive influence diffusion CLT model and influence blocking maximization algorithm CLDAG in [SDM’12, arXiv:1110.4723]: We study the competitive linear threshold model, and propose efficient heuristic algorithm CLDAG for selecting the positive seed set that most effectively block the diffusion of negative influence.
- Time-critical influence maximization with time-delayed diffusion process [AAAI’12, arXiv:1204.3074]: We study influence maximization in which diffusion on each step may be delayed, and the objective is to maximize influence spread within a certain deadline. Both IC and LT models are extended, and efficient algorithms are proposed and evaluated.
- Influence diffusion dynamics and maximization in networks with friend and foe relationships [WSDM’13, arXiv:1111.4729]: We extend the voter model to signed networks representing both friend and foe relationships, and study the influence diffusion dynamics and influence maximization problem in this context.
– Participation maximization based on influence in online discussion forums [ICWSM’11, MSR-TR-2010-142]: We propose and study the participation maximization problem in online discussion forums, in which forum participation is determined by influence propagation through forum users.
Properties of small-world networks
– Navigability of small-world networks [WWW’15, arXiv:1411.4097]: We provide a game-theoretic formulation of navigable small-world networks to explain why real networks are often navigable. We provide strong theoretical and empirical results showing that navigable small-world network is the only stable equilibrium in the game. Our payoff function balances distance with relationship reciprocity, and this is the first work providing a surprising connection between relationship reciprocity and network navigability.
– Complex routing in small-world networks [COCOON’16, arXiv:1503.00448]: We define the decentralized routing problem of the complex contagion, which is the diffusion behavior in which a node is activated if and only if the number of its active friends is above a certain threshold greater than 1. We study the routing efficiency of complex contagions, and show that in Kleinberg’s small-world networks, the decentralized routing time is polynomial to the size of the graph in all parameter range, which means it cannot be efficient.
– The hyperbolicity of small-world and tree-like random graphs [ISAAC’12, arXiv:1201.1717]: There are empirical evidence that many real-world networks such as Internet or social networks are hyperbolic, and theoretical studies show that hyperbolic networks allow efficient decentralized routing behavior. We study the hyperbolicity of Kleinberg small-world random graphs and a family of tree-like random graphs. Our results show that Kleinberg small-world graphs are not strongly hyperbolic, which indicates that efficient decentralized routing does not imply graph hyperbolicity.
Combinatorial online learning
– Contextual combinatorial cascading bandit [ICML’16]: We incorporate contextual information, together with position discounts and general reward functions to the combinatorial cascade bandit, which has applications in online advertising and online recommendations.
– Online greedy learning [NIPS’15]: We show how to turn an offline greedy algorithm into an online greedy learning algorithm, with competitive regret bound compared with the solution of the offline greedy algorithm.
– Combinatorial pure exploration [NIPS’14]: We study the problem of how to explore stochastic arms efficiently so that in the end we can output a subset of arms satisfying certain combinatorial constraint (k-set, matching, spanning tree, etc.) and maximizing the sum of expected rewards of these arms with high probability. We provide generic fix-confidence and fix-budget algorithms and prove a lower bound on sample complexity, which implies that our fix-confidence algorithm is tight (up to a logarithmic factor) for combinatorial constraints formed by bases of a matroid.
– Combinatorial partial monitoring [ICML’14, supplementary material]: We study the online learning problem where the optimization problem is combinatorial (e.g. matching) and thus the action space is exponentially large, and the feedback is limited. We provide efficient solutions to this problem, and demonstrate how to apply it to problems such as crowd sourcing task allocations.
– Combinatorial multi-armed bandit [ICML’13, supplementary material, extended journal version: JMLR’16]: We provide a general stochastic framework that encompasses a large class of combinatorial mult-armed bandit problems, including many non-linear reward problems not considered before. We provide a CUCB learning algorithm with a tight analysis to show its regret bound. The framework can be applied to solve online learning problems with nonlinear reward functions such as probabilistic maximum coverage for online advertising, social influence maximization, as well as many optimization problems with linear reward functions.
Networked game theory and economics
– Sybil-proof mechanisms in query incentive networks [EC’13, arXiv:1304.7432]: Query incentive networks investigate how to design incentives to allow queries to be propagated to a large fraction of networks so as to find the answers to the queries. We study sybil-proof mechanisms for query incentive networks, and show that a class of direct referral mechanisms is both cost effective and avoid users creating fake identities (sybils) in the network.
– Pricing and revenue maximization with social influence consideration [WINE’11, arXiv:1007.1501]: We study the revenue maximization problem in selling a digital product in a social network where social influence affects agents’ purchasing decisions.
– Game-theoretic approach to overlapping community detection [DMKD’10 special issue on ECML PKDD’10]: We propose a community formation game and use its equilibrium to detect overlapping communities in social networks.
– Bounded budget betweenness centrality game [ESA’09, MSR-TR-2008-167, MSR-TR-2009-78]: We study a strategic network formation game in which nodes strategically select connections to other nodes to maximize their betweenness centralities in the network.