Influence maximization algorithm based on directed acyclic graph in heterogeneous information networks

doi:10.11772/j.issn.1001-9081.2021020369

Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (3): 895-903.DOI: 10.11772/j.issn.1001-9081.2021020369

• Data science and technology • Previous Articles Next Articles

Influence maximization algorithm based on directed acyclic graph in heterogeneous information networks

Qingqing WU¹, Lihua ZHOU¹(), Xuanyi CUN¹, Guowang DU¹, Yiting JIANG²

^1.School of information Science & Engineering，Yunnan University，Kunming Yunnan 650000，China
^2.School of information，Yunnan Normal University，Kunming Yunnan 650000，China

Received:2021-03-11 Revised:2021-05-11 Accepted:2021-05-13 Online:2021-05-27 Published:2022-03-10
Contact: Lihua ZHOU
About author:WU Qingqing， born in 1995， M. S. candidate. Her research interests include data mining， heterogeneous information network， information diffusion.
CUN Xuanyi， born in 1995， M. S. candidate. His research interests include data mining， heterogeneous information network，information diffusion.
DU Guowang， born in 1994， Ph. D. candidate. His research interests include multi-perspective learning.
JIANG Yiting， born in 1983， M. S.， lecturer. Her research interests include data mining.
Supported by:
National Natural Science Foundation of China(62062066);Key Project of Yunnan Province Applied Basic Research Program in 2022

异质信息网络中基于有向无环图的影响力最大化算法

吴晴晴¹, 周丽华¹(), 寸轩懿¹, 杜国王¹, 姜懿庭²

^1.云南大学信息学院，昆明 650000
^2.云南师范大学信息学院，昆明 650000

通讯作者: 周丽华
作者简介:吴晴晴（1995—），女，安徽亳州人，硕士研究生，主要研究方向：数据挖掘、异质信息网络、信息扩散
寸轩懿（1995—），男，云南腾冲人，硕士研究生，主要研究方向：数据挖掘、异质信息网络、信息扩散
杜国王（1994—），男，河南洛阳人，博士研究生，主要研究方向：多视角学习
姜懿庭（1983—），女，云南昆明人，讲师，硕士，主要研究方向：数据挖掘。
基金资助:
国家自然科学基金资助项目(62062066);2022年云南省应用基础研究计划重点项目

Abstract

Abstract:

Aiming at the problem of Influence Maximization （IM） in heterogeneous information networks， an Influence Maximization algorithm （DAGIM） based on Directed Acyclic Graph （DAG） was proposed. Firstly， the influence of nodes was measured based on the DAG structure， and then the marginal gain strategy was used to select the nodes with the most influence. The DAG structure has strong expressive power， which not only describes the explicit relationship between different types of nodes， but also depicts the implicit relationship between nodes， and more completely retains the heterogeneous information of the network. Experimental results on three real datasets verify that the performance of the proposed DAGIM algorithm is better than those of Degree， PageRank， Local Directed Acyclic Graph （LDAG） and Meta-Path-based Information Entropy （MPIE） algorithms.

Key words: social network, heterogeneous information network, information diffusion, influence maximization, Directed Acyclic Graph (DAG)

摘要：

针对异质信息网络中的影响力最大化（IM）问题，提出了一种基于有向无环图（DAG）的影响力最大化算法（DAGIM）。首先基于DAG结构度量节点的影响力，然后采用边际增益策略选择影响力最大的节点。DAG结构表达力强，不仅描述了不同类型节点之间的显性关系，也刻画了节点之间的隐性关系，较完整地保留了网络的异质信息。在三个真实数据集上的实验结果验证所提DAGIM的性能优于Degree、PageRank、局部有向无环图（LDAG）以及基于元路径的信息熵（MPIE）算法。

关键词: 社会网络, 异质信息网络, 信息扩散, 影响力最大化, 有向无环图

CLC Number:

TP391.9

