从消息传播概率到概率亲密度矩阵的社区挖掘算法

Community Mining Algorithm of Information Propagation Probability to Probability Matrix of Affinity

随着现代网络的结构越来越复杂,规模越来越大,基于局部最优的社区挖掘算法受到了越来越多的关注.这些算法的计算速度快,但是结果精度较低.针对上述问题,对已有的CONCLUDE算法进行改进,利用消息传播概率代替结构相似性来构造亲密度矩阵,表示网络中的全局信息,计算过程的时间复杂度由O(珔d(v)2V)降低到O(珔d(v)V).与其它算法(LM,CONCLUDE)进行比较和分析,该算法具有较高的计算效率和精度.实验结果表明,该算法不仅提高了LFR基准网络上的NM I值,而且对真实网络上的模块度也有一定的提升.

There is growing concern about Community Mining Algorithms based on local optimum as the structure of modern network becomes more and more complex and the scale of it becomes larger and larger. These algorithms have quick calculating speed but a lower accuracy result. In response to these issues,this article proposes a probability matrix of affinity which use Information Propaga- tion to instead of Struc^ral Similarity to represent the global information in the network. This method improves the CONCLUDE algo- rithm and at the same time reduces the computational complexity of time from O（d（v） 2 ｜V｜） to O（ d（v）｜ V｜ ）. When compared with other algorithms on several networks,it shows that this algorithm not only improves the NMI on LFR networks but also the modularity on real networks. The result proves our algorithms has higher computational efficiency and precision.