融合知识图谱的多层次传承影响力计算与泛化研究

doi:10.11896/jsjkx.210700144

计算机科学 ›› 2022, Vol. 49 ›› Issue (9): 221-227.doi: 10.11896/jsjkx.210700144

融合知识图谱的多层次传承影响力计算与泛化研究

孔世明¹, 冯永², 张嘉云³

1 重庆文理学院人工智能学院重庆 402160
2 重庆大学计算机学院重庆 400044
3 中国检验认证集团重庆有限公司重庆 401120

收稿日期:2021-07-13 修回日期:2021-10-19 出版日期:2022-09-15 发布日期:2022-09-09
通讯作者: 冯永(fengyong@cqu.edu.cn)
作者简介:(20070114@cqwu.edu.cn)
基金资助:
之江实验室开放课题(2021KE0AB01);广西可信软件重点实验室研究课题(kx202006);重庆英才计划创新创业示范团队(CQYC201903167);重庆市技术创新与应用发展专项面上项目(cstc2020jscx-sbqwX0015);重庆市高技术产业重大产业技术研发项目(2018148208)

Multi-level Inheritance Influence Calculation and Generalization Based on Knowledge Graph

KONG Shi-ming¹, FENG Yong², ZHANG Jia-yun³

1 College of Artificial Intelligence,Chongqing University of Arts and Sciences,Chongqing 402160,China
2 College of Computer Science,Chongqing University,Chongqing 400044,China
3 China Certification & Inspection Group Chongqing Co., Ltd.,Chongqing 401120,China

Received:2021-07-13 Revised:2021-10-19 Online:2022-09-15 Published:2022-09-09
About author:KONG Shi-ming,born in 1972,master,lecturer,is a member of China Compu-ter Federation.His main research in-terests include social network analysis,knowledge graph and machine learning.
FENG Yong,born in 1977,Ph.D,professor,Ph.D supervisor, is a member of China Computer Federation.His main research interests include big data ana-lysis and data mining,artificial intelligence and big data processing,deep learning.
Supported by:
Zhejiang Lab(2021KE0AB01),Guangxi Key Laboratory of Trusted Software(kx202006),Chongqing Talent Plan Innovation and Entrepreneurship Demonstration Team(CQYC201903167),Chongqing Technology Innovation and Application Development Special General Project(cstc2020jscx-sbqwX0015) and Major Industrial Technology R & D Projects of Chongqing High Tech Industry(2018148208).

摘要/Abstract

摘要： 影响力计算和分析在社交网络、网页重要度评估等领域有着广泛应用。对于有传承链和时间跨度因素的多层次影响力计算,目前尚缺乏较好且通用的解决办法。同时,传播影响力最大化计算是一个NP难题,近似算法求解准确度不高且计算复杂。针对上述问题,文中提出了融合知识图谱的多层次传承影响力与泛化算法,实现了传承影响力和传承关系的计算。该算法融合了知识图谱中的广度优先搜索层次计算模型,兼顾时间跨度限制计算传承影响力和传承链;为了优化计算效率,进一步使用深度优先搜索和不同层次加不同权重的策略,只计算前n层次的影响力;不仅能很好地计算传承影响力,还可以泛化成各种传播影响力计算模型。在此基础上,文中又提出了通过筛选传播影响力大的节点作为候选节点进行局部最优搜索的传播影响力最大化近似算法,该算法在运行速度和最大传播节点数上都取得了良好的效果。最后,通过多种仿真实验验证了所提方法的有效性。

关键词: 传承影响力计算, 传承链计算, 知识图谱, 传播影响力最大化

Abstract: Influence calculation and analysis are widely used in social networks,web page importance evaluation and other fields.There is still a lack of effective and universal solution for the multi-level influence calculation with inheritance chain and time span factors.At the same time,the calculation of maximizing the propagation influence is an NP hard problem,whose approximate algorithm has low accuracy and complicated computation.In order to solve the above problems,this paper proposes a multi-level inheritance influence and generalization algorithm based on knowledge graph to realize the calculation of inheritance influence and inheritance relationship.The algorithm uses the breadth first search hierarchy computing model of knowledge graph,and takes into account the time span constraints to calculate the inheritance influence and inheritance chain.In order to optimize the computational efficiency,the strategy of depth first search and different levels with different weights is further used to only calculate the influence of the top n levels.The above method can not only calculate the inheritance influence and inheritance chain well,but also can be generalized into various communication influence calculation models.On this basis,this paper proposes a local optimal search similarity algorithm to maximize the propagation influence by selecting the nodes with large propagation influence as spare nodes.It achieves competitive results in running speed and the maximum number of propagation nodes.Finally,the effectiveness of the proposed method is verified by a variety of simulation experiments.

