社会网络中的影响力最大化问题_颜庆

《社会网络中的影响力最大化问题_颜庆》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ＣＮ４３－１２５８／ＴＰ计算机工程与科学第３７卷第２期２０１５年２月ＩＳＳＮ１００７－１３０ＸＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ＆ＳｃｉｅｎｃｅＶｏｌ．３７，Ｎｏ．２，Ｆｅｂ．２０１５文章编号：１００７－１３０Ｘ（２０１５）０２－０２６３－０６＊社会网络中的影响力最大化问题颜庆，张鹏（山东大学计算机科学与技术学院，山东济南２５０１０１）摘要：影响力最大化问题要求在网络中选取若干节点，使得以它们为初始节点进行信息传播时，在网络中产生的影响能够达到最大。影响力最大化问题是近十年来社会网络中的研究热点之一，其研究不仅具有理论意义，并且还具有应用

2、前景。介绍了影响力最大化问题产生的背景，分析了问题的研究现状、研究用的几种主要传播模型以及解决问题的几种主要算法。最后，讨论了该研究面临的一些问题，对未来可能发展的研究方向进行了展望。关键词：影响力最大化；社会网络；传播模型；近似算法中图分类号：ＴＰ３９３文献标志码：Ａｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００７－１３０Ｘ．２０１５．０２．０１２ＡｒｅｖｉｅｗｏｆｔｈｅｉｎｆｌｕｅｎｃｅｍａｘｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｉｎｓｏｃｉａｌｎｅｔｗｏｒｋｓＹＡＮＱｉｎｇ，ＺＨＡＮＧＰｅｎｇ（ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎ

3、ｄＴｅｃｈｎｏｌｏｇｙ，ＳｈａｎｄｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｊｉｎａｎ２５０１０１，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｉｎｆｌｕｅｎｃｅｍａｘｉｍｉｚａｔｉｏｎｉｓａｐｒｏｂｌｅｍｏｆｆｉｎｄｉｎｇｔｈｅｍｏｓｔｉｎｆｌｕｅｎｔｉａｌｓｅｔｏｆｎｏｄｅｓｉｎａｓｏｃｉａｌｎｅｔｗｏｒｋｗｈｉｃｈｃａｎｍａｘｉｍｉｚｅｔｈｅｓｐｒｅａｄｏｆｉｎｆｌｕｅｎｃｅ．Ｔｈｅｉｎｆｌｕｅｎｃｅｍａｘｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｈａｓｂｅｅｎｏｎｅｏｆｔｈｅｈｏｔｔｏｐｉｃｓｉｎｓｏｃｉａｌｎｅｔｗｏｒｋｓｏｖｅｒｔｈｅｐａｓｔｄｅｃａｄｅ．Ｔｈｅｓｔｕ

4、ｄｙｉｓｎｏｔｏｎｌｙｏｆｔｈｅｏｒｅｔｉｃａｌｓｉｇｎｉｆｉ－ｃａｎｃｅ，ｂｕｔａｌｓｏｏｆｐｒｏｍｉｓｉｎｇａｐｐｌｉｃａｔｉｏｎｓ．Ｔｈｅｂａｓｉｃｐｒｉｎｃｉｐｌｅｓａｎｄｔｈｅｂａｃｋｇｒｏｕｎｄｏｆｔｈｅｐｒｏｂｌｅｍａｒｅｉｎ－ｔｒｏｄｕｃｅｄ．Ｗｅａｌｓｏｄｉｓｃｕｓｓｔｈｅｃｕｒｒｅｎｔｄｅｖｅｌｏｐｍｅｎｔｓｔａｔｕｓ，ｅｘｉｓｔｉｎｇｐｒｏｂｌｅｍｓ，ｓｏｍｅｄｉｆｆｕｓｉｏｎｍｏｄｅｌｓａｎｄｓｅｖｅｒａｌａｌｇｏｒｉｔｈｍｓｆｏｒｓｏｌｖｉｎｇｔｈｅｓｅｐｒｏｂｌｅｍｓ．Ｆｉｎａｌｌｙ，ｓｏｍｅｆｕｔｕｒｅｒｅｓｅａ

5、ｒｃｈｄｉｒｅｃｔｉｏｎｓｏｆｔｈｅｐｒｏｂｌｅｍａｒｅｐｒｏｐｏｓｅｄ．Ｋｅｙｗｏｒｄｓ：ｉｎｆｌｕｅｎｃｅｍａｘｉｍｉｚａｔｉｏｎ；ｓｏｃｉａｌｎｅｔｗｏｒｋ；ｄｉｆｆｕｓｉｏｎｍｏｄｅｌ；ａｐｐｒｏｘｉｍａｔｉｏｎａｌｇｏｒｉｔｈｍ入社会网络研究领域后，成为近年来的一大研究热［４］１引言点。自２００１年ＤｏｍｉｎｇｏｓＰ等人第一次将影响力最大化问题抽象成一个算法问题以来，各种传播随着电子设备的不断普及以及社交媒体的日模型和求解问题的算法也相继提出，近几年备受研趋强大，人们之间的联系越来越密切。如何通过社究者们的关注，发表的论文数量也越来

6、越多。虽然会网络中人们之间建立起来的关系来进行信息的影响力最大化问题的研究已经有了十多年的时间，传播，逐渐得到研究者们的关注。由最初营销领域但是迄今为止关于它的综述文章却很少。因此，非［１～５］的“口碑效应”和“病毒式营销策略”的推广方常有必要对影响力最大化问题的背景、理论基础、式，人们发现可以在人群中选取具有代表性的节点传播模型、研究现状、存在的问题以及未来的研究子集，由它们可以引起更大的级联影响，逐步产生方向等方面作个较全面、系统的总结和评述，以期出了影响力最大化问题。影响力最大化问题被引能对后来的研究者提供指导，从而能更有效地解决＊收稿

7、日期：２０１４－０８－１０；修回日期：２０１４－１０－２５基金项目：山东省自然科学基金资助项目（ＺＲ２０１２ＦＺ００２，ＺＲ２０１３ＦＭ０３０）；山东大学基本科研业务费资助项目（２０１２ＴＳ０７２）通信地址：２５０１０１山东省济南市舜华路１５００号山东大学计算机科学与技术学院Ａｄｄｒｅｓｓ：ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＳｈａｎｄｏｎｇＵｎｉｖｅｒｓｉｔｙ，１５００ＳｈｕｎｈｕａＲｄ，Ｊｉｎａｎ２５０１０１，Ｓｈａｎｄｏｎｇ，Ｐ．Ｒ．Ｃｈｉｎａ２６４ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ＆Ｓｃｉｅｎ

8、ｃｅ计算机工程与科学２０１５，３７（２）［７～９］更多的实际问题。Ｔｈｒｅｓｈｏｌｄ）模型。２．２．１独立级联模型２理论基础独立级联模型是基于概率论中的交互粒子系［