Qingqing WU, Lihua ZHOU, Xuanyi CUN, Guowang DU, Yiting JIANG. Influence maximization algorithm based on directed acyclic graph in heterogeneous information networks[J]. Journal of Computer Applications, 2022, 42(3): 895-903.

吴晴晴, 周丽华, 寸轩懿, 杜国王, 姜懿庭. 异质信息网络中基于有向无环图的影响力最大化算法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 895-903.

Figures/Tables 9

References 33

1	KEMPE D， KLEINBERG J， TARDOS E. Maximizing the spread of influence through a social network［C］// Proceedings of the 2003 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2003：137-146. 10.1145/956750.956769
2	LESKOVEC J， KRAUSE A， GUESTRIN C. Cost-effective out-break detection in networks［C］// Proceedings of the 2007 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2007： 420-429. 10.1145/1281192.1281239
3	GOYAL A， LU W， LAKSHMANAN L V. Celf++： Optimizing the greedy algorithm for influence maximization in social networks［C］// Proceedings of the 2011 International Conference Companion on World Wide Web. New York： ACM， 2011： 47-48. 10.1145/1963192.1963217
4	CHEN W， WANG Y， YANG S. Efficient influence maximization in social networks［C］// Proceedings of the 2009 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2009： 199-208. 10.1145/1557019.1557047
5	LIU H L， MA C， XIANG B B， et al. Identifying multiple influential spreaders based on generalized closeness centrality［J］. Physica A： Statistical Mechanics and its Applications， 2018， 492： 2237-2248. 10.1016/j.physa.2017.11.138
6	KIM J， KIM S-K， YU H. Scalable and parallelizable processing of influence maximization for large-scale social networks［C］// Proceedings of the 2013 IEEE International Conference on Data Engineering. Piscataway： IEEE， 2013： 266-277. 10.1109/icde.2013.6544831
7	KO Y Y， CHAE D K， KIM S W. Accurate path-based methods for influence maximization in social networks［C］// Proceedings of the 2016 International Conference Companion on World Wide Web. New York： ACM， 2016： 59-60. 10.1145/2872518.2889407
8	WANG Y， CONG G， SONG G， et al. Community-based greedy algorithm for mining top-k influential nodes in mobile social networks［C］// Proceedings of the 2010 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2010： 1039-1048. 10.1145/1835804.1835935
9	SHANG J， ZHOU S， LI X. CoFIM： a community-based framework for influence maximization on large-scale networks［J］. Knowledge Based Systems， 2017， 117： 88-100. 10.1016/j.knosys.2016.09.029
10	WU H， SHANG J， ZHOU S， et al. IMPC： influence maximization based on multi-neighbor potential in community networks［J］. Physica A， 2018， 512： 1085-1103. 10.1016/j.physa.2018.08.045
11	CHEN W， YUAN Y， ZHANG L. Scalable influence maximization in social networks under the linear threshold model［C］// Proceedings of the 2010 IEEE International Conference on Data Mining. Piscataway： IEEE， 2010： 88-97. 10.1109/icdm.2010.118
12	郭静. 社会网络影响力传播的分析与挖掘研究［D］. 北京：北京邮电大学， 2014：18-19.
	GUO J. Research on the analysis and mining of social network influence spreading ［D］. Beijing： Beijing University of Posts and Telecommunications， 2014： 18-19.
13	QIU L， GU C， ZHANG S， et al. TSIM： a two-stage selection algorithm for influence maximization in social networks［J］. IEEE Access， 2020， 8： 12084-12095. 10.1109/access.2020.2966056
14	QIU L， TIAN X， SAI S， et al. LGIM： a global selection algorithm based on local influence for influence maximization in social networks［J］. IEEE Access， 2020， 8： 12084-12095. 10.1109/access.2019.2963100
15	BANERJEE S， JENAMANI M， PRATIHAR D K. A survey on influence maximization in a social network［J］. Knowledge and Information Systems， 2020， 62（9）： 3417-3455. 10.1007/s10115-020-01461-4
16	石川，孙怡舟，俞·菲利普. 信息网络的研究现状和未来发展［J］. 计算机学会通讯， 2017，11（13）： 35-39.
	SHI C， SUN Y Z， YU P. Research status and future development of heterogeneous information networks［J］. Communications of the Computer Society， 2017， 11（13）： 35-40.
