基于改进PageRank算法和spin-glass模型的多角度识别可控的社区发现算法  

Discovery algorithm of multi-angle identify controllable based on improved PageRank algorithm and spin-glass models

作　　者：石云[1,2,3] 陈钟[2,3] 孙兵[2,3,4] 

机构地区：[1]六盘水师范学院计算机科学与信息技术系,贵州六盘水553004 [2]北京大学信息科学技术学院,北京100871 [3]北京大学网络与软件安全保障教育部重点实验室,北京100871 [4]广东海洋大学信息学院,广东湛江524088

出　　处：《计算机应用研究》2015年第9期2597-2600,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(61170263);广东省高等教育学会实验室管理专业委员会基金资助项目(GDJ2012063)

摘　　要：针对如何有效解决社区发现算法中的社区重叠问题,以及如何改善社区扩张模式,提出了一种基于改进Page Rank算法和spin-glass模型的多角度识别可控的社区发现算法(PRSGMFCA)。首先通过优化的Page Rank算法对每一个节点排序,确定其中的核心节点;再通过基于Potts spin-glass模型的多角度识别模块度优化局部社区的扩张模式,解决传统模块度在分辨率极限方面的束缚和影响;同时在发现过程中,引入改进的贪心迭代算法发现局部社区;最后实现准确地发现重叠结构与节点。经过在计算机模拟网络与真实网络环境下应用比较分析,PRSGMFCA与传统的技术方案相比具有较好的稳定性与正确率,并且其算法复杂度也在可以接受的范围内。In order to effectively solve the problem of communities overlap in community discovery algorithm, and improve the community expansion model, this paper proposed a discovery algorithm of multi-angle identify controllable based on improved PageRank algorithm and spin-glass models. Firstly, it utilized optimized PageRank algorithm to sort each node, determined which of the core node. Secondly, it utilized multi-angle identification module degree based on the Ports spin-glass model to op- timize the expansion model of local community, and solved the shackles and influence of traditional modularity in terms of the resolution limit. Meanwhile in the discovery process, it introduced an improved greedy iterative algorithm to discover local com- munities, and ultimately found the overlapping structure and node exactly. After comparison and analysis the application in computer simulation network and real network environment, it is found that this algorithm has better stability and accuracy com- pared with traditional technology solutions, and the complexity of the algorithm is also within the acceptable range.

关 键 词：社区发现 改进PageRank算法 spin-glass模型 多角度识别可控 贪心迭代算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]