CAJ | 학술논문

传统的GN算法每次迭代删除一条边，时间复杂度高，其变种时间复杂度有所下降，但分割精度也有待于提高；在复杂网络图中，图的连通性是由拉普拉斯矩阵的第二小特征值决定的，通过最小化网络连通性，提出了贪婪谱优化割边模型，该模型在GN算法基础上，一次删除多条边，为避免出现边过度分割，每条边设置了权重；为了进一步降低时间复杂度，选择网络代数连通性下降最快的边进行删除，提出了基于边中心性测度的割边模型，与传统的利用最短距离和随机游走不同，模型采取谱分析方法对每条边定义边中心性测度，速度更快，分割精度能到达要求，适合处理中规模社区结构。
전통적GN산법매차질대산제일조변，시간복잡도고，기변충시간복잡도유소하강，단분할정도야유대우제고；재복잡망락도중，도적련통성시유랍보랍사구진적제이소특정치결정적，통과최소화망락련통성，제출료탐람보우화할변모형，해모형재GN산법기출상，일차산제다조변，위피면출현변과도분할，매조변설치료권중；위료진일보강저시간복잡도，선택망락대수련통성하강최쾌적변진행산제，제출료기우변중심성측도적할변모형，여전통적이용최단거리화수궤유주불동，모형채취보분석방법대매조변정의변중심성측도，속도경쾌，분할정도능도체요구，괄합처리중규모사구결구。
The GN algorithm removes one edge with the highest betweenness at each iteration. It has relatively high time complexity. Although the time complexity of variations on GN is reduced, the calculation accuracy needs to be improved. In complex network graph, the second smallest eigenvalue of Laplacian matrix is the algebraic connectivity. It presents greedy spectral optimal cut model by minimizing the algebraic connectivity of complex network. The model cuts k edges at an iteration based on GN algorithm. To avoid edges overcutting, the weight is set up for each edge. It proposes edge cen-trality cut model in order to reduce the time complexity further, which is different from the shortest distance and random walking methods. The model calculates edge centrality by the spectral analysis and can be used in medium-size networks with higher efficiency and accuracy.