17	SUN Y， NORICK B， HAN J， et al. PathSelClus： integrating meta-path selection with user-guided object clustering in heterogeneous information networks［J］. ACM Transactions on Knowledge Discovery from Data， 2013， 7（3）： 1-23. 10.1145/2513092.2500492
18	SUN Y， AGGARWAL C C， HAN J. Relation strength-aware clustering of heterogeneous information networks with incomplete attributes［J］. Proceedings of the VLDB Endowment， 2012， 5（5）： 394-405. 10.14778/2140436.2140437
19	KONG X， YU P S， DING Y， et al. Meta path-based collective classification in heterogeneous information networks［C］// Proceedings of the 2013 ACM International Conference on Information and Knowledge Management. New York： ACM， 2013： 1567-1571.
20	ZHOU Y， LIU L. Activity-edge centric multi-label classification for mining heterogeneous information networks［C］// Proceedings of the 2014 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2014： 1276-1285. 10.1145/2623330.2623737
21	SUN Y， HAN J， YAN X， et al. Pathsim： Meta path-based top-k similarity search in heterogeneous information networks［J］. Proceedings of the VLDB Endowment， 2011， 4（11）： 992-1003. 10.14778/3402707.3402736
22	LIU Z， ZHENG V， ZHAO Z， et al. Distance-aware dag embedding for proximity search on heterogeneous graphs［C］// Proceedings of the 2018 AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI， 2018： 2355-2362.
23	CAO B， KONG X， YU P S. Collective prediction of multiple types of links in heterogeneous information networks［C］// Proceedings of the 2014 IEEE International Conference on Data Mining， Piscataway： IEEE， 2014： 50-59. 10.1109/icdm.2014.25
24	CHEN L M， ZHANG Y， YANG L. Semi-supervised meta-path-based algorithm for community detection in heterogeneous information networks［C］// Proceedings of the 2019 International Conference on Web Information Systems and Applications， Cham： Springer， 2019： 506-511. 10.1007/978-3-030-30952-7_50
25	MOLAEI S， ZARE H， VEISI H. Deep learning approach on information diffusion in heterogeneous networks［J］. Knowledge-Based Systems， 2020， 189： 105153. 10.1016/j.knosys.2019.105153
26	LIU L， TANG J， HAN J， et al. Learning influence from heterogeneous social networks［J］. Data Mining and Knowledge Discovery， 2012， 25（3）： 511-544. 10.1007/s10618-012-0252-3
27	LI D， SHEN D， KOU Y， et al. Integrating sign prediction with behavior prediction for signed heterogeneous information networks［J］. IEEE Access， 2019， 7： 171357-171371. 10.1109/access.2019.2937508
28	LI C T， LIN S D， SHAN M K. Influence propagation and maximization for heterogeneous social networks［C］// Proceedings of the 2012 International Conference on World Wide Web. New York： ACM， 2012： 559-560. 10.1145/2187980.2188126
29	WANG Y， HUANG H， FENG C， et al. A co-ranking framework to select optimal seed set for influence maximization in heterogeneous network［C］// Proceedings of the 2015 Asia Pacific Web Conference. Cham： Springer， 2015： 141-153. 10.1007/978-3-319-25255-1_12
30	DENG X， LONG F， LI B， et al. An influence model based on heterogeneous online social network for influence maximization［J］. IEEE Transactions on Network Science and Engineering， 2020， 7（2）： 737-749. 10.1109/tnse.2019.2920371
31	SUN Y， HAN J， ZHAO P， et al. RankClus： integrating clustering with ranking for heterogeneous information network analysis［C］// Proceedings of the 2009 International Conference on Extending Database Technology. New York： ACM， 2009： 565-576. 10.1145/1516360.1516426
32	YANG Y， ZHANG J， CHEN Y， et al. Structural hole detection based on weighted meta path in heterogeneous networks［J］. Evolutionary Intelligence， 2020， 13（2）： 211-220. 10.1007/s12065-019-00342-2
33	YANG Y， ZHOU L， JIN Z， et al. Meta path-based information entropy for modeling social influence in heterogeneous information networks［C］// Proceedings of the 2019 IEEE International Conference on Mobile Data Management. Piscataway： IEEE， 2019： 557-562. 10.1109/mdm.2019.00119