Key words: Calculation of inheritance influence, Inheritance chain calculation, Knowledge graph, Maximization of propagationinfluence

中图分类号:

TP391

孔世明, 冯永, 张嘉云. 融合知识图谱的多层次传承影响力计算与泛化研究[J]. 计算机科学, 2022, 49(9): 221-227. https://doi.org/10.11896/jsjkx.210700144

KONG Shi-ming, FENG Yong, ZHANG Jia-yun. Multi-level Inheritance Influence Calculation and Generalization Based on Knowledge Graph[J]. Computer Science, 2022, 49(9): 221-227. https://doi.org/10.11896/jsjkx.210700144

参考文献

[1]BIAN R,KOH Y,DOBBIE G,et al.Identifying top-k nodes in social networks:a survey[J/OL].ACM Computing Surveys,2019,52(1).https://dl.acm.org/doi/epdf/10.1145/3301286.
[2]HUANG C,JIANG W,WU J,et al.Personalized review recommendation based on users' aspect sentiment[J].ACM Transactions on Internet Technology,2020,20(4):1-20.
[3]LIU Q,XIANG B,YUAN N J,et al.An Influence Propagation View of PageRank[J].ACM Transactions on Knowledge Discovery from Data,2017,11(3):1-30.
[4]CENTOLA D.The spread of behavior in an online social network experiment[J].Science,2010,329(5996):1194-1197.
[5]NEKOVEE M,MORENO Y,BIANCONI G,et al.Theory of rumour spreading in complex social networks[J].Phys. A,2007,374(1):457-470.
[6]KEMPE D,KLEINBERGJ M,TARDOS É.Maximizing thespread of influence through a social network[C]//Proceedings of the Ninth ACM SIGKDD International Conference on Know-ledge Discovery and Data Mining.Washington.DC,USA,2003:137-146.
[7]TANG Y,XIAO X,SHI Y.Inflfluence maximization:near-optimal time complexity meets practical efficiency[C]//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data.ACM,2014:75-86.
[8]WANG Z X,SUN C C,XI J K,et al.Influence maximization in social graphs based on community structure and node coverage gain[J].Future Generation Computer Systems,2021,118:327-338.
[9]NGUYEN H T,THAI M T,DINH T N.Stop-and-stare:opti-mal sampling algorithms for viral marketing in billion-scale networks[C]//Proceedings of the 2016 International Conference on Management of Data.ACM,2016:695-710.
[10]QU Q,LIU S,ZHU F,et al.Efficient Online Summarization of Large-Scale Dynamic Networks[J/OL].IEEE Transactions on Knowledge & Data Engineering,2016.https://ieeexplore.ieee.org/document/7549016.
[11]PEDRO D,MATT R.Mining the network value of customers[C]//Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2001:57-66.
[12]QIU L Q,TIAN X B,SAI S Q,et al.LGIM:A Global Selection Algorithm Based on Local Influence for Influence Maximization in Social Networks[J].IEEE Access,2020,8:4318-4328.
[13]CHEN W.Overview and classification of network propagationmodels[M]//Network Diffusion Models and Algorithms for Big Data.People's Posts and Telecommunications Press,2020.
[14]DING Z Y,JIA Y,ZHOU B,et al.Survey of Influellce Analysis for Social Networks [J].Computer Science,2014,41(1):48-53.
[15]KIANIAN S,ROSTAMNIA M.An efficient path-based ap-proach for influence maximization in social networks[J/OL].Expert Systems with Applications,2020,167(6).https://www.sciencedirect.com/science/article/abs/pii/S0957417420309064.
[16]LI W,ZHONG K,WANG J,et al.A Dynamic Algorithm based on Cohesive Entropy for Influence Maximization in Social Networks[J/OL].Expert Systems with Applications,2020,169(2).https://www.sciencedirect.com/science/article/abs/pii/S0957417420309350.
[17]Social network influence maximization algorithm(linear thres-hold algorithm and improved algorithm)[EB/OL].[2018-05-26].https://github.com/Asia-Lee/Linear_Threshold.
[18]Influence-maximization(LT and IC)[EB/OL].[2015-05-19].https://github.com/nd7141/influence-maximization.
[19]Influence-maximization(CELF)[EB/OL].[2018-09-07].https://hautahi.com/im_greedycelf.
[20]QIU L,TIAN X,ZHANG J,et al.LIDDE:A differential evolution algorithm based on local-influence-descending search strategy for influence maximization in social networks[J/OL].Journal of Network and Computer Applications,2021.http://www.sciencedirect.com/science/article/pii/S1084804520304240.

