一种改进Shapley值的符号网络聚类研究  

Clustering Research of an Improved Shapley Value in Signed Network

作　　者：陈晓[1,2,3] 郭景峰[2,3] 刘凤春 

机构地区：[1]华北理工大学迁安学院,河北迁安064400 [2]燕山大学信息科学与工程学院,河北秦皇岛066004 [3]河北省虚拟技术与系统集成重点实验室,河北秦皇岛066004

出　　处：《小型微型计算机系统》2016年第11期2448-2453,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61472340)资助;河北省自然科学基金项目(F2016209344)资助

摘　　要：符号网络中宏观网络结构(拓扑结构属性和符号属性)和微观博弈对联盟(社区)的形成具有相互影响,是符号网络博弈模型的新特征.基于以上思想,提出一种新的符号网络层次聚类算法HCSVSN(Hierarchical Clustering Based on the Shapley Value in Signed Netw ork).首先,基于结点的符号属性和结点度,提出改进Shapely值的计算方法,可以避免忽略外部环境(网络结构)对Shapley值的影响,并可以降低Shapley值计算的复杂性;其次,基于网络密度对联盟形成的影响,提出联盟收益均值的计算方法,并给出符号网络联盟博弈模型;然后,基于联盟平均收益最大化实现符号网络的社区发现;最后,通过实验验证算法的准确性和有效性.In Signed network,macro network structure （ topological attributes and signed attributes） and micro game have mutual influence on the formation of the coalition （ community）, which is a new feature of signed network game model. Based on the observation, to mining communities in signed network, a new hierarchical clustering algorithm HCSVSN （Hierarchical Clustering Based on the Shapley Value in Signed Network） is proposed. Firstly, according to the signed attributes and degree of the node, the calculation meth- od of Shapely value is improved to avoid ignoring the effect of external environment on the Shapley value and reduce the complexity of calculation of Shapley value. Secondly, considering the influence of network density on the formation of the coalition, we find the calculation method of average income of coalition and create coalition game model of signed network. Thirdly, depends on average payoff maximization Of coalition to achieve community discover of signed network. Finally ,check the correctness and effectiveness of the algorithm through experiments.

关 键 词：符号网络 联盟博弈 SHAPLEY值 层次聚类 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]