数据集	节点类型	节点数量	边类型	边数量
DBLP	Author（A）	7 677	P-A	28 939
	Paper（P）	14 376	P-C	14 376
	Paper（P）	20	P-T	114 624
	Term（T）	8 920
Yelp	User （U）	5 023	U-B	62 268
	Business （B）	14 284	U-U	50 532
	Category （Cat）	47	B-Cit	14 257
	City （Cit）	511	B-Cat	40 009
Amazon	User（U）	6 170	U-I	195 791
	Item（I）	2 753	I-V	5 694
	View（V）	3 857	I-C	5 508
	Category（C）	22	I-B	2 753
	Brand（B）	334

数据集	节点类型	节点数量	边类型	边数量
DBLP	Author（A）	7 677	P-A	28 939
	Paper（P）	14 376	P-C	14 376
	Paper（P）	20	P-T	114 624
	Term（T）	8 920
Yelp	User （U）	5 023	U-B	62 268
	Business （B）	14 284	U-U	50 532
	Category （Cat）	47	B-Cit	14 257
	City （Cit）	511	B-Cat	40 009
Amazon	User（U）	6 170	U-I	195 791
	Item（I）	2 753	I-V	5 694
	View（V）	3 857	I-C	5 508
	Category（C）	22	I-B	2 753
	Brand（B）	334

数据集	种子节点数K	运行耗时/s
数据集	种子节点数K	PageRank	Degree	MPIE	LDAG	DAGIM
DBLP	10	15.98	0.13	64 792.2	17 210.31	272.08
	20	18.13	0.35	64 795.8	17 239.42	277.66
	30	20.95	0.41	64 796.3	17 268.34	281.73
	40	22.50	0.56	64 799.0	17 302.55	287.29
	50	24.39	0.74	64 807.7	17 344.71	292.34
YELP	10	10.73	0.12	113 380.5	11 011.61	769.82
	20	11.10	0.25	113 385.2	11 038.57	774.49
	30	11.42	0.40	113 392.5	11 061.38	776.63
	40	12.03	0.52	113 399.1	11 092.07	779.72
	50	12.49	0.65	113 409.6	11 119.87	781.39
Amazon	10	5.67	0.14	53 320.3	13 310.30	3 816.98
	20	10.65	0.24	53 325.5	13 319.50	3 819.63
	30	11.23	0.29	53 328.8	13 326.81	3 823.72
	40	12.17	0.39	53 332.6	13 338.34	3 826.84
	50	12.67	0.44	53 335.1	13 343.21	3 828.74

数据集	种子节点数K	运行耗时/s
数据集	种子节点数K	PageRank	Degree	MPIE	LDAG	DAGIM
DBLP	10	15.98	0.13	64 792.2	17 210.31	272.08
	20	18.13	0.35	64 795.8	17 239.42	277.66
	30	20.95	0.41	64 796.3	17 268.34	281.73
	40	22.50	0.56	64 799.0	17 302.55	287.29
	50	24.39	0.74	64 807.7	17 344.71	292.34
YELP	10	10.73	0.12	113 380.5	11 011.61	769.82
	20	11.10	0.25	113 385.2	11 038.57	774.49
	30	11.42	0.40	113 392.5	11 061.38	776.63
	40	12.03	0.52	113 399.1	11 092.07	779.72
	50	12.49	0.65	113 409.6	11 119.87	781.39
