Influence propagation in social networks occur in many areas such as viral marketing, epidemiology, spread of innovations, etc. The word-of-mouth information propagation over a social network is modeled by an independent cascade model, a discrete random walk. One central task is to find the most influential set of nodes on the social network. This task is proved to be NP-hard and many approximate algorithms have been proposed. In this talk, we describe our work on providing exact solution to the problem albeit on small networks, and a fast approximate algorithm for large networks. We prove an inclusion-exclusion theory of the model, and use it to construct a linear algorithm on acyclic directed graph (DAG). We develop an injection-point algorithm to solve for generic directed graph/networks, repeated solving strongly connected components. Using precomputing, we the inclusion-exclusion theory to approximately compute the influences. This approximate algorithm out-perform the state-of-art MAFIA algorithm. Over-all, our work emphasize the probabilistic nature of the influence propagation, provides new insights to the influence propagation; our exact solution can be used to check the accuracy of solutions by faster but approximate algorithms.

报告人简介：

丁宏强于1981年考取李政道教授主持的CUSPEA,赴美国哥伦比亚大学李政道教授领导的研究小组求学，获得哥伦比亚大学博士学位。他曾长期工作于美国加州理工学院，美国喷气动力实验室及美国劳伦斯-伯克利国家实验室，2007年加入德州大学阿灵顿分校任终身正教授。他的研究兴趣主要包括数据挖掘、机器学习、信息检索等领域。从 2001 年开始，他和合作者创立了一个崭新的数据挖掘子领域——用矩阵模型作为主要的理论和计算方法进行数据挖掘。迄今为止，他已经在该领域发表了 170余篇高水平论文，被引用超过 13000 次。曾受邀在加州大学伯克利分校、斯坦福大学、卡耐基梅隆大学、滑铁卢大学、阿尔伯塔大学、Google研究院、IBM研究院、Microsoft研究院、香港大学、香港科技大学、新加坡国立大学、北大、清华做学术报告。多次担任美国、香港、爱尔兰、以色列等国家科学基金会项目评审人。获得四篇最佳论文奖(ICDM 2010, ECML2011,ICMLA2006, ISUG1996)。安徽大学特聘教授。