一种新型的社会网络影响最大化算法

《一种新型的社会网络影响最大化算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第３４卷第１０期计算机学报Ｖｏｌ．３４Ｎｏ．１０２０１１年１０月ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＯｃｔ．２０１１一种新型的社会网络影响最大化算法田家堂王轶彤冯小军（复旦大学计算机科学技术学院上海２０１２０３）摘要社会网络中影响最大化问题是对于给定犽值，寻找犽个具有最大影响范围的节点集．这是一个优化问题并且是ＮＰ完全的．Ｋｅｍｐｌｅ和Ｋｌｅｉｎｂｅｒｇ提出具有较好影响范围的贪心算法，但其时间复杂度很高，不能适用在大型社会网络中，并且不能保证最好的影响范围．文中利用线性阈值模型的“

2、影响力积累”特性，提出了一个该模型下影响最大化算法的框架，并在此框架基础上给出一个新的算法ＨＰＧ．ＨＰＧ综合考虑网络的结构特性和传播特性，首先启发式选择犘犐值最大的节点，然后寻找最具影响力的节点．实验结果显示ＨＰＧ在最终影响范围和运行时间上都获得比贪心算法更好的效果．关键词社会网络；贪心算法；影响最大化；带符号网络；信息传播中图法分类号ＴＰ３１１犇犗犐号：１０．３７２４／ＳＰ．Ｊ．１０１６．２０１１．０１９５６犃犖犲狑犎狔犫狉犻犱犃犾犵狅狉犻狋犺犿犳狅狉犐狀犳犾狌犲狀犮犲犕犪狓犻犿犻狕犪狋犻狅狀犻

3、狀犛狅犮犻犪犾犖犲狋狑狅狉犽狊ＴＩＡＮＪｉａＴａｎｇＷＡＮＧＹｉＴｏｎｇＦＥＮＧＸｉａｏＪｕｎ（犛犮犺狅狅犾狅犳犆狅犿狆狌狋犲狉犛犮犻犲狀犮犲，犉狌犱犪狀犝狀犻狏犲狉狊犻狋狔，犛犺犪狀犵犺犪犻２０１２０３）犃犫狊狋狉犪犮狋Ｉｎｆｌｕｅｎｃｅｍａｘｉｍｉｚａｔｉｏｎｉｓａｐｒｏｂｌｅｍｏｆｆｉｎｄｉｎｇａｓｍａｌｌｓｕｂｓｅｔｏｆｎｏｄｅｓ（ｔａｒｇｅｔｓｅｔ）ｉｎａｓｏｃｉａｌｎｅｔｗｏｒｋｔｈａｔｃｏｕｌｄｍａｘｉｍｉｚｅｔｈｅｓｐｒｅａｄｏｆｉｎｆｌｕｅｎｃｅ．Ｔｈｉｓｏｐｔｉｍｉｚａｔ

4、ｉｏｎｐｒｏｂｌｅｍｏｆｉｎｆｌｕｅｎｃｅｍａｘｉｍｉｚａｔｉｏｎｉｓＮＰｈａｒｄｕｎｄｅｒｓｅｖｅｒａｌｍｏｓｔｗｉｄｅｌｙｓｔｕｄｉｅｄｄｉｆｆｕｓｉｏｎｍｏｄｅｌｓａｎｄｉｓｅｖｅｎｃｈａｌｌｅｎｇｉｎｇｆｏｒｃｕｒｒｅｎｔｏｎｌｉｎｅｓｏｃｉａｌｎｅｔｗｏｒｋｓｗｈｉｃｈｃｏｎｔａｉｎｂｏｔｈｐｏｓｉｔｉｖｅａｎｄｎｅｇａｔｉｖｅｒｅｌａｔｉｏｎｓ．ＫｅｍｐｌｅａｎｄＫｌｅｉｎｂｅｒｇｐｒｏｐｏｓｅｄａｎａｔｕｒａｌｃｌｉｍｂｉｎｇｈｉｌｌｇｒｅｅｄｙａｌｇｏｒｉｔｈｍｔｈａｔｃｈ