Amazon	10	5.67	0.14	53 320.3	13 310.30	3 816.98
	20	10.65	0.24	53 325.5	13 319.50	3 819.63
	30	11.23	0.29	53 328.8	13 326.81	3 823.72
	40	12.17	0.39	53 332.6	13 338.34	3 826.84
	50	12.67	0.44	53 335.1	13 343.21	3 828.74

[1]	Meizi LI, Yifei MI, Qian ZHANG, Bo ZHANG. Opinion leader recognition algorithm based on K-core decomposition in social networks [J]. Journal of Computer Applications, 2022, 42(1): 26-35.
[2]	ZHANG Meng, LI Weihua. Influence maximization algorithm based on user interactive representation [J]. Journal of Computer Applications, 2021, 41(7): 1964-1969.
[3]	SUN Heli, SUN Yuzhu, ZHANG Xiaoyun. Event description generation based on generative adversarial network [J]. Journal of Computer Applications, 2021, 41(5): 1256-1261.
[4]	LIN Yixing, TANG Hua. Hybrid recommendation model based on heterogeneous information network [J]. Journal of Computer Applications, 2021, 41(5): 1348-1355.
[5]	JIANG Kun, LIU Zheng, ZHU Lei, LI Xiaoxing. Fixed word-aligned partition compression algorithm of inverted list based on directed acyclic graph [J]. Journal of Computer Applications, 2021, 41(3): 727-732.
[6]	SUN Heli, XU Tong, HE Liang, JIA Xiaolin. Personalized social event recommendation method integrating user historical behaviors and social relationships [J]. Journal of Computer Applications, 2021, 41(2): 324-329.
[7]	Xujian ZHAO, Chongwei WANG. Storyline extraction method from Weibo news based on graph convolutional network [J]. Journal of Computer Applications, 2021, 41(11): 3139-3144.
[8]	LI Xiangkun, JIA Caiyan. Collaborative filtering method fusing overlapping community regularization and implicit feedback [J]. Journal of Computer Applications, 2021, 41(1): 53-59.
[9]	SHENG Jun, LI Bin, CHEN Ling. Recommendation algorithm based on modularity and label propagation [J]. Journal of Computer Applications, 2020, 40(9): 2606-2612.
[10]	LI Chunying, TANG Yong, XIAO Zhenghong, LI Tiansong. Influential scholar recommendation model in academic social network [J]. Journal of Computer Applications, 2020, 40(9): 2594-2599.
[11]	YANG Shuxin, LIANG Wen, ZHU Kaili. Reverse influence maximization algorithm in social networks [J]. Journal of Computer Applications, 2020, 40(7): 1944-1949.
[12]	YI Dongyi, DENG Genqiang, DONG Chaoxiong, ZHU Miaomiao, LYU Zhouping, ZHU Suisong. Medical insurance fraud detection algorithm based on graph convolutional neural network [J]. Journal of Computer Applications, 2020, 40(5): 1272-1277.
[13]	FENG Liping, HAN Qi, ZHOU Zhigang, BAI Zengliang. Bad information diffusion modeling and optimal control strategy influenced by social networks [J]. Journal of Computer Applications, 2020, 40(3): 735-739.
[14]	Xiaohuan SHAN, Zhiguo ZHANG, Baoyan SONG, Chenglin REN. Activity recommendation method based on directed label graph and user feedback in event-based social network [J]. Journal of Computer Applications, 2020, 40(2): 448-453.
[15]	Ming DU, Anping YANG, Junfeng ZHOU, Ziyang CHEN, Yun YANG. Optimized algorithm for k-step reachability queries on directed acyclic graphs [J]. Journal of Computer Applications, 2020, 40(2): 426-433.

Influence maximization algorithm based on directed acyclic graph in heterogeneous information networks

异质信息网络中基于有向无环图的影响力最大化算法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 33

Related Articles 15

Recommended Articles

Metrics