Abstract: The Finding and Extracting Community (FEC) algorithm has some disadvantages as the algorithm stability is not enough, and the quality of extracting community needs to be improved. To solve these problems, some improvements were made from the following aspects: Add the function of selecting target vertex before random walk; cancel the parameter of random walk steps of the original algorithm by using a method of detecting steps automatically; supplement the quality evaluation of the link between the communities on the base of the original community extraction; achieve the controllability of particle size of community by introducing the threshold parameter. The results show that the improved algorithm has some improvements at the aspects of stability, anti-jam performance and clustering analysis.

Key words: signed network, clustering algorithm, network community, random walk, heuristic strategy

摘要： 针对FEC算法存在的稳定性不够、网络簇抽取质量亟待提高等问题,从以下几个方面对原算法进行了改进:在随机游走前添加了选择目标顶点功能;采用自动步数探测法取消了原算法的随机游走步数参数;在原有的簇抽取评价条件的基础上补充了簇间连接权重评价;通过引入阈值参数实现了簇抽取粒度的可控性。测试结果表明,改进后的算法在稳定性、抗干扰性和聚类分析质量等方面比原算法都有所提高。

关键词: 符号网络, 聚类算法, 网络簇, 随机游走, 启发式策略