基于节点效益纳什均衡的网络社区发现算法  

Social network community discovery algorithm based on node benefit Nash equilibrium

作　　者：范晖[1] 夏清国[2] 乌伟[1] 

机构地区：[1]西京学院电子信息工程系,陕西西安710123 [2]西北工业大学计算机学院,陕西西安710072

出　　处：《计算机工程与设计》2016年第10期2775-2779,2809,共6页Computer Engineering and Design

基　　金：国家自然科学基金项目(51405382)

摘　　要：为解决当前社区发现算法中模块度和社区划分精确度偏低、不能动态利用历史记录信息的不足,提出基于代理节点效益最大化筛选机制的高效动态社交网络社区发现算法。将节点博弈机制引入到动态网络社区划分中,利用代理节点效用函数与开销削减函数,定期从一组预定义的行为集合中选择最大化利益策略,当节点博弈状态达到纳什均衡时,可获取网络社区结构的时间快照,利用上一次得到的时间快照信息继续博弈,发现新的社区结构,获得社区结构的动态信息。理论分析和仿真结果表明,与当前社区发现算法相比,该算法在社区划分模块度和划分社区精确度上具备更好的划分效果。To solve the low modularity,low community division accuracy and inefficient use of the history snapshots dynamically in the traditional community detection algorithms,a dynamic community discovery algorithm for social network based on game theory（EDCD-PNBMG）was presented.By introducing reasonable utility function,a set of predefined behaviors collection was chosen from its utility function to maximize its benefits.A snapshot of community structure appeared when the game entered the Nash equilibrium.The nodes involved in the network as well as the agents made full use of history snapshots information to discover the structure of the community,and then the dynamic information of community was got.Results of theoretical analysis and simulation show that the EDCD-PNBMG outperforms the other existing algorithm in terms of the community detection modularity and fine-grained,and it improves the effectiveness of community division.

关 键 词：社区发现 社交网络 模块度 博弈机制 效用函数 纳什均衡 利益策略 

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