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
Qingqing WU1, Lihua ZHOU1(), Xuanyi CUN1, Guowang DU1, Yiting JIANG2
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.Supported by:
吴晴晴1, 周丽华1(), 寸轩懿1, 杜国王1, 姜懿庭2
通讯作者:
周丽华
作者简介:
吴晴晴(1995—),女,安徽亳州人,硕士研究生,主要研究方向:数据挖掘、异质信息网络、信息扩散基金资助:
CLC Number:
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.
Add to citation manager EndNote|Ris|BibTeX
URL: https://www.joca.cn/EN/10.11772/j.issn.1001-9081.2021020369
数据集 | 节点类型 | 节点数量 | 边类型 | 边数量 |
---|---|---|---|---|
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 |
Tab.1 Dataset detailed information
数据集 | 节点类型 | 节点数量 | 边类型 | 边数量 |
---|---|---|---|---|
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 | ||||
---|---|---|---|---|---|---|
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 |
Tab.2 Running time comparison of different algorithms on three datasets
数据集 | 种子节点数K | 运行耗时/s | ||||
---|---|---|---|---|---|---|
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 | 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 |
[1] | Xinrui LIN, Xiaofei WANG, Yan ZHU. Academic anomaly citation group detection based on local extended community detection [J]. Journal of Computer Applications, 2024, 44(6): 1855-1861. |
[2] | Xiting LYU, Jinghua ZHAO, Haiying RONG, Jiale ZHAO. Information diffusion prediction model based on Transformer and relational graph convolutional network [J]. Journal of Computer Applications, 2024, 44(6): 1760-1766. |
[3] | Tao SUN, Zhangtian DUAN, Haonan ZHU, Peihao GUO, Heli SUN. Social event recommendation method based on unexpectedness metric [J]. Journal of Computer Applications, 2024, 44(3): 760-766. |
[4] | Rui GAO, Xuebin CHEN, Zucuan ZHANG. Dynamic social network privacy publishing method for partial graph updating [J]. Journal of Computer Applications, 2024, 44(12): 3831-3838. |
[5] | Shiliang LIU, Yi WANG, Yinglong MA. Non-overlapping community detection with imbalanced community sizes [J]. Journal of Computer Applications, 2024, 44(11): 3396-3402. |
[6] | Nengqiang XIANG, Xiaofei ZHU, Zhaoze GAO. Information diffusion prediction model of prototype-aware dual-channel graph convolutional neural network [J]. Journal of Computer Applications, 2024, 44(10): 3260-3266. |
[7] | Li LI, Chunyan YANG, Jiangwen ZHU, Ronglei HU. User plagiarism identification scheme in social network under blockchain [J]. Journal of Computer Applications, 2024, 44(1): 242-251. |
[8] | Shijie PENG, Hongmei CHEN, Lizhen WANG, Qing XIAO. Hybrid point-of-interest recommendation model based on geographic preference ranking [J]. Journal of Computer Applications, 2023, 43(8): 2448-2455. |
[9] | Nannan SUN, Chunhui PIAO, Xinna MA. Group buying recommendation method based on social relationship and time-series information [J]. Journal of Computer Applications, 2023, 43(6): 1719-1729. |
[10] | Fuqin DENG, Huanzhao HUANG, Chaoen TAN, Lanhui FU, Jianmin ZHANG, Tinlun LAM. Multi-robot task allocation algorithm combining genetic algorithm and rolling scheduling [J]. Journal of Computer Applications, 2023, 43(12): 3833-3839. |
[11] | Qian LIU, Yangming ZHANG, Dingsheng WAN. Parallel computing algorithm of grid-based distributed Xin’anjiang hydrological model [J]. Journal of Computer Applications, 2023, 43(11): 3327-3333. |
[12] | Yu YANG, Weiwei DUAN. Spectral clustering based dynamic community discovery algorithm in social network [J]. Journal of Computer Applications, 2023, 43(10): 3129-3135. |
[13] | JIANG Songyan, LIAO Xiaojuan, CHEN Guangzhu. Optimal task scheduling method based on satisfiability modulo theory for multiple processors with communication delay [J]. Journal of Computer Applications, 2023, 43(1): 185-191. |
[14] | Xu WANG, Yumin SHEN, Xiaoyun XIONG, Peng LI, Jinlong WANG. Data management method for building internet of things based on Hashgraph [J]. Journal of Computer Applications, 2022, 42(8): 2471-2480. |
[15] | Shuxin YANG, Jingfeng XU. Positive influence maximization based on reverse influence sampling [J]. Journal of Computer Applications, 2022, 42(8): 2609-2616. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||