5、ｏｏｓｅｓｔｈｅｎｏｄｅｓｗｈｉｃｈｃｏｕｌｄｐｒｏｖｉｄｅａｇｏｏｄｍａｒｇｉｎａｌｉｎｆｌｕｅｎｃｅ．Ｔｈｉｓｇｒｅｅｄｙａｌｇｏｒｉｔｈｍｈａｓｌａｒｇｅｓｐｒｅａｄｏｆｉｎｆｌｕｅｎｃｅ，ｂｕｔｉｓｖｅｒｙｃｏｓｔｌｙａｎｄｃａｎｎｏｔｂｅａｐｐｌｉｅｄｔｏｌａｒｇｅｓｏｃｉａｌｎｅｔｗｏｒｋｓ．Ａｌｓｏ，ｇｒｅｅｄｙａｌｇｏｒｉｔｈｍｃｏｕｌｄｎｏｔｇｕａｒａｎｔｅｅｔｈｅｂｅｓｔｉｎｆｌｕｅｎｃｅｓｐｒｅａｄ．Ｉｎｔｈｉｓｐａｐｅｒ，ｗｅｐｒｏｐｏｓｅａｆｒａｍｅｗｏｒｋｏｎｔｈｅｌ

6、ｉｎｅａｒｔｈｒｅｓｈｏｌｄｍｏｄｅｌａｎｄａｈｙｂｒｉｄｐｏｔｅｎｔｉａｌｉｎｆｌｕｅｎｃｅｇｒｅｅｄｙａｌｇｏｒｉｔｈｍ（ＨＰＧ）ｗｈｉｃｈｃａｎｍａｋｅｇｏｏｄｕｓｅｏｆｔｈｅ“ｉｎｆｌｕｅｎｃｅａｃｃｕｍｕｌａｔｉｏｎ”ｐｒｏｐｅｒｔｙｏｆｔｈｅｌｉｎｅａｒｔｈｒｅｓｈｏｌｄｍｏｄｅｌ．Ｃｏｎｓｉｄｅｒｉｎｇｔｈｅｎｅｔｗｏｒｋｓｔｒｕｃｔｕｒｅａｎｄｐｒｏｐａｇａｔｉｏｎｃｈａｒａｃｔｅｒｉｓｔｉｃｓ，ＨＰＧａｌｇｏｒｉｔｈｍｆｉｒｓｔｈｅｕｒｉｓｔｉｃａｌｌｙｃｈｏｏｓｅｈａｌｆｏ

7、ｆｔｈｅｉｎｉｔｉａｌｓｅｅｄｓｗｉｔｈｔｈｅｂｉｇｇｅｓｔｐｏｔｅｎｔｉａｌｉｎｆｌｕｅｎｃｅ（犘犐）ａｎｄｔｈｅｎｇｒｅｅｄｉｌｙｃｈｏｏｓｅｔｈｅｏｔｈｅｒｈａｌｆｉｎｉｔｉａｌｓｅｅｄｓｗｉｔｈｔｈｅｍｏｓｔｉｎｆｌｕｅｎｃｅ．Ｅｘｐｅｒｉｍｅｎｔｓａｒｅｃｏｎｄｕｃｔｅｄｃｏｍｐｒｅｈｅｎｓｉｖｅｌｙｏｎｄｉｆｆｅｒｅｎｔｒｅａｌｄａｔａｓｅｔｓ（ｉｎｃｌｕｄｉｎｇｗｅｉｇｈｔｅｄｓｏｃｉａｌｎｅｔｗｏｒｋｓ，ｄｉｒｅｃｔｅｄｓｏｃｉａｌｎｅｔｗｏｒｋｓａｎｄｓｉｇｎｅｄｓｏｃｉａｌｎ

8、ｅｔｗｏｒｋｓ）．ＥｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｄｅｍｏｎｓｔｒａｔｅｔｈａｔＨＰＧａｌｇｏｒｉｔｈｍｓｉｇｎｉｆｉｃａｎｔｌｙｏｕｔｐｅｒｆｏｒｍｓｔｈｅｌｏｃａｌｏｐｔｉｍａｌｇｒｅｅｄｙａｌｇｏｒｉｔｈｍａｎｄｃｏｕｌｄａｃｈｉｅｖｅｒｅｄｕｃｅｄｒｕｎｎｉｎｇｔｉｍｅ．犓犲狔狑狅狉犱狊ｓｏｃｉａｌｎｅｔｗｏｒｋ；ｇｒｅｅｄｙａｌｇｏｒｉｔｈｍ；ｉｎｆｌｕｅｎｃｅｍａｘｉｍｉｚａｔｉｏｎ；ｓｉｇｎｅｄｓｏｃｉａｌｎｅｔｗｏｒｋ；ｉｎｆｏｒｍａｔｉｏｎｄｉｆｆｕｓｉｏ