基于节点多关系的社团挖掘算法及其应用  

Community mining algorithm based on multi-relationship of nodes and its application

作　　者：周琳 肖玉芝[1,2,3] 刘鹏[1,2,3] 秦有鹏 ZHOU Lin;XIAO Yuzhi;LIU Peng;QIN Youpeng(Computer College,Qinghai Normal University,Xining Qinghai 810016,China;Tibetan Information Processing and Machine Translation Key Laboratory of Qinghai Province(Qinghai Normal University),Xining Qinghai 810008,China;Key Laboratory of Tibetan Information Processing,Ministry of Education(Qinghai Normal University),Xining Qinghai 810008,China)

机构地区：[1]青海师范大学计算机学院,西宁810016 [2]青海省藏文信息处理与机器翻译重点实验室(青海师范大学),西宁810008 [3]藏文信息处理教育部重点实验室(青海师范大学),西宁810008

出　　处：《计算机应用》2023年第5期1489-1496,共8页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61763041);青海省重点研发计划项目(2020⁃GX⁃112)。

摘　　要：为度量多关系节点相似性、挖掘具有多关系节点的社团结构,提出基于节点多关系的社团挖掘算法LSL-GN。首先基于节点相似性和节点可达性刻画具有多关系的节点相似性度量指标LHN-ISL;然后利用该指标重构目标网络的低密度模型,并结合GN(Girvan-Newman)算法完成社团划分。将LSL-GN算法与多个经典社团挖掘算法在模块度(Q)、标准化互信息(NMI)和调整兰德指数(ARI)上进行对比,结果显示LSL-GN算法在3个指标上均优于经典算法,说明它的社团划分质量相对较好。将LSL-GN应用于“用户-应用”的移动漫游网络模型中,划分出了以携程旅行、高德地图、滴滴出行等为基础应用的社团结构,而这些社团划分结果可为设计个性化套餐业务提供策略参考信息。In order to measure the similarity of multi-relational nodes and mine the community structure with multirelational nodes,a community mining algorithm based on multi-relationship of nodes,called LSL-GN,was proposed.Firstly,based on node similarity and node reachability,LHN-ISL,a similarity measurement index for multi-relational nodes,was described to reconstruct the low-density model of the target network,and the community division was completed by combining with GN(Girvan-Newman)algorithm.The LSL-GN algorithm was compared with several classical community mining algorithms on Modularity(Q value),Normalized Mutual Information(NMI)and Adjusted Rand Index(ARI).The results show that LSL-GN algorithm achieves the best results in terms of three indexes,indicating that the community division quality of LSL-GN is better.The“User-Application”mobile roaming network model was divided by LSL-GN algorithm into community structures based on basic applications such as Ctrip,Amap and Didi Travel.These results of community division can provide strategic reference information for designing personalized package services.

关 键 词：社团挖掘 社团划分 社团检测 复杂网络 移动漫游网络 节点相似性 节点可达性 

分 类 号：TP311.3[自动化与计算机技术—计算机软件与理论]