相关文章 15

[1]	饶志双, 贾真, 张凡, 李天瑞. 基于Key-Value关联记忆网络的知识图谱问答方法 Key-Value Relational Memory Networks for Question Answering over Knowledge Graph 计算机科学, 2022, 49(9): 202-207. https://doi.org/10.11896/jsjkx.220300277
[2]	吴子仪, 李邵梅, 姜梦函, 张建朋. 基于自注意力模型的本体对齐方法 Ontology Alignment Method Based on Self-attention 计算机科学, 2022, 49(9): 215-220. https://doi.org/10.11896/jsjkx.210700190
[3]	徐涌鑫, 赵俊峰, 王亚沙, 谢冰, 杨恺. 时序知识图谱表示学习 Temporal Knowledge Graph Representation Learning 计算机科学, 2022, 49(9): 162-171. https://doi.org/10.11896/jsjkx.220500204
[4]	秦琪琦, 张月琴, 王润泽, 张泽华. 基于知识图谱的层次粒化推荐方法 Hierarchical Granulation Recommendation Method Based on Knowledge Graph 计算机科学, 2022, 49(8): 64-69. https://doi.org/10.11896/jsjkx.210600111
[5]	王杰, 李晓楠, 李冠宇. 基于自适应注意力机制的知识图谱补全算法 Adaptive Attention-based Knowledge Graph Completion 计算机科学, 2022, 49(7): 204-211. https://doi.org/10.11896/jsjkx.210400129
[6]	马瑞新, 李泽阳, 陈志奎, 赵亮. 知识图谱推理研究综述 Review of Reasoning on Knowledge Graph 计算机科学, 2022, 49(6A): 74-85. https://doi.org/10.11896/jsjkx.210100122
[7]	邓凯, 杨频, 李益洲, 杨星, 曾凡瑞, 张振毓. 一种可快速迁移的领域知识图谱构建方法 Fast and Transmissible Domain Knowledge Graph Construction Method 计算机科学, 2022, 49(6A): 100-108. https://doi.org/10.11896/jsjkx.210900018
[8]	杜晓明, 袁清波, 杨帆, 姚奕, 蒋祥. 军事指控保障领域命名实体识别语料库的构建 Construction of Named Entity Recognition Corpus in Field of Military Command and Control Support 计算机科学, 2022, 49(6A): 133-139. https://doi.org/10.11896/jsjkx.210400132
[9]	熊中敏, 舒贵文, 郭怀宇. 融合用户偏好的图神经网络推荐模型 Graph Neural Network Recommendation Model Integrating User Preferences 计算机科学, 2022, 49(6): 165-171. https://doi.org/10.11896/jsjkx.210400276
[10]	钟将, 尹红, 张剑. 基于学术知识图谱的辅助创新技术研究 Academic Knowledge Graph-based Research for Auxiliary Innovation Technology 计算机科学, 2022, 49(5): 194-199. https://doi.org/10.11896/jsjkx.210400195
[11]	朱敏, 梁朝晖, 姚林, 王翔坤, 曹梦琦. 学术引用信息可视化方法综述 Survey of Visualization Methods on Academic Citation Information 计算机科学, 2022, 49(4): 88-99. https://doi.org/10.11896/jsjkx.210300219
[12]	梁静茹, 鄂海红, 宋美娜. 基于属性图模型的领域知识图谱构建方法 Method of Domain Knowledge Graph Construction Based on Property Graph Model 计算机科学, 2022, 49(2): 174-181. https://doi.org/10.11896/jsjkx.210500076
[13]	黄梅根, 刘川, 杜欢, 刘佳乐. 基于知识图谱的认知诊断模型及其在教辅中的应用研究 Research on Cognitive Diagnosis Model Based on Knowledge Graph and Its Application in Teaching Assistant 计算机科学, 2021, 48(6A): 644-648. https://doi.org/10.11896/jsjkx.200700163
[14]	徐进. 面向工业装配的知识图谱构建与应用研究 Construction and Application of Knowledge Graph for Industrial Assembly 计算机科学, 2021, 48(6A): 285-288. https://doi.org/10.11896/jsjkx.200600116
[15]	李嘉明, 赵阔, 屈挺, 刘晓翔. 基于知识图谱的区块链物联网领域研究分析 Research and Analysis of Blockchain Internet of Things Based on Knowledge Graph 计算机科学, 2021, 48(6A): 563-567. https://doi.org/10.11896/jsjkx.200600071

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

融合知识图谱的多层次传承影响力计算与泛化研究

Multi-level Inheritance Influence Calculation and Generalization Based on Knowledge Graph

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0