一种基于合作博弈的社区检测算法

A Community Detection Algorithm Based on Cooperative Game

摘要: 随着互联网技术的迅速发展，虚拟大规模社会网络普遍存在。社区结构是社会网络的重要特征，挖掘大规模社会网络中的社区结构能帮助人们了解网络中的内部结构和关系，从而更好的应用这些网络。因此，社区检测具有重要的现实意义。本文基于合作博弈检测社区的模型及高效计算Shapley值(SH值)的迭代公式，提出了一种以个体理性为核心的合作博弈社区检测算法(CDCG算法)。CDCG算法包括初检测和社区调整两个步骤，初检测中每个节点在不断变化的策略环境下依据自身获得最大SH值作出决策，经过多轮决策后，网络中所有节点的SH值达到平衡状态，初检测结束；社区调整是利用社区内部连接紧密、社区之间连接相对稀疏的特征对初检测产生的不合理、无意义的小簇进行调整，使得检测得出的簇具有明显的社区特征。为了提高算法时间效率，本文提出了无贡献节点剪枝策略和已归属节点剪枝策略。最后通过大量实验验证了CDCG算法能够自动确定最终社区划分个数且具有较好的社区检测效果及时间效率。

Abstract: With the rapid development of Internet technology, the virtual large-scale social networks are wide- spread. Community structure is an important characteristic of social network, mining the communi-ty structure in large-scale social networks can help us to understand the internal structure and relationships of the network, so as to better apply these networks. Therefore, community detection has important practical significance. A kind of individual rationality as the core of cooperative game community detection algorithm was proposed in this paper, which based on cooperative game com- munity detection model and efficient iterative formula for computing the Shapley value (SH). CDCG algorithm includes initial detection and community adjustment. In the initial detection of changing the strategy environment, every node based on its own maximum SH value to make a decision, after several rounds of decisions, when all of the nodes’ SH value become balance in the network, then the initial detection ended. The characteristics of the internal tight connection of community and rela-tively sparse in communities, by which can detect the unreasonable and meaningless small clusters in step of community adjusting, then the detected cluster has obvious community features. In order to improve efficiency of the algorithm, no contribution nodes pruning and ownership nodes pruning strategies were proposed. Finally, extensive experiments show that CDCG algorithm can automati-cally determine the final number of divided communities, which is effective and efficiency.