Recent Projects

 

  • Influence diffusion dynamics and influence maximization in social networks.

    - 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'10DAMI'12]: scalable heuristic for the independent cascade model, using local tree structures to speed up influence computation for 3 orders of magnitude.
    • LDAG [ICDM'10MSR-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]

- 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'11MSR-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.

  • Crowd-sourcing in social networks

- 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.

  • Combinatorial online learning

- Combinatorial multi-armed bandit and its applications [ICML'13, supplementary material]: 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 in social influence maximization and online advertising.

  • Networked game theory and economics 

- 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.

  • The hyperbolicity of networks

- 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.

  • Incentive-compatible and fault-tolerant distributed computing

- Distributed consensus resilient to both crash failures and strategic manipulations [arXiv:1203.4324]: we study the classic consensus problem in which selfish agents may manipulate the consensus prototocol in order to achieve a preferred consensus decision value. The combination of crash failures and strategic manipulations make the situation much more complicated than the standard situation of fault-tolerant consensus.