基于影响路径的个性化影响最大化算法

J4 ›› 2016, Vol. 38 ›› Issue (06): 1128-1134.

基于影响路径的个性化影响最大化算法

杨书新，王希，彭秋英

（江西理工大学信息工程大学，江西赣州 341000）

收稿日期:2015-07-13 修回日期:2015-08-21 出版日期:2016-06-25 发布日期:2016-06-25
基金资助:
国家自然科学基金（41362015）；江西省科技厅青年科学基金（20122BAB211035）；江西省教育厅科技项目（GJJ14431,GJJ14432,GJJ14458）

A personalized influence maximization
algorithm based on influence path

YANG Shuxin,WANG Xi,PENG Qiuying

(School of Information Engineering,Jiangxi University of Science and Technology,Ganzhou 341000,China)

Received:2015-07-13 Revised:2015-08-21 Online:2016-06-25 Published:2016-06-25

摘要/Abstract

摘要：

个性化影响最大化问题是近年来社交网络影响最大化问题研究领域一个较新的分支，其现有解决方案普遍建立在网络边影响传播强度一致的假设下，该假设对于真实社交网络缺乏普遍适用性。为此基于独立级联模型，提出最大影响路径算法（MIPA）。该算法通过三个阶段来求解个性化影响最大化问题，首先将边影响强度作对数转换以获得最大影响路径，从而计算网络节点对目标节点的邻居节点的影响；然后利用多条经过目标节点邻居的最大影响路径联合计算目标节点受到的影响强度；最后选择Topk节点作为种子节点，从而摆脱边影响强度的一致性约束，获取高质量的种子集。在不同的真实社交网络数据集上进行的对比实验验证了算法的有效性。

关键词: 社交网络, 个性化, 影响最大化, 特定用户

Abstract:

Personalized influence maximization in social network has become a new branch of influence maximization study in recent years. Different from existing research that assumes equal propagating strengths of social network edges, our work aims to find out the topk most influential nodes for the target user without inappropriate assumption. We propose a maximizedinfluencepath algorithm (MIPA) based on the independent cascade model. It solves the problem through three stages. Firstly, to compute the propagating strengths from the nodes of social network to the neighbors of the target node, the strengths of edges are transformed into its logarithmic form for getting the maximized influence paths. Secondly, the strength of maximized influence paths which pass through different neighbors with the same source nodes are consolidated to calculate the node’s propagating strength on the target node. Finally, the seed set with high propagating strength is found out by selecting the topk nodes. We testify the algorithm on several realworld social networks. Experimental results validate the proposed algorithm.

Key words: social network;personalization;influence maximization;target user

杨书新，王希，彭秋英. 基于影响路径的个性化影响最大化算法[J]. J4, 2016, 38(06): 1128-1134.

YANG Shuxin,WANG Xi,PENG Qiuying. A personalized influence maximization
algorithm based on influence path [J]. J4, 2016, 38(06): 1128-1134.

参考文献［13］

［1］	Domingos P,Richardson M.Mining the network value of customers［C］∥Proc of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2001:5766.
［2］	Richardson M,Domingos P.Mining knowledgesharing sites for viral marketing［C］∥Proc of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2002: 6170.
［3］	Kempe D,Kleinberg J M,Tardos .Maximizing the spread of influence through a social network［C］∥Proc of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2003: 137146.
［4］	Leskovec J,Krause A,Guestrin C,et al.Costeffective outbreak detection in networks［C］∥Proc of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2007: 420429.
［5］	Goyal A,Lu W,Lakshmanan L.CELF++: optimizing the greedy algorithm for influence maximization in social networks［C］∥Proc of the 20th International Conference Companion on World Wide Web,WWW 2011,2011: 4748.
［6］	Chen Wei,Wang Yajun,Yang Siyu.Efficient influence maximization in social networks［C］∥Proc of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2009: 199208.
［7］	Wang Chi,Chen Wei,Wang Yajun.Scalable influence maximization for prevalent viral marketing in largescale social networks［C］∥Proc of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2010:10291038.
［8］	Jiang Qingye,Song Guojie,Cong Gao,et al.Simulated annealing based influence maximization in social networks［C］∥Proc of the National Conference on Artificial Intelligence,El Segundo: AI Access Foundation,2011: 127132.
［9］	Nguyen H,Zheng Rong.On budgeted influence maximization in social networks ［J］.IEEE Journal on Selected Areas in Communications,2013,31(6): 10841094.
［10］	Han Shuo, Zhuang Fuzhen, He Qing, et al. Balanced seed selection for budgeted influence maximization in social networks［C］∥Proc of the 18th PacificAsia Conference on Advances in Knowledge Discovery and Data Mining, 2014:6577.
［11］	Guo Jing,Zhang Peng,Zhou Chuan,et al.Personalized influence maximization on social networks［C］∥Proc of the 22nd ACM International Conference on Conference on Information & Knowledge Management,2013:199208.
［12］	Guo Jing,Zhang Peng,Fang Binxing,et al.Personalized key propagating users mining based on LT model［J］.Chinese Journal of Computers,2014,37(4): 809818.(in Chinese)
［13］	Zhang Bolei,Qian Zhuzhong,Wang Qinhui,et al.Maximize information coverage algorithm for target market［J］.Chinese Journal of Computers,2014,37(4): 894904.(in Chinese)
［14］	Nemhauser G,Wolsey L,Fisher M.An analysis of approximations for maximizing submodular set functions［J］.Mathematical Programming,1978,3(14):265294.
	附中文参考文献：
