面向双层网络的EWCC社区发现算法  

EWCC Community Discovery Algorithm for Two-Layer Network

作　　者：唐春阳 肖玉芝[1,2,3,4] 赵海兴 冶忠林[1,2,3,4] 张娜 TANG Chun-yang;XIAO Yu-zhi;ZHAO Hai-xing;YE Zhong-lin;ZHANG Na(College of Computer,Qinghai Normal University,Xining 810016,China;The Provincial and Ministerial Joint Construction of the State Key Laboratory of Tibetan Intelligent Information Processing and Application,Xining 810008,China;Key Laboratory of Tibetan Information Processing,Ministry of Education,Xining 810008,China;China Tibetan Information Processing and Machine Translation Key Laboratory of Qinghai Province,Xining 810008,China)

机构地区：[1]青海师范大学计算机学院,西宁810016 [2]省部共建藏语智能信息处理及应用国家重点实验室,西宁810008 [3]藏文信息处理教育部重点实验室,西宁810008 [4]青海省藏文信息处理与机器翻译重点实验室,西宁810008

出　　处：《计算机科学》2022年第4期49-55,共7页Computer Science

基　　金：国家自然科学基金(61763041);青海省科技项目(2020-GX-112);青海师范大学自然科学中青年科研基金(2020QZR007)。

摘　　要：针对关系型网络的社区发现问题,考虑节点间相互作用的强弱程度和信息渗流机理,创新性地提出了一种基于边权重和连通分支(Edge Weight and Connected Component,EWCC)的社区发现算法。为了验证算法的有效性,首先,构建了5种具有相互作用的双层网络模型,通过分析层间节点作用的强弱程度对网络拓扑结构的影响,确定了5种双层网络模型下生成的30个数据集;其次,选用真实数据集分别与GN算法和KL算法在模块度、算法复杂度和社区划分数目评价准则上进行了对比,实验结果表明EWCC算法的准确性较高;然后,结合数值仿真得出,随着层间作用关系减弱,模块度值和社区数目成反比,并且当双层网络层间节点关系较弱时,社区划分效果较好;最后,作为算法的应用,利用实证数据构建了“用户-APP”的双层网络并进行了社区划分。Aiming at the problem of community discovery in relational networks,considering the strength of interaction between nodes and information seepage mechanism,an edge weight and connected component(EWCC)community discovery algorithm based on edge weight and connected branches is innovatively proposed.In order to verify effectiveness of the algorithm,firstly,five kinds of interactive two-layer network models are constructed.By analyzing influence of interaction degree of nodes between layers on the network topology,30 data sets generated under five kinds of two-layer network models are determined.Secondly,the real data set is selected to compare with GN algorithm and KL algorithm in the evaluation criteria of modularity,algorithm complexity and community division number.Experimental results show that EWCC algorithm has high accuracy.Then,the numerical simulation shows that with the weakening of interaction relationship between layers,the module degree is inversely proportional to number of communities,and the community division effect is better when node relationship between layers is weaker.Finally,as an application of the algorithm,the“user-APP”two-layer network is constructed based on empirical data,and the community is divided.

关 键 词：关系型网络 社区发现 双层网络 边权重 连通分支 

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