［12］	郭静，张鹏，方滨兴，等.基于LT模型的个性化关键传播用户挖掘［J］.计算机学报,2014,37(4): 809818.
［13］	张伯雷，钱柱中，王钦辉，等.面向目标市场的信息最大覆盖算法［J］.计算机学报,2014,37(4): 894904.

[1]	刘云, 肖添, 王梓宇. 动态特征选择算法对恶意行为检测的优化研究[J]. 计算机工程与科学, 2022, 44(04): 665-673.
[2]	袁泉, 晏飞扬, 文志云, 张振康, . 基于谱聚类的社交网络差分隐私保护算法研究[J]. 计算机工程与科学, 2022, 44(02): 251-256.
[3]	谢小杰, 梁英, 王梓森, 董祥祥, . 社交网络用户隐私泄露量化评估方法[J]. 计算机工程与科学, 2021, 43(08): 1376-1386.
[4]	马汉达, 景迪. 基于SSD和时序模型的微博好友推荐算法[J]. 计算机工程与科学, 2021, 43(07): 1291-1298.
[5]	张琦, 张祖凡, 甘臣权. 融合社会关系的社交网络情感分析综述[J]. 计算机工程与科学, 2021, 43(01): 180-190.
[6]	杨丰瑞, 李前洋, 罗思烦, . 一种基于降噪自编码器的隐式反馈推荐算法[J]. 计算机工程与科学, 2020, 42(08): 1500-1505.
[7]	杨丰瑞, 李前洋, 罗思烦, . 基于降噪自编码器的社会化推荐算法[J]. 计算机工程与科学, 2020, 42(05): 944-950.
[8]	刘辉, ., 曾斌, 刘子恺. 融合邻居选择策略和信任关系的兴趣点推荐[J]. 计算机工程与科学, 2020, 42(02): 365-372.
[9]	宋春晓，黄峰，靳松清，白晓东，仇宏斌，姜杰，李艺. 基于汉字笔画与结构的特征字库构造及优化[J]. 计算机工程与科学, 2019, 41(05): 933-941.
[10]	黄进，周栋. 一种融合社会化标注系统中主题域相似的个性化排序方法[J]. 计算机工程与科学, 2018, 40(05): 880-887.
[11]	刘国梁，钱晓东. 基于加权网络结构的冷门资源推荐算法[J]. 计算机工程与科学, 2018, 40(05): 916-923.
[12]	鲜学丰1,陈晓杰2,赵朋朋2,杨元峰1,Victor S.Sheng3. 基于上下文感知和个性化度量嵌入的下一个兴趣点推荐[J]. 计算机工程与科学, 2018, 40(04): 616-625.
[13]	罗斌，陈翔. 幂律特性在新浪微博个性化推荐中的应用研究[J]. 计算机工程与科学, 2018, 40(04): 731-739.
[14]	齐会敏，刘群，戴大祥. 面向兴趣主题的个性化好友推荐[J]. 计算机工程与科学, 2018, 40(02): 348-353.
[15]	贾俊杰，陈菲. 数字图书馆个性化匿名发布方法[J]. 计算机工程与科学, 2017, 39(11): 2109-2114.